# [QUIZ] Sodoku Solver (#43)

(Kroeger Simon (ext)) #1

Ok, here's my latest. My big speedup was figuring out that if I make
a bad guess, I just eliminate that possibility and re-solve. See the
startGuessing method..

hmm ... I use cells with only 2 possibilities left for guessing, so if I

guess wrong, at least I know the right guess. (of course only if there
are cells with 2 possibilities - but that happens often) If I interpret
your guess method right you are doing the same thing. So I do not
understand where the speedup comes from.

BTW a lot of speed comes from rather minor changes, like changing

a_set -= [a_value]

to

a_set.delete(a_value)

this makes a HUGE difference. This is obvious if you take some time
to think about it, but it would be realy nice to optimize operators
like -= where you have no chance to use the intermediate objects anyway.

And I don't know why

Set.new(another_set)

seems to be faster than

another_set.clone

I didn't take the time to look into the implementations, yet.

Your 'findPairs' looks promissing... I think I will try something
similar...

It now solves #30 in 0.194s, and #55 in 0.124

Impressive!

( I'm not sure which puzzle you called #1)

The one posted by David Tran, with only 17 numbers given:

···

+-------+-------+-------+

_ _ 6 | 9 _ _ | _ 7 _ |
_ _ _ | _ 1 _ | _ _ 2 |
8 _ _ | _ _ _ | _ _ _ |

+-------+-------+-------+

_ 2 _ | _ _ _ | _ _ 4 |
_ _ _ | _ _ _ | _ _ 1 |
_ _ 5 | _ _ 6 | _ _ _ |

+-------+-------+-------+

_ _ _ | _ _ _ | _ 6 _ |
_ _ _ | _ _ 2 | _ 5 _ |
_ 1 _ | _ 4 3 | _ _ _ |

+-------+-------+-------+

cheers

Simon

> Ok, here's my latest. My big speedup was figuring out that if I make
> a bad guess, I just eliminate that possibility and re-solve. See the
> startGuessing method..

hmm ... I use cells with only 2 possibilities left for guessing, so if I

guess wrong, at least I know the right guess. (of course only if there
are cells with 2 possibilities - but that happens often) If I interpret
your guess method right you are doing the same thing. So I do not
understand where the speedup comes from.

I went back and looked at the differences between the two versions.
After a bad guess, my first version made another guess with the next
possibility on the same cell.
Now it just removes the bad guess and goes back to the logical solver.
I also speeded up the guesser itself - it used to check all the cells
for the one with the minimum number of possibilites, now it just finds
the first with 2 possibilities.

So that's why mine got better, but it was bad before.
I'd like to directly compare the speed of yours to mine on my machine,
but I can't get it to run correctly, It reports every board as UNSOLVABLE.
Has anyone else had any luck with it?

Your 'findPairs' looks promissing... I think I will try something
similar...

I thought that I could speed it up by deducing more cells before I
started guessing, soI tried adding another step to the logic phase:
If any row or col has all it's instances of a given digit in the same
3x3 box, then that digit can be removed from the other 6 cells in the
box.

But it turned out to make the code slower, I think because it wasn't
very efficient, and in most cases it only ended up solving 1 or 2
extra cells before having to go to the guesser anyway.

···

On 8/24/05, Kroeger Simon (ext) <simon.kroeger.ext@siemens.com> wrote:

(Simon Kröger) #3

[...] So that's why mine got better, but it was bad before. I'd like to directly compare the speed of yours to mine on my machine, but I can't get it to run correctly, It reports every board as UNSOLVABLE.
Has anyone else had any luck with it?

Is it posiible that you use ruby 1.8.1 or older?

COMBINEDNEIGHBOURS[c].each{|i|possibilities[i].delete(v)}

by

COMBINEDNEIGHBOURS[c].each{|i|possibilities[i] -= [v]}

I hope that helps (but makes it slower!)

cheers

Simon

Is it posiible that you use ruby 1.8.1 or older?

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

\$ 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

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.