In discrete maths this is called the "hamilton path" of the following connected graph:

- Code: Select all
`0--0--0--0--0--0--0--0--0`

| | | | | | | | |

0--0--0--0--0--0--0--0--0

| | | | | | | | |

0--0--0--0--0--0--0--0--0

| | | | | | | | |

0--0--0--0--0--0--0--0--0

| | | | | | | | |

0--0--0--0--0--0--0--0--0

| | | | | | | | |

0--0--0--0--0--0--0--0--0

| | | | | | | | |

0--0--0--0--0--0--0--0--0

| | | | | | | | |

0--0--0--0--0--0--0--0--0

| | | | | | | | |

0--0--0--0--0--0--0--0--0

Having done several of these paths, I asked myself some questions:

Q1. How many essentially different hamilton paths are there in total (just the structure, numbers are ignored)?

Q2. For each of these hamilton paths, we can construct the "minimum" sudoku grid so that the 81-digit number formed from the starting point to the finish point is the smallest. Surely for some of the paths this is a very enjoyable exercise to do (I strongly recommend everybody to try the "outbound spiral" and "outbound twisted spiral"). So, does there exist a "minimum of minimums", i.e. a path that produces the smallest minimum 81-digit number from them all?

Q3. Is it possible for a hamilton path to have the sequence "123456789123456789...123456789" (i.e. "123456789" repeated 9 times) filled in order?

Q1 is a classic discrete maths exercise, which I think some of the users here can answer elegantly... it's too difficult for me as I haven't touch this subject in a long long time... Like, what's the equivalent result with a chess board? I worked out the result for a 3x3 square, which is essentially only 3 different paths:

- Code: Select all
`zigzag spiral swirl`

0--0--0 0--0--0 0--0--0

| | |

0--0--0 0--0 0 0--0 0

| | | | | |

0--0--0 0--0--0 0 0--0

Q3 is very interesting to try, although after a while you'll find it's awfully hard to succeed... I'd be very interested to see if somebody can find the path or prove it's impossibility...

As for Q2, after some labouring work I've finally found the answer manually. I'm fairly confident I can prove it to be an unique result. It sure is a very very nice puzzle to do, and I can't describe the satisfaction I felt after I obtain the whole solution, which includes the filled grid, the path structure and the 81-digit number...

So, here is the puzzle, which I take the privilege to name it as "Sudoku Dragon", because, with it you can generate the smallest (or the largest if you like) 81-digit number of all snakes (paths), so this is like the "king of all snakes", i.e. a dragon (in oriental terms).

- Code: Select all
`Sudoku Dragon (minimum numbered Wazir's tour)`

1--2 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

Complete the grid with the remaining 79 numbers and orthogonal links between adjacent cells such that it's a valid sudoku grid with a hamilton path and the 81 entries along the path form the minimum 81-digit number.

Of course, you can find similar result for knight's tours or even king's tours/circuits but it's much more complicated because you now have 8 movements from most cells instead of 4... and I think those are best to be tackled by a computer, not by human brains like the one here...

And lastly I have to thank tso for introducing this wonderful idea of sudokus with 0 hint to me...