|Joined: 12 Aug 2005|
|Posted: Mon Dec 05, 2005 9:18 pm Post subject: program finds unavoidable sets, hitting sets
|New program "checker" available at http://www.maths.nuim.ie/staff/gmg/sudoku
This is the program used to show that the SF grid has no 16.
CHECKER will search a given grid for a puzzle with n clues. It stops when it finds one puzzle or has searched the grid completely and found none.
Downloads, details and examples at the above web site. Join the search for a 16-clue sudoku!
The method used by "checker" is this:
1. Find some unavoidable sets,
2. Enumerate all hitting sets of size n, i.e., enumerate all sets of n clues that intersect all the unavoidable sets found in part 1,
3. Check if any of these hitting sets uniquely determines the grid.
Input grids in a file grid.txt in this format:
Type "checker grid.txt 16" to search this grid for a 16-clue puzzle.
It can be used to search a given grid for a puzzle with, say, 25 clues, but there are better puzzle finders out there. It will find one (and only one) with 25 clues pretty quickly however.
Lots of room for improvement!
Co-written by a colleague (who wishes to remain anonymous) and myself.
Please report bugs, suggestions, etc.