Speedy VB6 backtracker solver (source coming later on)

Merri

Due to contest at VBForums I can't give out the source yet, so I just have to give what I can: the compiled executable. I do tell some technical aspects though.

The logics:
- Naked single
- Hidden single
- Naked pair/triplet/quad aka naked subset (partial)

Each of these are very optimized and there isn't much if any speed gain to do. The same logics are used in backtracking with an additional validator (which is also partial). With partial I mean that the features are so much optimized for speed that the feature is not "perfect": for example, the code doesn't detect all naked triplets. The validator doesn't recognise if there are two same numbers in the same row/col/square. But it validates super fast, which is very important in backtracking when using these logics.

Program features:
- benchmark sudokus (various methods)
- count number of solutions for a sudoku (limits to finding one million solutions per puzzle, which takes about 20 seconds)
- supports five different file formats (the most common ones?)
- supports two different multisudoku/batch formats ("web friendly" and a custom one)
- convert sudokus to different formats (both single file formats and multisudoku/batch formats)
- convert batch format file to different formats

Download

Feel free to compare with your own programs Smile

And I hope there is use for the conversion feature! It is still a work in progress, so please report any bugs etc. you find. The program is not meant for playing, it is more of a "technology preview".

dukuso · Posted: Tue Aug 16, 2005 3:37 am Post subject:

hi Merri,

thanks for the program.
I will install it later. (or wait 10days for the source...)
Is there a commandline version, which just times
the sodokus in a given file ?

what's

- Naked single
- Hidden single
- Naked pair/triplet/quad aka naked subset (partial)

G.

Merri · Posted: Tue Aug 16, 2005 7:11 am Post subject:

I saw these names being used elsewhere.

Naked single: take out the known numbers, if there is only one number left in some cell after doing this, it must be that number.
Hidden single: if a number in a cell is the only possible number in a row/column/square, it must be that number.
Partial naked pair: if there are two cells with the same candidates in a row/column/square, clear the candidates in the other cells in that row/column/square.
Partial naked triplet and naked quad: the same as above for three cells and three candidates and four cells and four candidates.

And no, there is no command line options or command line version (it is on a bit of a harder side to make a command line application in Visual Basic).

dukuso · Posted: Tue Aug 16, 2005 7:45 am Post subject:

Merri · Posted: Tue Aug 16, 2005 8:28 am Post subject:

Humm? How could I use them less or more? They are pretty much the core of the whole thing. Well... I could turn off hidden single and naked subset and it would still do the work, but it would be slower. The whole idea with the logics in backtracking mode is to turn off false answers and paths as fast as possible. These simple logic rules work the best when there are many cells filled and the whole speed of my program depend on how fast these can do their work.

Edit

Here is a more detailed description of how my algorithm works:

- look for naked singles until none can be found; try other logics:
-- look for hidden singles; return to naked singles if success
--- look for naked subset; return to naked singles if success
---- if still unsolved, exit
- if solved, return True; otherwise look for cell with least candidates
- start backtracking from the given cell; return True if success
-- make a copy of all optimization arrays
-- select one of the candidates of the cell, apply it to the cell
-- look for naked singles until none can be found; try Nishio
--- if Nishio succeeds, look for naked singles until none can be found
---- check for validity
----- look for hidden singles; return to naked singles if success
------ look for naked subset; return to naked singles if success
-- if valid but not solved, look for another cell with least candidates; backtrack
-- if valid and solved, return True and end all backtracking
-- if failed Nishio or if unvalid, reset all optimization arrays
-- unmark candidate value, prepare to try another one

This far I haven't found a faster algorithm, ie. all other programs I've tried have been slower.

Merri · Posted: Sun Aug 28, 2005 12:36 am Post subject:

Source code is now available over at VBForums. You can also find other solvers from there.

Won the contest Smile

dukuso · Posted: Sun Aug 28, 2005 7:06 am Post subject:

I tried to make it more exact. I hope, I understood everything correctly.