Matteo Redaelli

Computer Science OpenSource Linux Africa Volontariato Ambiente Energia solare Mezzi Pubblici Piste ciclabili

N queens solution with erlang 5 Jan 2009

Filed under: Me — Matteo @ 12:41
Tags: , ,

8queens

“The eight queens puzzle is the problem of putting eight chess queens on an 8×8 chessboard such that none of them is able to capture any other using the standard chess queen’s moves. The queens must be placed in such a way that no two queens would be able to attack each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n queens puzzle of placing n queens on an n×n chessboard, where solutions exist only for n = 1 or n ≥ 4… ” [Wikipedia]

Below my solution using ERLANG (very strong for concurrent programming, used by Ericsson, Facebook, Amazon,Google,..) with List comprehensions and suggestions from other sites.

-module(queens).

-export([queens/1]).
same_row({_,X},{_,X}) -> true;
same_row({_,_},{_,_}) -> false.
%% not necessary: recursive queens/2 calls with the next column
same_column({X,_},{X,_}) -> true;
same_column({_,_},{_,_}) -> false.
same_diagonal({X1,Y1},{X2,Y2}) ->
 DeltaX = abs(X1 - X2),
 DeltaY = abs(Y1 - Y2),
 case DeltaX == DeltaY of
 true  -> true;
 false -> false
 end.
attaccable({X1,Y1}, {X2,Y2}) ->
 same_row( {X1,Y1}, {X2,Y2} ) orelse
 same_column( {X1,Y1}, {X2,Y2} ) orelse
 same_diagonal( {X1,Y1}, {X2,Y2} ).
safe_cell({_,_}, []) -> true;
safe_cell({X1,Y1}, [{X2,Y2}|L]) ->
 not attaccable({X1,Y1}, {X2,Y2}) andalso
 safe_cell({X1,Y1}, L).
queens(N) ->
 S = queens(N, N),
 io:format("~w solutions found!: ~w~n", [length(S), S]).

queens(0, _) -> [[]];
queens(X, Rows) ->
 [[{X,Y}|L] ||
 L <- queens( X - 1, Rows),
 Y <- lists:seq(1,Rows),
 safe_cell({X,Y}, L)
 ].
 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s