--UFHRwCdBEJvubb2X
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

Here is a functional sodoku solver that uses continuations.  Note that
it works because all the functions called within the chooser are
purely functional -- they do not alter their arguments, and their
value does not depend on any saved state.


# Size of board
SIZE = 9
# Size of individual boxes
BOX = 3

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

# ---- Continuation-based Choooser -----------------
$paths = []

def choose(possibilities)
  catch(:the_choice){
    possibilities.each do |p|
      throw :the_choice, p  if callcc {|cc| $paths << cc;}
    end
    failure
  }
end

def failure
  raise "No solution" if $paths.empty?
  $paths.pop.call
end
# ----------------------------------------------------

# Returns board as a flat array
def parse(board)
  board.scan( /[1-9_]/ ).map {|x| x == '_' ? nil : x.to_i}
end

# all existing numbers on the same horizontal row as elt
def horiz(board, elt)
  board[ elt - elt%SIZE , SIZE ].select {|x| x}
end

# all existing numbers in same vertical column as elt
def vert(board, elt)
  result = []
  (elt % SIZE).step(SIZE*SIZE, SIZE) {|i|
    result << board[i] if board[i]
  }
  result
end

# all existing numbers in same box as elt
def box(board, elt)
  result = []
  start = (elt / SIZE / BOX * BOX) * SIZE + (elt % SIZE / BOX * BOX)
  BOX.times {|i| result += board[start + i*SIZE,BOX] }
  result.select {|x| x}
end

# numbers that can legally fill elt
def available(board, elt)
  (1..9).to_a - horiz(board,elt) - vert(board,elt) - box(board,elt)
end

# Recursive solution
def solve(board)
  elt = board.index(nil)
  return board unless elt
  newboard = board.dup
  newboard[elt] = choose(available(board,elt))
  solve(newboard)
end

def output(board)
  SIZE.times {|i|
    puts "#{board[i*SIZE,SIZE].join(' ')}\n"
  }
  :done
end

# Go!
output(solve(parse(input)))


regards,
Ed

--UFHRwCdBEJvubb2X
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFDhLBtnhUz11p9MSARAn8SAKCVO1T6GgBQ0km7zOfTqNLzVFJjBQCg0QaT
JKEdQoBOOqdaxwE2RMNU3gI=
=nCk5
-----END PGP SIGNATURE-----

--UFHRwCdBEJvubb2X--