[QUIZ] Sodoku Solver (#43)

Here's what my solver spewed out for this:

Problem:
    1 2 3 4 5 6 7 8 9

···

On 8/21/05, Vance A Heron <heron@jpl.nasa.gov> wrote:

I too did one back in April - and have modfied it to
read (and write) the current intput format.

Here's the puzzle that takes a *long* time - I don't
remember if it's even solvable, but my solver has
been running for over an hour so far ...
+-------+-------+-------+
> _ _ _ | _ _ _ | _ _ _ |
> 7 _ _ | _ 8 _ | 3 _ _ |
> _ _ _ | 7 _ _ | _ _ _ |
+-------+-------+-------+
> _ _ _ | _ _ _ | _ _ _ |
> _ _ 9 | _ 1 _ | _ _ _ |
> _ _ _ | _ _ 7 | _ _ _ |
+-------+-------+-------+
> _ _ 1 | _ _ 8 | _ 2 _ |
> _ _ _ | _ 2 6 | _ _ 1 |
> _ _ _ | 3 _ 5 | _ _ _ |
+-------+-------+-------+

  +--------------------------
1 | _, _, _, _, _, _, _, _, _
2 | 7, _, _, _, 8, _, 3, _, _
3 | _, _, _, _, _, _, _, _, _
4 | _, _, 9, _, 1, _, _, _, _
5 | _, _, _, _, _, 7, _, _, _
6 | _, _, 1, _, _, 8, _, 2, _
7 | _, _, _, _, 2, 6, _, _, 1
8 | _, _, _, 3, _, 5, _, _, _
9 | _, _, _, _, _, _, _, _, _
Filled: 14 / 81

Solution:
    1 2 3 4 5 6 7 8 9
  +--------------------------
1 | 1, 2, 3, 4, 5, 9, 6, 7, 8
2 | 7, 4, 5, 6, 8, 1, 3, 9, 2
3 | 6, 9, 8, 7, 3, 2, 1, 4, 5
4 | 2, 6, 9, 5, 1, 3, 7, 8, 4
5 | 5, 8, 4, 2, 6, 7, 9, 1, 3
6 | 3, 7, 1, 9, 4, 8, 5, 2, 6
7 | 9, 3, 7, 8, 2, 6, 4, 5, 1
8 | 4, 1, 2, 3, 7, 5, 8, 6, 9
9 | 8, 5, 6, 1, 9, 4, 2, 3, 7
Filled: 81 / 81

real 0m6.210s
user 0m6.203s
sys 0m0.006s

------

At 6 seconds... it really needed to crunch.

Mohit.

--
Mohit Muthanna [mohit (at) muthanna (uhuh) com]
"There are 10 types of people. Those who understand binary, and those
who don't."

Looking good. Here's a few general Ruby style tips. Feel free to ignore, if your not interested:

1. An easier way to write `print "line\n"` is `puts line`.
2. Instead of using the dprint() method and commenting out the print, try puts "whatever" if $DEBUG. Then you can use Ruby's -d command-line switch to enable debugging output whenever you like (it sets $DEBUG).
3. You can drop those outer parenthesis for if statements. `if (condition)` can be just `if condition`.

James Edward Gray II

···

On Aug 23, 2005, at 6:54 AM, Adam Shelly wrote:

Ok, I've updated my version to resort to guessing when it can't deduce
all the values.

But it is solvable:

Input:
_ 2 _ _ _ _ _ _ _
_ _ _ 6 _ _ _ _ 3
_ 7 4 _ 8 _ _ _ _
_ _ _ _ _ 3 _ _ 2
_ 8 _ _ 4 _ _ 1 _
6 _ _ 5 _ _ _ _ _
_ _ _ _ 1 _ 7 8 _
5 _ _ _ _ 9 _ _ _
_ _ _ _ _ _ _ 4 _
Solution:
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

···

On Tue, 23 Aug 2005 13:54:25 +0200, Adam Shelly <adam.shelly@gmail.com> wrote:

And it took a while to figure out that this one was unsolvable:
+-------+-------+-------+
> _ 2 _ | _ _ _ | _ _ _ |
> _ _ _ | 6 _ _ | _ _ 3 |
> _ 7 4 | _ 8 _ | _ _ _ |
+-------+-------+-------+
> _ _ _ | _ _ 3 | _ _ 2 |
> _ 8 _ | _ 4 _ | _ 1 _ |
> 6 _ _ | 5 _ _ | _ _ _ |
+-------+-------+-------+
> _ _ _ | _ 1 _ | 7 8 _ |
> 5 _ _ | _ _ 9 | _ _ _ |
> _ _ _ | _ _ _ | _ 4 _ |
+-------+-------+-------+

UNSOLVABLE

Mohit Muthanna wrote:

···

On 8/21/05, Vance A Heron <heron@jpl.nasa.gov> wrote:

>> [...]

Here's the puzzle that takes a *long* time - I don't
remember if it's even solvable, but my solver has
been running for over an hour so far ...
+-------+-------+-------+

_ _ _ | _ _ _ | _ _ _ |
7 _ _ | _ 8 _ | 3 _ _ |
_ _ _ | 7 _ _ | _ _ _ |

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

_ _ _ | _ _ _ | _ _ _ |
_ _ 9 | _ 1 _ | _ _ _ |
_ _ _ | _ _ 7 | _ _ _ |

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

_ _ 1 | _ _ 8 | _ 2 _ |
_ _ _ | _ 2 6 | _ _ 1 |
_ _ _ | 3 _ 5 | _ _ _ |

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

>

Here's what my solver spewed out for this:

Problem:
    1 2 3 4 5 6 7 8 9
  +--------------------------
1 | _, _, _, _, _, _, _, _, _
2 | 7, _, _, _, 8, _, 3, _, _
3 | _, _, _, _, _, _, _, _, _
4 | _, _, 9, _, 1, _, _, _, _
5 | _, _, _, _, _, 7, _, _, _
6 | _, _, 1, _, _, 8, _, 2, _
7 | _, _, _, _, 2, 6, _, _, 1
8 | _, _, _, 3, _, 5, _, _, _
9 | _, _, _, _, _, _, _, _, _
Filled: 14 / 81

This is missing the third row of the original Problem, which probably isn't solvable. (At least my solver claims that it isn't after 0.08 seconds of calculation... :wink:

Dennis

Looking good. Here's a few general Ruby style tips. Feel free to
ignore, if your not interested:

1. An easier way to write `print "line\n"` is `puts line`.
2. Instead of using the dprint() method and commenting out the

thanks

3. You can drop those outer parenthesis for if statements. `if
(condition)` can be just `if condition`.

I know, but C programmer habits die hard. just looks funny without them...

So here's one thing I couldn't figure out last night, maybe someone can help me:
I wanted to throw an exception in the middle of a pair of recursive
functions, and catch it at the beginning of recursion. But I can't
figure out where to put the rescue.
I wanted to do something like this pseudocode:

def solve
    deduce
    startGuessing if !solved
    return solved
end

def deduce
    ...work...
    raise BadGuess if conflict
end

def startGuessing
  @depth+=1
  begin
    while candidates do
      begin
        guess #chose a candidate
        cloneBoard.solve #with that candidate
     rescue BadGuess
        #go on to next candidate
      end
    end #while
    raise UnsolvableBoard if !solved
  rescue UnsolvableBoard if @depth == 1 # this doesn't work.
      # if I remove the if, I end up at the level I started with.
     # and putting the rescue in the solve function doesn't help either.
      # ? So can I get back to the next candidate on the 1st level,
     # without checking return codes the whole way down
     # (which is what I ended up doing)?
  end
end

Thanks for any ideas,
-Adam

···

On 8/23/05, James Edward Gray II <james@grayproductions.net> wrote:

Since everyone pointed this out, I worked on my guessing code more.
Now I get

···

On 8/23/05, Dominik Bathon <dbatml@gmx.de> wrote:

But it is solvable:

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

_ 2 _ | _ _ _ | _ _ _ |
_ _ _ | 6 _ _ | _ _ 3 |
_ 7 4 | _ 8 _ | _ _ _ |

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

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

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

_ _ _ | _ 1 _ | 7 8 _ |
5 _ _ | _ _ 9 | _ _ _ |
_ _ _ | _ _ _ | _ 4 _ |

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

Only Solveable by Guessing
+-------+-------+-------+

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 |

+-------+-------+-------+
real 0m0.203s
user 0m0.218s
sys 0m0.015s

And my previous slowest one went from 16.3s down to 0.37s
The newest slowest is
+-------+-------+-------+

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

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

_ 9 _ | _ _ _ | _ _ 7 |
_ _ _ | 3 _ _ | 4 _ 5 |
_ _ 6 | 7 _ _ | _ _ _ |

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

_ _ 1 | _ _ _ | _ _ _ |
2 _ _ | _ 7 4 | _ _ _ |
_ _ _ | 2 _ _ | 3 _ _ |

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

Only Solveable by Guessing
+-------+-------+-------+

7 8 2 | 4 5 3 | 6 1 9 |
4 6 5 | 1 9 7 | 8 2 3 |
3 1 9 | 6 8 2 | 7 5 4 |

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

5 9 3 | 8 4 1 | 2 6 7 |
1 2 7 | 3 6 9 | 4 8 5 |
8 4 6 | 7 2 5 | 9 3 1 |

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

6 7 1 | 9 3 8 | 5 4 2 |
2 3 8 | 5 7 4 | 1 9 6 |
9 5 4 | 2 1 6 | 3 7 8 |

+-------+-------+-------+
real 0m2.844s
user 0m2.858s
sys 0m0.015s

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

-Adam

You can always recuse it, then throw it again if you don't want it. At
least I assume so... I've never tried to do it in Ruby.

···

On 8/23/05, Adam Shelly <adam.shelly@gmail.com> wrote:

So here's one thing I couldn't figure out last night, maybe someone can help me:
I wanted to throw an exception in the middle of a pair of recursive
functions, and catch it at the beginning of recursion. But I can't
figure out where to put the rescue.
I wanted to do something like this pseudocode:

def solve
   deduce
   startGuessing if !solved
   return solved
end

def deduce
   ...work...
   raise BadGuess if conflict
end

def startGuessing
@depth+=1
begin
   while candidates do
     begin
       guess #chose a candidate
       cloneBoard.solve #with that candidate
    rescue BadGuess
       #go on to next candidate
     end
   end #while
   raise UnsolvableBoard if !solved
rescue UnsolvableBoard if @depth == 1 # this doesn't work.
     # if I remove the if, I end up at the level I started with.
    # and putting the rescue in the solve function doesn't help either.
     # ? So can I get back to the next candidate on the 1st level,
    # without checking return codes the whole way down
    # (which is what I ended up doing)?
end
end

--
~Travis

Adam Shelly said:

So here's one thing I couldn't figure out last night, maybe someone can
help me:
I wanted to throw an exception in the middle of a pair of recursive
functions, and catch it at the beginning of recursion. But I can't
figure out where to put the rescue.

You could try something like this:

  def search_for_solution
    solve
  rescue UnsolvableBoard
    # Handle Unsolvable Boards ...
  end

  def solve
    while candidates do
      begin
        guess #chose a candidate
        cloneBoard.solve #with that candidate
     rescue BadGuess
        #go on to next candidate
      end
    end #while
    raise UnsolvableBoard if !solved
  end

···

--
-- Jim Weirich jim@weirichhouse.org http://onestepback.org
-----------------------------------------------------------------
"Beware of bugs in the above code; I have only proved it correct,
not tried it." -- Donald Knuth (in a memo to Peter van Emde Boas)

Please do. I can only talk about in the summary what I see.

James Edward Gray II

···

On Aug 23, 2005, at 3:17 PM, Adam Shelly wrote:

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

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

Adam Shelly wrote:

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

He posts an 8000% speed increase and he wants to know if we want to see his code.... :slight_smile:

-dB

···

--
David Brady
ruby_talk@shinybit.com
I'm feeling really surreal today... OR AM I?

Adam Shelly wrote:

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

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..

It now solves #30 in 0.194s, and #55 in 0.124 ( I'm not sure which
puzzle you called #1)

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

Mine definitely feels wordy to me at 370 lines:

#!/usr/bin/env ruby

# SodukuSolver.rb
# author: Adam Shelly
# Solves soduku puzzles.
# supports arbitrary grid sizes (tested upto 16x16)

def dprint(s)
    print s if $DEBUG
end

class BadGuessException < Exception
end

    #Utility function to define the box dimensions inside a grid
    @@boxcols = 0
    def GetBoxBounds(gridsize)
        if (@@boxcols > 0)
            [gridsize/@@boxcols, @@boxcols]
        else
            case gridsize
                when 1 then [1,1]
                when 2 then [1,2]
                when 4 then [2,2]
                when 6 then [2,3]
                when 8 then [2,4]
                when 9 then [3,3]
                when 10 then [2,5]
                when 12 then [3,4]
                when 14 then [2,7]
                when 15 then [3,5]
                when 16 then [4,4]
                else
                    print "GridSize of #{gridsize} unsupported. Exiting\n"
                    [0,0]
                end
        end
    end
    
# a Cell represents a square on the grid.
# it keeps track of all possible values it could have.
# it knows its grid location for convenience
class Cell
    attr_reader :row, :col, :box, :possible
    def initialize(row, col, val=-1, max = 9)
        @row = row
        @col = col
        bounds = GetBoxBounds(max)
        @box = col/(bounds[0])+((row/bounds[1])*bounds[1])
        @processed = false
        if (val.is_a?(Array))
                @possible = val.dup
                #if you don't dup here, you get big trouble
                 # when undoing guesses
        elsif ((1..max) === val)
            @possible = [val]
        else
            @possible = (1..max).to_a
        end
    end

    def includes?(n)
        @possible.include?(n)
    end

    def mark
        @processed = true
    end
    
    def set(toValue)
        @possible = [toValue] if found = @possible.include?(toValue)
        found
    end
    
    def hasFinalValue
        return @possible[0] if (@possible.length == 1)
    end
    
    def eliminate(n)
        raise BadGuessException if (@possible.length == 0)
        @possible.delete(n)
        hasFinalValue && !@processed
    end
    
    def override(a)
        @possible = a.dup
        @processed = false
    end
    
    def to_s
        if $DEBUG
            s = @possible.to_s;
            s.length.upto(9) do s << " " end
            "["+s+"]"
        else
            (v = hasFinalValue)?" "+v.to_s(32):" _"
        end
    end
    def >(other)
        return (@row > other.row || (@row == other.row && @col > other.col))
    end
end

class Guess
    def initialize(cell )
        @row,@col = cell.row,cell.col
        @store = cell.possible.clone
        @index = 0
    end
    def value
        @store[@index]
    end
    def remove(cellset)
        cell=cellset[@row][@col]
        cell.eliminate(value)
        cell
    end
    def to_s
        "Guess [#{@row},#{@col}] to be #{@store[@index]} from [#{@store}] "
    end
end
    
class Solver
    def initialize(boardlist, size, presolved = false, lev=0)
        @level = lev+1
        @size = size
        become(boardlist, presolved)
    end
    #helper for init and cloning
    def become(boardlist, presolved = true)
        @boxes =
        @rows =
        @cols =
        @queue = #a list of cells to check for solutions.
        @size.times{ |n| @boxes[n] = ; @rows[n]=; @cols[n]= }
        r=c=0
        boardlist.each do |v|
            cell = Cell.new(r,c,v, @size)
            @boxes[cell.box] <<@rows[r][c] = @cols[c][r] = cell
            @queue << cell
            cell.mark if (presolved && cell.hasFinalValue)
            c+=1
            if (c==@size) then c=0; r=r+=1 end
        end
    end

    def unsolved
        @size.times do |n|
            @boxes[n].each {|c| return c if !c.hasFinalValue}
        end
        nil
    end

    def solve
        while @queue.size > 0
            while (cell = @queue.pop)
                eliminateChoices(cell)
            end
            checkForKnownValues()
        end
        dprint "Solved to...\n#{self}"
        return unsolved ? startGuessing : true
    end
    
    #for any resolved cell, eliminate its value from the possible values
     #of the other cells in the set
    def eliminateChoices(cell)
      if (value = cell.hasFinalValue)
            cell.mark
            [@boxes[cell.box],@rows[cell.row],@cols[cell.col]].each do |set|
                eliminateChoiceFromSet(set, cell, value)
            end
        end
    end
    
    def eliminateChoiceFromSet(g, exceptCell, n)
        g.each {|cell| eliminateValueFromCell(n,cell) if cell != exceptCell }
    end
    
    def eliminateValueFromCell(value, cell)
        @queue << cell if cell.eliminate(value) && !@queue.include?(cell)
    end
    
    def checkForKnownValues()
        @size.times do |n|
            [@rows[n],@cols[n],@boxes[n]].each do |set|
                findPairs(set)
                findUniqueChoices(set)
            end
        end
    end

    def findUniqueChoices(set)
        1.upto(@size) do |n| #check for every possible value
            lastCell = nil
            set.each do |c| #in every cell in the set
                if (c.includes?(n))
                    if (c.hasFinalValue || lastCell)
                        #found a 2nd instance, no good
                        lastCell = nil
                        break
                    end
                    lastCell = c;
                end
            end
            #if true, there is only one cell in the set with that value,
            #so let it be the answer
            if (lastCell && !lastCell.hasFinalValue)
                lastCell.set(n)
                @queue << lastCell
            end
        end
    end

    #find any pair of cells in a set with the same 2 possibilities
    # - these two can be removed from any other cell in the same set
    def findPairs(set)
        0.upto(@size-1) do |n|
            (n+1).upto(@size-1) do |m|
                if (set[n].possible.size == 2 && set[n].possible ==
set[m].possible)
                    eliminateExcept(set, [m,n], set[n].possible)
                end
            end
        end
    end

    #for every cell in a set except those in the skiplist, eliminate the values
    def eliminateExcept(set, skipList, values)
        @size.times do |n|
            if (!skipList.include?(n))
                values.each {|v| eliminateValueFromCell(v, set[n])}
            end
        end
    end
    
    def startGuessing
        print "Only Solveable by Guessing\n" if @level == 1
        while (c = unsolved)
                myclone = Solver.new(boardlist,@size, true,@level)
                myguess = myclone.guess
                return false if !myguess
                dprint myclone
            begin
                if (myclone.solve)
                    become(myclone.boardlist)
                    return true
                else
                    return false
                end
            rescue BadGuessException
                #this is the big speedup - remove the bad guess
                #from the possibilities, and re-solve
                @queue << myguess.remove(@rows)
                dprint "#{@level} Bad Guess\n #{self}"
                return solve
            end
        end
    end
    
    def guess
        2.upto(@size) do |mincount|
            @rows.each do |row|
                row.each do |cell|
                    if cell.possible.size == mincount
                        g = Guess.new(cell)
                        cell.set(g.value)
                        @queue << cell
                        return g
                    end
                end
            end
        end
        dprint "did not find a guess\n"
        return nil
    end

    #formating (vertical line every cbreak)
    def showBorder(cbreak)
        s = "+"
        1.upto(@size) do |n|
            s << "--"
            s<< "-+" if ((n)%cbreak == 0)
        end
        s <<"\n"
    end
        
    def to_s
        r=c=0
        cbreak,rbreak = GetBoxBounds(@size)
        s = showBorder(cbreak)
        @rows.each do |row|
            #r+=1
            s << "|"
            row.each do |cell|
                c+=1
                s << cell.to_s
                if (c==cbreak) then s << " |";c=0; end
            end
            s<<"\n"
            if (r+=1)==rbreak then s << showBorder(cbreak); r=0; end
        end
        s<<"\n"
        s
    end

    def boardlist
        a =
        @rows.each do |row|
            row.each do |cell|
                v = cell.hasFinalValue
                a<< ( v ? v : cell.possible )
            end
        end
        a
    end
    
end

#parses text file containing board. The only significant characters
are _, 0-9, A-Z.
# if bounded by +---+---+---+, uses the + char to determine the layout
of the boxes
#there must be an equal number of significant chars in each line, and
the same number of rows.
def ParseBoard(file)
    row = 0
    col = 0
    boxes = 0
    boardlist =
    file.each do |line|
        line.chomp.each_byte do |c|
            case c
                when ?0..?9
                    boardlist << c.to_i - ?0
                    col+=1
                when ?A..?Z
                    boardlist << c.to_i - ?A + 10
                    col+=1
                when ?a..?z
                    boardlist << c.to_i - ?a + 10
                    col+=1
                when ?_
                    boardlist << -1
                    col+=1
                when ?+
                     boxes+=1 if row == 0
            end
        end
        if (col > 0) then
            row+=1
            break if (row == col)
        end
        col=0
    end
    @@boxcols = boxes-1
    return boardlist,row
end

if __FILE__ == $0
    boardlist, size = ParseBoard(ARGF)
    sol = Solver.new(boardlist, size)

    print sol
    begin
        print "UNSOLVABLE\n" if (!sol.solve())
    rescue BadGuessException
        print "Malformed Puzzle\n"
    end
    print sol
end
    
--Adam

···

On 8/23/05, Simon Kröger <SimonKroeger@gmx.de> wrote:

My solution is 347 lines; I'll attach it below because I hate your mail gateway. :slight_smile:

You can view my complete solution on the web, however. My code, unit tests, and board data are at http://www.xmission.com/~dbrady/ruby/sodoku/sodoku.tgz . All of the files in that archive are also at that url, so you can grab any of the files directly by replacing sodoku.tgz with any of: sodoku.rb, test_sodoku.rb, dbrady_solutions.txt, board1.txt, board2.txt, board3.txt, board4.txt, board5.txt, board6.txt.

My strategy was to build an array of the possible moves for every row, every column and every 3x3 block, then take their intersection. I believe some other authors have already posted this concept; I'm only posting because I appear to be the only person to do it using array subtraction. :slight_smile: I find the intersection that has the fewest options available to it, and iterate over those choices, using recursion to solve the rest of the board. Using a set probably would have been better, but I didn't know about Ruby sets until after I finished my code. So my solution is a very elegant way of wielding a stone axe. :slight_smile:

My poor, unaccelerated laptop clocks in under 2s in most cases, and rejects Karl von Lauderman's unsolvable puzzle in 200ms. The really difficult one takes 33-38 seconds, depending on whether my mp3 player is going. :slight_smile:

One developmental note. Ruby continues to be an exceedingly pleasant language to work and design in. I wrote a complete solver with loads of unit tests, and I was pleased to discover that it could even solve Karl's unsolvable puzzle. Nifty! As I was double-checking everything, I realized that I had completely overlooked the requirement to have all the cells in a *block* be unique! (I have never heard of Sodoku before today.) I thought about it for a moment, then realized that all I needed to do was add Sodoku#possible_block_values to the class, and make sure that possible_values intersected that with the results from the row/column query. I plugged in the extra code, and discovered that my code became *faster* on account of rejecting more possibilities sooner.

I added another board, that seemed interesting to me to solve:

sodoku.rb (10 KB)

···

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

_ _ _ | _ _ _ | _ _ _ |

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

_ _ _ | _ _ _ | _ _ _ |

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

_ _ _ | _ _ _ | _ _ _ |

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

Also notably absent in my code is any kind of a custom Exception for bad boards. They're not idiomatic for me so I used them very sparingly.

Anyway, without further ado, my solution is attached.

Cheers,

-dB
--
David Brady
ruby_talk@shinybit.com
I'm feeling really surreal today... OR AM I?

I should be doing real work, but.....

I found a big speedup for the worst cases. I was looking at the debug
output for puzzle 50.

···

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

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

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

_ 9 _ | _ _ _ | _ _ 7 |
_ _ _ | 3 _ _ | 4 _ 5 |
_ _ 6 | 7 _ _ | _ _ _ |

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

_ _ 1 | _ _ _ | _ _ _ |
2 _ _ | _ 7 4 | _ _ _ |
_ _ _ | 2 _ _ | 3 _ _ |

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

I noticed that it spent a lot of time making wrong guesses and only
filling in the upper left corner.
So I made the guesser start with the center box instead. It went from
104 guesses to 36.

before:
$> for i in *.sdk; do time ruby SodukuSolver.rb $i ; done >btime 2>&1
$> ruby parsetime.rb btime
min max total ave
0.032 2.604 14.299 0.259

after:
min max total ave
0.031 0.938 12.667 0.230

And it was a simple change:
in Cell.initialize, replace
        @box = col/(bounds[0])+((row/bounds[1])*bounds[1])
with
        @box = (col/(bounds[0])+((row/bounds[1])*bounds[1])+max/2)%max
to make the box in the center have 0 index.

and replace the function Solver.guess so that it iterates over the
boxes instead of the rows:
    def guess
    2.upto(@size) do |min|
      @boxes.each do |set|
        set.each do |cell|
          if cell.possible.size == min
            g = Guess.new(cell)
            cell.set(g.value)
            @queue << cell
            dprint g
            return g
          end
        end
      end
    end
    dprint "did not find a guess\n"
        return nil
    end

Ok, I'm done now.
-Adam

How about just:
numbers = str.scan( /[\d_]/ ).collect{ |char| char.to_i }
and then check to see if you got 81 numbers or not (and split them up into chunks of nine if you so desire).

If nothing else, how about:
line.gsub!( /[+| -]/, '' )

···

On Aug 23, 2005, at 8:49 PM, David Brady wrote:

  # Loads the @board array from a string matching the example above.
  def load(str)
    line_num = 0
    str.each_line do |line|
      line.gsub! '+', ''
      line.gsub! '-', ''
      line.gsub! '|', ''
      line.gsub! ' ', ' '
      line.gsub! '_', '0'
      line.strip!
      if line.length > 0
        l = line.split
        fail "Line length was #{l.length}" unless l.length == 9
        @board[line_num] = l.collect {|x| x.to_i}
        line_num += 1
      end
    end

    fail "Board is not valid." unless self.valid?
  end

My strategy was to build an array of the possible moves for every row,
every column and every 3x3 block, then take their intersection. I
believe some other authors have already posted this concept; I'm only
posting because I appear to be the only person to do it using array
subtraction. :slight_smile: I find the intersection that has the fewest options
available to it, and iterate over those choices, using recursion to
solve the rest of the board.

Ahem... Mine used array subtraction too. Sorry.

--- SNIP (class Options) ----

  def calculate_options_at( row, col )
    (
      [1, 2, 3, 4, 5, 6, 7, 8, 9] -
      board.row( row ) -
      board.col( col ) -
      board.region(
        board.get_region_num( row, col )
      )
    )
  end

--- SNIP -----

I actually worked on this before the Sudoku challenge even came up. I
think, based on your e-mail, it uses the same recursive algorithm that
you do, but I haven't verified that yet.

Also, there's less idiomatic Ruby here than there could / should be.
After re-reading this code I realize that some of these methods can be
reduced to one-liners.

Here it is (Download at http://muthanna.com/ruby-sudoku.tar.gz\).

#!/usr/bin/env ruby

=begin rdoc
The Ruby Sudoku Solver

Mohit Muthanna Cheppudira <mohit@muthanna.com>

Sudoku, Japanese, sometimes spelled Su Doku,
is a placement puzzle, also known as Number Place in the
United States. The aim of the puzzle is to enter a numeral
from 1 through 9 in each cell of a grid, most frequently a
9×9 grid made up of 3×3 subgrids (called "regions"), starting
with various numerals given in some cells (the "givens"). Each
row, column and region must contain only one instance of each
numeral.

To Learn more about Sudoku, visit the great Wikipedia.

This implementation of the Sudoku solver uses an educated brute
force approach. By educated brute-force, I mean the solver:

* Narrows down options available in the empty places
* Fills in cells that have only one option
* For cells that have more than one option:
  * Try each one, then recurse (Narrow down, fill-in, etc.).

This file consists of five classes:

* Line: Represents a set of 9 cells. This could be a Row, a
Column, or a Region.

* Options: Represents a set of valid options for a cell. This is
meant to be used as a workspace or scratch-pad for the Solver.

* Board: Represents the 9x9 Sudoku board. Has helper methods
to access cells, rows, columns and regions.

* Csv: Utility class used to load boards from CSV files.

* Solver: Our educated brute-force solver.
=end

module Sudoku

=begin rdoc

A Sudoku Line is basically an array that is
1-indexed. A Line could be a complete row, column or region.

=end

class Line < Array

=begin rdoc
This class variable represents the set of digits that
are valid in a Sudoku cell.
=end

  @@valid_digits = [1, 2, 3, 4, 5, 6, 7, 8, 9]

=begin rdoc
We overload the operator so that the cells are
indexed from 1 till 9, instead of 0 till 8.
=end

  def ( num )
    at( num - 1 )
  end

=begin rdoc
The to_s method is called by other methods that
need a string representation of the class. E.g., puts()

In this case, the code:

   line = Line.new << 0 << 1 << 4 << 5
   puts line
  
Displays:
  
  0, 1, 4, 5
=end

  def to_s
    self.join( ", " )
  end

=begin
This method returns a list of missing digits
in the line.
=end

  def missing_digits
    return @@valid_digits - self
  end

=begin
Check if the Line or Region is
valid, i.e., has unique digits between
1 and 9, and has no zeros.

This method is used by the Solver to determine
if the solution is correct.
=end

  def valid?
    digits = Array.new

    # Navigate each cell:
    (1..9).each do |value|

      # Invalid if any zeros.
      return false if self[value] == 0

      # Invalid if duplicate.
      if digits[self[value]] == true
        return false
      else
        # First occurrence. Log it.
        digits[self[value]] = true
      end
    end

    # Valid Line.
    return true
  end
end

=begin rdoc
This class defines a basic 9 x 9 Sudoku
board. The board is subdivided into smaller
3 x 3 regions. These regions are numbered
from 1 to 9 as so: Top to Bottom, Left to Right.

e.g., Top Left is Region 1
      The region beneath 1 (row 4, col 1) is 2
      Top Middle is Region 4.

      You get the picture.
=end

class Board
  def initialize( board = nil )
    if board == nil
      reset
    else
      # Our copy constructor. In ruby all variables are
      # references to classes. Copies have to be
      # explicit.
      reset
      board.each {|row, col, val| self[row,col] = val}
    end
  end

=begin rdoc
Our board is represented by a two-dimensional 9x9 array.
=end

  def reset
    @board = Array.new( 9 ) { Array.new( 9, 0 ) }
  end

=begin rdoc
Cells in this board can be referenced with this method. Uses row, col; not x, y.
A bit retarded, but works.
=end

  def ( row, col )
    return @board[col-1][row-1]
  end

  def =( row, col, val )
    return (@board[col-1][row-1] = val)
  end

=begin
Draw up a simple ASCII Sudoku board.
=end

  def to_s
    string = " 1 2 3 4 5 6 7 8 9\n"
    string += " +--------------------------\n"
    filled_in = 0

    (1..9).each do |r|
      row( r ).each { |cell| filled_in += 1 unless cell == 0 }
      string += r.to_s + " | " + row( r ).to_s + "\n"
    end

    return string + "Filled: #{filled_in} / 81\n"
  end

  def row( row_num )
    r = Line.new
    (1..9).each { |c| r << self[ row_num, c ] }

    return r
  end

  def col( col_num )
    return Line.new( @board[ col_num - 1] )
  end

=begin
Return a region (class Line) of cells determined
by a region number. The regions are numbered incrementally
top to bottom, left to right. So the cell at row 2, column
2 is at region 1; 5, 5 is region 5; 7, 4 is region 8.
=end
  def region( region_num )
    region = Line.new

    start_row = ((( (region_num - 1) % 3 )) * 3) + 1
    start_col = (((region_num - 1) / 3) * 3) + 1

    (start_row..start_row + 2).each do |row|
      (start_col..start_col + 2).each do |col|
        region << self[row, col]
      end
    end

    return region
  end

=begin
Return a region number given a row and column.
=end
  def get_region_num( row, col )
    region_row = ( (row - 1) / 3 ) + 1
    region_col = ( (col - 1) / 3 ) + 1

    region_num = region_row + ( 3 * (region_col - 1))
  end

=begin
Used to iterate through each cell on the board.
=end
  def each
    (1..9).each do |row|
      (1..9).each do |col|
        yield row, col, self[row, col]
      end
    end
  end

=begin rdoc
Go through each row, column and region to
determine if the board is valid.
=end

  def valid?
    (1..9).each do |line|
      return false if (
        !row( line ).valid? ||
        !col( line ).valid? ||
        !region( line ).valid?
        )
    end

    return true
  end

end

=begin
This class loads a Sudoku board from a CSV file, A sample
board would look like this:

# Sample Board

0,0,0,0,2,3,4,0,0
0,6,3,0,9,8,0,0,0
4,0,0,5,0,0,0,0,0
0,2,5,0,8,0,0,7,3
0,1,0,0,0,0,0,5,0
6,4,0,0,5,0,1,9,0
0,0,0,0,0,5,0,0,8
0,0,0,9,7,0,3,6,0
0,0,6,8,3,0,0,0,0

Blank lines and lines beginning with hashes (#) are
ignored.

You can also save to CSV files by generating a
string via the to_s method.
=end

class Csv
  def initialize( board = nil )
    if board == nil
      @board = Board.new
    else
      @board = board
    end
  end

  def load( file_name )
    File.open( file_name, "r" ) do |file|
      row = 1

      while line = file.gets

        # Strip out all comments and
        # blank lines.
        line.chomp!
        next if line =~ /^\s*#/
        next if line =~ /^\s*$/

        col = 1
        line.split(",").each do |value|
          @board[row, col] = value.to_i
          col += 1
        end

        row += 1
      end
    end

    @board
  end

=begin rdoc
Generate a CSV string representing the board.
=end
  def to_s
    string = ""

    (1..9).each do |r|
      string += @board.row( r ).to_s + "\n"
    end

    return string
  end
end

=begin
This class is represents a set of options for Sudoku cells. It's
simply a three dimensional array.
=end

class Options
  def initialize
    @options = Array.new( 9 ) { Array.new( 9 ) { Array.new } }
  end

  def ( row, col )
    return @options[col-1][row-1]
  end
  
  def =( row, col, val )
    return (@options[col-1][row-1] = val)
  end

  def to_s
    string = ""

    (1..9).each do |row|
      (1..9).each do |col|
        string += self[row, col].join(",") + ":"
      end
      string += "\n"
    end

    string
  end
end

=begin
Our Edumicated Brute-Force Sudoku Solver.
=end

class Solver
  
  attr_accessor :board, :options

  def initialize( board=nil )
    if board
      @board = board
    else
      @board = Board.new
    end
    
    @options = Options.new
  end

=begin rdoc
This method returns a list of digits that are valid inside
a specific cell. It works by subtracting the set of cells
in the specific row, column and region from a full-line, i.e,
[1, 2, 3, 4, 5, 6, 7, 8, 9].
=end

  def calculate_options_at( row, col )
    (
      [1, 2, 3, 4, 5, 6, 7, 8, 9] -
      board.row( row ) -
      board.col( col ) -
      board.region(
        board.get_region_num( row, col )
      )
    )
  end

=begin rdoc
This method navigates through each cell in the board,
calculating a set of options for the cell. For cells
that have just one available option:

  * Set the cell with the available option.
  * Recalculate options.

If no options could be calculated, we hit a dead-end; return
false.
=end

  def calculate_options
    again = true
    have_options = false

    while again
      again = false
      self.options = Options.new

      # Navigate each cell...
      board.each do |row, col, value|

        # If the cell is empty...
        if value == 0
          
          # Set the options for the cell
          options[ row, col ] += calculate_options_at( row, col )
        end

        # How many options do we have?
        number_of_options = options[row, col].length

        # We had atleast one option; set return code.
        have_options = true if number_of_options > 0

        # Only one option here, reflect it on the
        # board.
        if number_of_options == 1
          board[row, col] = options[row, col][0]
          again = true
        end
      end
    end

    have_options
  end

=begin rdoc
Our solve algorithm.
=end
  def brute_force

    # First narrow the board down.
    calculate_options

    # Navigate each cell
    board.each do |row, col, value|

      # If we see and empty cell:
      if value == 0

        # Navigate each option
        options[row, col].each do |an_option|

          # Save the state of the board, this is
          # necessary because calculate_options()
          # mangles the board.
          old_board = Board.new( board )
           
          # Try this option
          board[row, col] = an_option

          # Recurse
          return true if brute_force
         
          # No solution. Revert to saved board
          # and try the next option.
          @board = old_board
        end

        break
      end

    end

    # Did we solve it?
    return true if board.valid?
    false
  end

  def solve
    brute_force
  end
end

=begin rdoc
Example code using this library. Reads a Sudoku-board file
from the command-line and solves it.
=end

def Sudoku.main
  puts "Ruby Sudoku Solver - 12 Aug 2005"
  puts "Mohit Muthanna Cheppudira <mohit@muthanna.com>"
  puts

  unless ARGV[0]
    puts "Usage: #{$0} filename"
    exit
  end

  # Load the board directly into the Solver.
  solver = Solver.new( Csv.new().load( ARGV[0] ))

  # Display the unsolved board.
  puts "Problem:"
  puts solver.board
  
  if solver.solve
    puts "\nSolution:"
  else
    puts "\nNo Solution. Best match:"
  end

  # Display the final board.
  puts solver.board
end

Sudoku.main

end

Or:
line.delete!("+-| ")

James Edward Gray II

···

On Aug 23, 2005, at 11:14 PM, Gavin Kistner wrote:

If nothing else, how about:
line.gsub!( /[+| -]/, '' )

Mohit Muthanna wrote:

Ahem... Mine used array subtraction too. Sorry.

Doh! I apologize for the oversight.

Well, at least I'm not the only stone-axe ninja here. :slight_smile:

I am doing these quizzes as much to learn Ruby as anything else... I especially like your use of rdoc. I need to pick that up next.

-dB

···

--
David Brady
ruby_talk@shinybit.com
I'm feeling really surreal today... OR AM I?

Mohit Muthanna wrote:

I actually worked on this before the Sudoku challenge even came up. I
think, based on your e-mail, it uses the same recursive algorithm that
you do, but I haven't verified that yet.

Our algorithms are essentially similar. One optimization I made is that instead of attempting to solve the first empty cell seen, I skim over all of the empty cells and find the one with the fewest possible solutions. The value of this optimization appears to be a wash; most boards I clock under your time by 20-50%, but on the "hard board" you clock a 20s against my "more efficient" 37s. Wild. Something about that puzzle forces any solver to grind deep and hard, and your not taking extra time to think about the next move pays off handsomely.

Your calculate_options method seems to do what my settle method does, finding unsolved cells with only one option. One question I had while reading your code, what happens if your loop finds a cell with options, then finds a cell to settle, and settling it causes the other cell to no longer have options (but to be settled)? have_options is never reset. The only valid case this can happen is if calculate_options solves the puzzle, so you could probably test for it outside the method.

Hmm, you don't use the return value, so I guess the point is moot. :slight_smile:

Also, I just noticed that the unit tests I uploaded yesterday were broken, because I renamed the settle() method. (It used to be called 'flatten', but that has some existing semantics from Array#flatten. Since they are not similar, I changed the name due to POLS.)

-dB
P.S. James, I made the changes to initialize; they are uploaded now. For the list's benefit, here is the new load method:

# ----------------------------------------------------------------------
  def load(str)
    line_num = 0
    str.each_line do |line|
      line.gsub!('_','0')
      line.delete!('+|-')
      line.strip!
      if line.length > 0
        l = line.split /\s+/
        fail "Line length was #{l.length}. line: #{line}" unless l.length == 9
        @board[line_num] = l.collect {|x| x.to_i}
        line_num += 1
      end
    end

    fail "Board is not valid." unless self.valid?
  end
# ----------------------------------------------------------------------

···

--
David Brady
ruby_talk@shinybit.com
I'm feeling really surreal today... OR AM I?

Oooh, I didn't know/forgot about that method. Nice :slight_smile:

···

On Aug 24, 2005, at 7:36 AM, James Edward Gray II wrote:

On Aug 23, 2005, at 11:14 PM, Gavin Kistner wrote:

If nothing else, how about:
line.gsub!( /[+| -]/, '' )

Or:
line.delete!("+-| ")