The New Sudoku Players' Forum

by **udosuk** » Sun Aug 14, 2005 3:42 pm

In the thread titled 0-hint sudoku puzzles, I've shown some paths that went thru' all 81 cells including the zigzag, the spiral and the "twisting spiral". Of course, my definition of a path is quite different from what Condor did, which was the broader definition and didn't care about physical movements. I require that each move must be either up/down/left/right 1 cell.

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...

by **udosuk** » Mon Aug 15, 2005 4:22 pm

Here are some hints for those stuck or don't know how to start, and hopefully these won't spoil too much for the interested. Thanks to dukuso/Guenter for suggesting the name "Wazir's tour". Will keep that in mind. ^_^

Hint 1: The following is the grid produced if you reverse the "Dragon path" (i.e. from the "tail" to the "head") and try to get the minimum 81-digit number. So if you've completed the Sudoku Dragon you can verify the answer by trying to number the path in reverse and see if you can reach this grid.

Code: Select all: 7 6 4 5 3 2 1 8 9 8 5 2 4 1 9 3 6 7 9 3 1 6 8 7 5 4 2 1 2 8 9 7 3 4 5 6 3 4 9 8 6 5 7 2 1 5 7 6 2 4 1 9 3 8 4 9 3 1 2 8 6 7 5 2 1 7 3 5 6 8 9 4 6 8 5 7 9 4 2 1 3

Hint 2: Colour the board in checkers as the following (B=black, w=white). Obviously there are 41 black cells and 40 white cells. So obviously the path has to start and end on black cells, which also implies the "Wazir's circuit" and "Knight's circuit" are both impossible. This is very useful information for the solving process if one can use it well. (BIG HINT!)

Code: Select all: B w B w B w B w B w B w B w B w B w B w B w B w B w B w B w B w B w B w B w B w B w B w B w B w B w B w B w B w B w B w B w B w B w B w B w B w B w B w B w B w B

Hint 3: The 81-digit Dragon number starts as "12121..." and ends as "...89". There are 7 occurences of "12" and "67" each.

Hint 4: Of course, the "1--2" shown at the top left corner in the original puzzle does not indicate the starting point, but is there just to fix the orientation of the solution grid. The true starting point is at R3C5. So now one knows the starting cell and the first 5 digits, one can start the action right now! Enjoy!

by **dukuso** » Tue Aug 16, 2005 1:41 pm

Q3 :
With the help of a computerprogram
I tried to find a (open) Wazir's tour on a 9*9 such that the
(movenumbers mod 9) plus one form a sudokugrid.
Provided I have no bug, there is none.

Now I tried to find a knight's tour with that property. This will
take about 100years to complete, just for starting in a corner.
I didn't yet fill in corced sudoku-clues once some squares are visited
which force other numbers. This would speed up the calculation
a lot, of course and will probably make it feasable.
Maybe I'll try later.

We could relax the consition to find a Wazir-path with above
property which is a valid _sudoku_ rather than a sudokugrid.
So, there is a unique solution and the Wazir only visits
the clues.

(Wazir makes moves of distance one, so these are moves which both, a chessrook and a chessking can make)

by **dukuso** » Tue Aug 16, 2005 3:23 pm

Code: Select all: 1.567.... 23498.... ...12345. ......76. ......8.. ..65.19.. ..7432... .98...... .1.......

rated easy

by **udosuk** » Tue Aug 16, 2005 5:29 pm

Thank you very much dukuso!

It's very nice to know that Q3 is impossible! And your puzzle is great too! (Albeit I wouldn't mind if there are more clues, not for the puzzle to be easier but just to prolong the "sequence".)

I think I could be able to find the Knight's tour by hand... because I just solved the King's tour and King's circuit by hand... (and how great puzzles they are!) But maybe I'm kidding myself here because we all know how much harder the Knight's tour/circuit are than the King's tour/circuit on the chessboard, even without the Sudoku criteria...

by **udosuk** » Tue Aug 16, 2005 8:45 pm

Didn't think it was possible but I managed to solve the minimum numbered King's tour and King's circuit by hand. Turns out that we don't have to worry about checkering the board and the diagonal movements make the numbers much smaller. And the fact that the solutions are both unique is quite delightful too (don't take this for granted). And they both have the "1--2" in the corner like the original Wazir's tour is quite a coincidence too. So, here are the puzzles:

Code: Select all: Sudoku Dragon 2 (minimum numbered King'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 links (orthogonal and diagonal) 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.

Hint 1: The following is the grid produced if you reverse the path (i.e. from the end to the start) and try to get the minimum 81-digit number. So if you've completed the puzzle you can verify the answer by trying to number the path in reverse and see if you can reach this grid.

Code: Select all: 7 9 2 6 8 4 1 3 5 8 1 6 3 5 7 9 4 2 5 3 4 2 1 9 8 7 6 9 5 1 4 7 2 3 6 8 4 6 8 9 3 1 2 5 7 3 2 7 8 6 5 4 1 9 1 8 5 7 2 3 6 9 4 2 7 9 1 4 6 5 8 3 6 4 3 5 9 8 7 2 1

Hint 2: R2C7 is the starting cell and the first few steps are as the following:

Code: Select all: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 / 0 0 0 0 0 1 0 0 0 / 0 0 0 0 1 0 0 0 0 / 0 0 0 2 0 0 0 0 0 / 0 0 1 0 0 0 0 0 0 / 0 1 0 0 0 0 2 0 0 \ / \ 0 0 2 0 0 3 0 1 0 \ / 0 0 0 1-2 0 0 0 0

Hint 3: The number ends as "6789", and "444" appears once inside the number.

Code: Select all: Sudoku Dragon 3 (minimum numbered King's circuit) 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 links (orthogonal and diagonal) between adjacent cells such that it's a valid sudoku grid with a hamilton circuit (i.e. the starting and finishing cells must be adjacent) and the 81 entries along the circuit form the minimum 81-digit number.

Hint 1: The following is the grid produced if you reverse the circuit (i.e. from the end to the start) and try to get the minimum 81-digit number. So if you've completed the puzzle you can verify the answer by trying to number the circuit in reverse and see if you can reach this grid.

Code: Select all: 9 2 3 8 7 1 6 5 4 7 4 8 5 2 6 9 1 3 6 1 5 4 3 9 8 7 2 8 3 2 1 5 7 4 6 9 1 9 7 6 4 3 2 8 5 4 5 6 9 8 2 1 3 7 2 8 4 3 6 5 7 9 1 3 7 9 2 1 8 5 4 6 5 6 1 7 9 4 3 2 8

Hint 2: Again, R2C7 is the starting cell and the first few steps are as the following (exactly same as the above puzzle):

Code: Select all: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 / 0 0 0 0 0 1 0 0 0 / 0 0 0 0 1 0 0 0 0 / 0 0 0 2 0 0 0 0 0 / 0 0 1 0 0 0 0 0 0 / 0 1 0 0 0 0 2 0 0 \ / \ 0 0 2 0 0 3 0 1 0 \ / 0 0 0 1-2 0 0 0 0

Hint 3: The number ends as "7649" this time, but "444" again appears once inside the number, just like the above puzzle.

by **Condor** » Wed Aug 17, 2005 3:44 am

udosuk, here is one for you to try.

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

For this one all the moves are king moves. A little tricky until you past the barrier.

I Think I have a proof it is impossible to cover all 81 cells with just single moves in a rookwise direction in a closed loop. i.e. the two ends can never be brought together.

BTW. There is a very easy way to find the maximum when you know the minimum. I will leave it to you to work out how it is done.

[Edit] When I first made this posting I said 'rook moves in a closed loop'. I meant one square a move.

by **udosuk** » Wed Aug 17, 2005 5:06 pm

Thanks for your very nice puzzle! Just sent you my answer. Hope I didn't mess up...

I can prove a wazir and a knight cannot have circuits on the 9x9 board by checkering the board. However I'm not sure about rook moves (i.e. the rook can move any number of squares orthogonally). Let me think about it...

From day one I know the minimum and maximum problems are the same. You just need to exchange 1's and 9's, 2's and 8's ... etc. That's why I always only listed the "minimum ..." puzzles only. I do think sometimes maximum works better like when you are counting scores. Every move your current score is multiplied by 10 and then add the number you just put in. To get a high score you must try to use the largest possible digit each time...

by **dukuso** » Wed Aug 17, 2005 5:44 pm

I don't so much like the pieces like rook,king,queen,knight,wazir
here, because their movements are incompatible with
the sudoku-symmetries.
So how about a piece with keeps one of {row,column,block}
at each move but changes the other two ? (16 moves)

That's maybe a too powerful piece.

Or a piece which keeps block+row or block+column
or block-position and row or block-position and column ?
(8 moves)

e.g. 35 can move to 34,36,25,15,32,38,65,95

just an idea, I haven't yet tried anything with this
sudoku-hopper.

Guenter.

by **udosuk** » Wed Aug 17, 2005 7:42 pm

I've just checked out that a rook CAN have a circuit (closed end loop) in the 9x9 sudoku board.

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

Afterwards the rook can simply jump back to the starting point. Maybe Condor was refering to the wazir instead?

I'll think about dukuso's suggestions. Mmm... your hopper piece sounds interesting. It can move orthogonally within the box, or "teleport" to the same position in another box... can try but must be a real pain to visualize when solving by hand! What about a piece that can only move 1 step orthogonally (i.e. wazir) within the box, and jump 3 steps diagonally (thus guarantee to move to another box in the same position)? That way it only has 8 moves when it's at R5C5 and in most other cells will have fewer moves... easier to analyse?

by **Condor** » Thu Aug 18, 2005 2:15 am

udosuk wrote:I've just checked out that a rook CAN have a circuit (closed end loop) in the 9x9 sudoku board.

Afterwards the rook can simply jump back to the starting point. Maybe Condor was refering to the wazir instead?

Sorry udosuk, I meant a rookwise move one square at a time. I have edited my posting above to show this.

by **dukuso** » Thu Aug 18, 2005 4:29 am

udosuk wrote:I'll think about dukuso's suggestions. Mmm... your hopper piece sounds interesting. It can move orthogonally within the box, or "teleport" to the same position in another box... can try but must be a real pain to visualize when solving by hand! What about a piece that can only move 1 step orthogonally (i.e. wazir) within the box, and jump 3 steps diagonally (thus guarantee to move to another box in the same position)? That way it only has 8 moves when it's at R5C5 and in most other cells will have fewer moves... easier to analyse?

well, my 8-directions hopper-piece is more related to the
"constraint sudoku"
or 4dim-sudoku or how it is called, where you have 9 additional
groups with the cells at the same offset within a block.
But it's also related in normal sudoku to the canonical normal
subgroups of the transformation-group. (except transposing,
which is special.
Your diagonal steps are incompatible with this.
It might be more interesting from a puzzler's POV but
mathematically it's less interesting IMO.

A pieces which moves to any cell in the same minirow or minicolumn
is also interesting, but it can never leave the block.

Maybe someone can develope a sort of "sudoku-chess" ?

by **udosuk** » Thu Aug 18, 2005 9:38 am

First, about "sudoku-chess", people have to know that the game of Shogi (Japanese chess) is played on a 9x9 board. I guess the origin of Sudoku might be related to Shogi in some way too.

In Shogi there are some interesting rules, none more so than that the captured pieces may be used against their original owner... another one is that the pieces can each promoted to a powered-up version once they reach the last 3 ranks, and they just need to be flipped to show their promoted value... I always wonder about the promotion in western chess... That to cater the full possibilities should we prepare 8 extra pieces of each type of queens, knights, bishop and rooks?

Stretching too far now...

Anyhow, there could be some interested Shogi pieces we can consider. Eg. the ginsho (silver general), which moves 1 step diagonally or 1 step forward, can have some interesting tours/circuits. However the moves are not symmetric anymore...

(Edit: correction of an error)

I'm currently still working on the minimum knight's tour. I think the best starting sequence you can get is "111111122122221...":

Code: Select all: 0 0 0 0 0 1 0 0 0 / \---\ 0 1 0 0 0 | 0 0 2 0 \ / / 0 0 | 0 0 2 0 0 | 0 1 \ / //---// 0 0 1 0 | 0 0 2 0 | 0 \ / / 0 0 0 | 2 0 0 0 1 0 /---/\ / 0 2 0 1 0 0 0 | 0 0 \ \ / 0 3 | 0 0 | 0 0 1 0 0 / \ \ /---/ 0 | 0 2 0 1 0 0 0 0 //---/ 1 0 0 0 0 0 0 0 0

Maybe somebody can help me with a program to find a better start? I have a feeling the minimum knight's tour might not be a unique one like the previous 3 cases. It's just too complicated to analyse...

by **Condor** » Fri Aug 19, 2005 2:18 am

udosuk, here are a couple more to try. The first is not as differcult as it looks, the second I have just thought up so have not tried yet.

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 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

[addenum] I should have stated the purpose of these puzzles for those not familiar with them.

The object of these puzzles is to construct a sudoku such that the path given is a minimum. There is 2 ways of doing this inbound and outbound.

Inbound starts from the end on the left-side of the puzzle (r5c1) and outbound starts in the center.

by **Condor** » Fri Aug 19, 2005 3:43 am

Just thought of this one. It looks like it will be quite differcult. I have tried it yet.

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

The purpose of this puzzle is the same as the one above except for inbound and outbound.