The New Sudoku Players' Forum

[msaghaei]

Having in mind the sudoku game I tried to do the same with a completed knight tour and the result, I named it XKnight Game hope to be interesting. I dont know whether it is previously known. XKnight is a (new) game based on knight's tour problem. It is a completed knight's tour in which some knights have been removed provided that the remaining knights have only one valid knight's tour (i.e. solution). Therefore the object of the game is to find the missing knights to complete their tour. The difficulty of the puzzle seems to depends on the number of remaining knights and also the pattern of knights removal (e.g. removing ranges versus isolated knights). Consider the following example of knight placements:

Code: Select all

+----+----+----+----+----+----+----+----+
|    |    |    | 39 |    |    |    |    |
+----+----+----+----+----+----+----+----+
|    |    | 57 | 18 |    |    |    | 20 |
+----+----+----+----+----+----+----+----+
| 16 | 59 | 40 | 51 |    |  1 |    |  3 |
+----+----+----+----+----+----+----+----+
|    |    | 63 |    |    |    |    | 54 |
+----+----+----+----+----+----+----+----+
|    |    |    | 45 | 64 | 55 |    | 25 |
+----+----+----+----+----+----+----+----+
|    |    | 61 | 30 |    | 28 |    |    |
+----+----+----+----+----+----+----+----+
|    |    | 34 |    |    |    |    |    |
+----+----+----+----+----+----+----+----+
| 35 |    | 13 | 32 |    |    | 11 |    |
+----+----+----+----+----+----+----+----+


To complete the suggested board we have only one solution:

Code: Select all

+----+----+----+----+----+----+----+----+
| 58 | 17 | 42 | 39 | 52 | 19 |  2 | 23 |
+----+----+----+----+----+----+----+----+
| 41 | 38 | 57 | 18 | 43 | 22 | 53 | 20 |
+----+----+----+----+----+----+----+----+
| 16 | 59 | 40 | 51 | 56 |  1 | 24 |  3 |
+----+----+----+----+----+----+----+----+
| 37 | 46 | 63 | 60 | 29 | 44 | 21 | 54 |
+----+----+----+----+----+----+----+----+
| 62 | 15 | 50 | 45 | 64 | 55 |  4 | 25 |
+----+----+----+----+----+----+----+----+
| 47 | 36 | 61 | 30 | 33 | 28 |  7 | 10 |
+----+----+----+----+----+----+----+----+
| 14 | 31 | 34 | 49 | 12 |  9 | 26 |  5 |
+----+----+----+----+----+----+----+----+
| 35 | 48 | 13 | 32 | 27 |  6 | 11 |  8 |
+----+----+----+----+----+----+----+----+


Also consider the following 6*6 board:

Code: Select all

+----+----+----+----+----+----+
|  7 |    | 21 | 28 |  1 | 12 |
+----+----+----+----+----+----+
|    |    |    | 11 |    |    |
+----+----+----+----+----+----+
|  9 |    |    | 26 |    |  2 |
+----+----+----+----+----+----+
|    |    |    |    |    |    |
+----+----+----+----+----+----+
|  5 |    | 25 | 36 |  3 | 14 |
+----+----+----+----+----+----+
| 24 | 31 |    | 15 |    | 35 |
+----+----+----+----+----+----+


and its solutin:

Code: Select all

+----+----+----+----+----+----+
|  7 | 10 | 21 | 28 |  1 | 12 |
+----+----+----+----+----+----+
| 22 | 29 |  8 | 11 | 20 | 27 |
+----+----+----+----+----+----+
|  9 |  6 | 33 | 26 | 13 |  2 |
+----+----+----+----+----+----+
| 32 | 23 | 30 | 17 | 34 | 19 |
+----+----+----+----+----+----+
|  5 | 16 | 25 | 36 |  3 | 14 |
+----+----+----+----+----+----+
| 24 | 31 |  4 | 15 | 18 | 35 |
+----+----+----+----+----+----+


I think the following board has the minimum number of knights:

Code: Select all

+----+----+----+----+----+----+
|    |    |    |    |    |    |
+----+----+----+----+----+----+
|    |    |    |    |    |    |
+----+----+----+----+----+----+
|    |    |    |    |    |    |
+----+----+----+----+----+----+
|    | 35 |    |  1 |    |    |
+----+----+----+----+----+----+
|    |    |    |    |    |    |
+----+----+----+----+----+----+
| 34 | 15 | 20 |    |    |    |
+----+----+----+----+----+----+


Its solution is:

Code: Select all

+----+----+----+----+----+----+
| 25 |  6 | 27 | 10 | 23 |  8 |
+----+----+----+----+----+----+
| 28 | 17 | 24 |  7 | 30 | 11 |
+----+----+----+----+----+----+
|  5 | 26 | 29 | 36 |  9 | 22 |
+----+----+----+----+----+----+
| 16 | 35 | 18 |  1 | 12 | 31 |
+----+----+----+----+----+----+
| 19 |  4 | 33 | 14 | 21 |  2 |
+----+----+----+----+----+----+
| 34 | 15 | 20 |  3 | 32 | 13 |
+----+----+----+----+----+----+


The following 8 x 8 board has the minimum number of knights which I have been able to produce:

Code: Select all

+----+----+----+----+----+----+----+----+
|    |    |    |    |    | 62 |    |    |
+----+----+----+----+----+----+----+----+
|    |    |    |    |    |  5 | 34 |    |
+----+----+----+----+----+----+----+----+
|    |    | 39 |    | 61 | 36 |    |    |
+----+----+----+----+----+----+----+----+
|    |  1 | 58 |    |    |    |    |    |
+----+----+----+----+----+----+----+----+
|    |    |    |    |    | 48 |  9 |    |
+----+----+----+----+----+----+----+----+
|    |    | 14 | 53 |    | 51 |    |    |
+----+----+----+----+----+----+----+----+
|    | 16 | 43 | 20 |    | 22 |    |    |
+----+----+----+----+----+----+----+----+
|    |    | 54 |    |    |    |    |    |
+----+----+----+----+----+----+----+----+


with the following unique solution:

Code: Select all

+----+----+----+----+----+----+----+----+
| 31 | 38 |  3 | 60 | 33 | 62 | 27 |  6 |
+----+----+----+----+----+----+----+----+
|  2 | 59 | 32 | 37 | 28 |  5 | 34 | 63 |
+----+----+----+----+----+----+----+----+
| 57 | 30 | 39 |  4 | 61 | 36 |  7 | 26 |
+----+----+----+----+----+----+----+----+
| 40 |  1 | 58 | 29 |  8 | 25 | 64 | 35 |
+----+----+----+----+----+----+----+----+
| 15 | 56 | 17 | 44 | 21 | 48 |  9 | 50 |
+----+----+----+----+----+----+----+----+
| 18 | 41 | 14 | 53 | 12 | 51 | 24 | 47 |
+----+----+----+----+----+----+----+----+
| 55 | 16 | 43 | 20 | 45 | 22 | 49 | 10 |
+----+----+----+----+----+----+----+----+
| 42 | 19 | 54 | 13 | 52 | 11 | 46 | 23 |
+----+----+----+----+----+----+----+----+


I implemented a desktop software for XKnight Game in visual basic and also tried to implement an online vesion in php. Unfortunately the algorrhythm I use is very slow for online implementation. Therefore I placed some sample output of the desktop version at:
http://www.saghaei.net/xknight/index.php
http://www.msaghaei.com/xknight/index.php

[udosuk]

I like this game! Especially after a few techniques are developed it becomes quite a lot of fun...

Of the 4 puzzles you posted, I managed to solve 3 of them "logically" (no trial & error). The one which troubles me is the 5-clue 6x6 puzzle. Is there any "purely logical" way to solve all the steps?

Finally, a couple techniques I developed:

1. Linkage - provided neither 1 nor 36/64 (the largest number) is the value in a cell, it must act as a "link" between 2 of the 8 "neighbours", i.e. if n is the value in the cell, then 2 of its "neighbours" must be n-1 & n+1 respectively. For example, the corner cells must act as a "link" to its only 2 neighbours...

2. Bridging - this is the exact opposite of the above. We don't know the value of the cell yet, but all but one of its neighbours are occupied already. So, the candidates of the cell must be adjacent to one of its neighbours, and the sole empty neighbour is an extension to this sequence. For example, of the 3 neighbours of a cell next to one of the corner, we have m, n and an empty cell. m-1 and m+1 already appear somewhere. So, the only possible candidates to the cell are n-1 & n+1, and the empty neighbour could only be n-2 or n+2...

Would really like to see a "walkthrough" of how to solve the 5-clue puzzle...

[msaghaei]

The idea of Linkage and Bridging is intersting and I think one will use it intuitively. In addition I think (but not certain) that some terminology of sudoku solving (unfortunately I'm not enough expert to cite them correctly) may also be useful here. For this it may be required to set up the possible values table (kandidates) and recuresivley rule out some kandidates (e.g. using naked pairs to exclude the kandidates from other cells).

[udosuk]

I think you are talking about naked and hidden subsets, which are quite intuitive to experienced sudoku players instead...

Besides setting candidates (which I didn't attempt in my spreadsheet as putting 36/64 possible candidates in each cell can look quite messy), I instead put up another 6x6/8x8 square showing all numbers that haven't been fixed on the grid (i.e. the "available pieces" if you think it as a board game), and it helps greatly...

Also, last year I was working on the "minimum numbered hamilitonian tours/circuits" (I coined it the "sudoku dragon", the link is here), and I studied a great deal on how to work a knight's tour on a 9x9 grid, so it is also possible to play your game on a 9x9 grid with 81 numbers...

Also, you could have made it a knight's circuit game (1 and the last number must be neighbours), and there could be even fewer starting clues...

So, is the 5-clue 6x6 puzzle solvable with logic only? Or must one do it with T&E/proof by contradiction?

[msaghaei]

Dear udosuk
Sorry for any misunderstanding. I do not mean any ruddness by using the word "intuitive". (my native lang is not english).

Thank you for the link to your sudoku dragon. I have visited it previously when searching this forum for "knight tour". Although I have read it previously and now, I was not able to catch the exact point (for me it is really twisted spiral). Is my game related to Q3? Indeed this caused me to remember another sudoku variant in which instead of blocks (as an extra constrain to latin squar) the knight movement (closed tour from 1 to 9) is the constrain (currently I'm working on it).
I was not able to solve the 5-clue 6x6 puzzle with logic only, I hope you can. Also currently I do not have any walkthrough to solve these puzzles.

[udosuk]

No rudeness was implied for the use of "intuitive"... I was just saying for a player familiar with knight touring puzzles (like you) my techniques would of course look intuitive, while for someone more familiar with sudoku puzzles (majority of viewers here) they might not look as intuitive as basic sudoku techniques such as hidden/naked subsets...

As a matter of fact I regard "intuitive" as a positive word as I myself am perhaps quite an intuitive person...

My "Sudoku Dragon" post was quite messy with other concepts intertwined (the spirals were another type of puzzles where you're given the path and just need to number the cells along it, whereas in "Sudoku Dragon" you're given the movement of the piece (wazir/king/knight) and need to construct the path instead). Perhaps if you go to the 2nd page and the knight-related puzzles are coined "Sudoku Dragon 4" & "Sudoku Dragon 4.5" respectively...

I will look again at the 5-clue 6x6 board... But I don't think it's probable for a pure logical solution... Nevertheless it's an amazing discovery with a unique solution for such few hints... Well done!