--EUPHORIA Sudoku solver (c) 2005 by Harm Veenstra
--with profile
constant TRUE = 1 ,FALSE = 0
integer count           --   used to count the number of tries
	count = 0       -- initialize
sequence B              -- the actual puzzle ( note 0 means empty square )
	 B = {0,3,0,0,9,8,0,0,0,
	      9,0,0,3,7,5,2,0,6,
	      0,0,8,0,0,0,1,0,9,
	      4,1,3,0,0,2,0,7,0,
	      0,0,6,0,5,0,0,0,2,
	      0,5,0,8,0,7,0,0,0,
	      8,0,0,0,4,0,6,0,0,
	      3,0,5,0,0,6,0,4,7,
	      0,0,0,7,0,0,9,2,0}

procedure printp(sequence p)
-- prinp prints the sudoku puzzle formatted in a 9 by 9 square
--  position(1,1)
    for y = 0 to 72 by 9  do
	for x = 1 to 9  do
	    printf(1,"%d  ",p[y + x])
	end for
	puts(1,"\n")
    end for
    puts(1,"\n")
end procedure

function valid(sequence puzzle,integer pos, integer val)
-- this function validates putting a number (val) on a certain
-- position (pos) in a given puzzle (puzzle)
sequence slice
integer x, y, z

count = count + 1           -- increment counter

-- constuct the row in slice
y = floor((pos - 1) / 9) * 9 + 1
slice = puzzle[y .. (y + 8)]
-- val is already in this row
if find(val,slice) != 0 then
    return FALSE
end if

-- construct the collumn in slice
x = remainder(pos - 1,9) + 1
slice = {puzzle[x],     puzzle[x +  9],puzzle[x + 18],
	 puzzle[x + 27],puzzle[x + 36],puzzle[x + 45],
	 puzzle[x + 54],puzzle[x + 63],puzzle[x + 72]}
-- val is already in this column
if find(val,slice) != 0 then
    return FALSE
end if

-- construct the 9 x 9 sub-square in slice
if    y < 28 then z = 1
elsif y < 55 then z = 28
else              z = 55
end if

if    x < 4 then z = z
elsif x < 7 then z = z + 3
else             z = z + 6
end if
slice = {puzzle[z],     puzzle[z +  1],puzzle[z +  2],
	 puzzle[z +  9],puzzle[z + 10],puzzle[z + 11],
	 puzzle[z + 18],puzzle[z + 19],puzzle[z + 20]}
	 -- val is already in this 9 x 9 subsquare
if find(val,slice) != 0 then
    return FALSE
end if

-- every test passed, move is valid
return TRUE
end function


function solve (sequence puzzle)
-- the main (recursive ) function
sequence dummy

--printp(puzzle)
for x = 1 to 81  do                         -- loop thru all squares
    if puzzle[x] = 0 then                   -- if empty
	for i = 1 to 9  do                  -- try all 9 numbers
	    if valid(puzzle,x,i) then       -- if valid
		puzzle[x] = i               -- pace number on square
		dummy = solve(puzzle)       -- solve this ( RECURSION )
	    end if
	end for
	return puzzle
    end if
end for
printp(puzzle)                              -- print the solution
return puzzle
end function

sequence dummy

dummy= solve(B)                             -- SOLVE THE PUZZLE
printf(1,"%d \n",count)                     -- print number of tries