--Apple-Mail-3-725309915
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	charset=US-ASCII;
	format=flowed

Begin forwarded message:

> From: gdefty / attglobal.net
> Date: August 25, 2005 10:13:34 PM CDT
> To: james / grayproductions.net,
>
>
> James,
>
> My stab at a sudoku solver. A bit rough roung the
> edges (I have a job to do!) but it works.
>
> It seemed to me that basic algorithm and by
> association, data representation were the key
> factors here, and I was reasonably pleased with my
> choices (until I see some of the other solutions
> and realise what a dummy I was somewhere :-)
>
> Where I know I will be disappointed is in the
> ruby-ness of my code (or rather, lack of it :-(
> Mine always seems a bit pedestrian compared to
> some of the elegant stuff you show. Sigh. I guess
> I have been doing this too long. I'm probably
> writing a COBOL solution in Ruby! Still, learning
> is the whole point, no?
>
> Anyway, I hope you find something of interest in
> it, and thanks again for a great site.
>
> Regards,
>
> graeme
--Apple-Mail-3-725309915
Content-Transfer-Encoding: 7bit
Content-Type: application/octet-stream;
	x-unix-mode=0666;
	name="Sod.rb"
Content-Disposition: attachment;
	filename=Sod.rb

# A number of design decisions (and some alternatives)
# 1. Store 'available numbers' 
#    a) at the cell level and make them unavailable to 
#       other cells in the row/col/block when one was set
#    b) at the row/col/block level and check these items each 
#       time a I needed to select a new cell value
#     I chose a), as I figured that there would be more time spent
#     checking than setting and unsetting. I think (without proof)
#     that this was a good choice 
# 2. Store available numbers for a given cell as 
#   a) a hash of the available keys
#   b) an array of 9 'true' and 'false' values
#     I chose b), and I think it was probably not the best choice.
#     you can see from the code that I have to access this array
#     in different ways which I suspect would have been easier with a hash.
# 3. Encapsulating the structure of the source data format was a 
#   'spur-of-the-moment' refactoring decision which just seemed like a good
#   idea at the time, and turned out to be so when I had to override
#   the 'clone' method for Sods

# The basic class to hold the value in a single location in the puzzle
class SodCell
  attr_reader :val
  
# can be initialised with a value, but in the event I didn't use this  
  def initialize(val)
    @val = val.to_i
    if @val == 0
      @allowed = Array.new(10, true)
    else
      @allowed = Array.new(10, false)
      @allowed[@val] = true
    end
  end

# set the cell to a given value
  def set(x)
    @val = x
  end

# unset the cell back to empty
  def unset()
    rslt = @val
    @val = 0
    return rslt
  end

# is the cell is allowed to contain 'x'?
  def allowed(x)
    @allowed[x]
  end
  
# what values are allowed?
# This is mostly to determine *how many* values are allowed
# and is the reason I think a Hash would have been better
  def alloweds
    rslt = ''
    @allowed.each_with_index{|v, i|
      rslt += v ? i.to_s : ''
    }
    return rslt
  end
  
# add 'x' to the list of allowed values
  def allow(x)
    @allowed[x] = true
  end

# drop 'x' from the list of allowed values
  def deny(x)
    @allowed[x] = false
  end

# create a printable representation of the cell (for debugging)
def to_s
    rslt = val.to_s + ':'
    @allowed.each_with_index{|v, i|
      rslt += v ? i.to_s : '.'
    }
    return rslt
  end
end

# A wrapper class round the input data
# Only one method 'each' which unravels the values
# and returns them one at a time. 
# Allows some flexibility in the input format (its's a feature ;-)
class SodSrc
  def initialize(src)
  @src = src
  end
  def each
    rowsrc = @src.split("\n")
    rownum = 0
    rowsrc.each{ |r|
      colnum = 0
      if r =~ /\d|'_'/ then
        while r =~ /.*?([\d_])(.*)/
          yield(rownum, colnum, $1)
          colnum += 1
          r = $2
        end
        rownum += 1
      end
    }
  end
end

# The main class representing a puzzle
class Sod

# can be created from a string representing a position,
# or from another Sod.
  def initialize(srcdata)
    @cells = []
    99.times{|i|
      @cells << SodCell.new('')
    }
    if srcdata.class == String then
      srcdata = SodSrc.new(srcdata)
    end
    srcdata.each{|row, col, val|
      setcell(row, col, val.to_i)
    }
  end

# return the cell at a given location
  def cell(row, col)
    @cells[row*10+col]
  end

# yield all the cells in a row
  def each_in_row(row)
    for col in 0..8
      yield cell(row, col)
    end
  end

# yield all the cells in a column
  def each_in_col(col)
    for row in 0..8
      yield cell(row, col)
    end
  end

# yield all the cells in a 3x3 block
  def each_in_block(row, col)
  baserow = row/3*3
  basecol = col/3*3
    for row in baserow..(baserow+2)
      for col in basecol..(basecol+2)
        yield cell(row, col)
      end
    end
  end
  
# yield all the cells in the puzzle. A bit different from the 
# other 'each...' methods in that it returns the location and
# value of the cell, instead of the cell itself. This is needed
# to make it work in 'initialize' (when cloning) which is the
# only place it is used
  def each()
    for row in 0..8
      for col in 0..8
        yield(row, col, cell(row, col).val)
      end
    end
  end

# set a given cell to a value and adjust all others in the row, column
# and block to deny them the use of that value
  def setcell (row, col, val)
    cell(row, col).set(val)     # set the cell value
    each_in_row(row){|c|        # and deny that value to others in the row ...
      c.deny(val)
    }
    each_in_col(col){|c|        # ... and column ...
      c.deny(val)
    }
    each_in_block(row, col){|c| # ... and block
      c.deny(val)
    }
  end

# reset a given cell and adjust all others in the row, column and block to
# allow them the use of that cell's value
  def unsetcell (row, col)
    val = cell(row, col).unset()# unset the cell value
    each_in_row(row){|c|        # and allow that value to others in the row ...
      c.allow(val)
    }
    each_in_col(col){|c|        # ... and column ...
      c.allow(val)
    }
    each_in_block(row, col){|c| # ... and block
      c.allow(val)
    }
  end
  
# Create a 'deep copy' clone of myself
# Needed because Object#clone creates a 'shallow' copy
  def clone
    Sod.new(self)
  end
  
# Generate the printable format
  def to_s
    rowconst = '+-------+-------+-------+'
    rslt = [rowconst]
    for blockrow in 0..2
      for relrow in 0..2
        rowdat = '|'
        for blockcol in 0..2
          for relcol in 0..2
            rowdat += ' ' + cell(blockrow*3 + relrow, blockcol*3 + relcol).val.to_s
          end
          rowdat += ' |'
        end
        rslt << rowdat
      end
      rslt << rowconst
    end
    rslt = rslt.join("\n")
    rslt.gsub('0', '_')
  end

# Dump the puzzle contents (for debugging only)
  def dump
    for row in 0..8
      for col in 0..8
        if cell(row, col).val == 0 then
          puts "(#{row.to_s},#{col.to_s})=#{cell(row,col).to_s}"
        end
      end
    end
  end
  
end
--Apple-Mail-3-725309915
Content-Transfer-Encoding: 7bit
Content-Type: application/octet-stream;
	x-unix-mode=0666;
	name="Sod_test.rb"
Content-Disposition: attachment;
	filename=Sod_test.rb

require 'test/unit'
require 'Sod.rb'


class TC_Cell < Test::Unit::TestCase
	def setup
	end
  
	def test_setup
		c = SodCell.new('3')
		assert_equal(3, c.val)
		c = SodCell.new('_')
		assert_equal(0, c.val)
	end

	def test_set_unset
		c = SodCell.new('3')
		assert_equal(3, c.val)
		c.unset()
		assert_equal(0, c.val)
		c.set(7)
		assert_equal(7, c.val)
	end

  def test_allow_deny
    c = SodCell.new('5')
    assert_equal(true, c.allowed(5))
    assert_equal(false, c.allowed(3))
    c.allow(3)
    assert_equal(true, c.allowed(3))
    c.deny(3)
    assert_equal(false, c.allowed(3))

    c = SodCell.new('_')
    assert_equal(true, c.allowed(5))
    assert_equal(true, c.allowed(3))
  end
  
  def test_to_s
    c = SodCell.new('')
    assert_equal('0:0123456789', c.to_s)
    c.deny(3)
    c.deny(4)
    c.deny(9)
    assert_equal('0:012..5678.', c.to_s)
  end
end


class TC_SodSrc < Test::Unit::TestCase
	def test_setup
    @testdata = '+-------+-------+-------+
| _ 6 _ | 1 
8
----
| 2
----'
    src = SodSrc.new(@testdata)
    rslt = ''
    src.each{|row, col, val|
      rslt += '|' + row.to_s + ',' + col.to_s + ',' + val.to_s
    }
    assert_equal('|0,0,_|0,1,6|0,2,_|0,3,1|1,0,8|2,0,2', rslt)
  end

end


class TC_Sod < Test::Unit::TestCase
	def setup
    @testdata = '+-------+-------+-------+
| _ 6 _ | 1 _ 4 | _ 5 _ |
| _ _ 8 | 3 _ 5 | 6 _ _ |
| 2 _ _ | _ _ _ | _ _ 1 |
+-------+-------+-------+
| 8 _ _ | 4 _ 7 | _ _ 6 |
| _ _ 6 | _ _ _ | 3 _ _ |
| 7 _ _ | 9 _ 1 | _ _ 4 |
+-------+-------+-------+
| 5 _ _ | _ _ _ | _ _ 2 |
| _ _ 7 | 2 _ 6 | 9 _ _ |
| _ 4 _ | 5 _ 8 | _ 7 _ |
+-------+-------+-------+'
	end
  
	def test_setup
		sod = Sod.new(@testdata)
		assert_equal(6, sod.cell(0,1).val)
		assert_equal(2, sod.cell(2,0).val)
		assert_equal(7, sod.cell(8,7).val)
		assert_equal(@testdata, sod.to_s)   # test to_s
    assert_equal('1:..23......', sod.cell(5,5).to_s)  # test cell 'allowed's
    assert_equal('23',           sod.cell(5,5).alloweds)  
    assert_equal('0:...34...89', sod.cell(2,7).to_s)
#    sod.dump
	end
  
	def test_each_in_row
		sod = Sod.new(@testdata)
    rslt = ''
		sod.each_in_row(3){|c|
      rslt += c.val.to_s
    }
    assert_equal('800407006', rslt)
	end
  
	def test_each_in_col
		sod = Sod.new(@testdata)
    rslt = ''
		sod.each_in_col(2){|c|
      rslt += c.val.to_s
    }
    assert_equal('080060070', rslt)
	end
  
	def test_each_in_block
		sod = Sod.new(@testdata)
    rslt = ''
		sod.each_in_block(7,1){|c|
      rslt += c.val.to_s
    }
    assert_equal('500007040', rslt)
	end
  
  def test_set_unset
    sod = Sod.new(@testdata)
    sod.setcell(2, 6, 7)
    assert_equal(7, sod.cell(2, 6).val)
    assert_equal(false, sod.cell(2, 5).allowed(7)) # check the row deny
    assert_equal(false, sod.cell(5, 6).allowed(7)) # and the col deny
    assert_equal(false, sod.cell(1, 7).allowed(7)) # and the block deny   

    sod.unsetcell(2, 6)
    assert_equal(0, sod.cell(2, 6).val)
    assert_equal(true, sod.cell(2, 5).allowed(7)) # check the row allow
    assert_equal(true, sod.cell(5, 6).allowed(7)) # and the col allow
    assert_equal(true, sod.cell(1, 7).allowed(7)) # and the block allow   
  end
  
end


--Apple-Mail-3-725309915
Content-Transfer-Encoding: 7bit
Content-Type: application/octet-stream;
	x-unix-mode=0666;
	name="Sodoku.rb"
Content-Disposition: attachment;
	filename=Sodoku.rb

require 'Sod.rb'

# The main solver of puzzles. The algorithm is straightforward
# 1.  Cycle through the grid looking for cells that can only take 
#     one value, and set them to that value. 
# 2.  This will restrict the values of other cells, so keep cycling thru
#     until all cells either are fixed or can take more than one value.
# 3.  (While this cycling is going on, also look for the cell which is unset
#     and also has the smallest list of possible values.)
# 4.  If there is NO smallest, all cells must already be set. That means
#     we have found a solution, so print it.
# 5.  Otherwise, cycle through the list of values that the chosen smallest
#     cell can take and for each one, 
#       - create a clone of the puzzle as it currently stands, 
#       - set the value of the cell to that value and 
#       - call 'solve' again recursively, passing it the clone.

# 6.  If more than one solution exists, this will find them all
# 7.  If no solution exists, none will be printed ;-)
# 8.  If the original puzzle was ill-formed, results are unpredictable.

def solve(sod)
  puts "\n\nSolver called to solve :\n#{sod.to_s}" if $VERBOSE

# set all the cells that can be determined from the initial conditions
  begin
    fixed = 0
    smallestval = 99
    smallest = []
    for row in 0..8
      for col in 0..8
        c = sod.cell(row, col)
        if c.val == 0
        if c.alloweds.size < smallestval.size
          smallest = [row,col]
          smallestval = c.alloweds
        end
          if c.alloweds.size == 1
            sod.setcell(row,col,c.alloweds.to_i)
            puts "(#{row},#{col}) set to #{c.val}" if $VERBOSE
            fixed += 1
          end
        end
      end
    end
    puts "#{fixed} were fixed" if $VERBOSE
  end while fixed > 0
  
  puts "\nSolver bottomed out at:\n#{sod.to_s}" if $VERBOSE
  puts "Smallest found was (#{smallest[0]},#{smallest[1]}) = #{smallestval}" if $VERBOSE

# If we got a solution, print it out
  if smallest == []
    puts "===> FOUND A SOLUTION !!"
    puts sod.to_s
    
# and if not, set a small-options cell to each of its options in turn (in a clone)...    
  else
    sod.cell(smallest[0], smallest[1]).alloweds.each_byte{|v|
      tempsod = sod.clone
      tempsod.setcell(smallest[0], smallest[1], v.chr.to_i)
# ... and call ourselves recursively to solve the clone      
      solve(tempsod)
    }
  end
end

#================== Main Program ====================

@testdata = <<HERE
'+-------+-------+-------+
| _ 6 _  | 1 _ 4  | _ 5 _ |
| _ _ 8  | 3 _ 5  | 6 _ _ |
| 2 _ _  | _ _ _  | _ _ 1 |
+-------+-------+-------+
| 8 _ _  | 4 _ 7  | _ _ 6 |
| _ _ 6  | _ _ _  | 3 _ _ |
| 7 _ _  | 9 _ 1  | _ _ 4 |
+-------+-------+-------+
| 5 _ _  | _ _ _  | _ _ 2 |
| _ _ 7  | 2 _ 6  | 9 _ _ |
| _ 4 _  | 5 _ 8  | _ 7 _ |
+-------+-------+-------+'
HERE
  
sod = Sod.new(@testdata)
puts "Solving... \n#{sod.to_s} \n"

solve sod

puts 'Press <ENTER> to continue...'
gets

--Apple-Mail-3-725309915
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	charset=US-ASCII;
	format=flowed



--Apple-Mail-3-725309915--