StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>To find paths that start at the center of the square board and finish at the borders, you can use a tweaked DFS (<a href="http://en.wikipedia.org/wiki/Depth-first_search" rel="nofollow">Depth First Search</a>) where you will store already visited tiles so you don't step on them again.</p> <p>There is indeed a lot of symmetry in the board. You can divide the number of searched paths by 4 just by noticing that:</p> <ul> <li>Starting from the center, you can go <strong><code>U</code>p</strong>, <strong><code>D</code>own</strong>, <strong><code>L</code>eft</strong>, <strong><code>R</code>ight</strong></li> <li>All the paths that start going <strong><code>U</code>p</strong> generate all other paths starting <strong><code>D</code>own</strong>, <strong><code>L</code>eft</strong>, <strong><code>R</code>ight</strong> by rotation</li> </ul> <p>Once you do that, you can go further by noticing that:</p> <ul> <li>Once you've gone <strong><code>U</code></strong>, you can go <strong><code>U</code></strong>, <strong><code>L</code></strong> or <strong><code>R</code></strong></li> <li>All paths generated when you go <strong><code>L</code></strong> are the same ones generated when you go <strong><code>R</code></strong> by mirror symmetry.</li> </ul> <p>You can repeat this several times until you reach the border of the square. The full amount of paths starting by going <strong><code>U</code></strong> will be:</p> <ul> <li><strong><code>U-U-U-U</code></strong> (one path)</li> <li>2 times paths starting with <strong><code>U-U-U-L</code></strong></li> <li>2 times paths starting with <strong><code>U-U-L</code></strong></li> <li>2 times paths starting with <strong><code>U-L</code></strong></li> </ul> <p>Once you count those, you have the full amount of paths by multiplying by four.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload