48 lines
1.4 KiB
Text
48 lines
1.4 KiB
Text
templates queens
|
||
def n: $;
|
||
templates getRowColumn
|
||
when <?($@queens.freeRows($.r::raw) <=0>)> do 0 !
|
||
when <?($@queens.freeMaxs($.r::raw + $.c::raw) <=0>)> do 0 !
|
||
when <?($@queens.freeMins($.c::raw - $.r::raw + $n) <=0>)> do 0 !
|
||
otherwise 1!
|
||
end getRowColumn
|
||
|
||
sink setRowColumn
|
||
def p: $;
|
||
@queens.freeRows($p.r::raw): $p.val::raw;
|
||
@queens.freeMaxs($p.c::raw + $p.r::raw): $p.val::raw;
|
||
@queens.freeMins($p.c::raw - $p.r::raw + $n): $p.val::raw;
|
||
end setRowColumn
|
||
|
||
data done <=1>
|
||
|
||
templates placeQueen
|
||
def c: $;
|
||
row´1 -> #
|
||
when <done> do 1!
|
||
when <=row´($n+1)> do 0 !
|
||
when <?({r: $, c: $c} -> getRowColumn <=1>)> do
|
||
def r: $;
|
||
@queens.queenRows($r::raw): $c;
|
||
{r: $, c: $c, val: 0} -> !setRowColumn
|
||
$c -> \(<=col´$n> done´1!
|
||
<?(col´($c::raw + 1) -> placeQueen <=1>)> done´1!
|
||
<>
|
||
{r: $r, c: $c, val: 1} -> !setRowColumn
|
||
row´($r::raw + 1) !\) -> #
|
||
otherwise row´($::raw + 1) -> #
|
||
end placeQueen
|
||
|
||
@: { freeRows: [1..$n -> 1],
|
||
freeMaxs: [1..$n*2 -> 1],
|
||
freeMins: [1..$n*2 -> 1],
|
||
queenRows: [1..$n -> -1] };
|
||
col´1 -> placeQueen -> \(<=1> $@queens.queenRows ! <> 'non-existent'!\)!
|
||
end queens
|
||
|
||
'A solution to the 8 queens problem is $:8 -> queens;
|
||
' -> !OUT::write
|
||
'A solution to the 4 queens problem is $:4 -> queens;
|
||
' -> !OUT::write
|
||
'A solution to the 3 queens problem is $:3 -> queens;
|
||
' -> !OUT::write
|