Sudoku: Difference between revisions

← Older editNewer edit →
Content deleted Content added
→‎{{header|Oz}}: simplified
Line 505: Line 505:


<lang oz>declare
<lang oz>declare
%% a puzzle is a function that returns an initial board configuration
%% A board is a list of nine rows.
fun {Puzzle1}
Board1 = [[4 _ _ _ _ _ _ 6 _]
[5 _ _ _ 8 _ 9 _ _]
%% a board is a list of 9 rows
[3 _ _ _ _ 1 _ _ _]
[[4 _ _ _ _ _ _ 6 _]
[5 _ _ _ 8 _ 9 _ _]
[_ 2 _ 7 _ _ _ _ 1]
[3 _ _ _ _ 1 _ _ _]
[_ 9 _ _ _ _ _ 4 _]
[8 _ _ _ _ 3 _ 5 _]
[_ 2 _ 7 _ _ _ _ 1]
[_ 9 _ _ _ _ _ 4 _]
[_ _ _ 2 _ _ _ _ 7]
[8 _ _ _ _ 3 _ 5 _]
[_ _ 6 _ 5 _ _ _ 8]
[_ 1 _ _ _ _ _ _ 6]]
[_ _ _ 2 _ _ _ _ 7]
[_ _ 6 _ 5 _ _ _ 8]
[_ 1 _ _ _ _ _ _ 6]]
end


%% Returns a list of solutions for the given puzzle.
%% Helper function: map the range 1..9 to something.
fun {MapRange F}
fun {Solve Puzzle}
{SearchAll {GetScript Puzzle}}
{Map [1 2 3 4 5 6 7 8 9] F}
end
end


%% Creates a solver script for a puzzle.
%% Returns the board as a list of rows.
fun {Rows Board}
fun {GetScript Puzzle}
proc {$ Board}
Board %% This is already the representation we have chosen.
%% Every row is a list of nine finite domain vars
end
%% 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.
%% Returns the board as a list of columns.
fun {Columns Board}
{FD.distribute ff {Flatten Board}}
end
{MapRange fun {$ I} {Column Board I} end}
end
end

%% Returns the board as a list of boxes (sub-grids).
%% Returns the board as a list of rows.
fun {Boxes Board}
fun {Rows Board}
Board %% This is already the representation we have chosen.
{MapRange fun {$ I} {Box Board I} end}
end
end

%% Returns the board as a list of columns.
%%
fun {Column Board Index}
fun {Columns Board}
{Map Board
{MapRange fun {$ I} {Column Board I} end}
end
fun {$ Row}
{Nth Row Index}
%% Returns the board as a list of boxes (sub-grids).
end
}
fun {Boxes Board}
{MapRange fun {$ I} {Box Board I} end}
end
end

%%
%% Helper function: map the range 1..9 to something.
fun {Box Board Index1}
fun {MapRange F}
Index = Index1-1
{Map [1 2 3 4 5 6 7 8 9] F}
Fields = {Flatten Board}
end
Start = (Index div 3) * 27 + (Index mod 3)*3
%% 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
in
{Inspect {Solve Puzzle1}.1}</lang>
{Flatten
for I in 0..2 collect:C do
{C {List.take {List.drop Fields Start+I*9} 3}}
end
}
end

%% Clone the unbound variables in Board.
%% (Because we cannot constrain free toplevel variables.)
fun {Fresh Board}
{Map Board
fun {$ Line}
{Map Line fun {$ F} if {IsDet F} then F else _ end end}
end
}
end

%% Create a solver script given an initial board.
fun {GetScript InitBoard}
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 = {Fresh InitBoard}
%% 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 a list of solutions for the given board.
fun {Solve Board}
{SearchAll {GetScript Board}}
end

in

{Browse {Solve Board1}.1} %% Tip: make browser window smaller to read the solution.</lang>


=={{header|Python}}==
=={{header|Python}}==
Retrieved from "https://rosettacode.org/wiki/Sudoku"