Minimum number of Clues for Jigsaw Sudoku

For fans of Killer Sudoku, Samurai Sudoku and other variants

Minimum number of Clues for Jigsaw Sudoku

Postby Ruud » Sun May 21, 2006 1:53 am

Despite the fact that I have a topic about jigsaw sudoku, I am posting this question here, because I know that the best math people are sort of glued to this forum.

We have a hunch, but no proof regarding the minimum number of clues for a classic sudoku. I can't find anything about minimum clues for a jigsaw. This depends on the pattern, of course.

Does anybody know what the best pattern is to generate low-clue jigsaws and what the minimum number of clues are for certain patterns? Has any research been done in this area?

This is what triggered my question. A 15-clue jigsaw, which is solved with singles and a few LoL eliminations.

Code: Select all
.---------------.---.---------------.
| .   .   .   . | . | .   .   9   . |
|       .-------'   '---.           |
| 7   . | .   .   .   3 | .   .   . |
|       |---.   .---.   '---.---.   |
| .   . | . | . | . | 8   . | . | 1 |
|   .---'   '---:   |   .---'   |   |
| . | .   .   . | . | . | 1   . | 3 |
:---'   .-------'   '---'---.   '---:
| .   . | .   .   6   .   . | .   . |
:---.   '---.---.   .-------'   .---:
| 3 | .   5 | . | . | .   .   . | . |
|   |   .---'   |   |---.   .---'   |
| 4 | . | .   1 | . | . | . | .   . |
|   '---'---.   '---'   '---:       |
| .   .   . | 4   .   .   . | .   8 |
|           '---.   .-------'       |
| .   9   .   . | . | .   .   .   . |
'---------------'---'---------------'

I was amazed that the same number of constraints could result in less clues required.

Any thoughts on this?

Ruud.
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby tso » Sun May 21, 2006 2:22 am

Eight clues is the minimum required given for 9x9 jigsaw.

See: http://www.bumblebeagle.org/dusumoh/9x9/index.html

If some type of symmetry is required -- either for the clues, the jigsaw or both -- it may very well increase this minimum.
tso
 
Posts: 798
Joined: 22 June 2005


Return to Sudoku variants