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.
-Adam
···
On 8/24/05, Kroeger Simon (ext) <simon.kroeger.ext@siemens.com> wrote:
[...] 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?
If so, download a newer version 
or replace
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?
If so, download a newer version or replace
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.
-adam