Eight queens puzzle (Erlang)

From LiteratePrograms

Other implementations: C | Erlang | Forth | J | Scala

The eight queens problem is the problem of placing eight queens on an 8×8 chessboard such that none of them attack one another (no two are in the same row, column, or diagonal). More generally, the n queens problem places n queens on an n×n chessboard.

Implementation

We start by creating a function which given an integer N will return the number of ways to place N queens on an NxN board. This calls another method which keeps track of the board size, the number of queens left to place and a list of queens that have already been placed. This list contains the row of each queen. Each call this checks the state of the already placed queens.

<<count>>=
count(N) ->
    count(N,N,[]).
count(_,0,List) ->
    case checkState(List) of
        true -> 1;
        false -> 0
    end;
count(N,Depth,List) ->
    case checkState(List) of
        true ->
            tryAllRows(N,Depth,N,List);
        false -> 0
    end.

This function tries to place a queen in every row recursively calling count and decreasing the number of queens left to place.

<<tryAllRows>>=
tryAllRows(_,_,0,_) ->
    0;
tryAllRows(N,Depth,Row,List) ->
    count(N,Depth-1,List ++ [Row]) + tryAllRows(N,Depth,Row-1,List).

A state is good if it is an empty list or if every queen is in a different row and diagonal.

<<checkState>>=
checkState([]) ->
    true;
checkState(List) ->
    differentRows(List) and differentDiagonals(List).

All the queens are in different rows if there is only one queen or if the row of the first queen is not in the rest of the list and the rest of the queens are all in different rows.

<<differentRows>>=
differentRows([_]) ->
    true;
differentRows([First|Rest]) ->
    not lists:member(First, Rest) and differentRows(Rest).

This function fans out from each queen checking that no other queen lies in its path.

<<differentDiagonals>>=
differentDiagonals([_]) ->
    true;
differentDiagonals([First|Rest]) ->
    differentDiagonals(Rest, First+1, First-1) and differentDiagonals(Rest).
differentDiagonals([], _, _) ->
    true;
differentDiagonals([First|_], First, _) ->
    false;
differentDiagonals([First|_], _, First) ->
    false;
differentDiagonals([_|Rest], Up, Down) ->
    differentDiagonals(Rest, Up+1, Down-1).

Putting this together we have a solution:

<<queens.erl>>=
-module(queens).
-export([count/1]).
count
tryAllRows
checkState
differentRows
differentDiagonals

Testing

<<test_queens.erl>>=
-module(queens_test).
-export([start/0]).
start() ->
    io:format("Testing queens...~n"),
    Inputs = [1,2,3,4,5,6,7,8,9,10],
    Outputs = [1,0,0,3,10,4,40,92,352,724],
    test_queens({queens,count},Inputs,Outputs),
    halt().
test_queens(_,[],[]) ->
    true;
test_queens({Mod,Fun},[InCurr|Inputs],[OutCurr|Outputs]) ->
    ModName = erlang:atom_to_list(Mod),
    FunName = erlang:atom_to_list(Fun),
    %Actual = ModName:FunName(InCurr),
    Actual = erlang:apply(Mod,Fun,[InCurr]),
    if
        Actual == OutCurr ->
            io:format("~s:~s - passed - input: ~B, actual: ~B~n", [ModName, FunName, InCurr, Actual]);
        true ->
            io:format("~s:~s - failed - input: ~B, expected: ~B, actual: ~B~n", [ModName, FunName, InCurr, OutCurr, Actual])
    end,
    test_queens({Mod,Fun},Inputs,Outputs).

This can be run by doing the following from a shell:

> erlc queens.erl 
> erlc queens_test.erl
> erl -run queens_test

Download code