Su Doku (Japanese meaning number place) is the name given to a popular puzzle concept. Its origin is unclear, but credit must be attributed to Leonhard Euler who invented a similar, and much more difficult, puzzle idea called Latin Squares. The objective of Su Doku puzzles, however, is to replace the blanks (or zeros) in a 9 by 9 grid in such that each row, column, and 3 by 3 box contains each of the digits 1 to 9. Below is an example of a typical starting puzzle grid and its solution grid.

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

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

A well constructed Su Doku puzzle has a unique solution and can be solved by logic, although it may be necessary to employ "guess and test" methods in order to eliminate options (there is much contested opinion over this). The complexity of the search determines the difficulty of the puzzle; the example above is considered easy because it can be solved by straight forward direct deduction.

The 6K text file, sudoku.txt (right click and 'Save Link/Target As...'), contains fifty different Su Doku puzzles ranging in difficulty, but all with unique solutions (the first puzzle in the file is the example above).

By solving all fifty puzzles find the sum of the 3-digit numbers found in the top left corner of each solution grid; for example, 483 is the 3-digit number found in the top left corner of the solution grid above.

+-#cartesian_product
def cartesian_product(*a)
	return [] if a.length==0
	return a[0].map{|h|[h]} if a.length==1
	a.map!{|b| b.to_a}
	b=cartesian_product(*(a[1..-1]))
	a=a[0]
	res=[]
	if block_given?
		a.each do |aitem|
			res=res+b.select{|i|yield(aitem,*i)}.map{|i|[aitem]+i}
		end
	else
		a.each do |aitem|
			b.each{|bitem| res.push([aitem]+bitem)}
		end
	end
	res
end

+-#Enumerable
module Enumerable
  def sum
    self.inject{|u,v|u+v}
  end
  def product
    self.inject{|u,v|u*v}
  end
  def count(ob)
    self.select{|i|i==ob}.length
  end
  def take_while
    return [] unless yield(self.first)
    if(self.class==Range)
      evalPoint=self.first
      evalPoint=evalPoint.succ while yield(evalPoint.succ) and not evalPoint==self.last
      return self.first..evalPoint
    else
      s=self.to_a
      upTo=1
      upTo+=1 while yield(s[upTo]) and upTo<self.length
      return self[0...upTo]
    end
  end
end

class Sudoku
  attr_reader :grid
  @@digs=(1..9).to_a
  @@range=(0...9)
  @@dub_range=cartesian_product(@@range,@@range)
  def initialize(grid)
    @grid=grid
    @grid.each do |r|
      r.map!{|c|c==0 ? @@digs : c}
    end
    @@dub_range.each do |r,c| 
      eliminate(r,c) unless @grid[r][c].class==Array
    end
  end

  #
  # Since unknown squares are represented by an array of possible values, this
  # function takes a known square and makes sure none of the unknown squares in
  # its row, column, or square have its value in their arrays. It's used in the
  # constructor, and any time a new value is determined
  #

  def eliminate(r,c)
    v=@grid[r][c]
    [row(r),col(c),square_of(r,c)].each do |pr|
      @@range.each do |i|
        if(pr[i].class==Array)
	  pr[i,pr[i]-[v]]
	end
      end
    end
  end

  #
  # These three functions returning procs act as an abstraction from rows, columns, and squares,
  # so that each case can be treated the same. The procs allow reading, writing, and returning
  # absolute coordinates
  #

  def row(n)
    Proc.new do |c,v|
      @grid[n][c]=v if v.class==Fixnum or v.class==Array
      r=@grid[n][c]
      r=[n,c] if v==:coord
      r
    end
  end

  def col(n)
    Proc.new do |r,v|
      @grid[r][n]=v if v.class==Fixnum or v.class==Array
      ret=@grid[r][n]
      ret=[r,n] if v==:coord
      ret
    end
  end

  def square_of(r,c)
    square(3*(r/3)+c/3)
  end

  def square(n)
    rowstart=n-n%3
    colstart=3*(n%3)
    Proc.new do |i,v|
      @grid[rowstart+i%3][colstart+i/3]=v if v.class==Fixnum or v.class==Array
      r=@grid[rowstart+i%3][colstart+i/3]
      r=[rowstart+i%3,colstart+i/3] if v==:coord
      r
    end
  end

  def solved?
    @@range.all? do |i|
      [row(i),col(i),square(i)].all? do |pr|
        vals=@@range.map{|j|pr[j]}
	vals.all?{|v|v.class==Fixnum} and vals.sort==@@digs
      end
    end
  end

  #
  # This test is important when the algorithm resorts to guessing
  #

  def impossible?
    @grid.any?{|r|r.any?{|c|c.class==Array and c.length==0}}
  end

  def solve
    until solved?
      return false if impossible?
      test=@grid.hash

      @@dub_range.each do |r,c|
	if @grid[r][c].class==Array and @grid[r][c].length==1
	  @grid[r][c]=@grid[r][c].first
	  eliminate(r,c)
        end
      end
      next unless test==@grid.hash
      @@range.each do |i|
        [row(i),col(i),square(i)].each do |pr|
	  possible=@@range.map{|j|pr[j]}.select{|j|j.class==Array}.flatten
	  possible.uniq.select{|j|possible.count(j)==1}[0..0].each do |e|
	    inc=0
	    inc+=1 until pr[inc].class==Array and pr[inc].index e
	    pr[inc,e]
	    eliminate(*pr[inc,:coord])
	  end
        end
      end
      next unless test==@grid.hash
      @@range.each do |i|
	[row(i),col(i),square(i)].each do |pr|
          empty=@@range.select{|j|pr[j].class==Array and pr[j].length>1}
	  vals=empty.map{|j|pr[j]}
	  vals.uniq.select{|v|vals.count(v)==v.length}.each do |v|
	    empty.reject{|e|pr[e]==v}.each do |ii|
              pr[ii,pr[ii]-v]
	    end
	  end
	end
      end
      break if test==@grid.hash
    end

    #
    # Begin guessing
    #

    unless solved?
      id=rand(10**6)
      i=0
      i+=1 until @grid[i%9][i/9].class==Array
      r,c=i%9,i/9
      options=@grid[r][c]
      options.each do |opt|
        @grid[r][c]=opt
        test=Sudoku.new(@grid.map{|rr|rr.clone})
        if test.solve
  	  @grid=test.grid
	  break
        end
      end
      @grid[r][c]=options unless solved?
    end
    solved?
  end
end

def p96
  lines=File.read("sudoku.txt").split("\n").reject{|l|l=~/Grid/}.map{|l|l.strip.split("").map{|i|i.to_i}}
  grids=(0...50).map{|i|Sudoku.new lines[i*9...(i+1)*9]}
  grids.each{|g|g.solve}
  puts grids.map{|g|g.grid[0][0...3].join("").to_i}.sum
end