Skip to main content

# Eight Queens

rascal-0.34.0

This demo implements a solver of the eight queens puzzle:

First the prerequisites:

``import List;import util::Math;``

We play eight queens on a chess board, n by n squares, but usually 8. very queen has her position:

``alias Pos = tuple[int x,int y];``

Queens challenge eachother diagonally if the absolute difference in x coordinates equals the absolute difference in y coordinates:

``bool diagonalOverlap(Pos l, Pos r) = l != r ==> abs(l.x - r.x) == abs(l.y - r.y);``

One particular guess at a solution can be checked by simply comparing all pairs of queens with one another for diagonal overlap:

``lrel[&T,&T] pairs(list[&T] p) =        [ <p[i],p[j]> | i <- [0..size(p)-1], j <- [i+1..size(p)]];bool isSolution(list[Pos] queens) = all(<l,r> <- pairs(queens), !diagonalOverlap(l,r));``

The main driver is a brute force generator of all possible permutations on the board:

``list[list[Pos]] nQueens(int n)     = [queens         | cols <- permutations([0..n]),          queens := [<i,cols[i]> | i <- [0..n]],          isSolution(queens)];``

Let's give it a try:

``rascal>nQueens(4)list[lrel[int x,int y]]: [  [    <0,2>,    <1,0>,    <2,3>,    <3,1>  ],  [    <0,1>,    <1,3>,    <2,0>,    <3,2>  ]]``