81 lines
1.1 KiB
Plaintext
81 lines
1.1 KiB
Plaintext
(* ****** ****** *)
|
|
//
|
|
// Solving N-queen puzzle
|
|
//
|
|
(* ****** ****** *)
|
|
//
|
|
// How to test:
|
|
// ./queens
|
|
// How to compile:
|
|
// patscc -DATS_MEMALLOC_LIBC -o queens queens.dats
|
|
//
|
|
(* ****** ****** *)
|
|
//
|
|
#include
|
|
"share/atspre_staload.hats"
|
|
//
|
|
#include
|
|
"share/HATS/atspre_staload_libats_ML.hats"
|
|
//
|
|
(* ****** ****** *)
|
|
|
|
fun
|
|
solutions(N:int) = let
|
|
//
|
|
fun
|
|
show
|
|
(
|
|
board: list0(int)
|
|
) : void =
|
|
(
|
|
list0_foreach<int>
|
|
( list0_reverse(board)
|
|
, lam(n) => ((N).foreach()(lam(i) => print_string(if i = n then " Q" else " _")); print_newline())
|
|
) ;
|
|
print_newline()
|
|
)
|
|
//
|
|
fun
|
|
safe
|
|
(
|
|
i: int, j: int, k: int, xs: list0(int)
|
|
) : bool =
|
|
(
|
|
case+ xs of
|
|
| nil0() => true
|
|
| cons0(x, xs) => x != i && x != j && x != k && safe(i, j+1, k-1, xs)
|
|
)
|
|
//
|
|
fun
|
|
loop
|
|
(
|
|
col: int, xs: list0(int)
|
|
) : void =
|
|
(N).foreach()
|
|
(
|
|
lam(i) =>
|
|
if
|
|
safe(i, i+1, i-1, xs)
|
|
then let
|
|
val xs = cons0(i, xs)
|
|
in
|
|
if col = N then show(xs) else loop(col+1, xs)
|
|
end // end of [then]
|
|
)
|
|
//
|
|
in
|
|
loop(1, nil0())
|
|
end // end of [solutions]
|
|
|
|
(* ****** ****** *)
|
|
|
|
val () = solutions(8)
|
|
|
|
(* ****** ****** *)
|
|
|
|
implement main0() = ()
|
|
|
|
(* ****** ****** *)
|
|
|
|
(* end of [queens.dats] *)
|