Sudoku: Difference between revisions
Content added Content deleted
m (→{{header|C++}}) |
(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}}== |