Sudoku: Difference between revisions
Content deleted Content added
m added brute force solver |
|||
Line 5,373:
=={{header|Phix}}==
Simple brute force solution. Generally quite good but
<lang Phix>sequence board = split("""
.......39
.....1..5
</lang>▼
..3.5.8..
OTT solution. Implements line/col and set exclusion, and x-wings.<BR>▼
..8.9...6
.7...2...
1..4.....
..9.8..5.
.2....6..
4..7.....""",'\n')
function valid_move(integer y, integer x, integer ch)
for i=1 to 9 do
if ch=board[i][x] then return 0 end if
if ch=board[y][i] then return 0 end if
end for
y -= mod(y-1,3)
x -= mod(x-1,3)
for ys=y to y+2 do
for xs=x to x+2 do
if ch=board[ys][xs] then return 0 end if
end for
end for
return 1
end function
sequence solution = {}
procedure brute_solve()
for y=1 to 9 do
for x=1 to 9 do
if board[y][x]<='0' then
for ch='1' to '9' do
if valid_move(y,x,ch) then
board[y][x] = ch
brute_solve()
board[y][x] = ' '
if length(solution) then return end if
end if
end for
return
end if
end for
end for
solution = board -- (already solved case)
end procedure
atom t0 = time()
brute_solve()
printf(1,"%s\n(solved in %3.2fs)\n",{join(solution,"\n"),time()-t0})</lang>
{{out}}
<pre>
751846239
892371465
643259871
238197546
974562318
165438927
319684752
527913684
486725193
(solved in 0.95s)
▲OTT solution. Implements line/col and set exclusion, and x-wings. Blisteringly fast<BR>
The included program demo\rosetta\Sudoku.exw is an extended version of this that performs extended validation,
contains 339 puzzles, can be run as a command-line or gui program, check for multiple solutions, and produce
| |||