N queens problem with erlang

2009-01-05

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.

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)
	].

Enter your instance's address


More posts like this

My Networking Survival Kit

2020-03-15 | #Me

In this small tutorial I’ll speak about tunneling, ssh port forwarding, socks, pac files, Sshuttle I’ve been using Linux since 1995 but I have never been interested a lot in networking.

Continue reading 