Sudoku: Difference between revisions
add Ada |
|||
Line 2: | Line 2: | ||
Solve a partially filled-in normal 9x9 [[wp:Sudoku|Sudoku]] grid and display the result in a human-readable format. [[wp:Algorithmics_of_sudoku|Algorithmics of Sudoku]] may help implement this. |
Solve a partially filled-in normal 9x9 [[wp:Sudoku|Sudoku]] grid and display the result in a human-readable format. [[wp:Algorithmics_of_sudoku|Algorithmics of Sudoku]] may help implement this. |
||
=={{header|Ada}}== |
|||
<lang Ada>with Ada.Text_IO; |
|||
procedure Sudoku is |
|||
subtype Number is Natural range 0 .. 9; |
|||
subtype Valid_Number is Number range 1 .. 9; |
|||
type Board is array (Valid_Number, Valid_Number) of Number; |
|||
function Check_Row (Data : in Board; Row : in Valid_Number) return Boolean is |
|||
Seen : array (Valid_Number) of Boolean := (others => False); |
|||
The_Number : Number; |
|||
begin |
|||
for Column in Data'Range (2) loop |
|||
The_Number := Data (Row, Column); |
|||
if The_Number in Valid_Number then |
|||
if Seen (The_Number) then |
|||
return False; |
|||
end if; |
|||
Seen (The_Number) := True; |
|||
end if; |
|||
end loop; |
|||
return True; |
|||
end Check_Row; |
|||
function Check_Column (Data : in Board; Column : in Valid_Number) return Boolean is |
|||
Seen : array (Valid_Number) of Boolean := (others => False); |
|||
The_Number : Number; |
|||
begin |
|||
for Row in Data'Range (1) loop |
|||
The_Number := Data (Row, Column); |
|||
if The_Number in Valid_Number then |
|||
if Seen (The_Number) then |
|||
return False; |
|||
end if; |
|||
Seen (The_Number) := True; |
|||
end if; |
|||
end loop; |
|||
return True; |
|||
end Check_Column; |
|||
function Check_Square (Data : in Board; Row, Column : in Valid_Number) return Boolean is |
|||
Seen : array (Valid_Number) of Boolean := (others => False); |
|||
The_Number : Number; |
|||
Row_Offset : constant Number := ((Row - 1) / 3) * 3; |
|||
Column_Offset : constant Number := ((Column - 1) / 3) * 3; |
|||
begin |
|||
for Sub_Row in 1 .. 3 loop |
|||
for Sub_Column in 1 .. 3 loop |
|||
The_Number := Data (Row_Offset + Sub_Row, Column_Offset + Sub_Column); |
|||
if The_Number in Valid_Number then |
|||
if Seen (The_Number) then |
|||
return False; |
|||
end if; |
|||
Seen (The_Number) := True; |
|||
end if; |
|||
end loop; |
|||
end loop; |
|||
return True; |
|||
end Check_Square; |
|||
function Is_Valid (Data : in Board) return Boolean is |
|||
Result : Boolean := True; |
|||
begin |
|||
for Row in Data'Range (1) loop |
|||
Result := Result and Check_Row (Data, Row); |
|||
end loop; |
|||
for Column in Data'Range (2) loop |
|||
Result := Result and Check_Column (Data, Column); |
|||
end loop; |
|||
for Square_Row in 1 .. 3 loop |
|||
for Square_Column in 1 .. 3 loop |
|||
Result := Result and Check_Square (Data, Square_Row * 3, Square_Column * 3); |
|||
end loop; |
|||
end loop; |
|||
return Result; |
|||
end Is_Valid; |
|||
Unsolvable : Exception; |
|||
procedure Solve (Data : in out Board) is |
|||
Solved : Boolean := False; |
|||
-- Try all possible values for given cell and continue with next cell. |
|||
procedure Place_Number (Row, Column : Valid_Number) is |
|||
Next_Row : Valid_Number := Row; |
|||
Next_Column : Valid_Number := Column; |
|||
Last : Boolean := False; |
|||
begin |
|||
-- determine if this is the last cell or else the next cell coordinates |
|||
if Row = Data'Last (1) and then Column = Data'Last (2) then |
|||
Last := True; |
|||
elsif Row = Data'Last (1) then |
|||
Next_Row := Data'First (1); |
|||
Next_Column := Column + 1; |
|||
else |
|||
Next_Row := Row + 1; |
|||
end if; |
|||
-- only need to try values for nonvalid cell entries (0) |
|||
if Data (Row, Column) not in Valid_Number then |
|||
-- try all possible values |
|||
for Test in Valid_Number loop |
|||
-- set the cell |
|||
Data (Row, Column) := Test; |
|||
if Is_Valid (Data) then |
|||
-- the last cell was processed and lead to a valid sudoku |
|||
-- this means all cells have valid entries -> solved. |
|||
if Last then |
|||
Solved := True; |
|||
return; |
|||
else |
|||
-- try next cells |
|||
Place_Number (Next_Row, Next_Column); |
|||
-- if we have a solved sudoku, exit procedure. |
|||
if Solved then |
|||
return; |
|||
end if; |
|||
end if; |
|||
end if; |
|||
-- reset the cell, it will be tried later again |
|||
Data (Row, Column) := 0; |
|||
end loop; |
|||
elsif Last then |
|||
-- last cell, already valid, it is solved and there is nothing to do |
|||
Solved := True; |
|||
else |
|||
-- this cell already has a value, continue to next |
|||
Place_Number (Next_Row, Next_Column); |
|||
end if; |
|||
end Place_Number; |
|||
begin |
|||
-- only accept sudokus without inconsistencies |
|||
if not Is_Valid (Data) then |
|||
raise Constraint_Error; |
|||
end if; |
|||
-- start with first cell |
|||
Place_Number (Data'First (1), Data'First (2)); |
|||
-- tried all combinations without success -> unsolvable. |
|||
if not Solved then |
|||
raise Unsolvable; |
|||
end if; |
|||
end Solve; |
|||
procedure Print_Board (Data : in Board) is |
|||
package Number_IO is new Ada.Text_IO.Integer_IO (Number); |
|||
begin |
|||
for X in Data'Range (1) loop |
|||
for Y in Data'Range (2) loop |
|||
Number_IO.Put (Data (X, Y)); |
|||
end loop; |
|||
Ada.Text_IO.New_Line; |
|||
end loop; |
|||
end Print_Board; |
|||
Sample_Board : Board := (1 => (3, 9, 4, 0, 0, 2, 6, 7, 0), |
|||
2 => (0, 0, 0, 3, 0, 0, 4, 0, 0), |
|||
3 => (5, 0, 0, 6, 9, 0, 0, 2, 0), |
|||
4 => (0, 4, 5, 0, 0, 0, 9, 0, 0), |
|||
5 => (6, 0, 0, 0, 0, 0, 0, 0, 7), |
|||
6 => (0, 0, 7, 0, 0, 0, 5, 8, 0), |
|||
7 => (0, 1, 0, 0, 6, 7, 0, 0, 8), |
|||
8 => (0, 0, 9, 0, 0, 8, 0, 0, 0), |
|||
9 => (0, 2, 6, 4, 0, 0, 7, 3, 5)); |
|||
begin |
|||
Ada.Text_IO.Put_Line ("Unsolved:"); |
|||
Print_Board (Sample_Board); |
|||
Solve (Sample_Board); |
|||
Ada.Text_IO.Put_Line ("Solved:"); |
|||
Print_Board (Sample_Board); |
|||
end Sudoku;</lang> |
|||
Output: |
|||
<pre>Unsolved: |
|||
3 9 4 0 0 2 6 7 0 |
|||
0 0 0 3 0 0 4 0 0 |
|||
5 0 0 6 9 0 0 2 0 |
|||
0 4 5 0 0 0 9 0 0 |
|||
6 0 0 0 0 0 0 0 7 |
|||
0 0 7 0 0 0 5 8 0 |
|||
0 1 0 0 6 7 0 0 8 |
|||
0 0 9 0 0 8 0 0 0 |
|||
0 2 6 4 0 0 7 3 5 |
|||
Solved: |
|||
3 9 4 8 5 2 6 7 1 |
|||
2 6 8 3 7 1 4 5 9 |
|||
5 7 1 6 9 4 8 2 3 |
|||
1 4 5 7 8 3 9 6 2 |
|||
6 8 2 9 4 5 3 1 7 |
|||
9 3 7 1 2 6 5 8 4 |
|||
4 1 3 5 6 7 2 9 8 |
|||
7 5 9 2 3 8 1 4 6 |
|||
8 2 6 4 1 9 7 3 5</pre> |
|||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
Revision as of 14:01, 16 December 2010
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
Solve a partially filled-in normal 9x9 Sudoku grid and display the result in a human-readable format. Algorithmics of Sudoku may help implement this.
Ada
<lang Ada>with Ada.Text_IO; procedure Sudoku is
subtype Number is Natural range 0 .. 9; subtype Valid_Number is Number range 1 .. 9; type Board is array (Valid_Number, Valid_Number) of Number;
function Check_Row (Data : in Board; Row : in Valid_Number) return Boolean is Seen : array (Valid_Number) of Boolean := (others => False); The_Number : Number; begin for Column in Data'Range (2) loop The_Number := Data (Row, Column); if The_Number in Valid_Number then if Seen (The_Number) then return False; end if; Seen (The_Number) := True; end if; end loop; return True; end Check_Row;
function Check_Column (Data : in Board; Column : in Valid_Number) return Boolean is Seen : array (Valid_Number) of Boolean := (others => False); The_Number : Number; begin for Row in Data'Range (1) loop The_Number := Data (Row, Column); if The_Number in Valid_Number then if Seen (The_Number) then return False; end if; Seen (The_Number) := True; end if; end loop; return True; end Check_Column;
function Check_Square (Data : in Board; Row, Column : in Valid_Number) return Boolean is Seen : array (Valid_Number) of Boolean := (others => False); The_Number : Number; Row_Offset : constant Number := ((Row - 1) / 3) * 3; Column_Offset : constant Number := ((Column - 1) / 3) * 3; begin for Sub_Row in 1 .. 3 loop for Sub_Column in 1 .. 3 loop The_Number := Data (Row_Offset + Sub_Row, Column_Offset + Sub_Column); if The_Number in Valid_Number then if Seen (The_Number) then return False; end if; Seen (The_Number) := True; end if; end loop; end loop; return True; end Check_Square;
function Is_Valid (Data : in Board) return Boolean is Result : Boolean := True; begin for Row in Data'Range (1) loop Result := Result and Check_Row (Data, Row); end loop; for Column in Data'Range (2) loop Result := Result and Check_Column (Data, Column); end loop; for Square_Row in 1 .. 3 loop for Square_Column in 1 .. 3 loop Result := Result and Check_Square (Data, Square_Row * 3, Square_Column * 3); end loop; end loop; return Result; end Is_Valid;
Unsolvable : Exception;
procedure Solve (Data : in out Board) is Solved : Boolean := False; -- Try all possible values for given cell and continue with next cell. procedure Place_Number (Row, Column : Valid_Number) is Next_Row : Valid_Number := Row; Next_Column : Valid_Number := Column; Last : Boolean := False; begin -- determine if this is the last cell or else the next cell coordinates if Row = Data'Last (1) and then Column = Data'Last (2) then Last := True; elsif Row = Data'Last (1) then Next_Row := Data'First (1); Next_Column := Column + 1; else Next_Row := Row + 1; end if; -- only need to try values for nonvalid cell entries (0) if Data (Row, Column) not in Valid_Number then -- try all possible values for Test in Valid_Number loop -- set the cell Data (Row, Column) := Test; if Is_Valid (Data) then -- the last cell was processed and lead to a valid sudoku -- this means all cells have valid entries -> solved. if Last then Solved := True; return; else -- try next cells Place_Number (Next_Row, Next_Column); -- if we have a solved sudoku, exit procedure. if Solved then return; end if; end if; end if; -- reset the cell, it will be tried later again Data (Row, Column) := 0; end loop; elsif Last then -- last cell, already valid, it is solved and there is nothing to do Solved := True; else -- this cell already has a value, continue to next Place_Number (Next_Row, Next_Column); end if; end Place_Number; begin -- only accept sudokus without inconsistencies if not Is_Valid (Data) then raise Constraint_Error; end if; -- start with first cell Place_Number (Data'First (1), Data'First (2)); -- tried all combinations without success -> unsolvable. if not Solved then raise Unsolvable; end if; end Solve;
procedure Print_Board (Data : in Board) is package Number_IO is new Ada.Text_IO.Integer_IO (Number); begin for X in Data'Range (1) loop for Y in Data'Range (2) loop Number_IO.Put (Data (X, Y)); end loop; Ada.Text_IO.New_Line; end loop; end Print_Board;
Sample_Board : Board := (1 => (3, 9, 4, 0, 0, 2, 6, 7, 0), 2 => (0, 0, 0, 3, 0, 0, 4, 0, 0), 3 => (5, 0, 0, 6, 9, 0, 0, 2, 0), 4 => (0, 4, 5, 0, 0, 0, 9, 0, 0), 5 => (6, 0, 0, 0, 0, 0, 0, 0, 7), 6 => (0, 0, 7, 0, 0, 0, 5, 8, 0), 7 => (0, 1, 0, 0, 6, 7, 0, 0, 8), 8 => (0, 0, 9, 0, 0, 8, 0, 0, 0), 9 => (0, 2, 6, 4, 0, 0, 7, 3, 5));
begin
Ada.Text_IO.Put_Line ("Unsolved:"); Print_Board (Sample_Board); Solve (Sample_Board); Ada.Text_IO.Put_Line ("Solved:"); Print_Board (Sample_Board);
end Sudoku;</lang>
Output:
Unsolved: 3 9 4 0 0 2 6 7 0 0 0 0 3 0 0 4 0 0 5 0 0 6 9 0 0 2 0 0 4 5 0 0 0 9 0 0 6 0 0 0 0 0 0 0 7 0 0 7 0 0 0 5 8 0 0 1 0 0 6 7 0 0 8 0 0 9 0 0 8 0 0 0 0 2 6 4 0 0 7 3 5 Solved: 3 9 4 8 5 2 6 7 1 2 6 8 3 7 1 4 5 9 5 7 1 6 9 4 8 2 3 1 4 5 7 8 3 9 6 2 6 8 2 9 4 5 3 1 7 9 3 7 1 2 6 5 8 4 4 1 3 5 6 7 2 9 8 7 5 9 2 3 8 1 4 6 8 2 6 4 1 9 7 3 5
AutoHotkey
<lang AutoHotkey>#SingleInstance, Force SetBatchLines, -1 SetTitleMatchMode, 3
Loop 9 { r := A_Index, y := r*17-8 + (A_Index >= 7 ? 4 : A_Index >= 4 ? 2 : 0) Loop 9 { c := A_Index, x := c*17+5 + (A_Index >= 7 ? 4 : A_Index >= 4 ? 2 : 0) Gui, Add, Edit, x%x% y%y% w17 h17 v%r%_%c% Center Number Limit1 gNext } } Gui, Add, Button, vButton gSolve w175 x10 Center, Solve Gui, Add, Text, vMsg r3, Enter Sudoku puzzle and click Solve Gui, Show,, Sudoku Solver
Return
Solve:
Gui, Submit, NoHide Loop 9 { r := A_Index Loop 9 If (%r%_%A_Index% = "") puzzle .= "@" Else puzzle .= %r%_%A_Index% } s := A_TickCount answer := Sudoku(puzzle) iterations := ErrorLevel e := A_TickCount seconds := (e-s)/1000 StringSplit, a, answer, | Loop 9 { r := A_Index Loop 9 { b := (r*9)+A_Index-9 GuiControl,, %r%_%A_Index%, % a%b% GuiControl, +ReadOnly, %r%_%A_Index% } } if answer GuiControl,, Msg, Solved!`nTime: %seconds%s`nIterations: %iterations% else GuiControl,, Msg, Failed! :(`nTime: %seconds%s`nIterations: %iterations% GuiControl,, Button, Again! GuiControl, +gAgain, Button
return
GuiClose:
ExitApp
Again:
Reload
- IfWinActive, Sudoku Solver
~*Enter::GoSub % GetKeyState( "Shift", "P" ) ? "~Up" : "~Down" ~Up::
GuiControlGet, f, focus StringTrimLeft, f, f, 4 f := ((f >= 1 && f <= 9) ? f+72 : f-9) GuiControl, Focus, Edit%f%
return ~Down::
GuiControlGet, f, focus StringTrimLeft, f, f, 4 f := ((f >= 73 && f <= 81) ? f-72 : f + 9) GuiControl, Focus, Edit%f%
return ~Left::
GuiControlGet, f, focus StringTrimLeft, f, f, 4 f := Mod(f + 79, 81) + 1 GuiControl, Focus, Edit%f%
return Next: ~Right::
GuiControlGet, f, focus StringTrimLeft, f, f, 4 f := Mod(f, 81) + 1 GuiControl, Focus, Edit%f%
return
- IfWinActive
- Functions Start here
Sudoku( p ) { ;ErrorLevel contains the number of iterations
p := RegExReplace(p, "[^1-9@]"), ErrorLevel := 0 ;format puzzle as single line string return Sudoku_Display(Sudoku_Solve(p))
}
Sudoku_Solve( p, d = 0 ) { ;d is 0-based
- http://www.autohotkey.com/forum/topic46679.html
- p
- 81 character puzzle string
- (concat all 9 rows of 9 chars each)
- givens represented as chars 1-9
- fill-ins as any non-null, non 1-9 char
- d
- used internally. omit on initial call
- returns
- 81 char string with non-givens replaced with valid solution
If (d >= 81), ErrorLevel++ return p ;this is 82nd iteration, so it has successfully finished iteration 81 If InStr( "123456789", SubStr(p, d+1, 1) ) ;this depth is a given, skip through return Sudoku_Solve(p, d+1) m := Sudoku_Constraints(p,d) ;a string of this level's constraints. ; (these will not change for all 9 loops) Loop 9 { If InStr(m, A_Index) Continue NumPut(Asc(A_Index), p, d, "Char") If r := Sudoku_Solve(p, d+1) return r } return 0
}
Sudoku_Constraints( ByRef p, d ) {
- returns a string of the constraints for a particular position
c := Mod(d,9) , r := (d - c) // 9 , b := r//3*27 + c//3*3 + 1 ;convert to 1-based , c++ return "" ; row: . SubStr(p, r * 9 + 1, 9) ; column: . SubStr(p,c ,1) SubStr(p,c+9 ,1) SubStr(p,c+18,1) . SubStr(p,c+27,1) SubStr(p,c+36,1) SubStr(p,c+45,1) . SubStr(p,c+54,1) SubStr(p,c+63,1) SubStr(p,c+72,1) ;box . SubStr(p, b, 3) SubStr(p, b+9, 3) SubStr(p, b+18, 3)
}
Sudoku_Display( p ) {
If StrLen(p) = 81 loop 81 r .= SubStr(p, A_Index, 1) . "|" return r
}</lang>
BCPL
<lang BCPL>// This can be run using Cintcode BCPL freely available from www.cl.cam.ac.uk/users/mr10.
// This is a really naive program to solve Su Doku problems. Even so it is usually quite fast.
// SuDoku consists of a 9x9 grid of cells. Each cell should contain // a digit in the range 1..9. Every row, column and major 3x3 // square should contain all the digits 1..9. Some cells have // given values. The problem is to find digits to place in // the unspecified cells satisfying the constraints.
// A typical problem is:
// - - - 6 3 8 - - - // 7 - 6 - - - 3 - 5 // - 1 - - - - - 4 -
// - - 8 7 1 2 4 - - // - 9 - - - - - 5 - // - - 2 5 6 9 1 - -
// - 3 - - - - - 1 - // 1 - 5 - - - 6 - 8 // - - - 1 8 4 - - -
SECTION "sudoku"
GET "libhdr"
GLOBAL { count:ug
// The 9x9 board
a1; a2; a3; a4; a5; a6; a7; a8; a9 b1; b2; b3; b4; b5; b6; b7; b8; b9 c1; c2; c3; c4; c5; c6; c7; c8; c9 d1; d2; d3; d4; d5; d6; d7; d8; d9 e1; e2; e3; e4; e5; e6; e7; e8; e9 f1; f2; f3; f4; f5; f6; f7; f8; f9 g1; g2; g3; g4; g5; g6; g7; g8; g9 h1; h2; h3; h4; h5; h6; h7; h8; h9 i1; i2; i3; i4; i5; i6; i7; i8; i9 }
MANIFEST { N1=1<<0; N2=1<<1; N3=1<<2; N4=1<<3; N5=1<<4; N6=1<<5; N7=1<<6; N8=1<<7; N9=1<<8 }
LET start() = VALOF { count := 0
initboard() prboard() ta1() writef("*n*nTotal number of solutions: %n*n", count) RESULTIS 0
}
AND initboard() BE { a1, a2, a3, a4, a5, a6, a7, a8, a9 := 0, 0, 0, N6,N3,N8, 0, 0, 0 b1, b2, b3, b4, b5, b6, b7, b8, b9 := N7, 0,N6, 0, 0, 0, N3, 0,N5 c1, c2, c3, c4, c5, c6, c7, c8, c9 := 0,N1, 0, 0, 0, 0, 0,N4, 0 d1, d2, d3, d4, d5, d6, d7, d8, d9 := 0, 0,N8, N7,N1,N2, N4, 0, 0 e1, e2, e3, e4, e5, e6, e7, e8, e9 := 0,N9, 0, 0, 0, 0, 0,N5, 0 f1, f2, f3, f4, f5, f6, f7, f8, f9 := 0, 0,N2, N5,N6,N9, N1, 0, 0 g1, g2, g3, g4, g5, g6, g7, g8, g9 := 0,N3, 0, 0, 0, 0, 0,N1, 0 h1, h2, h3, h4, h5, h6, h7, h8, h9 := N1, 0,N5, 0, 0, 0, N6, 0,N8 i1, i2, i3, i4, i5, i6, i7, i8, i9 := 0, 0, 0, N1,N8,N4, 0, 0, 0
// Un-comment the following to test that the backtracking works // giving 184 solutions. //h1, h2, h3, h4, h5, h6, h7, h8, h9 := N1, 0,N5, 0, 0, 0, N6, 0, 0 //i1, i2, i3, i4, i5, i6, i7, i8, i9 := 0, 0, 0, 0, 0, 0, 0, 0, 0 }
AND c(n) = VALOF SWITCHON n INTO { DEFAULT: RESULTIS '?'
CASE 0: RESULTIS '-' CASE N1: RESULTIS '1' CASE N2: RESULTIS '2' CASE N3: RESULTIS '3' CASE N4: RESULTIS '4' CASE N5: RESULTIS '5' CASE N6: RESULTIS '6' CASE N7: RESULTIS '7' CASE N8: RESULTIS '8' CASE N9: RESULTIS '9'
}
AND prboard() BE { LET form = "%c %c %c %c %c %c %c %c %c*n"
writef("*ncount = %n*n", count) newline() writef(form, c(a1),c(a2),c(a3),c(a4),c(a5),c(a6),c(a7),c(a8),c(a9)) writef(form, c(b1),c(b2),c(b3),c(b4),c(b5),c(b6),c(b7),c(b8),c(b9)) writef(form, c(c1),c(c2),c(c3),c(c4),c(c5),c(c6),c(c7),c(c8),c(c9)) newline() writef(form, c(d1),c(d2),c(d3),c(d4),c(d5),c(d6),c(d7),c(d8),c(d9)) writef(form, c(e1),c(e2),c(e3),c(e4),c(e5),c(e6),c(e7),c(e8),c(e9)) writef(form, c(f1),c(f2),c(f3),c(f4),c(f5),c(f6),c(f7),c(f8),c(f9)) newline() writef(form, c(g1),c(g2),c(g3),c(g4),c(g5),c(g6),c(g7),c(g8),c(g9)) writef(form, c(h1),c(h2),c(h3),c(h4),c(h5),c(h6),c(h7),c(h8),c(h9)) writef(form, c(i1),c(i2),c(i3),c(i4),c(i5),c(i6),c(i7),c(i8),c(i9))
newline()
//abort(1000) }
AND try(p, f, row, col, sq) BE { LET x = !p
TEST x THEN f() ELSE { LET bits = row|col|sq
//prboard() // writef("x=%n %b9*n", x, bits) //abort(1000)
IF (N1&bits)=0 DO { !p:=N1; f() } IF (N2&bits)=0 DO { !p:=N2; f() } IF (N3&bits)=0 DO { !p:=N3; f() } IF (N4&bits)=0 DO { !p:=N4; f() } IF (N5&bits)=0 DO { !p:=N5; f() } IF (N6&bits)=0 DO { !p:=N6; f() } IF (N7&bits)=0 DO { !p:=N7; f() } IF (N8&bits)=0 DO { !p:=N8; f() } IF (N9&bits)=0 DO { !p:=N9; f() } !p := 0 }
}
AND ta1() BE try(@a1, ta2, a1+a2+a3+a4+a5+a6+a7+a8+a9,
a1+b1+c1+d1+e1+f1+g1+h1+i1, a1+a2+a3+b1+b2+b3+c1+c2+c3)
AND ta2() BE try(@a2, ta3, a1+a2+a3+a4+a5+a6+a7+a8+a9,
a2+b2+c2+d2+e2+f2+g2+h2+i2, a1+a2+a3+b1+b2+b3+c1+c2+c3)
AND ta3() BE try(@a3, ta4, a1+a2+a3+a4+a5+a6+a7+a8+a9,
a3+b3+c3+d3+e3+f3+g3+h3+i3, a1+a2+a3+b1+b2+b3+c1+c2+c3)
AND ta4() BE try(@a4, ta5, a1+a2+a3+a4+a5+a6+a7+a8+a9,
a4+b4+c4+d4+e4+f4+g4+h4+i4, a4+a5+a6+b4+b5+b6+c4+c5+c6)
AND ta5() BE try(@a5, ta6, a1+a2+a3+a4+a5+a6+a7+a8+a9,
a5+b5+c5+d5+e5+f5+g5+h5+i5, a4+a5+a6+b4+b5+b6+c4+c5+c6)
AND ta6() BE try(@a6, ta7, a1+a2+a3+a4+a5+a6+a7+a8+a9,
a6+b6+c6+d6+e6+f6+g6+h6+i6, a4+a5+a6+b4+b5+b6+c4+c5+c6)
AND ta7() BE try(@a7, ta8, a1+a2+a3+a4+a5+a6+a7+a8+a9,
a7+b7+c7+d7+e7+f7+g7+h7+i7, a7+a8+a9+b7+b8+b9+c7+c8+c9)
AND ta8() BE try(@a8, ta9, a1+a2+a3+a4+a5+a6+a7+a8+a9,
a8+b8+c8+d8+e8+f8+g8+h8+i8, a7+a8+a9+b7+b8+b9+c7+c8+c9)
AND ta9() BE try(@a9, tb1, a1+a2+a3+a4+a5+a6+a7+a8+a9,
a9+b9+c9+d9+e9+f9+g9+h9+i9, a7+a8+a9+b7+b8+b9+c7+c8+c9)
AND tb1() BE try(@b1, tb2, b1+b2+b3+b4+b5+b6+b7+b8+b9,
a1+b1+c1+d1+e1+f1+g1+h1+i1, a1+a2+a3+b1+b2+b3+c1+c2+c3)
AND tb2() BE try(@b2, tb3, b1+b2+b3+b4+b5+b6+b7+b8+b9,
a2+b2+c2+d2+e2+f2+g2+h2+i2, a1+a2+a3+b1+b2+b3+c1+c2+c3)
AND tb3() BE try(@b3, tb4, b1+b2+b3+b4+b5+b6+b7+b8+b9,
a3+b3+c3+d3+e3+f3+g3+h3+i3, a1+a2+a3+b1+b2+b3+c1+c2+c3)
AND tb4() BE try(@b4, tb5, b1+b2+b3+b4+b5+b6+b7+b8+b9,
a4+b4+c4+d4+e4+f4+g4+h4+i4, a4+a5+a6+b4+b5+b6+c4+c5+c6)
AND tb5() BE try(@b5, tb6, b1+b2+b3+b4+b5+b6+b7+b8+b9,
a5+b5+c5+d5+e5+f5+g5+h5+i5, a4+a5+a6+b4+b5+b6+c4+c5+c6)
AND tb6() BE try(@b6, tb7, b1+b2+b3+b4+b5+b6+b7+b8+b9,
a6+b6+c6+d6+e6+f6+g6+h6+i6, a4+a5+a6+b4+b5+b6+c4+c5+c6)
AND tb7() BE try(@b7, tb8, b1+b2+b3+b4+b5+b6+b7+b8+b9,
a7+b7+c7+d7+e7+f7+g7+h7+i7, a7+a8+a9+b7+b8+b9+c7+c8+c9)
AND tb8() BE try(@b8, tb9, b1+b2+b3+b4+b5+b6+b7+b8+b9,
a8+b8+c8+d8+e8+f8+g8+h8+i8, a7+a8+a9+b7+b8+b9+c7+c8+c9)
AND tb9() BE try(@b9, tc1, b1+b2+b3+b4+b5+b6+b7+b8+b9,
a9+b9+c9+d9+e9+f9+g9+h9+i9, a7+a8+a9+b7+b8+b9+c7+c8+c9)
AND tc1() BE try(@c1, tc2, c1+c2+c3+c4+c5+c6+c7+c8+c9,
a1+b1+c1+d1+e1+f1+g1+h1+i1, a1+a2+a3+b1+b2+b3+c1+c2+c3)
AND tc2() BE try(@c2, tc3, c1+c2+c3+c4+c5+c6+c7+c8+c9,
a2+b2+c2+d2+e2+f2+g2+h2+i2, a1+a2+a3+b1+b2+b3+c1+c2+c3)
AND tc3() BE try(@c3, tc4, c1+c2+c3+c4+c5+c6+c7+c8+c9,
a3+b3+c3+d3+e3+f3+g3+h3+i3, a1+a2+a3+b1+b2+b3+c1+c2+c3)
AND tc4() BE try(@c4, tc5, c1+c2+c3+c4+c5+c6+c7+c8+c9,
a4+b4+c4+d4+e4+f4+g4+h4+i4, a4+a5+a6+b4+b5+b6+c4+c5+c6)
AND tc5() BE try(@c5, tc6, c1+c2+c3+c4+c5+c6+c7+c8+c9,
a5+b5+c5+d5+e5+f5+g5+h5+i5, a4+a5+a6+b4+b5+b6+c4+c5+c6)
AND tc6() BE try(@c6, tc7, c1+c2+c3+c4+c5+c6+c7+c8+c9,
a6+b6+c6+d6+e6+f6+g6+h6+i6, a4+a5+a6+b4+b5+b6+c4+c5+c6)
AND tc7() BE try(@c7, tc8, c1+c2+c3+c4+c5+c6+c7+c8+c9,
a7+b7+c7+d7+e7+f7+g7+h7+i7, a7+a8+a9+b7+b8+b9+c7+c8+c9)
AND tc8() BE try(@c8, tc9, c1+c2+c3+c4+c5+c6+c7+c8+c9,
a8+b8+c8+d8+e8+f8+g8+h8+i8, a7+a8+a9+b7+b8+b9+c7+c8+c9)
AND tc9() BE try(@c9, td1, c1+c2+c3+c4+c5+c6+c7+c8+c9,
a9+b9+c9+d9+e9+f9+g9+h9+i9, a7+a8+a9+b7+b8+b9+c7+c8+c9)
AND td1() BE try(@d1, td2, d1+d2+d3+d4+d5+d6+d7+d8+d9,
a1+b1+c1+d1+e1+f1+g1+h1+i1, d1+d2+d3+e1+e2+e3+f1+f2+f3)
AND td2() BE try(@d2, td3, d1+d2+d3+d4+d5+d6+d7+d8+d9,
a2+b2+c2+d2+e2+f2+g2+h2+i2, d1+d2+d3+e1+e2+e3+f1+f2+f3)
AND td3() BE try(@d3, td4, d1+d2+d3+d4+d5+d6+d7+d8+d9,
a3+b3+c3+d3+e3+f3+g3+h3+i3, d1+d2+d3+e1+e2+e3+f1+f2+f3)
AND td4() BE try(@d4, td5, d1+d2+d3+d4+d5+d6+d7+d8+d9,
a4+b4+c4+d4+e4+f4+g4+h4+i4, d4+d5+d6+e4+e5+e6+f4+f5+f6)
AND td5() BE try(@d5, td6, d1+d2+d3+d4+d5+d6+d7+d8+d9,
a5+b5+c5+d5+e5+f5+g5+h5+i5, d4+d5+d6+e4+e5+e6+f4+f5+f6)
AND td6() BE try(@d6, td7, d1+d2+d3+d4+d5+d6+d7+d8+d9,
a6+b6+c6+d6+e6+f6+g6+h6+i6, d4+d5+d6+e4+e5+e6+f4+f5+f6)
AND td7() BE try(@d7, td8, d1+d2+d3+d4+d5+d6+d7+d8+d9,
a7+b7+c7+d7+e7+f7+g7+h7+i7, d7+d8+d9+e7+e8+e9+f7+f8+f9)
AND td8() BE try(@d8, td9, d1+d2+d3+d4+d5+d6+d7+d8+d9,
a8+b8+c8+d8+e8+f8+g8+h8+i8, d7+d8+d9+e7+e8+e9+f7+f8+f9)
AND td9() BE try(@d9, te1, d1+d2+d3+d4+d5+d6+d7+d8+d9,
a9+b9+c9+d9+e9+f9+g9+h9+i9, d7+d8+d9+e7+e8+e9+f7+f8+f9)
AND te1() BE try(@e1, te2, e1+e2+e3+e4+e5+e6+e7+e8+e9,
a1+b1+c1+d1+e1+f1+g1+h1+i1, d1+d2+d3+e1+e2+e3+f1+f2+f3)
AND te2() BE try(@e2, te3, e1+e2+e3+e4+e5+e6+e7+e8+e9,
a2+b2+c2+d2+e2+f2+g2+h2+i2, d1+d2+d3+e1+e2+e3+f1+f2+f3)
AND te3() BE try(@e3, te4, e1+e2+e3+e4+e5+e6+e7+e8+e9,
a3+b3+c3+d3+e3+f3+g3+h3+i3, d1+d2+d3+e1+e2+e3+f1+f2+f3)
AND te4() BE try(@e4, te5, e1+e2+e3+e4+e5+e6+e7+e8+e9,
a4+b4+c4+d4+e4+f4+g4+h4+i4, d4+d5+d6+e4+e5+e6+f4+f5+f6)
AND te5() BE try(@e5, te6, e1+e2+e3+e4+e5+e6+e7+e8+e9,
a5+b5+c5+d5+e5+f5+g5+h5+i5, d4+d5+d6+e4+e5+e6+f4+f5+f6)
AND te6() BE try(@e6, te7, e1+e2+e3+e4+e5+e6+e7+e8+e9,
a6+b6+c6+d6+e6+f6+g6+h6+i6, d4+d5+d6+e4+e5+e6+f4+f5+f6)
AND te7() BE try(@e7, te8, e1+e2+e3+e4+e5+e6+e7+e8+e9,
a7+b7+c7+d7+e7+f7+g7+h7+i7, d7+d8+d9+e7+e8+e9+f7+f8+f9)
AND te8() BE try(@e8, te9, e1+e2+e3+e4+e5+e6+e7+e8+e9,
a8+b8+c8+d8+e8+f8+g8+h8+i8, d7+d8+d9+e7+e8+e9+f7+f8+f9)
AND te9() BE try(@e9, tf1, e1+e2+e3+e4+e5+e6+e7+e8+e9,
a9+b9+c9+d9+e9+f9+g9+h9+i9, d7+d8+d9+e7+e8+e9+f7+f8+f9)
AND tf1() BE try(@f1, tf2, f1+f2+f3+f4+f5+f6+f7+f8+f9,
a1+b1+c1+d1+e1+f1+g1+h1+i1, d1+d2+d3+e1+e2+e3+f1+f2+f3)
AND tf2() BE try(@f2, tf3, f1+f2+f3+f4+f5+f6+f7+f8+f9,
a2+b2+c2+d2+e2+f2+g2+h2+i2, d1+d2+d3+e1+e2+e3+f1+f2+f3)
AND tf3() BE try(@f3, tf4, f1+f2+f3+f4+f5+f6+f7+f8+f9,
a3+b3+c3+d3+e3+f3+g3+h3+i3, d1+d2+d3+e1+e2+e3+f1+f2+f3)
AND tf4() BE try(@f4, tf5, f1+f2+f3+f4+f5+f6+f7+f8+f9,
a4+b4+c4+d4+e4+f4+g4+h4+i4, d4+d5+d6+e4+e5+e6+f4+f5+f6)
AND tf5() BE try(@f5, tf6, f1+f2+f3+f4+f5+f6+f7+f8+f9,
a5+b5+c5+d5+e5+f5+g5+h5+i5, d4+d5+d6+e4+e5+e6+f4+f5+f6)
AND tf6() BE try(@f6, tf7, f1+f2+f3+f4+f5+f6+f7+f8+f9,
a6+b6+c6+d6+e6+f6+g6+h6+i6, d4+d5+d6+e4+e5+e6+f4+f5+f6)
AND tf7() BE try(@f7, tf8, f1+f2+f3+f4+f5+f6+f7+f8+f9,
a7+b7+c7+d7+e7+f7+g7+h7+i7, d7+d8+d9+e7+e8+e9+f7+f8+f9)
AND tf8() BE try(@f8, tf9, f1+f2+f3+f4+f5+f6+f7+f8+f9,
a8+b8+c8+d8+e8+f8+g8+h8+i8, d7+d8+d9+e7+e8+e9+f7+f8+f9)
AND tf9() BE try(@f9, tg1, f1+f2+f3+f4+f5+f6+f7+f8+f9,
a9+b9+c9+d9+e9+f9+g9+h9+i9, d7+d8+d9+e7+e8+e9+f7+f8+f9)
AND tg1() BE try(@g1, tg2, g1+g2+g3+g4+g5+g6+g7+g8+g9,
a1+b1+c1+d1+e1+f1+g1+h1+i1, g1+g2+g3+h1+h2+h3+i1+i2+i3)
AND tg2() BE try(@g2, tg3, g1+g2+g3+g4+g5+g6+g7+g8+g9,
a2+b2+c2+d2+e2+f2+g2+h2+i2, g1+g2+g3+h1+h2+h3+i1+i2+i3)
AND tg3() BE try(@g3, tg4, g1+g2+g3+g4+g5+g6+g7+g8+g9,
a3+b3+c3+d3+e3+f3+g3+h3+i3, g1+g2+g3+h1+h2+h3+i1+i2+i3)
AND tg4() BE try(@g4, tg5, g1+g2+g3+g4+g5+g6+g7+g8+g9,
a4+b4+c4+d4+e4+f4+g4+h4+i4, g4+g5+g6+h4+h5+h6+i4+i5+i6)
AND tg5() BE try(@g5, tg6, g1+g2+g3+g4+g5+g6+g7+g8+g9,
a5+b5+c5+d5+e5+f5+g5+h5+i5, g4+g5+g6+h4+h5+h6+i4+i5+i6)
AND tg6() BE try(@g6, tg7, g1+g2+g3+g4+g5+g6+g7+g8+g9,
a6+b6+c6+d6+e6+f6+g6+h6+i6, g4+g5+g6+h4+h5+h6+i4+i5+i6)
AND tg7() BE try(@g7, tg8, g1+g2+g3+g4+g5+g6+g7+g8+g9,
a7+b7+c7+d7+e7+f7+g7+h7+i7, g7+g8+g9+h7+h8+h9+i7+i8+i9)
AND tg8() BE try(@g8, tg9, g1+g2+g3+g4+g5+g6+g7+g8+g9,
a8+b8+c8+d8+e8+f8+g8+h8+i8, g7+g8+g9+h7+h8+h9+i7+i8+i9)
AND tg9() BE try(@g9, th1, g1+g2+g3+g4+g5+g6+g7+g8+g9,
a9+b9+c9+d9+e9+f9+g9+h9+i9, g7+g8+g9+h7+h8+h9+i7+i8+i9)
AND th1() BE try(@h1, th2, h1+h2+h3+h4+h5+h6+h7+h8+h9,
a1+b1+c1+d1+e1+f1+g1+h1+i1, g1+g2+g3+h1+h2+h3+i1+i2+i3)
AND th2() BE try(@h2, th3, h1+h2+h3+h4+h5+h6+h7+h8+h9,
a2+b2+c2+d2+e2+f2+g2+h2+i2, g1+g2+g3+h1+h2+h3+i1+i2+i3)
AND th3() BE try(@h3, th4, h1+h2+h3+h4+h5+h6+h7+h8+h9,
a3+b3+c3+d3+e3+f3+g3+h3+i3, g1+g2+g3+h1+h2+h3+i1+i2+i3)
AND th4() BE try(@h4, th5, h1+h2+h3+h4+h5+h6+h7+h8+h9,
a4+b4+c4+d4+e4+f4+g4+h4+i4, g4+g5+g6+h4+h5+h6+i4+i5+i6)
AND th5() BE try(@h5, th6, h1+h2+h3+h4+h5+h6+h7+h8+h9,
a5+b5+c5+d5+e5+f5+g5+h5+i5, g4+g5+g6+h4+h5+h6+i4+i5+i6)
AND th6() BE try(@h6, th7, h1+h2+h3+h4+h5+h6+h7+h8+h9,
a6+b6+c6+d6+e6+f6+g6+h6+i6, g4+g5+g6+h4+h5+h6+i4+i5+i6)
AND th7() BE try(@h7, th8, h1+h2+h3+h4+h5+h6+h7+h8+h9,
a7+b7+c7+d7+e7+f7+g7+h7+i7, g7+g8+g9+h7+h8+h9+i7+i8+i9)
AND th8() BE try(@h8, th9, h1+h2+h3+h4+h5+h6+h7+h8+h9,
a8+b8+c8+d8+e8+f8+g8+h8+i8, g7+g8+g9+h7+h8+h9+i7+i8+i9)
AND th9() BE try(@h9, ti1, h1+h2+h3+h4+h5+h6+h7+h8+h9,
a9+b9+c9+d9+e9+f9+g9+h9+i9, g7+g8+g9+h7+h8+h9+i7+i8+i9)
AND ti1() BE try(@i1, ti2, i1+i2+i3+i4+i5+i6+i7+i8+i9,
a1+b1+c1+d1+e1+f1+g1+h1+i1, g1+g2+g3+h1+h2+h3+i1+i2+i3)
AND ti2() BE try(@i2, ti3, i1+i2+i3+i4+i5+i6+i7+i8+i9,
a2+b2+c2+d2+e2+f2+g2+h2+i2, g1+g2+g3+h1+h2+h3+i1+i2+i3)
AND ti3() BE try(@i3, ti4, i1+i2+i3+i4+i5+i6+i7+i8+i9,
a3+b3+c3+d3+e3+f3+g3+h3+i3, g1+g2+g3+h1+h2+h3+i1+i2+i3)
AND ti4() BE try(@i4, ti5, i1+i2+i3+i4+i5+i6+i7+i8+i9,
a4+b4+c4+d4+e4+f4+g4+h4+i4, g4+g5+g6+h4+h5+h6+i4+i5+i6)
AND ti5() BE try(@i5, ti6, i1+i2+i3+i4+i5+i6+i7+i8+i9,
a5+b5+c5+d5+e5+f5+g5+h5+i5, g4+g5+g6+h4+h5+h6+i4+i5+i6)
AND ti6() BE try(@i6, ti7, i1+i2+i3+i4+i5+i6+i7+i8+i9,
a6+b6+c6+d6+e6+f6+g6+h6+i6, g4+g5+g6+h4+h5+h6+i4+i5+i6)
AND ti7() BE try(@i7, ti8, i1+i2+i3+i4+i5+i6+i7+i8+i9,
a7+b7+c7+d7+e7+f7+g7+h7+i7, g7+g8+g9+h7+h8+h9+i7+i8+i9)
AND ti8() BE try(@i8, ti9, i1+i2+i3+i4+i5+i6+i7+i8+i9,
a8+b8+c8+d8+e8+f8+g8+h8+i8, g7+g8+g9+h7+h8+h9+i7+i8+i9)
AND ti9() BE try(@i9, suc, i1+i2+i3+i4+i5+i6+i7+i8+i9,
a9+b9+c9+d9+e9+f9+g9+h9+i9, g7+g8+g9+h7+h8+h9+i7+i8+i9)
AND suc() BE { count := count + 1
prboard()
} </lang>
C
See e.g. this GPLed solver written in C.
C++
After the Java solution. <lang cpp>
- include <iostream>
using namespace std;
class SudokuSolver { private:
int* grid;
public:
SudokuSolver(string s) { grid = new int[81]; for (unsigned int i = 0; i < s.length(); i++) { grid[i] = (int) (s[i] - '0'); } }
~SudokuSolver() { delete [] grid; }
void solve() { try { placeNumber(0); cout << "Unsolvable!" << endl; } catch (char* ex) { cout << ex << endl; cout << this->toString() << endl; } }
void placeNumber(int pos) { if (pos == 81) { throw (char*) "Finished!"; } if (grid[pos] > 0) { placeNumber(pos + 1); return; } for (int n = 1; n <= 9; n++) { if (checkValidity(n, pos % 9, pos / 9)) { grid[pos] = n; placeNumber(pos + 1); grid[pos] = 0; } } }
bool checkValidity(int val, int x, int y) { for (int i = 0; i < 9; i++) { if (grid[y * 9 + i] == val || grid[i * 9 + x] == val) return false; } int startX = (x / 3) * 3; int startY = (y / 3) * 3; for (int i = startY; i < startY + 3; i++) { for (int j = startX; j < startX + 3; j++) { if (grid[i * 9 + j] == val) return false; } } return true; }
string toString() { string sb; for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { char c[2]; c[0] = grid[i * 9 + j] + '0'; c[1] = '\0'; sb.append(c); sb.append(" "); if (j == 2 || j == 5) sb.append("| "); } sb.append("\n"); if (i == 2 || i == 5) sb.append("------+-------+------\n"); } return sb; }
};
int main() {
SudokuSolver ss( (string) "850002400" + (string) "720000009" + (string) "004000000" + (string) "000107002" + (string) "305000900" + (string) "040000000" + (string) "000080070" + (string) "017000000" + (string) "000036040" ); ss.solve();
} </lang>
Clojure
<lang clojure>(ns sudoku
(:use [clojure.contrib.math :only (sqrt)]))
(defn print-grid [grid]
(doseq [y (range (count grid))] (doseq [x (range (count grid))] (print (retrieve grid x y) " ")) (println)) (println))
(defn retrieve [grid x y]
(get (get grid y) x))
(defn store [grid x y n]
(assoc grid y (assoc (get grid y) x n)))
(defn coordinates [grid x y]
(let [n (sqrt (count grid)) zx (* n (quot x n)) zy (* n (quot y n))] (for [x (range zx (+ zx n)) y (range zy (+ zy n))] [x y])))
(defn compatible? [grid x y n]
(or (= n (retrieve grid x y)) (and (zero? (retrieve grid x y)) (every? #(and (not= n (retrieve grid % y)) (not= n (retrieve grid x %))) (range (count grid))) (every? #(not= n (retrieve grid (first %) (second %))) (coordinates grid x y)))))
(defn solve [grid x y]
(let [m (count grid)] (if (= y m) (print-grid grid) (doseq [n (range 1 (inc m))] (when (compatible? grid x y n) (let [new-grid (store grid x y n)] (if (= x (dec m)) (solve new-grid 0 (inc y)) (solve new-grid (inc x) y))))))))
</lang>
<lang clojure>sudoku> (solve [[3 9 4 0 0 2 6 7 0]
[0 0 0 3 0 0 4 0 0] [5 0 0 6 9 0 0 2 0] [0 4 5 0 0 0 9 0 0] [6 0 0 0 0 0 0 0 7] [0 0 7 0 0 0 5 8 0] [0 1 0 0 6 7 0 0 8] [0 0 9 0 0 8 0 0 0] [0 2 6 4 0 0 7 3 5]] 0 0)
3 9 4 8 5 2 6 7 1 2 6 8 3 7 1 4 5 9 5 7 1 6 9 4 8 2 3 1 4 5 7 8 3 9 6 2 6 8 2 9 4 5 3 1 7 9 3 7 1 2 6 5 8 4 4 1 3 5 6 7 2 9 8 7 5 9 2 3 8 1 4 6 8 2 6 4 1 9 7 3 5
nil </lang>
Common Lisp
A simple solver without optimizations (except for pre-computing the possible entries of a cell).
<lang lisp>(defun row-neighbors (row column grid &aux (neighbors '()))
(dotimes (i 9 neighbors) (let ((x (aref grid row i))) (unless (or (eq '_ x) (= i column)) (push x neighbors)))))
(defun column-neighbors (row column grid &aux (neighbors '()))
(dotimes (i 9 neighbors) (let ((x (aref grid i column))) (unless (or (eq x '_) (= i row)) (push x neighbors)))))
(defun square-neighbors (row column grid &aux (neighbors '()))
(let* ((rmin (* 3 (floor row 3))) (rmax (+ rmin 3)) (cmin (* 3 (floor column 3))) (cmax (+ cmin 3))) (do ((r rmin (1+ r))) ((= r rmax) neighbors) (do ((c cmin (1+ c))) ((= c cmax)) (let ((x (aref grid r c))) (unless (or (eq x '_) (= r row) (= c column)) (push x neighbors)))))))
(defun choices (row column grid)
(nset-difference (list 1 2 3 4 5 6 7 8 9) (nconc (row-neighbors row column grid) (column-neighbors row column grid) (square-neighbors row column grid))))
(defun solve (grid &optional (row 0) (column 0))
(cond ((= row 9) grid) ((= column 9) (solve grid (1+ row) 0)) ((not (eq '_ (aref grid row column))) (solve grid row (1+ column))) (t (dolist (choice (choices row column grid) (setf (aref grid row column) '_)) (setf (aref grid row column) choice) (when (eq grid (solve grid row (1+ column))) (return grid))))))</lang>
Example:
> (defparameter *puzzle* #2A((3 9 4 _ _ 2 6 7 _) (_ _ _ 3 _ _ 4 _ _) (5 _ _ 6 9 _ _ 2 _) (_ 4 5 _ _ _ 9 _ _) (6 _ _ _ _ _ _ _ 7) (_ _ 7 _ _ _ 5 8 _) (_ 1 _ _ 6 7 _ _ 8) (_ _ 9 _ _ 8 _ _ _) (_ 2 6 4 _ _ 7 3 5))) *PUZZLE* > (pprint (solve *puzzle*)) #2A((3 9 4 8 5 2 6 7 1) (2 6 8 3 7 1 4 5 9) (5 7 1 6 9 4 8 2 3) (1 4 5 7 8 3 9 6 2) (6 8 2 9 4 5 3 1 7) (9 3 7 1 2 6 5 8 4) (4 1 3 5 6 7 2 9 8) (7 5 9 2 3 8 1 4 6) (8 2 6 4 1 9 7 3 5))
Curry
Copied from Curry: Example Programs.
<lang curry>
--- Solving Su Doku puzzles in Curry with FD constraints --- --- @author Michael Hanus --- @version December 2005
import CLPFD import List
-- Solving a Su Doku puzzle represented as a matrix of numbers (possibly free -- variables): sudoku :: Int -> Success sudoku m =
domain (concat m) 1 9 & -- define domain of all digits foldr1 (&) (map allDifferent m) & -- all rows contain different digits foldr1 (&) (map allDifferent (transpose m)) & -- all columns have different digits foldr1 (&) (map allDifferent (squaresOfNine m)) & -- all 3x3 squares are different labeling [FirstFailConstrained] (concat m)
-- translate a matrix into a list of small 3x3 squares squaresOfNine :: a -> a squaresOfNine [] = [] squaresOfNine (l1:l2:l3:ls) = group3Rows [l1,l2,l3] ++ squaresOfNine ls
group3Rows l123 = if null (head l123) then [] else
concatMap (take 3) l123 : group3Rows (map (drop 3) l123)
-- read a Su Doku specification written as a list of strings containing digits -- and spaces readSudoku :: [String] -> Int readSudoku s = map (map transDigit) s
where transDigit c = if c==' ' then x else ord c - ord '0' where x free
-- show a solved Su Doku matrix showSudoku :: Int -> String showSudoku = unlines . map (concatMap (\i->[chr (i + ord '0'),' ']))
-- the main function, e.g., evaluate (main s1): main s | sudoku m = putStrLn (showSudoku m)
where m = readSudoku s
s1 = ["9 2 5 ",
" 4 6 3 ", " 3 6", " 9 2 ", " 5 8 ", " 7 4 3", "7 1 ", " 5 2 4 ", " 1 6 9"]
s2 = ["819 5 ",
" 2 75 ", " 371 4 6 ", "4 59 1 ", "7 3 8 2", " 3 62 7", " 5 7 921 ", " 64 9 ", " 2 438"]
</lang>
D
<lang d>import std.stdio;
bool[char]genFull() {
return ['1':true, '2':true, '3':true, '4':true, '5':true, '6':true, '7':true, '8':true, '9':true];
} // these three functions assume that the number has not already been found bool[char]availRow(int x,int y,bool[char]available=genFull()) {
// x designates row, y designates column foreach(ele;puzzle[x]) { if (ele != '_') available.remove(ele); } return available;
}
bool[char]availCol(int x,int y,bool[char]available=genFull()) {
// x designates row, y designates column for(int i = 0;i<9;i++) { if (puzzle[i][y] != '_') available.remove(puzzle[i][y]); } return available;
}
bool[char]availBox(int x,int y,bool[char]available=genFull()) {
// x designates row, y designates column // get a base index for the boxes int bx = x/3;bx*=3; int by = y/3;by*=3; for(int i = 0;i<3;i++) for(int j = 0;j<3;j++) { if (puzzle[bx+i][by+j] != '_') available.remove(puzzle[bx+i][by+j]); } return available;
}
char[][]puzzle; void main() {
puzzle ~= "394__267_".dup; puzzle ~= "___3__4__".dup; puzzle ~= "5__69__2_".dup; puzzle ~= "_45___9__".dup; puzzle ~= "6_______7".dup; puzzle ~= "__7___58_".dup; puzzle ~= "_1__67__8".dup; puzzle ~= "__9__8___".dup; puzzle ~= "_264__735".dup; while(1) { bool done = true; foreach(i,row;puzzle) foreach(j,ref ele;row) if (ele == '_') { // poke at the elements that are _ auto remaining = availBox(i,j,availRow(i,j,availCol(i,j))); if (remaining.keys.length == 1) ele = remaining.keys[0]; else done = false; } if (done) break; } // write out completed puzzle writefln("Completed puzzle:"); foreach(row;puzzle) writefln("%s",row);
}</lang>
Forth
<lang forth>include lib/interprt.4th include lib/istype.4th include lib/argopen.4th
\ --------------------- \ Variables \ ---------------------
81 string sudokugrid 9 array sudoku_row 9 array sudoku_col 9 array sudoku_box
\ ------------- \ 4tH interface \ -------------
- >grid ( n2 a1 n1 -- n3)
rot dup >r 9 chars * sudokugrid + dup >r swap 0 do ( a1 a2) over i chars + c@ dup is-digit ( a1 a2 c f) if [char] 0 - over c! char+ else drop then loop ( a1 a2) nip r> - 9 / r> + ( n3)
0 s" 090004007" >grid s" 000007900" >grid s" 800000000" >grid s" 405800000" >grid s" 300000002" >grid s" 000009706" >grid s" 000000004" >grid s" 003500000" >grid s" 200600080" >grid drop
\ --------------------- \ Logic \ --------------------- \ Basically : \ Grid is parsed. All numbers are put into sets, which are \ implemented as bitmaps (sudoku_row, sudoku_col, sudoku_box) \ which represent sets of numbers in each row, column, box. \ only one specific instance of a number can exist in a \ particular set.
\ SOLVER is recursively called \ SOLVER looks for the next best guess using FINDNEXTSPACE \ tries this trail down... if fails, backtracks... and tries \ again.
\ Grid Related
- xy 9 * + ; \ x y -- offset ;
- getrow 9 / ;
- getcol 9 mod ;
- getbox dup getrow 3 / 3 * swap getcol 3 / + ;
\ Puts and gets numbers from/to grid only
- setnumber sudokugrid + c! ; \ n position --
- getnumber sudokugrid + c@ ;
- cleargrid sudokugrid 81 bounds do 0 i c! loop ;
\ -------------- \ Set related: sets are sudoku_row, sudoku_col, sudoku_box
\ ie x y -- ; adds x into bitmap y
- addbits_row cells sudoku_row + dup @ rot 1 swap lshift or swap ! ;
- addbits_col cells sudoku_col + dup @ rot 1 swap lshift or swap ! ;
- addbits_box cells sudoku_box + dup @ rot 1 swap lshift or swap ! ;
\ ie x y -- ; remove number x from bitmap y
- removebits_row cells sudoku_row + dup @ rot 1 swap lshift invert and swap ! ;
- removebits_col cells sudoku_col + dup @ rot 1 swap lshift invert and swap ! ;
- removebits_box cells sudoku_box + dup @ rot 1 swap lshift invert and swap ! ;
\ clears all bitsmaps to 0
- clearbitmaps 9 0 do i cells
0 over sudoku_row + ! 0 over sudoku_col + ! 0 swap sudoku_box + ! loop ;
\ Adds number to grid and sets
- addnumber \ number position --
2dup setnumber 2dup getrow addbits_row 2dup getcol addbits_col getbox addbits_box
\ Remove number from grid, and sets
- removenumber \ position --
dup getnumber swap 2dup getrow removebits_row 2dup getcol removebits_col 2dup getbox removebits_box nip 0 swap setnumber
\ gets bitmap at position, ie \ position -- bitmap
- getrow_bits getrow cells sudoku_row + @ ;
- getcol_bits getcol cells sudoku_col + @ ;
- getbox_bits getbox cells sudoku_box + @ ;
\ position -- composite bitmap (or'ed)
- getbits
dup getrow_bits over getcol_bits rot getbox_bits or or
\ algorithm from c.l.f circa 1995 ? Will Baden
- countbits ( number -- bits )
[HEX] DUP 55555555 AND SWAP 1 RSHIFT 55555555 AND + DUP 33333333 AND SWAP 2 RSHIFT 33333333 AND + DUP 0F0F0F0F AND SWAP 4 RSHIFT 0F0F0F0F AND + [DECIMAL] 255 MOD
\ Try tests a number in a said position of grid \ Returns true if it's possible, else false.
- try \ number position -- true/false
getbits 1 rot lshift and 0=
\ --------------
- parsegrid \ Parses Grid to fill sets.. Run before solver.
sudokugrid \ to ensure all numbers are parsed into sets/bitmaps 81 0 do dup i + c@ dup if dup i try if i addnumber else unloop drop drop FALSE exit then else drop then loop drop TRUE
\ Morespaces? manually checks for spaces ... \ Obviously this can be optimised to a count var, done initially \ Any additions/subtractions made to the grid could decrement \ a 'spaces' variable.
- morespaces?
0 sudokugrid 81 bounds do i c@ 0= if 1+ then loop ;
- findnextmove \ -- n ; n = index next item, if -1 finished.
-1 10 \ index prev_possibilities -- \ err... yeah... local variables, kind of...
81 0 do i sudokugrid + c@ 0= IF i getbits countbits 9 swap -
\ get bitmap and see how many possibilities \ stack diagram: \ index prev_possibilities new_possiblities --
2dup > if \ if new_possibilities < prev_possibilities... nip nip i swap \ new_index new_possibilies --
else \ else prev_possibilities < new possibilities, so:
drop \ new_index new_possibilies --
then THEN loop drop
\ findnextmove returns index of best next guess OR returns -1 \ if no more guesses. You then have to check to see if there are \ spaces left on the board unoccupied. If this is the case, you \ need to back up the recursion and try again.
- solver
findnextmove dup 0< if morespaces? if drop false exit else drop true exit then then
10 1 do i over try if i over addnumber recurse if drop unloop TRUE EXIT else dup removenumber then then loop
drop FALSE
\ SOLVER
- startsolving
clearbitmaps \ reparse bitmaps and reparse grid parsegrid \ just in case.. solver AND
\ --------------------- \ Display Grid \ ---------------------
\ Prints grid nicely
- .sudokugrid
CR CR sudokugrid 81 0 do dup i + c@ . i 1+ dup 3 mod 0= if dup 9 mod 0= if CR dup 27 mod 0= if dup 81 < if ." ------+-------+------" CR then then else ." | " then then drop loop drop CR
\ --------------------- \ Higher Level Words \ ---------------------
- checkifoccupied ( offset -- t/f)
sudokugrid + c@
- add ( n x y --)
xy 2dup dup checkifoccupied if dup removenumber then try if addnumber .sudokugrid else CR ." Not a valid move. " CR 2drop then
- rm
xy removenumber .sudokugrid
- clearit
cleargrid clearbitmaps .sudokugrid
- solveit
CR startsolving if ." Solution found!" CR .sudokugrid else ." No solution found!" CR CR then
- showit .sudokugrid ;
\ Print help menu
- help
CR ." Type clearit ; to clear grid " CR ." 1-9 x y add ; to add 1-9 to grid at x y (0 based) " CR ." x y rm ; to remove number at x y " CR ." showit ; redisplay grid " CR ." solveit ; to solve " CR ." help ; for help " CR CR
\ --------------------- \ Execution starts here \ ---------------------
- godoit
clearbitmaps parsegrid if CR ." Grid valid!" else CR ." Warning: grid invalid!" then .sudokugrid help
\ ------------- \ 4tH interface \ -------------
- read-sudoku
input 1 arg-open 0 begin dup 9 < while refill while 0 parse >grid repeat drop close
- bye quit ;
create wordlist \ dictionary
," clearit" ' clearit , ," add" ' add , ," rm" ' rm , ," showit" ' showit , ," solveit" ' solveit , ," quit" ' bye , ," exit" ' bye , ," bye" ' bye , ," q" ' bye , ," help" ' help , NULL ,
wordlist to dictionary
- noname ." Unknown command '" type ." '" cr ; is NotFound
\ sudoku interpreter
- sudoku
argn 1 > if read-sudoku then godoit begin ." OK" cr refill drop ['] interpret catch if ." Error" cr then again
sudoku</lang>
Fortran
This implementation uses a brute force method. The subroutine solve
recursively checks valid entries using the rules defined in the function is_safe
. When solve
is called beyond the end of the sudoku, we know that all the currently entered values are valid. Then the result is displayed.
<lang fortran>program sudoku
implicit none integer, dimension (9, 9) :: grid integer, dimension (9, 9) :: grid_solved grid = reshape ((/ & & 0, 0, 3, 0, 2, 0, 6, 0, 0, & & 9, 0, 0, 3, 0, 5, 0, 0, 1, & & 0, 0, 1, 8, 0, 6, 4, 0, 0, & & 0, 0, 8, 1, 0, 2, 9, 0, 0, & & 7, 0, 0, 0, 0, 0, 0, 0, 8, & & 0, 0, 6, 7, 0, 8, 2, 0, 0, & & 0, 0, 2, 6, 0, 9, 5, 0, 0, & & 8, 0, 0, 2, 0, 3, 0, 0, 9, & & 0, 0, 5, 0, 1, 0, 3, 0, 0/), & & shape = (/9, 9/), & & order = (/2, 1/)) call pretty_print (grid) call solve (1, 1) write (*, *) call pretty_print (grid_solved)
contains
recursive subroutine solve (i, j) implicit none integer, intent (in) :: i integer, intent (in) :: j integer :: n integer :: n_tmp if (i > 9) then grid_solved = grid else do n = 1, 9 if (is_safe (i, j, n)) then n_tmp = grid (i, j) grid (i, j) = n if (j == 9) then call solve (i + 1, 1) else call solve (i, j + 1) end if grid (i, j) = n_tmp end if end do end if end subroutine solve
function is_safe (i, j, n) result (res) implicit none integer, intent (in) :: i integer, intent (in) :: j integer, intent (in) :: n logical :: res integer :: i_min integer :: j_min if (grid (i, j) == n) then res = .true. return end if if (grid (i, j) /= 0) then res = .false. return end if if (any (grid (i, :) == n)) then res = .false. return end if if (any (grid (:, j) == n)) then res = .false. return end if i_min = 1 + 3 * ((i - 1) / 3) j_min = 1 + 3 * ((j - 1) / 3) if (any (grid (i_min : i_min + 2, j_min : j_min + 2) == n)) then res = .false. return end if res = .true. end function is_safe
subroutine pretty_print (grid) implicit none integer, dimension (9, 9), intent (in) :: grid integer :: i integer :: j character (*), parameter :: bar = '+-----+-----+-----+' character (*), parameter :: fmt = '(3 ("|", i0, 1x, i0, 1x, i0), "|")' write (*, '(a)') bar do j = 0, 6, 3 do i = j + 1, j + 3 write (*, fmt) grid (i, :) end do write (*, '(a)') bar end do end subroutine pretty_print
end program sudoku</lang> Output:
+-----+-----+-----+ |0 0 3|0 2 0|6 0 0| |9 0 0|3 0 5|0 0 1| |0 0 1|8 0 6|4 0 0| +-----+-----+-----+ |0 0 8|1 0 2|9 0 0| |7 0 0|0 0 0|0 0 8| |0 0 6|7 0 8|2 0 0| +-----+-----+-----+ |0 0 2|6 0 9|5 0 0| |8 0 0|2 0 3|0 0 9| |0 0 5|0 1 0|3 0 0| +-----+-----+-----+ +-----+-----+-----+ |4 8 3|9 2 1|6 5 7| |9 6 7|3 4 5|8 2 1| |2 5 1|8 7 6|4 9 3| +-----+-----+-----+ |5 4 8|1 3 2|9 7 6| |7 2 9|5 6 4|1 3 8| |1 3 6|7 9 8|2 4 5| +-----+-----+-----+ |3 7 2|6 8 9|5 1 4| |8 1 4|2 5 3|7 6 9| |6 9 5|4 1 7|3 8 2| +-----+-----+-----+
Haskell
Visit the Haskell wiki Sudoku
J
See Solving Sudoku in J.
Java
<lang java>public class SudokuSolver {
private int[] grid;
public SudokuSolver(String s) { grid = new int[81]; for (int i = 0; i < s.length(); i++) { grid[i] = Character.getNumericValue(s.charAt(i)); } }
public void solve() { try { placeNumber(0); System.out.println("Unsolvable!"); } catch (Exception ex) { System.out.println(ex.getMessage()); System.out.println(this); } }
public void placeNumber(int pos) throws Exception { if (pos == 81) { throw new Exception("Finished!"); } if (grid[pos] > 0) { placeNumber(pos + 1); return; } for (int n = 1; n <= 9; n++) { if (checkValidity(n, pos % 9, pos / 9)) { grid[pos] = n; placeNumber(pos + 1); grid[pos] = 0; } } }
public boolean checkValidity(int val, int x, int y) { for (int i = 0; i < 9; i++) { if (grid[y * 9 + i] == val || grid[i * 9 + x] == val) return false; } int startX = (x / 3) * 3; int startY = (y / 3) * 3; for (int i = startY; i < startY + 3; i++) { for (int j = startX; j < startX + 3; j++) { if (grid[i * 9 + j] == val) return false; } } return true; }
@Override public String toString() { StringBuilder sb = new StringBuilder(); for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { sb.append(grid[i * 9 + j] + " "); if (j == 2 || j == 5) sb.append("| "); } sb.append('\n'); if (i == 2 || i == 5) sb.append("------+-------+------\n"); } return sb.toString(); }
public static void main(String[] args) { new SudokuSolver("850002400" + "720000009" + "004000000" + "000107002" + "305000900" + "040000000" + "000080070" + "017000000" + "000036040").solve(); }
}</lang>
MATLAB
This solution impliments a recursive, depth-first search of the possible values unfilled sudoku cells can take. The search tree is pruned using logical deduction rules and takes about a minute to solve some of the more difficult puzzles. This code can be cleaned by making the main code blocks, denoted by "%% [Block Title]," into their own separate functions. This can also be further improved by implementing a Sudoku class and making this solver a member function. There are also several lines of code that can be vectorized to improve efficiency, but at the expense of readability.
For this to work, this code must be placed in a file named "sudokuSolver.m"
<lang MATLAB>function solution = sudokuSolver(sudokuGrid)
%Define what each of the sub-boxes of the sudoku grid are by defining %the start and end coordinates of each sub-box. The indecies represent %the column and row of a grid coordinate on the actual sudoku grid. %The contents of each cell with the same grid coordinates contain the %information to determine which sub-box that grid coordinate is %contained in on the sudoku grid. The array in position 1, i.e. %subBoxes{row,column}(1), represents the row indecies of the subbox. %The array in position 2, i.e. subBoxes{row,column}(2),represents the %column indecies of the subbox. subBoxes(1:9,1:9) = Template:(1:3),(1:3); subBoxes(4:6,:)= Template:(4:6),(1:3); subBoxes(7:9,:)= Template:(7:9),(1:3); for column = (4:6) for row = (1:9) subBoxes{row,column}(2)= {4:6}; end end for column = (7:9) for row = (1:9) subBoxes{row,column}(2)= {7:9}; end end
%Generate a cell of arrays which contain the possible values of the %sudoku grid for each cell in the grid. The possible values a specific %grid coordinate can take share the same indices as the sudoku grid %coordinate they represent. %For example sudokuGrid(m,n) can be possibly filled in by the %values stored in the array at possibleValues(m,n). possibleValues(1:9,1:9) = { (1:9) }; %Filter the possibleValues so that no entry exists for coordinates that %have already been filled in. This will replace any array with an empty %array in the possibleValues cell matrix at the coordinates of a grid %already filled in the sudoku grid. possibleValues( ~isnan(sudokuGrid) )={[]}; %Iterate through each grid coordinate and filter out the possible %values for that grid point that aren't alowed by the rules given the %current values that are filled in. Or, if there is only one possible %value for the current coordinate, fill it in. solution = sudokuGrid; %so the original sudoku input isn't modified memory = 0; %contains the previous iterations possibleValues dontStop = true; %stops the while loop when nothing else can be reasoned about the sudoku while( dontStop )
%% Process of elimination deduction method
while( ~isequal(possibleValues,memory) ) %Stops using the process of elimination deduction method when this deduction rule stops working
memory = possibleValues; %Copies the current possibleValues into memory, for the above conditional on the next iteration.
%Iterate through everything for row = (1:9) for column = (1:9)
if isnan( solution(row,column) ) %If grid coordinate hasn't been filled in, try to determine it's value.
%Look at column to see what values have already %been filled in and thus the current grid %coordinate can't be removableValues = solution( ~isnan(solution(:,column)),column );
%If there are any values that have been assigned to %other cells in the same column, filter those out %of the current cell's possiblValues if ~isempty(removableValues) for m = ( 1:numel(removableValues) ) possibleValues{row,column}( possibleValues{row,column}==removableValues(m) )=[]; end end
%If the current grid coordinate can only atain one %possible value, assign it that value if numel( possibleValues{row,column} ) == 1 solution(row,column) = possibleValues{row,column}; possibleValues(row,column)={[]}; end end %end if
if isnan( solution(row,column) ) %If grid coordinate hasn't been filled in, try to determine it's value.
%Look at row to see what values have already %been filled in and thus the current grid %coordinate can't be removableValues = solution( row,~isnan(solution(row,:)) );
%If there are any values that have been assigned to %other cells in the same row, filter those out %of the current cell's possiblValues if ~isempty(removableValues) for m = ( 1:numel(removableValues) ) possibleValues{row,column}( possibleValues{row,column}==removableValues(m) )=[]; end end %If the current grid coordinate can only atain one %possible value, assign it that value if numel( possibleValues{row,column} ) == 1 solution(row,column) = possibleValues{row,column}; possibleValues(row,column)={[]}; end end %end if
if isnan( solution(row,column) ) %If grid coordinate hasn't been filled in, try to determine it's value. %Look at sub-box to see if any possible values can be %filtered out. First pull the boundaries of the sub-box %containing the current array coordinate currentBoxBoundaries=subBoxes{row,column};
%Then pull the sub-boxes values out of the solution box = solution(currentBoxBoundaries{:});
%Look at sub-box to see what values have already %been filled in and thus the current grid %coordinate can't be removableValues = box( ~isnan(box) );
%If there are any values that have been assigned to %other cells in the same sub-box, filter those out %of the current cell's possiblValues if ~isempty(removableValues) for m = ( 1:numel(removableValues) ) possibleValues{row,column}( possibleValues{row,column}==removableValues(m) )=[]; end end %If the current grid coordinate can only atain one %possible value, assign it that value if numel( possibleValues{row,column} ) == 1 solution(row,column) = possibleValues{row,column}; possibleValues(row,column)={[]}; end end %end if end %end for column end %end for row end %stop process of elimination
%% Check that there are no contradictions in the solved grid coordinates.
%Check that each row at most contains one of each of the integers %from 1 to 9 if ~isempty( find( histc( solution,(1:9),1 )>1 ) ) solution = false; return end %Check that each column at most contains one of each of the integers %from 1 to 9 if ~isempty( find( histc( solution,(1:9),2 )>1 ) ) solution = false; return end %Check that each sub-box at most contains one of each of the integers %from 1 to 9 subBoxBins = zeros(9,9); counter = 0; for row = [2 5 8] for column = [2 5 8] counter = counter +1; %because the sub-boxes are extracted as square matricies, %we need to reshape them into row vectors so all of the %boxes can be input into histc simultaneously subBoxBins(counter,:) = reshape( solution(subBoxes{row,column}{:}),1,9 ); end end if ~isempty( find( histc( subBoxBins,(1:9),2 )>1 ) ) solution = false; return end %Check to make sure there are no grid coordinates that are not %filled in and have no possible values. [rowStack,columnStack] = find(isnan(solution)); %extracts the indicies of the unsolved grid coordinates if (numel(rowStack) > 0) for counter = (1:numel(rowStack)) if isempty(possibleValues{rowStack(counter),columnStack(counter)}) solution = false; return end end %if there are no more grid coordinates to be filed in then the %sudoku is solved and we can return the solution without further %computation elseif (numel(rowStack) == 0) return end
%% Use the unique relative compliment of sets deduction method
%Because no more information can be determined by the process of %ellimination we have to try a new method of reasoning. Now we will %look at the possible values a cell can take. If there is a value that %that grid coordinate can take but no other coordinates in the same row, %column or sub-box can take that value then we assign that coordinate %that value.
keepGoing = true; %signals to keep applying rules to the current grid-coordinate because it hasn't been solved using previous rules dontStop = false; %if this method doesn't figure anything out, this will terminate the top level while loop [rowStack,columnStack] = find(isnan(solution)); %This will also take care of the case where the sudoku is solved counter = 0; %makes sure the loop terminates when there are no more cells to consider while( keepGoing && (counter < numel(rowStack)) ) %stop this method of reasoning when the value of one of the cells has been determined and return to the process of elimination method counter = counter + 1; row = rowStack(counter); column = columnStack(counter); gridPossibles = [possibleValues{row,column}]; coords = (1:9); coords(column) = []; rowPossibles = [possibleValues{row,coords}]; %extract possible values for everything in the same row except the current grid coordinate totalMatches = zeros( numel(gridPossibles),1 ); %preallocate for speed %count how many times a possible value for the current cell %appears as a possible value for the cells in the same row for n = ( 1:numel(gridPossibles) ) totalMatches(n) = sum( (rowPossibles == gridPossibles(n)) ); end %remove any possible values for the current cell that have %matches in other cells gridPossibles = gridPossibles(totalMatches==0); %if there is only one possible value that the current cell can %take that aren't shared by other cells, assign that value to %the current cell. if numel(gridPossibles) == 1 solution(row,column) = gridPossibles; possibleValues(row,column)={[]}; keepGoing = false; %stop this method of deduction and return to the process of elimination dontStop = true; %keep the top level loop going end if(keepGoing) %do the same as above but for the current cell's column
gridPossibles = [possibleValues{row,column}]; coords = (1:9); coords(row) = []; columnPossibles = [possibleValues{coords,column}];
totalMatches = zeros( numel(gridPossibles),1 ); for n = ( 1:numel(gridPossibles) ) totalMatches(n) = sum( (columnPossibles == gridPossibles(n)) ); end
gridPossibles = gridPossibles(totalMatches==0);
if numel(gridPossibles) == 1
solution(row,column) = gridPossibles; possibleValues(row,column)={[]}; keepGoing = false; dontStop = true;
end end if(keepGoing) %do the same as above but for the current cell's sub-box
gridPossibles = [possibleValues{row,column}]; currentBoxBoundaries = subBoxes{row,column}; subBoxPossibles = []; for m = currentBoxBoundaries{1} for n = currentBoxBoundaries{2} if ~((m == row) && (n == column)) subBoxPossibles = [subBoxPossibles possibleValues{m,n}]; end end end
totalMatches = zeros( numel(gridPossibles),1 ); for n = ( 1:numel(gridPossibles) ) totalMatches(n) = sum( (subBoxPossibles == gridPossibles(n)) ); end
gridPossibles = gridPossibles(totalMatches==0);
if numel(gridPossibles) == 1
solution(row,column) = gridPossibles; possibleValues(row,column)={[]}; keepGoing = false; dontStop = true;
end end %end end %end set comliment rule while loop end %end top-level while loop
%% Depth-first search of the solution tree
%There is no more reasoning that can solve the puzzle so now it is time %for a depth-first search of the possible answers, basically %guess-and-check. This is implimented recursively. [rowStack,columnStack] = find(isnan(solution)); %Get all of the unsolved cells if (numel(rowStack) > 0) %If all of the above stuff terminates then there will be at least one grid coordinate not filled in %Treat the rowStack and columnStack like stacks, and pop the top %value off the stack to act as the current node whose %possibleValues to search through, then assign the possible values %of that grid coordinate to a variable that holds that values to %search through searchTreeNodes = possibleValues{rowStack(1),columnStack(1)}; keepSearching = true; %used to continue the search counter = 0; %counts the amount of possible values searched for the current node tempSolution = solution; %used so that the solution is not overriden until a solution hase been found while( keepSearching && (counter < numel(searchTreeNodes)) ) %stop recursing if we run out of possible values for the current node counter = counter + 1; tempSolution(rowStack(1),columnStack(1)) = searchTreeNodes(counter); %assign a possible value to the current node in the tree tempSolution = sudokuSolver(tempSolution); %recursively call the solver with the current guess value for the current grid coordinate if ~islogical(tempSolution) %if tempSolution is not a boolean but a valid sudoku stop recursing and set solution to tempSolution keepSearching = false; solution = tempSolution; elseif counter == numel(searchTreeNodes) %if we have run out of guesses for the current node, stop recursing and return a value of "false" for the solution solution = false; else %reset tempSolution to the current state of the board and try the next guess for the possible value of the current cell tempSolution = solution; end end %end recursion end %end if
%% End of program end %end sudokuSolver</lang>
Test Input: All empty cells must have a value of NaN.
<lang MATLAB>sudoku = [NaN NaN NaN NaN 8 3 9 NaN NaN
1 NaN NaN NaN NaN NaN NaN 3 NaN NaN NaN 4 NaN NaN NaN NaN 7 NaN NaN 4 2 NaN 3 NaN NaN NaN NaN 6 NaN NaN NaN NaN NaN NaN NaN 4 NaN NaN NaN NaN 7 NaN NaN 1 NaN NaN 2 NaN NaN NaN NaN NaN NaN NaN NaN 8 NaN NaN NaN 9 2 NaN NaN NaN NaN NaN 2 5 NaN NaN NaN 6]</lang>
Output: <lang MATLAB>solution =
7 6 5 4 8 3 9 2 1 1 9 8 7 2 6 4 3 5 2 3 4 9 1 5 6 7 8 8 4 2 5 3 1 7 6 9 6 1 7 8 9 2 3 5 4 3 5 9 6 7 4 8 1 2 9 2 6 1 4 7 5 8 3 5 8 1 3 6 9 2 4 7 4 7 3 2 5 8 1 9 6</lang>
OCaml
uses the library ocamlgraph <lang ocaml>(* Ocamlgraph demo program: solving the Sudoku puzzle using graph coloring
Copyright 2004-2007 Sylvain Conchon, Jean-Christophe Filliatre, Julien Signoles
This software is free software; you can redistribute it and/or modify it under the terms of the GNU Library General Public License version 2, with the special exception on linking described in file LICENSE.
This software is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. *)
open Format open Graph
(* We use undirected graphs with nodes containing a pair of integers
(the cell coordinates in 0..8 x 0..8). The integer marks of the nodes will store the colors. *)
module G = Imperative.Graph.Abstract(struct type t = int * int end)
(* The Sudoku grid = a graph with 9x9 nodes *) let g = G.create ()
(* We create the 9x9 nodes, add them to the graph and keep them in a matrix
for later access *)
let nodes =
let new_node i j = let v = G.V.create (i, j) in G.add_vertex g v; v in Array.init 9 (fun i -> Array.init 9 (new_node i))
let node i j = nodes.(i).(j) (* shortcut for easier access *)
(* We add the edges:
two nodes are connected whenever they can't have the same value, i.e. they belong to the same line, the same column or the same 3x3 group *)
let () =
for i = 0 to 8 do for j = 0 to 8 do for k = 0 to 8 do if k <> i then G.add_edge g (node i j) (node k j); if k <> j then G.add_edge g (node i j) (node i k); done; let gi = 3 * (i / 3) and gj = 3 * (j / 3) in for di = 0 to 2 do for dj = 0 to 2 do let i' = gi + di and j' = gj + dj in if i' <> i || j' <> j then G.add_edge g (node i j) (node i' j') done done done done
(* Displaying the current state of the graph *) let display () =
for i = 0 to 8 do for j = 0 to 8 do printf "%d" (G.Mark.get (node i j)) done; printf "\n"; done; printf "@?"
(* We read the initial constraints from standard input and we display g *) let () =
for i = 0 to 8 do let s = read_line () in for j = 0 to 8 do match s.[j] with | '1'..'9' as ch -> G.Mark.set (node i j) (Char.code ch - Char.code '0') | _ -> () done done; display (); printf "---------@."
(* We solve the Sudoku by 9-coloring the graph g and we display the solution *) module C = Coloring.Mark(G)
let () = C.coloring g 9; display ()</lang>
Oz
Using built-in constraint propagation and search.
<lang oz>declare
%% a puzzle is a function that returns an initial board configuration fun {Puzzle1} %% a board is a list of 9 rows [[4 _ _ _ _ _ _ 6 _] [5 _ _ _ 8 _ 9 _ _] [3 _ _ _ _ 1 _ _ _] [_ 2 _ 7 _ _ _ _ 1] [_ 9 _ _ _ _ _ 4 _] [8 _ _ _ _ 3 _ 5 _] [_ _ _ 2 _ _ _ _ 7] [_ _ 6 _ 5 _ _ _ 8] [_ 1 _ _ _ _ _ _ 6]] end
%% Returns a list of solutions for the given puzzle. fun {Solve Puzzle} {SearchAll {GetScript Puzzle}} end
%% Creates a solver script for a puzzle. fun {GetScript Puzzle} proc {$ Board} %% Every row is a list of nine finite domain vars %% with the domain 1..9. Board = {MapRange fun {$ _} {FD.list 9 1#9} end} %% Post initial configuration. Board = {Puzzle} %% The core constraints: {ForAll {Rows Board} FD.distinct} {ForAll {Columns Board} FD.distinct} {ForAll {Boxes Board} FD.distinct}
%% Search if necessary. {FD.distribute ff {Flatten Board}} end end %% Returns the board as a list of rows. fun {Rows Board} Board %% This is already the representation we have chosen. end %% Returns the board as a list of columns. fun {Columns Board} {MapRange fun {$ I} {Column Board I} end} end %% Returns the board as a list of boxes (sub-grids). fun {Boxes Board} {MapRange fun {$ I} {Box Board I} end} end %% Helper function: map the range 1..9 to something. fun {MapRange F} {Map [1 2 3 4 5 6 7 8 9] F} end %% Returns a column of the board as a list of fields. fun {Column Board Index} {Map Board fun {$ Row} {Nth Row Index} end } end %% Returns a box of the board as a list of fields. fun {Box Board Index} Index0 = Index-1 Fields = {Flatten Board} Start = (Index0 div 3) * 27 + (Index0 mod 3)*3 in {Flatten for I in 0..2 collect:C do {C {List.take {List.drop Fields Start+I*9} 3}} end } end
in
{Inspect {Solve Puzzle1}.1}</lang>
PicoLisp
<lang PicoLisp>(load "lib/simul.l")
- Fields/Board ###
- val lst
(setq
*Board (grid 9 9) *Fields (apply append *Board) )
- Init values to zero (empty)
(for L *Board
(for This L (=: val 0) ) )
- Build lookup lists
(for (X . L) *Board
(for (Y . This) L (=: lst (make (let A (* 3 (/ (dec X) 3)) (do 3 (inc 'A) (let B (* 3 (/ (dec Y) 3)) (do 3 (inc 'B) (unless (and (= A X) (= B Y)) (link (prop (get *Board A B) 'val) ) ) ) ) ) ) (for Dir '(`west `east `south `north) (for (This (Dir This) This (Dir This)) (unless (memq (:: val) (made)) (link (:: val)) ) ) ) ) ) ) )
- Cut connections (for display only)
(for (X . L) *Board
(for (Y . This) L (when (member X (3 6)) (con (car (val This))) ) (when (member Y (4 7)) (set (cdr (val This))) ) ) )
- Display board
(de display ()
(disp *Board 0 '((This) (if (=0 (: val)) " " (pack " " (: val) " ") ) ) ) )
- Initialize board
(de main (Lst)
(for (Y . L) Lst (for (X . N) L (put *Board X (- 10 Y) 'val N) ) ) (display) )
- Find solution
(de go ()
(unless (recur (*Fields) (with (car *Fields) (if (=0 (: val)) (loop (NIL (or (assoc (inc (:: val)) (: lst)) (recurse (cdr *Fields)) ) ) (T (= 9 (: val)) (=: val 0)) ) (recurse (cdr *Fields)) ) ) ) (display) ) )
(main
(quote (5 3 0 0 7 0 0 0 0) (6 0 0 1 9 5 0 0 0) (0 9 8 0 0 0 0 6 0) (8 0 0 0 6 0 0 0 3) (4 0 0 8 0 3 0 0 1) (7 0 0 0 2 0 0 0 6) (0 6 0 0 0 0 2 8 0) (0 0 0 4 1 9 0 0 5) (0 0 0 0 8 0 0 7 9) ) )</lang>
Output:
+---+---+---+---+---+---+---+---+---+ 9 | 5 3 | 7 | | + + + + + + + + + + 8 | 6 | 1 9 5 | | + + + + + + + + + + 7 | 9 8 | | 6 | +---+---+---+---+---+---+---+---+---+ 6 | 8 | 6 | 3 | + + + + + + + + + + 5 | 4 | 8 3 | 1 | + + + + + + + + + + 4 | 7 | 2 | 6 | +---+---+---+---+---+---+---+---+---+ 3 | 6 | | 2 8 | + + + + + + + + + + 2 | | 4 1 9 | 5 | + + + + + + + + + + 1 | | 8 | 7 9 | +---+---+---+---+---+---+---+---+---+ a b c d e f g h i
<lang>(go)</lang> Output:
+---+---+---+---+---+---+---+---+---+ 9 | 5 3 4 | 6 7 8 | 9 1 2 | + + + + + + + + + + 8 | 6 7 2 | 1 9 5 | 3 4 8 | + + + + + + + + + + 7 | 1 9 8 | 3 4 2 | 5 6 7 | +---+---+---+---+---+---+---+---+---+ 6 | 8 5 9 | 7 6 1 | 4 2 3 | + + + + + + + + + + 5 | 4 2 6 | 8 5 3 | 7 9 1 | + + + + + + + + + + 4 | 7 1 3 | 9 2 4 | 8 5 6 | +---+---+---+---+---+---+---+---+---+ 3 | 9 6 1 | 5 3 7 | 2 8 4 | + + + + + + + + + + 2 | 2 8 7 | 4 1 9 | 6 3 5 | + + + + + + + + + + 1 | 3 4 5 | 2 8 6 | 1 7 9 | +---+---+---+---+---+---+---+---+---+ a b c d e f g h i
PureBasic
A brute force method is used, it seemed the fastest as well as the simplest. <lang PureBasic>DataSection
puzzle: Data.s "394002670" Data.s "000300400" Data.s "500690020" Data.s "045000900" Data.s "600000007" Data.s "007000580" Data.s "010067008" Data.s "009008000" Data.s "026400735"
EndDataSection
- IsPossible = 0
- IsNotPossible = 1
- Unknown = 0
Global Dim sudoku(8, 8)
- -declarations
Declare readSudoku() Declare displaySudoku() Declare.s buildpossible(x, y, Array possible.b(1)) Declare solvePuzzle(x = 0, y = 0)
- -procedures
Procedure readSudoku()
Protected a$, row, column Restore puzzle For row = 0 To 8 Read.s a$ For column = 0 To 8 sudoku(column, row) = Val(Mid(a$, column + 1, 1)) Next Next
EndProcedure
Procedure displaySudoku()
Protected row, column Static border.s = "+-----+-----+-----+" For row = 0 To 8 If row % 3 = 0: PrintN(border): EndIf For column = 0 To 8 If column % 3 = 0: Print("|"): Else: Print(" "): EndIf If sudoku(column, row): Print(Str(sudoku(column, row))): Else: Print("."): EndIf Next PrintN("|") Next PrintN(border)
EndProcedure
Procedure.s buildpossible(x, y, Array possible.b(1))
Protected index, column, row, boxColumn = (x / 3) * 3, boxRow = (y / 3) * 3 Dim possible.b(9)
For index = 0 To 8 possible(sudoku(index, y)) = #IsNotPossible ;record possibles in column possible(sudoku(x, index)) = #IsNotPossible ;record possibles in row Next ;record possibles in box For row = boxRow To boxRow + 2 For column = boxColumn To boxColumn + 2 possible(sudoku(column, row)) = #IsNotPossible Next Next
EndProcedure
Procedure solvePuzzle(x = 0, y = 0)
Protected row, column, spot, digit Dim possible.b(9) For row = y To 8 For column = x To 8 If sudoku(column, row) = #Unknown buildpossible(column, row, possible()) For digit = 1 To 9 If possible(digit) = #IsPossible sudoku(column, row) = digit spot = row * 9 + column + 1 If solvePuzzle(spot % 9, spot / 9) Break 3 EndIf EndIf Next
If digit = 10 sudoku(column, row) = #Unknown ProcedureReturn #False EndIf EndIf Next x = 0 ;reset column start point Next ProcedureReturn #True
EndProcedure
If OpenConsole()
readSudoku() displaySudoku() If solvePuzzle() PrintN("Solved.") displaySudoku() Else PrintN("Unable to solve puzzle") ;due to bad starting data EndIf Print(#CRLF$ + #CRLF$ + "Press ENTER to exit") Input() CloseConsole()
EndIf </lang> Sample output:
+-----+-----+-----+ |3 9 4|. . 2|6 7 .| |. . .|3 . .|4 . .| |5 . .|6 9 .|. 2 .| +-----+-----+-----+ |. 4 5|. . .|9 . .| |6 . .|. . .|. . 7| |. . 7|. . .|5 8 .| +-----+-----+-----+ |. 1 .|. 6 7|. . 8| |. . 9|. . 8|. . .| |. 2 6|4 . .|7 3 5| +-----+-----+-----+ Solved. +-----+-----+-----+ |3 9 4|8 5 2|6 7 1| |2 6 8|3 7 1|4 5 9| |5 7 1|6 9 4|8 2 3| +-----+-----+-----+ |1 4 5|7 8 3|9 6 2| |6 8 2|9 4 5|3 1 7| |9 3 7|1 2 6|5 8 4| +-----+-----+-----+ |4 1 3|5 6 7|2 9 8| |7 5 9|2 3 8|1 4 6| |8 2 6|4 1 9|7 3 5| +-----+-----+-----+
Python
See Solving Sudoku puzzles with Python for GPL'd solvers of increasing complexity of algorithm.
Ruby
Example of a back-tracking solver, from wp:Algorithmics of sudoku
<lang ruby>def read_matrix(fh)
matrix = [] (0..8).each { |i| l = fh.readline matrix[i] = [] (0..8).each { |j| matrix[i][j] = l[j..j].to_i } } matrix
end
def permissible(matrix, i, j)
ok = [true] * 9 # Same as another in the column isn't permissible... (0..8).each { |i2| next if matrix[i2][j] == 0 ok[matrix[i2][j] - 1] = false } # Same as another in the row isn't permissible... (0..8).each { |j2| next if matrix[i][j2] == 0 ok[matrix[i][j2] - 1] = false } # Same as another in the 3x3 block isn't permissible... igroup = (i / 3) * 3 jgroup = (j / 3) * 3 (igroup..(igroup + 2)).each { |i2| (jgroup..(jgroup + 2)).each { |j2| next if matrix[i2][j2] == 0 ok[matrix[i2][j2] - 1] = false } } # Convert to the array format... (1..9).select { |i2| ok[i2-1] }
end
def deep_copy_sudoku(matrix)
matrix.collect { |row| row.dup }
end
def solve_sudoku(matrix)
loop do options = [] (0..8).each { |i| (0..8).each { |j| next if matrix[i][j] != 0 p = permissible(matrix, i, j) # If nothing is permissible, there is no solution at this level. return nil if p.length == 0 options.push({:i => i, :j => j, :permissible => p}) } } # If the matrix is complete, we have a solution... return matrix if options.length == 0 omin = options.min_by { |x| x[:permissible].length } # If there is an option with only one solution, set it and re-check permissibility if omin[:permissible].length == 1 matrix[omin[:i]][omin[:j]] = omin[:permissible][0] next end # We have two or more choices. We need to search both... omin[:permissible].each { |v| mtmp = deep_copy_sudoku(matrix) mtmp[omin[:i]][omin[:j]] = v ret = solve_sudoku(mtmp) return ret if ret } # We did an exhaustive search on this branch and nothing worked out. return nil end
end
def print_matrix(matrix)
if not matrix puts "Impossible" return end border = "+-----+-----+-----+" (0..8).each { |i| puts border if i%3 == 0 (0..8).each { |j| print(j%3 == 0 ? "|" : " ") print(matrix[i][j] == 0 ? "." : matrix[i][j]) } print "|\n" } puts border
end
matrix = read_matrix(DATA) print_matrix(matrix) puts print_matrix(solve_sudoku(matrix))
__END__ 394__267_ ___3__4__ 5__69__2_ _45___9__ 6_______7 __7___58_ _1__67__8 __9__8___ _264__735</lang>
output
+-----+-----+-----+ |3 9 4|. . 2|6 7 .| |. . .|3 . .|4 . .| |5 . .|6 9 .|. 2 .| +-----+-----+-----+ |. 4 5|. . .|9 . .| |6 . .|. . .|. . 7| |. . 7|. . .|5 8 .| +-----+-----+-----+ |. 1 .|. 6 7|. . 8| |. . 9|. . 8|. . .| |. 2 6|4 . .|7 3 5| +-----+-----+-----+ +-----+-----+-----+ |3 9 4|8 5 2|6 7 1| |2 6 8|3 7 1|4 5 9| |5 7 1|6 9 4|8 2 3| +-----+-----+-----+ |1 4 5|7 8 3|9 6 2| |6 8 2|9 4 5|3 1 7| |9 3 7|1 2 6|5 8 4| +-----+-----+-----+ |4 1 3|5 6 7|2 9 8| |7 5 9|2 3 8|1 4 6| |8 2 6|4 1 9|7 3 5| +-----+-----+-----+
Tcl
Adapted from a page on the Tcler's Wiki to use a standard object system.
Note that you can implement more rules if you want. Just make another subclass of Rule
and the solver will pick it up and use it automatically.
or
<lang tcl>package require Tcl 8.6 oo::class create Sudoku {
variable idata
method clear {} {
for {set y 0} {$y < 9} {incr y} { for {set x 0} {$x < 9} {incr x} { my set $x $y {} } }
} method load {data} {
set error "data must be a 9-element list, each element also being a\ list of 9 numbers from 1 to 9 or blank or an @ symbol." if {[llength $data] != 9} { error $error } for {set y 0} {$y<9} {incr y} { set row [lindex $data $y] if {[llength $row] != 9} { error $error } for {set x 0} {$x<9} {incr x} { set d [lindex $row $x] if {![regexp {^[@1-9]?$} $d]} { error $d-$error } if {$d eq "@"} {set d ""} my set $x $y $d } }
} method dump {} {
set rows {} for {set y 0} {$y < 9} {incr y} { lappend rows [my getRow 0 $y] } return $rows
}
method Log msg {
# Chance to print message
}
method set {x y value} {
if {[catch {set value [format %d $value]}]} {set value 0} if {$value<1 || $value>9} { set idata(sq$x$y) {} } else { set idata(sq$x$y) $value }
} method get {x y} {
if {![info exists idata(sq$x$y)]} { return {} } return $idata(sq$x$y)
}
method getRow {x y} {
set row {} for {set x 0} {$x<9} {incr x} { lappend row [my get $x $y] } return $row
} method getCol {x y} {
set col {} for {set y 0} {$y<9} {incr y} { lappend col [my get $x $y] } return $col
} method getRegion {x y} {
set xR [expr {($x/3)*3}] set yR [expr {($y/3)*3}] set regn {} for {set x $xR} {$x < $xR+3} {incr x} { for {set y $yR} {$y < $yR+3} {incr y} { lappend regn [my get $x $y] } } return $regn
}
}
- SudokuSolver inherits from Sudoku, and adds the ability to filter
- possibilities for a square by looking at all the squares in the row, column,
- and region that the square is a part of. The method 'solve' contains a list
- of rule-objects to use, and iterates over each square on the board, applying
- each rule sequentially until the square is allocated.
oo::class create SudokuSolver {
superclass Sudoku method validchoices {x y} {
if {[my get $x $y] ne {}} { return [my get $x $y] }
set row [my getRow $x $y] set col [my getCol $x $y] set regn [my getRegion $x $y] set eliminate [list {*}$row {*}$col {*}$regn] set eliminate [lsearch -all -inline -not $eliminate {}] set eliminate [lsort -unique $eliminate]
set choices {} for {set c 1} {$c < 10} {incr c} { if {$c ni $eliminate} { lappend choices $c } } if {[llength $choices]==0} { error "No choices left for square $x,$y" } return $choices
} method completion {} {
return [expr { 81-[llength [lsearch -all -inline [join [my dump]] {}]] }]
} method solve {} {
foreach ruleClass [info class subclass Rule] { lappend rules [$ruleClass new] }
while {1} { set begin [my completion] for {set y 0} {$y < 9} {incr y} { for {set x 0} {$x < 9} {incr x} { if {[my get $x $y] eq ""} { foreach rule $rules { set c [$rule solve [self] $x $y] if {$c} { my set $x $y $c my Log "[info object class $rule] solved [self] at $x,$y for $c" break } } } } } set end [my completion] if {$end==81} { my Log "Finished solving!" break } elseif {$begin==$end} { my Log "A round finished without solving any squares, giving up." break } } foreach rule $rules { $rule destroy }
}
}
- Rule is the template for the rules used in Solver. The other rule-objects
- apply their logic to the values passed in and return either '0' or a number
- to allocate to the requested square.
oo::class create Rule {
method solve {hSudoku x y} {
if {![info object isa typeof $hSudoku SudokuSolver]} { error "hSudoku must be an instance of class SudokuSolver." }
tailcall my Solve $hSudoku $x $y [$hSudoku validchoices $x $y]
}
}
- Get all the allocated numbers for each square in the the row, column, and
- region containing $x,$y. If there is only one unallocated number among all
- three groups, it must be allocated at $x,$y
oo::class create RuleOnlyChoice {
superclass Rule method Solve {hSudoku x y choices} {
if {[llength $choices]==1} { return $choices } else { return 0 }
}
}
- Test each column to determine if $choice is an invalid choice for all other
- columns in row $X. If it is, it must only go in square $x,$y.
oo::class create RuleColumnChoice {
superclass Rule method Solve {hSudoku x y choices} {
foreach choice $choices { set failed 0 for {set x2 0} {$x2<9} {incr x2} { if {$x2 != $x && $choice in [$hSudoku validchoices $x2 $y]} { set failed 1 break } } if {!$failed} {return $choice} } return 0
}
}
- Test each row to determine if $choice is an invalid choice for all other
- rows in column $y. If it is, it must only go in square $x,$y.
oo::class create RuleRowChoice {
superclass Rule method Solve {hSudoku x y choices} {
foreach choice $choices { set failed 0 for {set y2 0} {$y2<9} {incr y2} { if {$y2 != $y && $choice in [$hSudoku validchoices $x $y2]} { set failed 1 break } } if {!$failed} {return $choice} } return 0
}
}
- Test each square in the region occupied by $x,$y to determine if $choice is
- an invalid choice for all other squares in that region. If it is, it must
- only go in square $x,$y.
oo::class create RuleRegionChoice {
superclass Rule method Solve {hSudoku x y choices} {
foreach choice $choices { set failed 0 set regnX [expr {($x/3)*3}] set regnY [expr {($y/3)*3}] for {set y2 $regnY} {$y2 < $regnY+3} {incr y2} { for {set x2 $regnX} {$x2 < $regnX+3} {incr x2} { if { ($x2!=$x || $y2!=$y) && $choice in [$hSudoku validchoices $x2 $y2] } then { set failed 1 break } } } if {!$failed} {return $choice} } return 0
}
}</lang> Demonstration code: <lang tcl>SudokuSolver create sudoku sudoku load {
{3 9 4 @ @ 2 6 7 @} {@ @ @ 3 @ @ 4 @ @} {5 @ @ 6 9 @ @ 2 @}
{@ 4 5 @ @ @ 9 @ @} {6 @ @ @ @ @ @ @ 7} {@ @ 7 @ @ @ 5 8 @}
{@ 1 @ @ 6 7 @ @ 8} {@ @ 9 @ @ 8 @ @ @} {@ 2 6 4 @ @ 7 3 5}
} sudoku solve
- Simple pretty-printer for completed sudokus
puts +-----+-----+-----+ foreach line [sudoku dump] postline {0 0 1 0 0 1 0 0 1} {
puts |[lrange $line 0 2]|[lrange $line 3 5]|[lrange $line 6 8]| if {$postline} {
puts +-----+-----+-----+
}
} sudoku destroy</lang> Sample output:
+-----+-----+-----+ |3 9 4|8 5 2|6 7 1| |2 6 8|3 7 1|4 5 9| |5 7 1|6 9 4|8 2 3| +-----+-----+-----+ |1 4 5|7 8 3|9 6 2| |6 8 2|9 4 5|3 1 7| |9 3 7|1 2 6|5 8 4| +-----+-----+-----+ |4 1 3|5 6 7|2 9 8| |7 5 9|2 3 8|1 4 6| |8 2 6|4 1 9|7 3 5| +-----+-----+-----+
If we'd added a logger method (after creating the sudoku
object but before running the solver) like this:
<lang tcl>oo::objdefine sudoku method Log msg {puts $msg}</lang>
Then this additional logging output would have been produced prior to the result being printed:
::RuleOnlyChoice solved ::sudoku at 8,0 for 1 ::RuleColumnChoice solved ::sudoku at 1,1 for 6 ::RuleRegionChoice solved ::sudoku at 4,1 for 7 ::RuleRowChoice solved ::sudoku at 7,1 for 5 ::RuleOnlyChoice solved ::sudoku at 8,1 for 9 ::RuleColumnChoice solved ::sudoku at 1,2 for 7 ::RuleColumnChoice solved ::sudoku at 5,2 for 4 ::RuleRowChoice solved ::sudoku at 6,2 for 8 ::RuleOnlyChoice solved ::sudoku at 8,2 for 3 ::RuleColumnChoice solved ::sudoku at 3,3 for 7 ::RuleRowChoice solved ::sudoku at 1,4 for 8 ::RuleRowChoice solved ::sudoku at 5,4 for 5 ::RuleRowChoice solved ::sudoku at 6,4 for 3 ::RuleRowChoice solved ::sudoku at 0,5 for 9 ::RuleOnlyChoice solved ::sudoku at 1,5 for 3 ::RuleOnlyChoice solved ::sudoku at 0,6 for 4 ::RuleOnlyChoice solved ::sudoku at 2,6 for 3 ::RuleColumnChoice solved ::sudoku at 3,6 for 5 ::RuleOnlyChoice solved ::sudoku at 6,6 for 2 ::RuleOnlyChoice solved ::sudoku at 7,6 for 9 ::RuleOnlyChoice solved ::sudoku at 0,7 for 7 ::RuleOnlyChoice solved ::sudoku at 1,7 for 5 ::RuleColumnChoice solved ::sudoku at 4,7 for 3 ::RuleOnlyChoice solved ::sudoku at 6,7 for 1 ::RuleOnlyChoice solved ::sudoku at 0,8 for 8 ::RuleOnlyChoice solved ::sudoku at 4,8 for 1 ::RuleOnlyChoice solved ::sudoku at 5,8 for 9 ::RuleOnlyChoice solved ::sudoku at 3,0 for 8 ::RuleOnlyChoice solved ::sudoku at 4,0 for 5 ::RuleColumnChoice solved ::sudoku at 2,1 for 8 ::RuleOnlyChoice solved ::sudoku at 5,1 for 1 ::RuleOnlyChoice solved ::sudoku at 2,2 for 1 ::RuleRowChoice solved ::sudoku at 0,3 for 1 ::RuleColumnChoice solved ::sudoku at 4,3 for 8 ::RuleColumnChoice solved ::sudoku at 5,3 for 3 ::RuleOnlyChoice solved ::sudoku at 7,3 for 6 ::RuleOnlyChoice solved ::sudoku at 8,3 for 2 ::RuleOnlyChoice solved ::sudoku at 2,4 for 2 ::RuleColumnChoice solved ::sudoku at 3,4 for 9 ::RuleOnlyChoice solved ::sudoku at 4,4 for 4 ::RuleOnlyChoice solved ::sudoku at 7,4 for 1 ::RuleColumnChoice solved ::sudoku at 3,5 for 1 ::RuleOnlyChoice solved ::sudoku at 4,5 for 2 ::RuleOnlyChoice solved ::sudoku at 5,5 for 6 ::RuleOnlyChoice solved ::sudoku at 8,5 for 4 ::RuleOnlyChoice solved ::sudoku at 3,7 for 2 ::RuleOnlyChoice solved ::sudoku at 7,7 for 4 ::RuleOnlyChoice solved ::sudoku at 8,7 for 6 ::RuleOnlyChoice solved ::sudoku at 0,1 for 2 Finished solving!
Ursala
<lang Ursala>#import std
- import nat
sudoku =
@FL mat0+ block3+ mat` *+ block3*+ block9+ -+
~&rSL+ (psort (nleq+)* <~&blrl,~&blrr>)+ ~&arg^& -+ ~&al?\~&ar ~&aa^&~&afahPRPfafatPJPRY+ ~&farlthlriNCSPDPDrlCS2DlrTS2J, ^|J/~& ~&rt!=+ ^= ~&s+ ~&H( -+.|=&lrr;,|=&lrl;,|=≪+-, ~&rgg&& ~&irtPFXlrjrXPS; ~&lrK2tkZ2g&& ~&llrSL2rDrlPrrPljXSPTSL)+-, //~&p ^|DlrDSLlrlPXrrPDSL(~&,num*+ rep2 block3)*= num block27 ~&iiK0 iota9, * `0?=\~&iNC ! ~&t digits+-</lang>
test program: <lang Ursala>#show+
example =
sudoku
-[ 394002670 000300400 500690020 045000900 600000007 007000580 010067008 009008000 026400735]-</lang> output:
394 852 671 268 371 459 571 694 823 145 783 962 682 945 317 937 126 584 413 567 298 759 238 146 826 419 735