The New Sudoku Players' Forum

[Moschopulus]

There is a new release of checker available at this link.

The main improvement is to the part of the program that finds a max clique and the MCN. Even for the MC (most canonical) grid, which was the worst case, it now finds a max clique in a few seconds. For most grids it is instant. Hopefully it is now less painful to use the the MC grid.

Other changes:

-"checkerall", the very slow version of checker using *all* unavoidable sets (not just 64, 128, 192, ...) no longer exists. Instead, we added checker320 which might be faster for very long searches than checker256.

-Renamed "checker" to "checker192", to avoid confusion. So there is no longer an executable file called "checker".

-Added a small speed improvement to the enumeration part of checker.

[wapati]

What is interesting about checker that puzzle solvers should use it?

If solvers don't "want" it, who does, and why?

Thanks!

[udosuk]

If I understand it correctly it's a mathematical tool to compute the number of unavoidables/deadly patterns in a solution grid... And the average sudoku players probably won't have much interest in it...

But this program is probably desirable to puzzle designers and people who're interested about the mathematical aspects of sudoku grids... So good job Moschopulus and keep up the good work!

[RW]

If I understand it correctly it's a mathematical tool to compute the number of unavoidables/deadly patterns in a solution grid...

The tool that finds the unavoidables is only a small part of the program and it doesn't find all, only the smallest ones, which is a very small percent of the unavoidables in any grid. Checker then uses these unavoidable sets to run a exhaustive search through the grid for puzzles with a given number of clues. With this tool you may thus prove that a grid either has or has not valid puzzles with a given number of clues.

And the average sudoku players probably won't have much interest in it...

That is true, it's mostly useful for research.

RW

[udosuk]

Thanks RW for the explanation... I didn't understand it correctly before but hopefully do now...

[wapati]

The tool that finds the unavoidables is only a small part of the program and it doesn't find all, only the smallest ones, which is a very small percent of the unavoidables in any grid. Checker then uses these unavoidable sets to run a exhaustive search through the grid for puzzles with a given number of clues. With this tool you may thus prove that a grid either has or has not valid puzzles with a given number of clues.

RW

This tool only finds a few of the unavoidables and then draws a conclusion?

[RW]

This tool only finds a few of the unavoidables and then draws a conclusion?

No. It finds the smallest unavoidables, and counts the MCN (=maximum amount of disjoint unavoidable sets). All of these must have at least one clue in them. Then it goes through all possible combinations with one clue in all of these disjoint sets + extra clues adding up to the specified number. So if a grid has MCN 15 and you look for 17 clue puzzles, then for each possibility to put 15 clues in the 15 disjoint sets, it tests all possible configuration with those clues + 2 more anywhere in the grid. If these 15 + 2 clues hits all unavoidables in use (depending on witch version of checker you use), then a fast solver solves it to see if it has an unique solution. The exhaustive search usually takes several hours to several days, depending on the grid, but the answer it gives is cold fact. It will find ALL unique puzzles in the grid with the given amount of clues.

RW

[wapati]

Thanks RW,

the explaination helps.