Sudoku: Difference between revisions
add Ada
m (→{{header|C++}}) |
(add Ada) |
||
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.
=={{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}}==
| |||