23
$\begingroup$

This is a puzzle that was a fad when I was back in school. (It's not sooo long ago, but way before Smartphones with AngryBirds or DoodleJump came up...). For quite a while, everybody was scribbling this instead of paying attention in class. It is somehow addicting ("This can't be so hard..."), and can be played everywhere and everytime, just using a pen and a piece of squared paper. In the end, when I solved it (with the help of a computer, to be honest), I wrote the solution on a piece of paper, and still carry it around in my wallet (although I don't know why).

The rules are simple: Given a grid of 10x10 squares, your task is to visit every square exactly once. In each step, you may

  • skip 2 squares horizontally or vertically or
  • skip 1 square diagonally

as in this image:

Puzzle01.png

The starting point is arbitrary (and I don't know whether it matters, but at least I can say that it is possible to solve it when starting with the sequence depicted in the image).

There certainly are many solutions, but it's definitely harder than it looks. There is a way to simplify it (maybe an obvious one for an experienced puzzler?), but this will be part of a hint, if it turns out to be necessary. Otherwise, you may have a nice pastime (for when the battery of your Smartphone is empty...)

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Trying to find a name for this puzzle, I came across an app that coined the name "Hopido", as well as this thread with a solution that uses a different approach than the first two answers here. $\endgroup$
    – Miles
    Aug 19, 2015 at 7:03

7 Answers 7

Reset to default
12
$\begingroup$

I must admit that I have heard of this before, and I remember the right way of approaching this puzzle.

My tactic was to make four 5x5 squares, because that will make it much easier. After spending some time with trial & error (with some kind of logic although I didn't bruteforce it), I came up with this solution (Probably not yours, but I think it's valid):

Solution Screenshot

Edit: After reading Anachors answer I realised his "style" was way nicer to read, so I also changed my image.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ That was faster than I expected, congratulations! The tactic that you employed was exactly what would have been the first hint. In fact, I even used this in my solver program, because otherwise, the backtracking was not able to find a solution in reasonable time either. However, maybe others still take the chance to fight boredom with the hard way ;-) $\endgroup$
    – Marco13
    Aug 18, 2015 at 18:03
  • $\begingroup$ @Marco13 I think the only reason why I came up with a solution so fast is because it wasn't long time ago when I stumbled into this puzzle. I even remembered a bit of the right "pattern" for some 5x5 squares. Very nice puzzle! The Knight's tour is also related to this :) $\endgroup$
    – user14478
    Aug 18, 2015 at 18:10
  • $\begingroup$ I copied the idea of using numbered cells from you, I was attempting to write $(0,0) \to (2,2) \to (4,4).......$ $\endgroup$
    – Rohcana
    Aug 18, 2015 at 19:59
8
$\begingroup$

This is similar to the other solution, but uses a slightly different trick. Call a path which traverses all squares a complete path.

Instead of generating four $5 \times 5$ complete path, we generate a single complete "circular" path ie. one that traverses all squares and returns to the starting cell. By doing this we can make complete paths from each starting cell by properly "rotating" the circular path. In fact, we can generate 2 complete paths, one moving forwards, one backwards.

Circular 5x5 path
Note that you just have to jump from 25 to 1 to make a circular path.

Rotating this path properly we have the solution:

10x10

The lower right grid uses the backward path while other three move forwards.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ I like this answer because it generalizes to any grid having width and height divisible by 5. $\endgroup$
    – Carl Löndahl
    Aug 18, 2015 at 19:48
  • 1
    $\begingroup$ That's a neat trick! I wondered whether something like this was possible before, but didn't think about it thoroughly, and would probably not have come to the idea of mirroring and reversing, and even less "shifting" the path. A great idea! $\endgroup$
    – Marco13
    Aug 18, 2015 at 19:49
  • $\begingroup$ Seems like you got lucky that the cycle finishes one move away from the next quadrant. I guess you get to mirror/flip the cycle to achieve this, but if you tried this on say a 25x25 board, would it still work? $\endgroup$
    – Trenin
    Aug 19, 2015 at 15:28
  • $\begingroup$ @Trenin, I have some options, I can reverse the sequence or flip it along diagonal, that gives me four potential paths, I haven't tried it, but at least one of them should work. $\endgroup$
    – Rohcana
    Aug 19, 2015 at 15:53
4
$\begingroup$

I used Rohcana's circular board to build a solution for any (5N)×(5M) board that does not require any rotations or flipping.

It only uses two interesting properties with Rohcana's board with enables one to connect adjacent boards.

  • If two boards are placed next to each other horizontally, it is possible to go between 23 on the left board to 16 on the right board, and between 24 on the left board to 15 on the right board.

  • If two boards are placed next to each other vertically, it is possible to go between 12 on the upper board to 8 on the lower board, and between 13 on the upper board to 7 on the lower board board.

This gives the following solution for creating circuits going through all the cells.

  • Tile the (5N)×(5M) board with 5×5 sub-boards

  • Create an arbitrary path S that connects all the sub-boards (a simple snake-pattern, going right on the first row, left on the second row, right on the third row, etc. will do). The complete circuit will move forwards and backwards along this path.

  • If S connects a board with the board to the right of it, immediately connect 23 and 24 on the left board with 16 and 15 on the right board.

  • If S connects a board with the board below it, immediately connect 12 and 13 on the top board with 8 and 7 on the lower board. The picture below shows how the board will look like at this step, the gray line indicating S and the green lines being the connections between the sub-boards.

  • Start at 1 on the board that is on the beginning of the path S and keep counting upwards, connecting each cell to the next one.

  • If you reach a cell that is already connected to a cell on a neighbouring board, jump to that connected cell and keep counting upwards.

  • If you reach 25 connect it to the 1 on the same board you are at.

Eventually you will get back to 1 on your starting board, and will have created a circuit that connects all the cells on all the boards.

Essential bits of the solution for a 10×10 board

The complete circuit here will be

TopLeft(1...23) -> TopRight(16...25,1...12) -> BottomRight(8...15) -> BottomLeft(24,25,1...23) -> BottomRight(16...25,1...7) -> TopRight(13...15)-> TopLeft(24,25,1)

Improve this answer
$\endgroup$
1
  • $\begingroup$ Good to see that this puzzle is still active after 3 years, and that there are still interesting generalizations - great work! $\endgroup$
    – Marco13
    Oct 3, 2018 at 16:09
4
$\begingroup$

Just to show that solutions exist that don't split the square up in 5x5 chunks:

$$\begin{array}{|r|c|} \hline 30 &12 &57 &31 &13 &10 &55 &45 &9 &54 \\ \hline 69 &25 &28 &70 &67 &27 &88 &42 &100 &87 \\ \hline 58 &32 &65 &11 &56 &44 &14 &53 &90 &46 \\ \hline 29 &71 &68 &26 &85 &41 &99 &86 &8 &98 \\ \hline 64 &24 &19 &33 &66 &16 &89 &43 &15 &52 \\ \hline 59 &38 &84 &74 &39 &1 &77 &40 &91 &47 \\ \hline 18 &72 &61 &17 &5 &34 &80 &49 &7 &97 \\ \hline 63 &23 &20 &2 &78 &75 &92 &95 &76 &51 \\ \hline 60 &37 &83 &73 &36 &82 &6 &35 &81 &48 \\ \hline 21 &3 &62 &22 &4 &94 &79 &50 &93 &96 \\ \hline \end{array}$$

Found with the following program I wrote:

import z3

N = 10
grid = [[z3.Int("{},{}".format(i, j)) for j in range(N)] for i in range(N)]

diag = [(-2, -2), (-2, 2), (2, -2), (2, 2)]
ortho = [(-3, 0), (3, 0), (0, -3), (0, 3)]

solver = z3.Solver()

for i in range(N):
    for j in range(N):
        solver.add(grid[i][j] >= 1)
        solver.add(grid[i][j] <= N*N)
        neighbours = []
        for di, dj in diag + ortho:
            ni = i + di
            nj = j + dj
            if not (0 <= ni < N): continue
            if not (0 <= nj < N): continue
            neighbours.append(grid[ni][nj])

        is_next = z3.Or([grid[i][j] == ne + 1 for ne in neighbours])
        is_prev = z3.Or([grid[i][j] == ne - 1 for ne in neighbours])
        solver.add(z3.Or(grid[i][j] == 1, is_next))
        solver.add(z3.Or(grid[i][j] == N*N, is_prev))

solver.add(z3.Distinct([grid[i][j] for i in range(N) for j in range(N)]))

solver.check()
model = solver.model()

for i in range(N):
    for j in range(N):
        grid[i][j] = model[grid[i][j]].as_long()

for row in grid:
    print(" ".join("{:{}}".format(n, len(str(N*N))) for n in row))

And with a small modification it can also find tours:

$$\begin{array}{|r|c|} \hline 43 &21 &24 &42 &20 &25 &30 &19 &89 &29 \\ \hline 9 &93 &45 &34 &92 &46 &33 &27 &47 &81 \\ \hline 23 &41 &11 &22 &40 &12 &90 &39 &31 &18 \\ \hline 44 &35 &8 &94 &51 &26 &6 &80 &88 &28 \\ \hline 10 &56 &53 &73 &91 &38 &32 &13 &48 &82 \\ \hline 63 &95 &76 &36 &7 &79 &50 &84 &3 &17 \\ \hline 54 &72 &98 &55 &52 &86 &5 &68 &87 &14 \\ \hline 75 &57 &62 &74 &58 &37 &2 &16 &49 &83 \\ \hline 64 &96 &77 &65 &97 &78 &66 &85 &4 &67 \\ \hline 61 &71 &99 &60 &70 &100 &59 &69 &1 &15 \\ \hline \end{array}$$

Improve this answer
$\endgroup$
3
  • $\begingroup$ Nice, I think that this is the first one that does not use the 5x5 tiling approach. How long does the solver take for this? (Just a ballpark: Seconds, minutes or hours?). I remember having tried it with a very simple brute force backtracking and it didn't seem to be so promising... $\endgroup$
    – Marco13
    Oct 3, 2018 at 20:57
  • 1
    $\begingroup$ @Marco13 Roughly 30 seconds. $\endgroup$
    – orlp
    Oct 4, 2018 at 2:08
  • $\begingroup$ That's very resonable. I guess that something like the en.wikipedia.org/wiki/Knight%27s_tour#Warnsdorf's_rule could also work here pretty well to speed up the backtracking, but have not investigated this further (yet - this puzzle seemed to gain some attention recently, and maybe I'll try it out when I have some spare time...) $\endgroup$
    – Marco13
    Oct 4, 2018 at 11:36
3
$\begingroup$

This problem is related to the Knight's Tour. Both essentially construct a valid directed graph, with the only difference being which connections are considered valid. There's a pretty good heuristic for constructing knight's tours called Warnsdorf's rule, so I was curious to see whether it applied to this problem as well, so I implemented it in Python.

Using the simplest tie-breaking rule (random choice) solves the problem in negligible time (0.04 s on my laptop):

enter image description here

Warnsdorf can generate solutions on boards of up to about 100 x 100 in size with reasonable probability. Here's a solution on a board of 30 x 30:

enter image description here

This seems in line with the results in a paper on the Knight's Tour by Squirrel & Cull, which is cited in the section on Warnsdorf's rule on the above Wikipedia page. The paper also details a more successful tie-breaking rule, but I haven't gotten around to implementing that one yet. It might not even work for this particular game.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Awesome! I considered giving the Warnsdorf rule a try for that one, as mentioned in this comment, but didn't yet find the time. Did you try whether it can find solutions for boards that have a size that is not a multiple of 5? The other approaches basically all divided the board into pieces of size 5x5, and I wonder whether, for example, boards with "odd" sizes like 9 or 13 can be solved at all...? $\endgroup$
    – Marco13
    Nov 20, 2018 at 17:02
  • $\begingroup$ Since it doesn't rely on any divide-and-conquer algorithm, there are essentially no restrictions on board size besides your own patience. Here's a solution on a 13x13 board. I was honestly really surprised it works as well as it does! $\endgroup$
    – Jesse van Rhijn
    Nov 20, 2018 at 17:15
2
$\begingroup$

Here is a slightly different solution. It doesn't necessarily scale well, but it does form a complete cycle of the board.

Solution

First, we create a 5x5 board like this:

+--+--+--+--+--+
| 1|17|24| 2|18|
+--+--+--+--+--+
|22|14| 5|21|13|
+--+--+--+--+--+
|25| 8|11|16| 7|
+--+--+--+--+--+
| 4|20|23| 3|19|
+--+--+--+--+--+ 
|10|15| 6| 9|12|
+--+--+--+--+--+

Notice that if you move up 3 from the 25th spot, it takes you out of the current 5x5 square. Thus, we can position 4 of these squares to make a 10x10 square, each starting their cycle in the square next to the shared vertex.

Lets call the square above $A$.

Now, define the function $R(S)$ to be the 90 degree counter-clockwise rotation of $S$. Then, we can create a 10x10 square with the following:

  R(R(A))   R(A)
R(R(R(A)))   A

We'd end up with the following in the middle 6x6 square:

        +---+
        | 75|
        +---+    ...
   ...  |   |
        +---+---+---+---+
        | 51| 26|   | 50|
+---+---+---+---+---+---+
|100|   | 76| 1 |
+---+---+---+---+
            |   |  ...
     ...    +---+
            | 25|
            +---+

By doing this, we've created a 10x10 board with a complete cycle.

More General Solution

Consider the following 5x5 squares.

+--+--+--+--+--+
| 1|24| 8| 2|23|
+--+--+--+--+--+ 
|19|16| 5|20|17| 
+--+--+--+--+--+  
| 7|10|13|25| 9|  
+--+--+--+--+--+  
| 4|21|18| 3|22| 
+--+--+--+--+--+  
|12|15| 6|11|14|  
+--+--+--+--+--+

Notice that moving diagonally up and to the right from the 25th spot will take you to the upper left position of the next 5x5 square, and moving diagonally down and to the right will take you to the bottom left position of the next square. Thus, when entering this square from the top left position, you can enter the square to the right in the bottom left or top left position.

For example (S is the starting point in the first square, E is the ending point, and p is the possible starting point in the next square):

+-----+-
|S    |p
|     | 
|   E | ...
|     | 
|     |p
+-----+-

A diagonal flip of this square will let you enter the square below in either the top left or top right position when starting in the top left corner.

+-----+
|S    |
|     | 
|     |
|  E  | 
|     |
+-----+
|p   p|
  ...

Now consider this second square:

+--+--+--+--+--+
| 1|17| 7| 2|14|
+--+--+--+--+--+
| 9|22|25|10|21|
+--+--+--+--+--+
| 6| 3|13|18| 4|
+--+--+--+--+--+
|24|16| 8|23|15|
+--+--+--+--+--+
|12|19| 5|11|20|
+--+--+--+--+--+

Similar to the first, you can enter the square above in either bottom corner. A diagonal flip means you can enter the square to the left in either right corner.

Throught the use of these two squares and their diagonal flip, you are able to enter the corner of any adjacent square when starting in the upper left corner.

Through rotations, this also means you can also start in any corner!

To tile any rectangle which sides are multiples of 5, simply divide it up into 5x5 squares and then trace a path through these squares. A spiral will work, or back and forth through each row will also work. Use the appropriate square above to enter/exit the right corner and it is possible to tile any rectangle whose sides are multiples of 5.

Example

Here is a 30x20 rectangle. This is made up of 6x4 5x5 squares. The starting corner of each 5x5 square is lettered in order.

+--+--+--+--+--+--+
|a |b |c |d |e |f |
|  |  |  |  |  |  |
+--+--+--+--+--+--+
| l| k| j| i| h| g|
|  |  |  |  |  |  |
+--+--+--+--+--+--+
|m |n |o |p |q |r |
|  |  |  |  |  |  |
+--+--+--+--+--+--+
| x| w| v| u| t| s|
|  |  |  |  |  |  |
+--+--+--+--+--+--+

The squares a-e and m-n all start in the top left and enter the square to the right in the top left. The squares g-k and s-w all start in the top right and enter the square to the left in the top right. The squares f and r start in the top left and enter the square below in the top right. The sqaures l and x start in the top right and enter the square below in the top left.

Another way to tile this using a spiral pattern. For example, here is a 7x5 set of 5x5 squares.

+--+--+--+--+--+--+--+
|a |b |c |d |e |f |g |
|  |  |  |  |  |  |  |
+--+--+--+--+--+--+--+
|  |u |v |w |x |y | h|
|t |  |  |  |  |  |  |
+--+--+--+--+--+--+--+
|  |  |G |H |I | z| i|
|s |F |  |  |  |  |  |
+--+--+--+--+--+--+--+
|  |  |  |  |  | A| j|
|r | E| D| C| B|  |  |
+--+--+--+--+--+--+--+
|  |  |  |  |  |  | k|
| q| p| o| n| m| l|  |
+--+--+--+--+--+--+--+

The pattern is to simply enter the next square in the corner farthest from the center.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Very nice idea! I think this is the best and easiest so far. $\endgroup$
    – user14478
    Aug 19, 2015 at 17:26
  • $\begingroup$ Indeed, another nice generalization! $\endgroup$
    – Marco13
    Aug 19, 2015 at 18:19
1
$\begingroup$

My solution (one of many) started by solving for a 5x5 square, then expanding it to a 10x10 square....my solution also went one step further by making it a true perfect square, with the 1 and 100 aligning such that it forms an infinite loop...this loop therefore allows for any number to start in square 1 as long as the sequence is followed...this in turn gives 100 unique solutions for the same sequence of numbers...furthermore, if the board is rotated 90 degrees, there are 100 new solutions...so in essence one solution now turns into 400...Further, the sequence can be put in reverse order, thus making 100 new solutions, rotate, 400 new solutions...but on experimentation i believe there would be duplicates...so i will stick with 400 unique solutions from my one sequence

$$\begin{array}{|r|c|} \hline 1 &96 &84 &89 &97 &65 &60 &73 &78 &61 \\ \hline 93 &87 &99 &94 &86 &57 &76 &63 &58 &75 \\ \hline 81 &90 &2 &80 &83 &70 &79 &66 &69 &72 \\ \hline 100 &95 &85 &88 &98 &64 &59 &74 &77 &62 \\ \hline 92 &4 &82 &91 &3 &56 &68 &71 &55 &67 \\ \hline 16 &11 &24 &29 &12 &50 &45 &33 &38 &46 \\ \hline 8 &27 &14 &9 &26 &42 &36 &48 &43 &35 \\ \hline 21 &5 &17 &20 &23 &30 &39 &51 &54 &32 \\ \hline 15 &10 &25 &28 &13 &49 &44 &34 &37 &47 \\ \hline 7 &19 &22 &6 &18 &41 &53 &31 &40 &52 \\ \hline \end{array}$$

of course i can make many many more solutuions from my otiginal 5x5 square (of which i have found two unique solutions that fit MY crteria)...enjoy my solution :)

Improve this answer
$\endgroup$
1
  • $\begingroup$ Well done. Note that building a cycle was also one goal of Trenins answer $\endgroup$
    – Marco13
    Jul 31, 2016 at 13:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.