N queens problem with erlang
2009-01-05
“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.
same_column({X,_},{X,_}) -> true;
same_column({_,_},{_,_}) -> false.
same_diagonal({X1,Y1},{X2,Y2}) ->
DeltaX = abs(X1 - X2),
DeltaY = abs(Y1 - Y2),
DeltaX == DeltaY.
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!", [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)
].