Sudoku: Difference between revisions
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 _] |
|||
%% a board is a list of 9 rows |
|||
[[4 _ _ _ _ _ _ 6 _] |
|||
[5 _ _ _ 8 _ 9 _ _] |
|||
[3 _ _ _ _ 1 _ _ _] |
|||
[_ 9 _ _ _ _ _ 4 _] |
|||
[_ 2 _ 7 _ _ _ _ 1] |
|||
[_ 9 _ _ _ _ _ 4 _] |
|||
[8 _ _ _ _ 3 _ 5 _] |
|||
[_ _ 6 _ 5 _ _ _ 8] |
|||
[_ _ _ 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 { |
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 { |
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. |
|||
{FD.distribute ff {Flatten Board}} |
|||
end |
|||
{MapRange fun {$ I} {Column Board I} end} |
|||
end |
end |
||
%% Returns the board as a list of |
%% Returns the board as a list of rows. |
||
fun { |
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 { |
fun {Columns 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}}== |