

Solve the eight queens puzzle.



You can extend the problem to solve the puzzle with a board of size   NxN.

For the number of solutions for small values of   N,   see   OEIS: A000170.



Related tasks

 A* search algorithm
 Solve a Hidato puzzle
 Solve a Holy Knight's tour
 Knight's tour
 Peaceful chess queen armies
 Solve a Hopido puzzle
 Solve a Numbrix puzzle
 Solve the no connection puzzle


 
-module( n_queens ).
 
-export( [display/1, solve/1, task/0] ).
 
display( Board ) ->
	%% Queens are in the positions in the Board list.
	%% Top left corner is {1, 1}, Bottom right is {N, N}. There is a queen in the max column.
	N = lists:max( [X || {X, _Y} <- Board] ),
	[display_row(Y, N, Board) || Y <- lists:seq(1, N)].
 
solve( N ) ->
    Positions = [{X, Y} || X <- lists:seq(1, N), Y <- lists:seq(1, N)],
    try
    bt( N, Positions, [] )
 
    catch
    _:{ok, Board} -> Board
 
    end.
 
task() ->
    task( 4 ),
    task( 8 ).
 
 
 
bt( N, Positions, Board ) -> bt_reject( is_not_allowed_queen_placement(N, Board), N, Positions, Board ).
 
bt_accept( true, _N, _Positions, Board ) -> erlang:throw( {ok, Board} );
bt_accept( false, N, Positions, Board ) -> bt_loop( N, Positions, [], Board ).
 
bt_loop( _N, [], _Rejects, _Board ) -> failed;
bt_loop( N, [Position | T], Rejects, Board ) ->
	bt( N, T ++ Rejects, [Position | Board] ),
	bt_loop( N, T, [Position | Rejects], Board ).
 
bt_reject( true, _N, _Positions, _Board ) -> backtrack;
bt_reject( false, N, Positions, Board ) -> bt_accept( is_all_queens(N, Board), N, Positions, Board ).
 
diagonals( N, {X, Y} ) ->
	D1 = diagonals( N, X + 1, fun diagonals_add1/1, Y + 1, fun diagonals_add1/1 ),
	D2 = diagonals( N, X + 1, fun diagonals_add1/1, Y - 1, fun diagonals_subtract1/1 ),
	D3 = diagonals( N, X - 1, fun diagonals_subtract1/1, Y + 1, fun diagonals_add1/1 ),
	D4 = diagonals( N, X - 1, fun diagonals_subtract1/1, Y - 1, fun diagonals_subtract1/1 ),
	D1 ++ D2 ++ D3 ++ D4.
 
diagonals( _N, 0, _Change_x, _Y, _Change_y ) -> [];
diagonals( _N, _X, _Change_x, 0, _Change_y ) -> [];
diagonals( N, X, _Change_x, _Y, _Change_y ) when X > N -> [];
diagonals( N, _X, _Change_x, Y, _Change_y ) when Y > N -> [];
diagonals( N, X, Change_x, Y, Change_y ) -> [{X, Y} | diagonals( N, Change_x(X), Change_x, Change_y(Y), Change_y )].
 
diagonals_add1( N ) -> N + 1.
 
diagonals_subtract1( N ) -> N - 1.
 
display_row( Row, N, Board ) ->
	[io:fwrite("~s", [display_queen(X, Row, Board)]) || X <- lists:seq(1, N)],
	io:nl().
 
display_queen( X, Y, Board ) -> display_queen( lists:member({X, Y}, Board) ).
display_queen( true ) -> " Q";
display_queen( false ) -> " .".
 
is_all_queens( N, Board ) -> N =:= erlang:length( Board ).
 
is_diagonal( _N, [] ) -> false;
is_diagonal( N, [Position | T] ) ->
	Diagonals = diagonals( N, Position ),
	T =/= (T -- Diagonals)
	orelse is_diagonal( N, T ).
 
is_not_allowed_queen_placement( N, Board ) ->
	Pieces = erlang:length( Board ),
	{Xs, Ys} = lists:unzip( Board ),
	Pieces =/= erlang:length( lists:usort(Xs) )
	orelse Pieces =/= erlang:length( lists:usort(Ys) )
	orelse is_diagonal( N, Board ).
 
task( N ) ->
    io:fwrite( "N = ~p. One solution.~n", [N] ),
    Board = solve( N ),
    display( Board ).
 