[QUIZ] Sodoku Solver (#43)

ruby-talk
1

> Is it posiible that you use ruby 1.8.1 or older?
> If so, download a newer version :slight_smile: or replace

Thanks, that was it.

It took me some time to figure that out on a second pc :slight_smile:

And congrats, you win :slight_smile: I modified your code to run a single puzzle
at at time, and ran the set of 55 puzzles:

hmm .. it should be happy with just one puzzle.
But thank you for the flowers anyway :slight_smile:

$ for i in *.sdk; do time ruby MySolver.rb $i ;done >tmy 2>&1

$ ruby parsetimes.rb tmy
min max total ave
0.037 0.722 11.55 0.21

$ for i in *.sdk; do time ruby SKSolver.rb $i ;done >tsk 2>&1

$ ruby parsetimes.rb tsk
min max total ave
0.049 0.331 10.043 0.1826

You have a fast machine!
~0.2 average on this set isn't bad at all.

Your time on the hard ones is twice as fast as mine.
I really like the idea of the COMBINED_NEIGHBORHOODS array.
I think I learned a lot by deciphering your code even if I'm still not
sure I completely understand the main loop.

which one? the one labeled #main or the main solving loop?

Ok, just some random thoughs because I don't have time to come up
with another version before this nice quiz is over:

I tried some more elaborated logic (as others) but it seems they don't
buy you much. e.g. I generalise your findPairs to find groups of
identical possibilities and clear these possibilities from the other
cells (if the group is as large as the number of possibilities
contained) But it never found such a group with more than 2 members.

I also tried a lookahead algorithm:
If there is no stringent next move, look for a cell with only 2
possibilities. Create 2 Boards which these cell set to each of the
possibilities, solve both of them as far as possible without guessing.
If one turns out to be unsolveable this is trivial, if not remove
from the original board for all cells all possibilities that are not in
either of the 2 boards.
(its slower than just brute forcing)

What I had done if I had more time:
Replacing the possibilities Sets by plain Fixnumns, using the first
9 bits as indicators if a move is still possible or not.
Perhaps even move the value of the cell in the upper part of that
fixnum, so there is only one array of 81 fixnums containing the whole
board.

Show that a totally braindead brute force solution written in c is
faster :confused:

cheers

Simon

p.s.: may I suggest finding hard sodukus one of the next quizes?