program finds unavoidable sets, hitting sets

Moschopulus

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

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.