[QUIZ] Sodoku Solver (#43)

ruby-talk
1

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

···

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Sodokus are simple number puzzles that often appear in various sources of print.
The puzzle you are given is a 9 x 9 grid of numbers and blanks, that might look
something like this:

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

The task is to fill in the remaining digits (1 through 9 only) such that each
row, column, and 3 x 3 box contains exactly one of each digit. Here's the
solution for the above puzzle:

  +-------+-------+-------+
  > 9 6 3 | 1 7 4 | 2 5 8 |
  > 1 7 8 | 3 2 5 | 6 4 9 |
  > 2 5 4 | 6 8 9 | 7 3 1 |
  +-------+-------+-------+
  > 8 2 1 | 4 3 7 | 5 9 6 |
  > 4 9 6 | 8 5 2 | 3 1 7 |
  > 7 3 5 | 9 6 1 | 8 2 4 |
  +-------+-------+-------+
  > 5 8 9 | 7 1 3 | 4 6 2 |
  > 3 1 7 | 2 4 6 | 9 8 5 |
  > 6 4 2 | 5 9 8 | 1 7 3 |
  +-------+-------+-------+

This week's Ruby Quiz is to write a solver that takes the puzzle on STDIN and
prints the solution to STDOUT.

2

In article
<20050819130127.ELYX12628.eastrmmtao02.cox.net@localhost.localdomain>,

Sodokus are simple number puzzles that often appear in various sources of
print.

<snip>

This week's Ruby Quiz is to write a solver that takes the puzzle on STDIN and
prints the solution to STDOUT.

Heh. I already wrote a Sudoku solver back in May; all I have to do is
change the input/output format a bit to match the quiz example. In the
meantime, here's a harder puzzle to test your programs with:

···

Ruby Quiz <james@grayproductions.net> wrote:

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

_ _ 2 | _ _ 5 | _ 7 9 |
1 _ 5 | _ _ 3 | _ _ _ |
_ _ _ | _ _ _ | 6 _ _ |

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

_ 1 _ | 4 _ _ | 9 _ _ |
_ 9 _ | _ _ _ | _ 8 _ |
_ _ 4 | _ _ 9 | _ 1 _ |

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

_ _ 9 | _ _ _ | _ _ _ |
_ _ _ | 1 _ _ | 3 _ 6 |
6 8 _ | 3 _ _ | 4 _ _ |

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

--
Karl von Laudermann - karlvonl(a)rcn.com - Yahoo | Mail, Weather, Search, Politics, News, Finance, Sports & Videos
#!/usr/bin/env ruby
require "complex";w=39;m=2.0;w.times{|y|w.times{|x|c=Complex.new((m*x/w)-1.5,
(2.0*y/w)-1.0);z=c;e=false;49.times{z=z*z+c;if z.abs>m then e=true;break;end}
print(e ?" ":"@@");puts if x==w-1;}}

3

I figured that participating in the ruby quiz would be a good way to
learn ruby. Here are my results followin what was done by vance.

···

for i in *.txt; do time ./sudoku.rb < $i; done

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

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

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

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

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

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

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

real 0m0.041s
user 0m0.013s
sys 0m0.007s
+-------+-------+-------+

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

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

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

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

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

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

real 0m0.062s
user 0m0.048s
sys 0m0.003s
+-------+-------+-------+

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

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

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

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

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

+-------+-------+-------+
I can't solve this one

real 0m0.031s
user 0m0.012s
sys 0m0.006s
+-------+-------+-------+

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

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

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

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

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

+-------+-------+-------+
I can't solve this one

real 0m0.029s
user 0m0.014s
sys 0m0.005s

Should I post my code now or later? It still has a lot of kinks to work
out, but it seems to work pretty well. I'll be back later today to post
it. Thanks!!

-----Horndude77

4

Ok, I'm pretty sure that it's been over 48 hours, so here's my solution,
sudoku_solve.rb:

#!/usr/bin/env ruby

···

#
# =Description
#
# Solves a Su Doku puzzle. Prints the solution to stdout.
#
# =Usage
#
# sudoku_solve.rb <puzzle.txt>
#
# puzzle.txt is a text file containing a sudoku puzzle in the following format:
#
# +-------+-------+-------+
# | _ _ 2 | _ _ 5 | _ 7 9 |
# | 1 _ 5 | _ _ 3 | _ _ _ |
# | _ _ _ | _ _ _ | 6 _ _ |
# +-------+-------+-------+
# | _ 1 _ | 4 _ _ | 9 _ _ |
# | _ 9 _ | _ _ _ | _ 8 _ |
# | _ _ 4 | _ _ 9 | _ 1 _ |
# +-------+-------+-------+
# | _ _ 9 | _ _ _ | _ _ _ |
# | _ _ _ | 1 _ _ | 3 _ 6 |
# | 6 8 _ | 3 _ _ | 4 _ _ |
# +-------+-------+-------+
#
# Characters '-', '+', '|', and whitespace are ignored, and thus optional. The
# file just has to have 81 characters that are either numbers or other
# printables besides the above mentioned. Any non-numeric character is
# considered a blank (unsolved) grid entry.
#
# The puzzle can also be passed in via stdin, e.g.:
# cat puzzle.txt | sudoku_solve.rb

require 'rdoc/usage'

#==============================================================================
# ----- Classes -----
#==============================================================================

class UnsolvableException < Exception
end

# Represents one grid space. Holds known value or list of candidate values.
class Space
    def initialize(num = nil)
        @value = num
        @cands = num ? [] : [1, 2, 3, 4, 5, 6, 7, 8, 9]
    end

    def value() @value end
    def value=(val) @value = val; @cands.clear end
    def remove_cand(val) @cands.delete(val) end
    def cand_size() @cands.size end
    def first_cand() @cands[0] end
end

# Represents puzzle grid. Grid has 81 spaces, composing 9 rows, 9 columns, and
# 9 "squares":
#
# Colums
# Spaces 012 345 678
#
# 0 1 2| 3 4 5| 6 7 8 0 | |
# 9 10 11|12 13 14|15 16 17 1 0 | 1 | 2 <- Squares
# 18 19 20|21 22 23|24 25 26 2 | | |
# --------+--------+-------- R ---+---+--- |
# 27 28 29|30 31 32|33 34 35 o 3 | | |
# 36 37 38|39 40 41|42 43 44 w 4 3 | 4 | 5 <----+
# 45 46 47|48 49 50|51 52 53 s 5 | | |
# --------+--------+-------- ---+---+--- |
# 54 55 56|57 58 59|60 61 62 6 | | |
# 63 64 65|66 67 68|69 70 71 7 6 | 7 | 8 <----+
# 72 73 74|75 76 77|78 79 80 8 | |
class Board
    # Stores which spaces compose each square
    @@squares = []
    @@squares[0] = [ 0, 1, 2, 9, 10, 11, 18, 19, 20].freeze
    @@squares[1] = [ 3, 4, 5, 12, 13, 14, 21, 22, 23].freeze
    @@squares[2] = [ 6, 7, 8, 15, 16, 17, 24, 25, 26].freeze
    @@squares[3] = [27, 28, 29, 36, 37, 38, 45, 46, 47].freeze
    @@squares[4] = [30, 31, 32, 39, 40, 41, 48, 49, 50].freeze
    @@squares[5] = [33, 34, 35, 42, 43, 44, 51, 52, 53].freeze
    @@squares[6] = [54, 55, 56, 63, 64, 65, 72, 73, 74].freeze
    @@squares[7] = [57, 58, 59, 66, 67, 68, 75, 76, 77].freeze
    @@squares[8] = [60, 61, 62, 69, 70, 71, 78, 79, 80].freeze
    @@squares.freeze

    # Takes a string containing the text of a valid puzzle file as described in
    # the Usage comment at the top of this file
    def initialize(grid = nil)
        @spaces = Array.new(81) { |n| Space.new }

        if grid
            count = 0
            chars = grid.split(//).delete_if { |c| c =~ /[\+\-\|\s]/ }

            chars.each do |c|
                set(count, c.to_i) if c =~ /\d/
                count += 1
                break if count == 81
            end
        end
    end

    def set(idx, val)
        @spaces[idx].value = val
        adjust_cands_from(idx)
    end

    # Remove indicated space's value from candidates of all spaces in its
    # row/col/square
    def adjust_cands_from(sidx)
        val = @spaces[sidx].value
        
        row_each(which_row(sidx)) do |didx|
            @spaces[didx].remove_cand(val)
        end
        
        col_each(which_col(sidx)) do |didx|
            @spaces[didx].remove_cand(val)
        end
        
        square_each(which_square(sidx)) do |didx|
            @spaces[didx].remove_cand(val)
        end
    end

    # Return number of row/col/square containing the given space index
    def which_row(idx) idx / 9 end
    def which_col(idx) idx % 9 end

    def which_square(idx)
        @@squares.each_with_index { |s, n| return n if s.include?(idx) }
    end
        
    # Yield each space index in the row/col/square indicated by number
    def row_each(row) ((row * 9)...((row + 1) * 9)).each { |n| yield(n) } end
    def col_each(col) 9.times { yield(col); col += 9 } end
    def square_each(squ) @@squares[squ].each { |n| yield(n) } end

    def solved?() @spaces.all? { |sp| sp.value } end

    # For each empty space that has only one candidate, set the space's value to
    # that candidate and update all related spaces. Repeat process until no
    # empty spaces with only one candidate remain
    def deduce_all
        did = true
        
        while did
            did = false
            
            @spaces.each_index do |idx|
                sp = @spaces[idx]

                raise UnsolvableException if ((!sp.value) && sp.cand_size == 0)
                if (sp.cand_size == 1)
                    sp.value = sp.first_cand
                    adjust_cands_from(idx)
                    did = true
                end
            end
        end
    end

    def to_s
        div = "+-------+-------+-------+\n"
        ret = "" << div
        
        @spaces.each_index do |idx|
            ret << "|" if (idx % 9 == 0)
            ret << " " + (@spaces[idx].value || '_').to_s
            ret << " |" if (idx % 3 == 2)
            ret << "\n" if (idx % 9 == 8)
            ret << div if ([26, 53, 80].include?(idx))
        end
        
        ret
    end

    def solve()
        # Solve
        deduce_all
        return if solved?
        
        # Find an unsolved space with the fewest candidate values and store its
        # index and first candidate
        min_count = nil
        test_idx = nil

        @spaces.each_with_index do |sp, n|
            if !sp.value
                if (!min_count) || (sp.cand_size < min_count)
                    test_idx, min_count = n, sp.cand_size
                end
            end
        end

        test_cand = @spaces[test_idx].first_cand
    
        # Solve clone of board in which the value of the space found above is
        # set to it's first candidate value
        str = ""
        
        @spaces.each_index do |idx|
            str << (idx == test_idx ? test_cand.to_s :
                (@spaces[idx].value || '_').to_s)
        end
        
        b_clone = Board.new(str)

        begin
            b_clone.solve
            initialize(b_clone.to_s) # Take state from clone
        rescue UnsolvableException
            @spaces[test_idx].remove_cand(test_cand)
            solve
        end
    end
end

#==============================================================================
# ----- Script start -----
#==============================================================================

b_str = ARGF.readlines().join()
board = Board.new(b_str)

begin
    board.solve()
    puts board.to_s
rescue UnsolvableException
    puts "This puzzle has no solution!"
end

--
Karl von Laudermann - karlvonl(a)rcn.com - http://www.geocities.com/~karlvonl
#!/usr/bin/env ruby
require "complex";w=39;m=2.0;w.times{|y|w.times{|x|c=Complex.new((m*x/w)-1.5,
(2.0*y/w)-1.0);z=c;e=false;49.times{z=z*z+c;if z.abs>m then e=true;break;end}
print(e ?" ":"@@");puts if x==w-1;}}

5

Hi,

here is my solution. The algorithm is well described by Horndude77,
but this implementation also features the brute force part to solve
them all. (which may need some more seconds)

This one is hardest for my algorithm (from the list i posted):

···

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

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

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

it took 18.6s to solve:
+-------+-------+-------+

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 |

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

here is the code:
----------------------------------------------------------------------
require 'Set'
require 'Benchmark'

class Board
   @@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)}}

   @@neighbourhoods = Array.new(81) {|i|
     [, @@row[i /9], @@col[i % 9], @@box[(i / 27) * 3 + (i % 9) / 3]]}

   attr_reader :cells, :possibilities

   def initialize cells
     @possibilities = Array.new(81) {(1..9).to_set}
     @cells = Array.new(81){0}
     81.times{|i|set_cell(i, cells[i]) if cells[i] != 0}
   end

   def set_cell c, v
     @@neighbourhoods[c].flatten.each{|i|
       possibilities[i]-=[v] unless c==i}
     @cells[c], @possibilities[c] = v, [v]
   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].nonzero? || "_"
           end.join(" ")
         end.join(" | ")
       end.join(" |\n| ")
     end.join(" |\n+-------+-------+-------+\n| ") +
     " |\n+-------+-------+-------+\n"
   end

   def solve_with_logic!
     count, changed = 0, 0
     begin
       next if @cells[i = count % 81] != 0
       p = possibilities[i]
       @@neighbourhoods[i].each do |neighbours|
         pn = neighbours.inject(p){|r, j|(j != i)?r-possibilities[j]:r}
         if pn.size == 1
           pn.each{|c| set_cell(i, c)}
           changed = count
           break
         end
       end
     end until ((count += 1) - changed) > 81
     self
   end

   def solve_with_logic
     Board.new(@cells).solve_with_logic!
   end

   def solve
     board = solve_with_logic
     return nil if (0..80).find{|i| board.possibilities[i].size == 0}
     return board unless board.cells.find{|c| c==0}

     #we have to guess
     (2..9).each do |c|
       81.times do |i|
         if (p = board.possibilities[i]).size == c
           p.each do |j|
             board.set_cell(i,j)
             b = board.solve
             return b if b
           end
           return nil
         end
       end
     end
   end

end

# main
count, $stdout.sync = 0, true
Benchmark.bm 20 do |bm|
   loop do
     cells =
     while cells.size < 81 do
       exit 0 if ARGF.eof
       ARGF.gets.scan(/[0-9_.]/).each{|c| cells << c.to_i}
     end
     board = Board.new(cells)
     bm.report "solving nr #{count+=1}" do
       board = board.solve
     end
     puts board.to_s + "\n\n"
   end
end
----------------------------------------------------------------------

cheers

Simon

6

Here is my solution.

It uses logic to deduce numbers for open cells which is enough for most easy and intermediate sudokus (this is quite fast, usually <100ms), but it can also guess and backtrack to solve the hard ones and those with multiple solutions.

The SudokuSolver class can solve sudokus for all valid square board sizes (1x1, 4x4, 9x9, 16x16, ...), but the "if $0 == __FILE__"-part only handles 9x9 puzzles.

Dominik

The code:

class SudokuSolver

     # sudoku is an array of arrays, containing the rows, which contain the
     # cells (all non valid entries are interpreted as open)
     def initialize(sudoku)
         # determine @n / @sqrt_n
         @n = sudoku.size
         @sqrt_n = Math.sqrt(@n).to_i
         raise "wrong sudoku size" unless @sqrt_n * @sqrt_n == @n

         # populate internal representation
         @arr = sudoku.collect { |row|
             # ensure correct width for all rows
             (0...@n).collect { |i|
                 # fixed cell or all values possible for open cell
                 ((1..@n) === row[i]) ? [row[i]] : (1..@n).to_a
             }
         }

         # initialize fix arrays
         # they will contain all fixed cells for all rows, cols and boxes
         @rfix=Array.new(@n) { [] }
         @cfix=Array.new(@n) { [] }
         @bfix=Array.new(@n) { [] }
         @n.times { |r| @n.times { |c| update_fix(r, c) } }

         # check for non-unique numbers
         [@rfix, @cfix, @bfix].each { |fix| fix.each { |x|
             unless x.size == x.uniq.size
                 raise "non-unique numbers in row, col or box"
             end
         } }
     end

     # returns the internal representation as array of arrays
     def to_a
         @arr.collect { |row| row.collect { |x|
             (x.size == 1) ? x[0] : nil
         } }
     end

     # returns a simple string representation
     def to_s
         fw = @n.to_s.size
         to_a.collect { |row| row.collect { |x|
             (x ? x.to_s : "_").rjust(fw)
         }.join " " }.join "\n"
     end

     # returns whether the puzzle is solved
     def finished?
         @arr.each { |row| row.each { |x| return false if x.size > 1 } }
         true
     end

     # for each cell remove the possibilities, that are already used in the
     # cell's row, col or box
     # return if successful
     def reduce
         success = false
         @n.times { |r| @n.times { |c|
             if (sz = @arr[r][c].size) > 1
                 @arr[r][c] = @arr[r][c] -
                     (@rfix[r] | @cfix[c] | @bfix[rc2box(r, c)])
                 raise "impossible to solve" if @arr[r][c].empty?
                 # have we been successful
                 if @arr[r][c].size < sz
                     success = true
                     update_fix(r, c)
                 end
             end
         } }
         success
     end

     # find open cells with unique elements in their row, col or box
     # return if successful
     # reduce must return false when this method is called (if the possibilities
     # aren't reduced, bad things may happen...)
     def deduce
         success = false
         [:col_each, :row_each, :box_each].each { |meth|
             @n.times { |i|
                 u = uniqs_in(meth, i)
                 unless u.empty?
                     send(meth, i) { |x|
                         if x.size > 1 && ((u2 = u & x).size == 1)
                             success = true
                             u2
                         else
                             nil
                         end
                     }
                     # change only one row/col/box at a time
                     return success if success
                 end
             }
         }
         success
     end

     # tries to solve the sudoku with reduce and deduce
     # returns one of :impossible, :solved, :unknown
     def solve
         begin
             until finished?
                 progress = false
                 while reduce
                     progress = true
                 end
                 progress = true if deduce
                 return :unknown unless progress
             end
             :solved
         rescue
             :impossible
         end
     end

     # solves the sudoku using solve and if that fails, it tries to guess
     # returns one of :impossible, :solved, :multiple_solutions
     def backtrack_solve
         if (res = solve) == :unknown
             # find first open cell
             r, c = 0, 0
             @rfix.each_with_index { |rf, r|
                 break if rf.size < @n
             }
             @arr[r].each_with_index { |x, c|
                 break if x.size > 1
             }
             partial = to_a
             solutions = []
             # try all possibilities for the open cell
             @arr[r][c].each { |guess|
                 partial[r][c] = guess
                 rsolver = SudokuSolver.new(partial)
                 case rsolver.backtrack_solve
                 when :multiple_solutions
                     initialize(rsolver.to_a)
                     return :multiple_solutions
                 when :solved
                     solutions << rsolver
                 end
             }
             if solutions.empty?
                 return :impossible
             else
                 initialize(solutions[0].to_a)
                 return solutions.size > 1 ? :multiple_solutions : :solved
             end
         end
         res
     end

     private

     # returns the box index of row r and col c
     def rc2box(r, c)
          (r - (r % @sqrt_n)) + (c / @sqrt_n)
     end

     # if row r, col c contains a fixed cell, it is added to the fixed arrays
     def update_fix(r, c)
         if @arr[r][c].size == 1
             @rfix[r] << @arr[r][c][0]
             @cfix[c] << @arr[r][c][0]
             @bfix[rc2box(r, c)] << @arr[r][c][0]
         end
     end

     # yields each cell of row r and assigns the result of the yield unless it
     # is nil
     def row_each(r)
         @n.times { |c|
             if (res = yield(@arr[r][c]))
                 @arr[r][c] = res
                 update_fix(r, c)
             end
         }
     end
     # yields each cell of col c and assigns the result of the yield unless it
     # is nil
     def col_each(c)
         @n.times { |r|
             if (res = yield(@arr[r][c]))
                 @arr[r][c] = res
                 update_fix(r, c)
             end
         }
     end
     # yields each cell of box b and assigns the result of the yield unless it
     # is nil
     def box_each(b)
         off_r, off_c = (b - (b % @sqrt_n)), (b % @sqrt_n) * @sqrt_n
         @n.times { |i|
             r, c = off_r + (i / @sqrt_n), off_c + (i % @sqrt_n)
             if (res = yield(@arr[r][c]))
                 @arr[r][c] = res
                 update_fix(r, c)
             end
         }
     end

     # find unique numbers in possibility lists of a row, col or box
     # each_meth must be :row_each, :col_each or :box_each
     def uniqs_in(each_meth, index)
         h = Hash.new(0)
         send(each_meth, index) { |x|
             x.each { |n| h[n] += 1 } if x.size > 1
             nil # we didn't change anything
         }
         h.select { |k, v| v == 1 }.collect { |k, v| k }
     end

end

if $0 == __FILE__
     # read a sudoku from stdin
     sudoku = []
     while sudoku.size < 9
         row = gets.scan(/\d|_/).map { |s| s.to_i }
         sudoku << row if row.size == 9
     end
     # solve
     begin
         solver = SudokuSolver.new(sudoku)
         puts "Input:", solver
         case solver.backtrack_solve
         when :solved
             puts "Solution:"
         when :multiple_solutions
             puts "There are multiple solutions!", "One solution:"
         else
             puts "Impossible:"
         end
         puts solver
     rescue => e
         puts "Error: #{e.message}"
     end
end

7

Karl von Laudermann wrote:

Heh. I already wrote a Sudoku solver back in May; all I have to do
is change the input/output format a bit to match the quiz
example. In the meantime, here's a harder puzzle to test your
programs with:

Why is it harder? If an algorithm works, all solvable puzzles are
the same?

There's a soln on RubyForge somewhere I saw the other day...

···

--
Chris Game

This time it will surely run.

8

I always ask that people wait 48 hours from the time on the quiz message. Thanks.

Looking forward to seeing the solutions though...

James Edward Gray II

···

On Aug 21, 2005, at 9:51 AM, horndude77@gmail.com wrote:

Should I post my code now or later?

9

Here's my (poor) solution. I started out thinking "Hey, that's easy!", and only when I was done did I realize that my solution cannot make the guesses necessary to "try out" numbers to fill in empty spaces to try and progress.

What it does do is solve the puzzle if there's always a simple logical next step (i.e. at least one row, column, or tile with exactly one number missing).

I failed the quiz, but feel the need to share my results anyhow :slight_smile:
(The board that I load happens to be the Quiz board, with the first row and third tile filled in just enough for my solver to be able to handle it.)

module Soduku
     class Board
         attr_reader :spaces, :tiles, :rows, :cols
         def initialize( board_to_load=nil )
             @spaces = (0..80).to_a.map{ |i| Space.new }

             @rows =
             0.step( 80, 9 ){ |i|
                 @rows << @spaces[ i..(i+8) ]
             }

             @cols =
             0.upto( 8 ){ |i|
                 @cols << col =
                 0.step( 80, 9 ){ |j|
                     col << @spaces[ i+j ]
                 }
             }

             @tiles =
             0.step(54,27){ |a|
                 0.step(6,3){ |b|
                     @tiles << tile =
                     corner = a+b
                     0.step(18,9){ |row_offset|
                         0.upto(2){ |col_offset|
                             tile << @spaces[ corner + row_offset + col_offset ]
                         }
                     }
                 }
             }

             if board_to_load
                 values = board_to_load.scan( /[\d_]/ )
                 raise "Supplied board does not have 81 distinct values" unless values.length == 81
                 values.each_with_index{ |v,i|
                     @spaces[i].value = v.to_i if v != '_'
                 }
             end
         end

         def solve
             unsolved_count = 81
             iteration = 1
             row_solved = {}
             col_solved = {}
             tile_solved = {}

             while unsolved_count > 0 && iteration < 100
                 puts "Iteration #{iteration}" if $DEBUG
                 unsolved_count = 81 - @spaces.select{ |s| s.value }.length
                 puts "\t#{unsolved_count} spaces unsolved" if $DEBUG

                 @rows.each_with_index{ |row,i|
                     unless row_solved[i]
                         if solve_set( row )
                             row_solved[i] = true
                         end
                     end
                 }

                 @cols.each_with_index{ |col,i|
                     unless col_solved[i]
                         if solve_set( col )
                             col_solved[i] = true
                         end
                     end
                 }

                 @tiles.each_with_index{ |tile,i|
                     unless tile_solved[i]
                         if solve_set( tile )
                             tile_solved[i] = true
                         end
                     end
                 }

                 iteration += 1
             end
         end

         def synchronize
             @spaces.each{ |s| s.synchronize }
         end

         def to_s
             row_sep = "+-------+-------+-------+\n"
             out = ''
             @spaces.each_with_index{ |s,i|
                 out << row_sep if i % 27 == 0
                 out << '| ' if i % 3 == 0
                 out << s.to_s + ' '
                 out << "|\n" if i % 9 == 8
             }
             out << row_sep
             out
         end

         private
             def solve_set( spaces )
                 unknown_spaces = spaces.select{ |s| !s.value }
                 return true if unknown_spaces.length == 0
                 known_spaces = spaces - unknown_spaces
                 known_values = known_spaces.collect{ |s| s.value }
                 unknown_spaces.each{ |s|
                     possibles = s.possibles
                     known_values.each{ |v| possibles.delete( v ) }
                     s.synchronize
                 }
                 # Recheck now that they've all been synchronized
                 unknown_spaces = spaces.select{ |s| !s.value }
                 return true if unknown_spaces.length == 0
                 return false
             end

     end

     class Space
         attr_accessor :value, :possibles
         def initialize( value=nil )
             @possibles = {}
             unless @value = value
                 1.upto(9){ |i| @possibles[i]=true }
             end
         end
         def synchronize
             possible_numbers = @possibles.keys
             if possible_numbers.length == 1
                 @value = possible_numbers.first
             end
         end
         def to_s
             @value ? @value.to_s : '_'
         end
     end
end

b = Soduku::Board.new( <<ENDBOARD )

···

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

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

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

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

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

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

+-------+-------+-------+
ENDBOARD

$DEBUG = true
puts b
b.solve
puts b

10

OK - here's my solution - without the change I plan to
make after looking at Simons answer...

I find it interesting comparing the times of Simons pgm
vs mine - his is faster about half the time, but in a
one case, his program runs in .9 Seconds, while mine
takes 85.7 ... a huge difference.

The one that's hardest for mine to solve is:

···

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

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

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

_ _ _ | _ _ 5 | _ _ _ |
_ 9 _ | _ 1 _ | _ 6 _ |
_ _ _ | 4 _ _ | _ _ _ |

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

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

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

although his finds that there's no solution
for
+-------+-------+-------+

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

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

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

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

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

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

in about 0.2 S.

Here's my (first) solution ...

-----
class Sudoku
  def initialize(dbg = false)
    @dbg = dbg
    @board =
  end

  def read(fname = STDIN)
    while line = gets
      next unless line =~ /^[\d\|]/
      line.gsub!(/,/, ' ')if line =~ /^\d/ # to keep working w/old
boards
      @board << line.gsub(/\|/,'').split(' ').map{|p| p.to_i}
    end
  end

  def to_s
    tb = "+-------+-------+-------+\n"
    out = ''
    @board.each_with_index{|row,rndx|
      out += tb if rndx % 3 == 0
      row.each_with_index{|cell, cndx|
        out += '| ' if cndx % 3 == 0
        out += cell == 0 ? "_ " : "#{cell} "
      }
      out += "|\n"
    }
    out += tb
  end

  def solve
    begin
      fill_spec # fill fully specified spaces
    rescue
      return # if try made illegal partial ...
    end

    if count_zeros > 0 # some empty spaces
      sav =
      copy_board(sav,@board) # save last known legal bd
      x,y = first_zero
      choices = find_choices(x,y)
      choices.each{|v| # try each possible choice for a 0
        copy_board(@board,sav)
        @board[y] = v
        puts "Try #{x},#{y} <- #{v}" if @dbg
        self.solve # recurse...
        break if count_zeros == 0
      }
    end
  end

  # fill fully specified entries
  def fill_spec
    zeros = count_zeros # how many to fill
    begin
      last_zeros = zeros
      (0..8).each{|i|
        (0..8).each{|j|
          next if @board[i][j] != 0 # skip filled spaces
          choices = find_choices(i, j)
          raise "Illegal Board #{i+1} #{j+1}" if choices.length == 0
          @board[i][j] = choices[0] if choices.length == 1
        }
      }
      zeros = count_zeros
    # if filled some, possibly others are now fully specified
    end while ((zeros > 0) && (last_zeros > zeros))
  end

  def find_choices (x, y) # get all choices for a given location
    choices = Array.new(9) {|i| i+1}
    # remove numbers from same line & row
    (0..8).each{|i|
      choices[@board[i] -1] = 0 if (@board[i] != 0 ) # rm digits
in row
      choices[@board[i][y] -1] = 0 if (@board[i][y] != 0 ) # rm digits
in col
    }
    # remove numbers from same square ...
    xs = (x/3) * 3
    xe = xs + 2
    ys = (y/3) * 3
    ye = ys + 2
    (xs..xe).each{|i|
      (ys..ye).each{|j|
        choices[(@board[i][j]) - 1] = 0 if (@board[i][j] != 0)
      }
    }
    choices.delete_if {|v| v == 0}
  end

  def count_zeros # to determine if I'm done ...
    @board.inject(0){|sum, row| sum += row.select{|e| e == 0}.length }
  end

  def copy_board(dst, src)
    (0..8).each{|i| dst[i] = src[i].dup}
  end
  def first_zero
    (0..8).each{|j| (0..8).each{|i| return i,j if @board[i][j] == 0 }}
  end

end

dbg = ARGV[0] =~ /-d/ ? true : false
ARGV.shift if dbg

bd = Sudoku.new(dbg)
bd.read(ARGV[0])
puts "Input\n#{bd}"
bd.solve
puts bd.count_zeros == 0 ? "Solution\n#{bd}" : "Unsolvable\n#{bd}"

----
Vance

11

Hi. This is my first attempt at a ruby quiz, and my first post to ruby-talk.
I've been messing with ruby for about a year. I actually wrote a version of
this solver with a fxwindows gui a while ago. The quiz was a good excuse to
clean it up and refactor it to handle text input.

It takes grids of almost arbitrary sizes upto 16 (and could be extended
more). It doesn't do any guessing, so it never solves some of the posted
programs. On the other hand, the official sudoku program from
www.soduku.com<http://www.soduku.com>tells me that those are not valid
puzzles, so I don't feel so bad. Anyway,
here it is:

#!/usr/bin/env ruby

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

#Utility function to define the inner sets of a grid
def GetGroupBounds(gridsize)
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 [5,2]
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

# 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, :group, :possible
def initialize(row, col, val=-1, max = 9)
@row = row
@col = col
bounds = GetGroupBounds(max)
@group = col/(bounds[0])+((row/bounds[1])*bounds[1])
@solved = false
case val
when 1..max
@possible = [val]
else
@possible = (1..max).to_a
end
end

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

def markSolved
@solved = true
end

def set(toValue)
if (found = @possible.include?(toValue))
@possible = [toValue];
end
return found
end

def hasFinalValue
if (@possible.length == 1)
return @possible[0]
end
end

def eliminate(n)
@possible.delete(n)
return hasFinalValue && !@solved
end

def show
(v = hasFinalValue)?" "+v.to_s(32):" _"
end

def to_s #for debugging
s = @possible.to_s;
s.length.upto(9) do s << " " end
"(#{row},#{col})["+s+"]"
end
end

class Solver
def initialize(boardlist, size)
@groups =[]
@rows =[]
@cols = []
@queue = [] #a list of cells to check for solutions.
@size = size
0.upto(@size-1) { |n| @groups[n] = [] ; @rows[n]=[]; @cols[n]=[] }
r=c=0
boardlist.each do |v|
cell = Cell.new(r,c,v, size)
@groups[cell.group] <<@rows[r][c] = @cols[c][r] = cell
@queue << cell
c+=1
if (c==size) then c=0; r=r+=1 end
end
end

def solve
while @queue.size > 0
while (cell = @queue.pop)
eliminateChoices(cell)
end
checkForKnownValues()
end
end

#for any resolved cell, eliminate its value from the possible values of the
other cells in the set
def eliminateChoices(cell)
value = cell.hasFinalValue
if (value)
cell.markSolved
eliminateChoiceFromGroup(@groups[cell.group], cell, value)
eliminateChoiceFromGroup(@rows[cell.row], cell, value)
eliminateChoiceFromGroup(@cols[cell.col], cell, value)
end
end

def eliminateChoiceFromGroup(g, exceptThisCell, n)
g.each do |cell|
eliminateValueFromCell(n,cell) if (cell != exceptThisCell)
end
end

def eliminateValueFromCell(value, cell)
if (cell.eliminate(value) && !@queue.include?(cell))
@queue << cell #if this cell is now resolved, put it on the queue.
end
end

def checkForKnownValues()
0.upto(@size-1) do |n|
findPairs(@rows[n])
findPairs(@cols[n])
findPairs(@groups[n])
findUniqueChoices(@rows[n])
findUniqueChoices(@cols[n])
findUniqueChoices(@groups[n])
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
lastCell = nil
break
end
lastCell = c;
end
end
#if true, there is only one cell in the set with that value, so 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.upto(@size-1) do |m|
if (n != m && 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)
0.upto(@size-1) do |i|
if (!skipList.include?(i))
values.each {|v| eliminateValueFromCell(v, set[i])}
end
end
end

#formating (vertical line every cbreak)
def showBorder(cbreak)
s = "+"
1.upto(@size) do |n|
s << "--"
if ((n)%cbreak == 0) then s<< "-+" end
end
s <<"\n"
end

def show
r=c=0
cbreak,rbreak = GetGroupBounds(@size)
s = showBorder(cbreak)
@rows.each do |row|
r+=1
s << "|"
row.each do |cell|
c+=1
s << cell.show
if (c==cbreak) then s << " |";c=0; end
end
s<<"\n"
if (r==rbreak) then s << showBorder(cbreak); r=0; end
end
s<<"\n"
print s
end
end

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

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

sol.show
sol.solve()
sol.show

end

···

--
-Adam Shelly

12

Chris Game wrote:

Karl von Laudermann wrote:

Heh. I already wrote a Sudoku solver back in May; all I have to do
is change the input/output format a bit to match the quiz
example. In the meantime, here's a harder puzzle to test your
programs with:

Why is it harder? If an algorithm works, all solvable puzzles are
the same?

This is true for brute force solving only. If you apply some logic
to cut down the calculation time things gets more interesting.

There's a soln on RubyForge somewhere I saw the other day...

Maybe, but its fun.

To those who try, here is a very neat one:

···

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

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

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

_ 8 7 | 4 _ _ | 1 _ _ |
4 6 3 | _ 8 _ | _ _ _ |
_ _ _ | _ _ 7 | _ 8 _ |

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

8 _ _ | 7 _ _ | _ _ _ |
7 _ _ | _ _ _ | _ 2 8 |
_ 5 _ | 2 6 8 | _ _ _ |

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

I can't confirm thats its solveable (yet) :slight_smile:

cheers

Simon

13

In article <15hhca6w53u5l.dlg@example.net>,

Karl von Laudermann wrote:

> Heh. I already wrote a Sudoku solver back in May; all I have to do
> is change the input/output format a bit to match the quiz
> example. In the meantime, here's a harder puzzle to test your
> programs with:

Why is it harder? If an algorithm works, all solvable puzzles are
the same?

Well, it's harder for a human to solve; I forget where I snagged it
from, but it was labelled as "really hard". And it took my solver
program a whole 7 seconds to solve it (on my old computer), while other
examples I tested it with took less than a second to solve. So it's
probably useful for profiling your program's performance.

Ok, here's one that's *not* solvable, useful for making sure that your
program can handle such a case gracefully:

···

Chris Game <chrisgame@example.net> wrote:

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

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

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

_ 9 _ | 7 _ _ | 5 _ _ |
_ 4 2 | _ 5 _ | 1 3 _ |
_ _ 3 | _ _ 9 | _ 4 _ |

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

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

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

--
Karl von Laudermann - karlvonl(a)rcn.com - Yahoo | Mail, Weather, Search, Politics, News, Finance, Sports & Videos
#!/usr/bin/env ruby
require "complex";w=39;m=2.0;w.times{|y|w.times{|x|c=Complex.new((m*x/w)-1.5,
(2.0*y/w)-1.0);z=c;e=false;49.times{z=z*z+c;if z.abs>m then e=true;break;end}
print(e ?" ":"@@");puts if x==w-1;}}

14

Ok, I've seen a couple other solutions posted. Here is my code. I threw
this together pretty quick.

I start out by populating the board matrix with either the given value
or an array of possibilities. We then go through each row, column and
box eliminating possibilities from the unknown squares. If there is
ever only one possibility for a square we set that square to the now
known value. Next we go through each row, column and box to find
instances where a square has multiple possibilities, but for that set
one of these possibilities is the only one. So if a square has
possibilities of 2 and 7, but no other square in the same row can be 2
then this square must be 2 and not 7. We alternate between this process
and eliminating until we either find a solution or we have gone through
a loop without finding anything to change.

I'm not convinced that this fully solves ever puzzle. I'd be interested
in a proof though. (ie if a given sudoku board has only one possible
solution then this algorithm will find it) The next logical step would
be to brute force the rest of the puzzle looking for solutions. A Depth
First Search would work.

In any case. This was a good help for me learning ruby. I was
especially happy to find the set operators for arrays. That made my
day.

-----Horndude77

#!/usr/bin/env ruby

class Sudoku
  def initialize(boardstring)
    @board = Array.new(9)
    9.times { |i| @board[i] = Array.new(9) }
    flattened = boardstring.delete("-+|\n").split
    index = 0
    @unknown = []

    # set up actual array
    9.times do |i|
      9.times do |j|
        if(flattened[index] == '_') then
          @board[i][j] = [1, 2, 3, 4, 5, 6, 7, 8, 9]
          @unknown << [i,j]
        else
          @board[i][j] = flattened[index].to_i
        end
        index += 1
      end
    end

    #set up what each row, col, and box contains
    @rows = Array.new(9)
    @cols = Array.new(9)
    @boxes = Array.new(9)
    9.times { |i| @rows[i] = numsInRow(i) }
    9.times { |j| @cols[j] = numsInCol(j) }
    3.times { |i| 3.times { |j| @boxes[i+3*j] = numsInBox(3*i,3*j) } }
  end

  def numsInRow(row)
    toreturn = []
    9.times do |j|
      if(@board[row][j].kind_of? Fixnum) then
        toreturn << @board[row][j]
      end
    end
    return toreturn
  end

  def numsInCol(col)
    toreturn = []
    9.times do |i|
      if(@board[i][col].kind_of? Fixnum) then
        toreturn << @board[i][col]
      end
    end
    return toreturn
  end

  def numsInBox(boxrow, boxcol)
    toreturn = []
    x = boxrow - boxrow%3
    y = boxcol - boxcol%3
    3.times do |i|
      3.times do |j|
        if(@board[x+i][y+j].kind_of? Fixnum) then
          toreturn << @board[x+i][y+j]
        end
      end
    end
    return toreturn
  end

  def to_s
    s = ""
    9.times do |i|
      if(i%3 == 0) then
        s += "+-------+-------+-------+\n"
      end
      9.times do |j|
        if(j%3 == 0) then
          s += "| "
        end
        if(@board[i][j].kind_of? Array) then
          s += "_ "
        else
          s += "#{@board[i][j]} "
        end
      end
      s += "|\n"
    end
    s += "+-------+-------+-------+\n"
    return s
  end

  # Looks in row, column and box to eliminate impossible values
  def eliminate(i,j)
    changed = false
    if(@board[i][j].kind_of? Array) then
      combined = @rows[i] | @cols[j] | @boxes[(i/3)+(j-j%3)]
      if( (@board[i][j] & combined).length > 0) then
        changed = true
        @board[i][j] -= combined
      end

      if(@board[i][j].length == 1) then
        foundsolution(i,j,@board[i][j][0])
      end
    end
    return changed
  end

  def foundsolution(x,y,val)
    @board[x][y] = val
    @rows[x] << @board[x][y]
    @cols[y] << @board[x][y]
    @boxes[(x/3)+(y-y%3)] << @board[x][y]
    @unknown.delete([x,y])
  end

  def eliminateall
    changed = true
    while(changed)
      changed = false
      @unknown.each do |u|
        if(eliminate(u[0],u[1])) then changed = true end
      end
    end
    return changed
  end

  #these check functions look for squares that have multiple
  # possibilities except the set itself only has one.
  def checkrow(i)
    changed = false
    set = Hash.new
    9.times do |j|
      if (@board[i][j].kind_of? Array) then
        @board[i][j].each do |e|
          if(set[e]) then
            set[e] << j
          else
            set[e] = [j]
          end
        end
      end
    end
    set.each do |k,v|
      if(v.length == 1) then
        foundsolution(i,v[0],k)
        changed = true
      end
    end
    return changed
  end

  def checkcol(j)
    changed = false
    set = Hash.new
    9.times do |i|
      if (@board[i][j].kind_of? Array) then
        @board[i][j].each do |e|
          if(set[e]) then
            set[e] << i
          else
            set[e] = [i]
          end
        end
      end
    end
    set.each do |k,v|
      if(v.length == 1) then
        foundsolution(v[0],j,k)
        changed = true
      end
    end
    return changed
  end

  def checkbox(n)
    x = 3*(n%3)
    y = 3*(n/3)
    changed = false
    set = Hash.new
    3.times do |i|
      3.times do |j|
        if (@board[x+i][y+j].kind_of? Array) then
          @board[x+i][y+j].each do |e|
            if(set[e]) then
              set[e] << [x+i,y+j]
            else
              set[e] = [ [x+i,y+j] ]
            end
          end
        end
      end
    end
    set.each do |k,v|
      if(v.length == 1) then
        foundsolution(v[0][0], v[0][1], k)
        changed = true
      end
    end
    return changed
  end

  def checkallrows
    changed = false
    9.times do |i|
      if(checkrow(i)) then changed = true end
    end
    return changed
  end

  def checkallcols
    changed = false
    9.times do |j|
      if(checkcol(j)) then changed = true end
    end
    return changed
  end

  def checkallboxes
    changed = false
    9.times do |n|
      if(checkbox(n)) then changed = true end
    end
    return changed
  end

  def solve
    #is there a better way to do this? it seems messy
    # and redundant.
    changed = true
    while(changed && @unknown.length>0)
      changed = false
      changed = eliminateall ? true : changed
      changed = checkallrows ? true : changed
      changed = eliminateall ? true : changed
      changed = checkallcols ? true : changed
      changed = eliminateall ? true : changed
      changed = checkallboxes ? true : changed
    end
    puts self
    if(@unknown.length>0)
      puts "I can't solve this one"
    end
  end
end

board = Sudoku.new($stdin.readlines.join)
board.solve

15

aargh. What happened to my tabs?

···

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

Hi. This is my first attempt at a ruby quiz, and my first post to
ruby-talk.

...

16

Welcome to the Ruby community and thanks for the quiz submission!

I'm not sure what happened to your tabs. Did you just paste the code right into a message?

James Edward Gray II

···

On Aug 22, 2005, at 9:08 PM, Adam Shelly wrote:

Hi. This is my first attempt at a ruby quiz, and my first post to ruby-talk.

17

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

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

The 4 problems we've been given (the orignal with the
quiz and the 3 new ones seemed to yield fairly
quickly. I'm looking forward to see other
solutions and try them on this one.

Here's the results of running the 1st 4.

Vance

heron-linux:for i in rqi* ; do time sd2.rb $i ; done
Input
+-------+-------+-------+

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

+-------+-------+-------+
Solution
+-------+-------+-------+

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

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

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

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

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

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

real 0m0.060s
user 0m0.050s
sys 0m0.000s
Input
+-------+-------+-------+

_ _ 2 | _ _ 5 | _ 7 9 |
1 _ 5 | _ _ 3 | _ _ _ |
_ _ _ | _ _ _ | 6 _ _ |

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

_ 1 _ | 4 _ _ | 9 _ _ |
_ 9 _ | _ _ _ | _ 8 _ |
_ _ 4 | _ _ 9 | _ 1 _ |

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

_ _ 9 | _ _ _ | _ _ _ |
_ _ _ | 1 _ _ | 3 _ 6 |
6 8 _ | 3 _ _ | 4 _ _ |

+-------+-------+-------+
Solution
+-------+-------+-------+

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

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

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

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

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

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

real 0m1.626s
user 0m0.830s
sys 0m0.010s
Input
+-------+-------+-------+

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

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

_ 8 7 | 4 _ _ | 1 _ _ |
4 6 3 | _ 8 _ | _ _ _ |
_ _ _ | _ _ 7 | _ 8 _ |

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

8 _ _ | 7 _ _ | _ _ _ |
7 _ _ | _ _ _ | _ 2 8 |
_ 5 _ | 2 6 8 | _ _ _ |

+-------+-------+-------+
Solution
+-------+-------+-------+

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

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

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

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

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

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

real 0m0.960s
user 0m0.450s
sys 0m0.000s
Input
+-------+-------+-------+

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

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

_ 9 _ | 7 _ _ | 5 _ _ |
_ 4 2 | _ 5 _ | 1 3 _ |
_ _ 3 | _ _ 9 | _ 4 _ |

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

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

+-------+-------+-------+
Unsolvable
+-------+-------+-------+

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

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

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

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

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

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

real 0m0.046s
user 0m0.030s
sys 0m0.010s

On Sat, 2005-08-20 at 23:41 +0900, Karl von Laudermann wrote:

In article <15hhca6w53u5l.dlg@example.net>,
Chris Game <chrisgame@example.net> wrote:

> Karl von Laudermann wrote:
>
> > Heh. I already wrote a Sudoku solver back in May; all I have to do
> > is change the input/output format a bit to match the quiz
> > example. In the meantime, here's a harder puzzle to test your
> > programs with:
>
> Why is it harder? If an algorithm works, all solvable puzzles are
> the same?

Well, it's harder for a human to solve; I forget where I snagged it
from, but it was labelled as "really hard". And it took my solver
program a whole 7 seconds to solve it (on my old computer), while other
examples I tested it with took less than a second to solve. So it's
probably useful for profiling your program's performance.

Ok, here's one that's *not* solvable, useful for making sure that your
program can handle such a case gracefully:

+-------+-------+-------+
> _ _ 1 | _ 2 _ | 8 _ _ |
> _ 7 _ | 3 1 _ | _ 9 _ |
> 3 _ _ | _ 4 5 | _ _ 7 |
+-------+-------+-------+
> _ 9 _ | 7 _ _ | 5 _ _ |
> _ 4 2 | _ 5 _ | 1 3 _ |
> _ _ 3 | _ _ 9 | _ 4 _ |
+-------+-------+-------+
> 2 _ _ | 5 7 _ | _ _ 4 |
> _ 3 _ | _ 9 1 | _ 6 _ |
> _ _ 4 | _ _ _ | 3 _ _ |
+-------+-------+-------+

18

Then you'll want to look at the standard "set" library. That will make your whole weekend. :wink:

James Edward Gray II

···

On Aug 21, 2005, at 3:31 PM, horndude77@gmail.com wrote:

In any case. This was a good help for me learning ruby. I was
especially happy to find the set operators for arrays. That made my
day.

19

Ok, I've updated my version to resort to guessing when it can't deduce
all the values.
It guesses pretty slowly, my worst time was

···

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

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

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

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

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

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

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

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

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

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

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

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

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

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

real 0m16.308s
user 0m16.311s
sys 0m0.015s

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

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

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

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

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

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

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

real 0m12.531s
user 0m12.514s
sys 0m0.030s

Here's the code. (hope the tabs work this time - last time I pasted
directly from SciTE into gmail and lost them. This time I went
through a plain text editor first...)
---
#!/usr/bin/env ruby

# SudokuSolver.rb
# author: Adam Shelly

# Solves sudoku puzzles.
# supports arbitrary grid sizes (tested upto 16x16)

def dprint(s)
# print s
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])
        @solved = 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 markSolved
        @solved = true
    end
    
    def set(toValue)
        if (found = @possible.include?(toValue))
            @possible = [toValue];
        end
        return found
    end
    
    def hasFinalValue
        if (@possible.length == 1)
            return @possible[0]
        end
    end
    
    def eliminate(n)
        raise BadGuessException if (@possible.length == 0)
        @possible.delete(n)
        return hasFinalValue && !@solved
    end
    
    def override(a)
        @possible = a.dup
        @solved = false
    end
    
    def to_s
        (v = hasFinalValue)?" "+v.to_s(32):" _"
    end
    
    def show #for debugging
        s = @possible.to_s;
        s.length.upto(9) do s << " " end
        "(#{row},#{col})["+s+"]"
    end
    
    def >(other)
        return (@row > other.row || (@row == other.row && @col > other.col))
    end
end

class Guess
    attr_reader :cell, :index
    def initialize(cell )
        @row = cell.row
        @col = cell.col
        @cell = cell
        @store = @cell.possible.clone
        @index = 0
    end
    def value
        @store[@index]
    end
    def increment(cellset)
        if (@index+1 < @store.size)
            @index += 1
            @cell=cellset[@row][@col] #because we may be on a cloned board
            return true
        end
    end
    def apply
            @cell.set(value)
            dprint "Applying #{self}\n"
            return @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
    
    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.markSolved if (presolved && cell.hasFinalValue)
            c+=1
            if (c==@size) then c=0; r=r+=1 end
        end
    end
    
    def solve
        while @queue.size > 0
            while (cell = @queue.pop)
                eliminateChoices(cell)
            end
            checkForKnownValues()
        end
        dprint "Solved to...\n#{self}"
            return startGuessing if (unsolved)
        return true
    end
    
    def unsolved
        @size.times do |n|
            @boxes[n].each {|c| return c if !c.hasFinalValue}
        end
        nil
    end
    
    #for any resolved cell, eliminate its value from the possible
values of the other cells in the set
    def eliminateChoices(cell)
      value = cell.hasFinalValue
      if (value)
            cell.markSolved
            eliminateChoiceFromSet(@boxes[cell.box], cell, value)
            eliminateChoiceFromSet(@rows[cell.row], cell, value)
            eliminateChoiceFromSet(@cols[cell.col], cell, value)
        end
    end
    
    def eliminateChoiceFromSet(g, exceptThisCell, n)
        g.each do |cell|
            eliminateValueFromCell(n,cell) if (cell != exceptThisCell)
        end
    end
    
    def eliminateValueFromCell(value, cell)
        if (cell.eliminate(value) && !@queue.include?(cell))
            @queue << cell #if this cell is now resolved, put it on
the queue.
        end
    end
    
    def checkForKnownValues()
        @size.times do |n|
            findPairs(@rows[n])
            findPairs(@cols[n])
            findPairs(@boxes[n])
            findUniqueChoices(@rows[n])
            findUniqueChoices(@cols[n])
            findUniqueChoices(@boxes[n])
        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
                        lastCell = nil
                        break
                    end
                    lastCell = c;
                end
            end
            #if true, there is only one cell in the set with that
value, so 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.upto(@size-1) do |m|
                if (n != m && 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
        myguess = nil
        while (c = unsolved)
            begin
                myclone = Solver.new(boardlist,@size, true,@level)
                myguess = myclone.guess(myguess)
                if !myguess
                    dprint "did not find a guess\n"
                    return false
                end
                dprint myclone
                if (myclone.solve)
                    print "Only Solveable by Guessing\n" if @level == 1
                    become(myclone.boardlist)
                    return true
                elsif @level > 1
                    dprint "unwinding #{@level}\n"
                    return false
                end
            rescue BadGuessException
                dprint "#{@level} Bad Guess\n"
            end
        end
    end
    
    def guess(oldguess)
        if (oldguess && oldguess.increment(@rows))
            @queue << oldguess.apply
            return oldguess
        else
            mincell = nil
            mincount = @size+1
            @size.times do |r|
                @size.times do |c|
                    cell = @rows[r][c]
                    if (!cell.hasFinalValue && cell.possible.size <
mincount && (!oldguess || cell > oldguess.cell))
                        mincell = cell
                        mincount = cell.possible.size
                    end
                end
            end
            if mincell
                g = Guess.new(mincell)
                @queue << g.apply
                return g
            end
        end
        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 boardlist
        a =
        @rows.each do |row|
            row.each do |cell|
                v = cell.hasFinalValue
                if (v)
                    e = v
                else
                    #~ e = cell.possible.clone #if you don't clone
here you get a mess!
                    #~ e.freeze;
                    e = cell.possible
                end
                a<<e
            end
        end
        a
    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==rbreak) then s << showBorder(cbreak); r=0; end
            end
            s<<"\n"
        s
    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 many 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/22/05, James Edward Gray II <james@grayproductions.net> wrote:

On Aug 22, 2005, at 9:08 PM, Adam Shelly wrote:

> Hi. This is my first attempt at a ruby quiz, and my first post to
> ruby-talk.

Welcome to the Ruby community and thanks for the quiz submission!

I'm not sure what happened to your tabs. Did you just paste the code
right into a message?

James Edward Gray II

20

Hi!

aargh. What happened to my tabs?

Vanished. Well-known problem in ASCII-artist communities.

Follows best current practice to prepare a Ruby program before
including it in the text of an e-mail. Valid for all e-mail programs
running in Emacsen:

1. mark whole program
2. issue 'M-x untabify'
3. mark whole program again
4. issue 'M-x comment-region'

This leaves the program readable while at the same time keeping the
whitespace intact.

Using 'M-x comment-region' makes sure that the whitespace is no
leading one. Some MUAs are known to remove *any* leading whitespace -
not just spaces!

For making the program runnable again 'M-x uncomment-region' is
suficient.

irb(main):001:0> algorithm.port(user.mua) == exercise(message.reader)
true

(^_^)

Josef 'Jupp' SCHUGT

···

At Tue, 23 Aug 2005 11:11:46 +0900,Adam Shelly wrote:
--
Receiving this message does not necessarily imply that you are
expected to understand it. If you do not understand it the best
current practice (BCP) is ignoring it. If you only understand parts
of it the BCP is ignoring the rest.