Adam Shelly wrote:

> Should I post my third version, or is everyone sick of looking at my
> code by now?
> 
> -Adam

You have been busy, hmm?

I also did some refactoring:

                      user     system      total        real
solving nr 1     0.062000   0.000000   0.062000 (  0.093000)
+-------+-------+-------+
| 1 4 6 | 9 2 8 | 3 7 5 |
| 5 9 3 | 6 1 7 | 8 4 2 |
| 8 7 2 | 4 3 5 | 9 1 6 |
+-------+-------+-------+
| 7 2 1 | 3 5 9 | 6 8 4 |
| 9 6 8 | 2 7 4 | 5 3 1 |
| 4 3 5 | 1 8 6 | 2 9 7 |
+-------+-------+-------+
| 2 5 7 | 8 9 1 | 4 6 3 |
| 3 8 4 | 7 6 2 | 1 5 9 |
| 6 1 9 | 5 4 3 | 7 2 8 |
+-------+-------+-------+
...
solving nr 30    1.235000   0.015000   1.250000 (  1.281000)
+-------+-------+-------+
| 1 2 6 | 4 3 7 | 9 5 8 |
| 8 9 5 | 6 2 1 | 4 7 3 |
| 3 7 4 | 9 8 5 | 1 2 6 |
+-------+-------+-------+
| 4 5 7 | 1 9 3 | 8 6 2 |
| 9 8 3 | 2 4 6 | 5 1 7 |
| 6 1 2 | 5 7 8 | 3 9 4 |
+-------+-------+-------+
| 2 6 9 | 3 1 4 | 7 8 5 |
| 5 4 8 | 7 6 9 | 2 3 1 |
| 7 3 1 | 8 5 2 | 6 4 9 |
+-------+-------+-------+
...
solving nr 55    0.625000   0.016000   0.641000 (  0.672000)
+-------+-------+-------+
| 9 3 5 | 1 7 2 | 8 6 4 |
| 2 1 6 | 9 8 4 | 7 5 3 |
| 4 7 8 | 6 5 3 | 2 9 1 |
+-------+-------+-------+
| 3 6 4 | 8 1 9 | 5 7 2 |
| 7 8 2 | 3 4 5 | 9 1 6 |
| 1 5 9 | 2 6 7 | 4 3 8 |
+-------+-------+-------+
| 8 9 3 | 7 2 6 | 1 4 5 |
| 5 2 7 | 4 3 1 | 6 8 9 |
| 6 4 1 | 5 9 8 | 3 2 7 |
+-------+-------+-------+
total           36.205000   0.172000  36.377000 ( 38.749000)
average          0.658273   0.003127   0.661400 (  0.704527)

So it seems like your version is even faster than this, i would
like to see it.

here is mine (i'm especialy delighted on what can be done in 90
lines of code):

-------------------------------------------------------------------
require 'Set'
require 'Benchmark'

col = Array.new(9) {|o| Array.new(9){|i| o + i*9}}
row = Array.new(9) {|o| Array.new(9){|i| o*9 + i}}
box = Array.new(9) {|o| Array.new(9){|i|
   (o / 3) * 27 + (o % 3) * 3 + ((i % 3) + (i / 3) * 9)}}

# this contains the 3 'neighbourhoods' (row/col/box)
# of each of the 81 cells
NEIGHBOURHOODS = Array.new(81) {|o|
   [row[o / 9], col[o % 9],  box[(o / 27) * 3 + (o % 9) / 3]]}

COMBINEDNEIGHBOURS = Array.new(81) {|o|
   NEIGHBOURHOODS[o].flatten.uniq! - [o]}

class Board
   attr_reader :cells, :possibilities

   #initializes the cells and possibilities
   def initialize c
     @possibilities = Array.new(81) {(1..9).to_set}
     @cells = Array.new(81, nil)
     81.times{|i|set_cell(i, c[i]) if c[i]}
   end

   def initialize_copy(b)
      @cells, p = b.cells.clone, b.possibilities
      @possibilities = Array.new(81) {|i|Set.new(p[i])}
   end

   def to_s
     "+-------+-------+-------+\n| " +
     Array.new(3) do |br|
       Array.new(3) do |r|
         Array.new(3) do |bc|
           Array.new(3) do |c|
             cells[br*27 + r * 9 + bc * 3 + c] || "_"
           end.join(" ")
         end.join(" | ")
       end.join(" |\n| ")
     end.join(" |\n+-------+-------+-------+\n| ") +
     " |\n+-------+-------+-------+\n"
   end

   #recursively sets cell 'c' to 'v' and all trivial dependend cells
   def set_cell c, v
     cells[c], possibilities[c] = v, Set[v]
     COMBINEDNEIGHBOURS[c].each{|i|possibilities[i].delete(v)}

     COMBINEDNEIGHBOURS[c].each{|i|
       set_cell(i, possibilities[i].min) if !cells[i] && 
possibilities[i].size == 1}

     return self
   end

   #solves with logic and brute force if neccessary',
   #returns nil if unsolvable
   def solve!
     c = i = changed = 0
     while i = ((i+1)..(changed+81)).find{|x|!cells[x % 81]}
       NEIGHBOURHOODS[c = i % 81].each do |neighbours|
         pn = neighbours.inject(possibilities[c].clone){|r, j|
           (j != c) ? r.subtract(possibilities[j]) : r}
         set_cell(changed = i = c, pn.min) && break if pn.size == 1
       end
     end

     return self if cells.all?
     return nil if possibilities.any?{|p| p.empty?}

     p, i = possibilities.zip((0..80).to_a).select{|a, b|a.size > 1}.
       min{|a, b|a[0].size <=> b[0].size}
     p.each{|j| b=clone.set_cell(i, j).solve! and return b}
     return nil
   end
end

# main
count, $stdout.sync, total = 0, true, Benchmark::Tms.new
Benchmark.bm(15, "total", "average") do |bm|
   loop do
     cells = []
     while !ARGF.eof? && (cells.size < 81) do
       ARGF.gets.scan(/[0-9_.]/).each{|c| cells << c.to_i.nonzero?}
     end
     break if ARGF.eof?
     board = nil
     total += bm.report("solving nr #{count+=1}") do
       board = Board.new(cells).solve!
     end
     puts board ? board.to_s :  "UNSOLVEABLE!" + "\n\n"
   end
   [total, total / count]
end
------------------------------------------------------------------