# \[QUIZ\] Sodoku Solver (#43) **URL:** \ **Category:** ruby-talk\ **Created:** [24 August 2005 08:59 UTC](https://rubytalk.org/t/quiz-sodoku-solver-43/20364 "2005-08-24T08:59:32Z")\ **Posts on this page:** 4\ **Page:** 1
**Author:** ![Kroeger\_Simon\_ext](https://avatars.discourse-cdn.com/v4/letter/k/5daacb/32.png) [@Kroeger\_Simon\_ext](https://rubytalk.org/u/Kroeger_Simon_ext)\ **Post date:** [24 August 2005 08:59 UTC](https://rubytalk.org/t/quiz-sodoku-solver-43/20364/1 "2005-08-24T08:59:32Z")
> 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 ---
**Author:** ![Adam\_Shelly](https://avatars.discourse-cdn.com/v4/letter/a/e19b73/32.png) [@Adam\_Shelly](https://rubytalk.org/u/Adam_Shelly)\ **Post date:** [24 August 2005 22:20 UTC](https://rubytalk.org/t/quiz-sodoku-solver-43/20364/2 "2005-08-24T22:20:49Z")
> \> 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) \ wrote: ---
**Author:** ![Simon\_Kroger](https://avatars.discourse-cdn.com/v4/letter/s/49beb7/32.png) [@Simon\_Kroger](https://rubytalk.org/u/Simon_Kroger)\ **Post date:** [24 August 2005 23:11 UTC](https://rubytalk.org/t/quiz-sodoku-solver-43/20364/3 "2005-08-24T23:11:59Z")
> [...] 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 ---
**Author:** ![Adam\_Shelly](https://avatars.discourse-cdn.com/v4/letter/a/e19b73/32.png) [@Adam\_Shelly](https://rubytalk.org/u/Adam_Shelly)\ **Post date:** [25 August 2005 05:59 UTC](https://rubytalk.org/t/quiz-sodoku-solver-43/20364/4 "2005-08-25T05:59:55Z")
> 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