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

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
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

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