

Solve the eight queens puzzle.



You can extend the problem to solve the puzzle with a board of size   NxN.

For the number of solutions for small values of   N,   see   OEIS: A000170.



Related tasks

 A* search algorithm
 Solve a Hidato puzzle
 Solve a Holy Knight's tour
 Knight's tour
 Peaceful chess queen armies
 Solve a Hopido puzzle
 Solve a Numbrix puzzle
 Solve the no connection puzzle


 
(* ****** ****** *)
//
// 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] *)
 