New Release of Checker

Programs which generate, solve, and analyze Sudoku puzzles

New Release of Checker

Postby Moschopulus » Tue Nov 14, 2006 5:50 pm

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.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby wapati » Wed Nov 15, 2006 10:06 am

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

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

Thanks!
wapati
2010 Supporter
 
Posts: 527
Joined: 13 September 2006
Location: Brampton, Ontario, Canada

Postby udosuk » Thu Nov 16, 2006 12:33 pm

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!:)
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby RW » Thu Nov 16, 2006 3:23 pm

udosuk wrote: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.

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

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

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby udosuk » Fri Nov 17, 2006 5:30 am

Thanks RW for the explanation... I didn't understand it correctly before but hopefully do now...:)
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby wapati » Fri Nov 17, 2006 9:07 am

RW wrote: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?
wapati
2010 Supporter
 
Posts: 527
Joined: 13 September 2006
Location: Brampton, Ontario, Canada

Postby RW » Fri Nov 17, 2006 9:29 am

wapati wrote: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
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby wapati » Fri Nov 17, 2006 9:56 am

Thanks RW,

the explaination helps.
wapati
2010 Supporter
 
Posts: 527
Joined: 13 September 2006
Location: Brampton, Ontario, Canada


Return to Software