% File : Queens.Pl % Author : Richard A O'Keefe % Updated: 8 Feb 84 % Purpose: Solve the N queens problem in Prolog. :- public % declarations added last queens/1. :- mode forbidden(+, +, +, +), least_room_to_move(+, -, -, -), lr2m(+, +, +, -, -, -), make_initial_table(+, -), make_initial_table(+, +, -), number_list(+, -), place(+, -), prune(+, +, +, -), prune(+, +, +, +, -), shorter(+, +). /* The N-queens problem is to place N queens on an NxN chessboard so that no two queens attack each other. Suppose we have a queen in (Row1,Col1) and a queen in (Row2,Col2). They attack each other if 1. Same rank: Row1 = Row2. 2. Same file: Col1 = Col2. 3. Same NW-SE diagonal Row2 - Row1 = Col2 - Col1. 4. Same SW-NE diagonal Row2 - Row1 = Col1 - Col2. We can express 3 and 4 another way: 3. Row2 - Col2 = Row1 - Col1. 4. Row2 + Col2 = Row1 + Col1. So each of the N queens has four numbers associated with it, (Row,Col,Dif,Sum), and any two queens must have different numbers in all these positions. The possible values are Row : 1 .. N Col : 1 .. N Sum : 1 .. 2N Dif : 1-N .. N-1 The first question is, how shall we represent the board? It is sufficient to have a table indexed by rows, whose elements are the columns in which the corresponding queen is placed. For example, with rows horizontal and columns vertical 1 2 3 4 -column / row +---+---+---+---+ | | Q | | | 1 +---+---+---+---+ | | | | Q | 2 +---+---+---+---+ | Q | | | | 3 +---+---+---+---+ | | | Q | | 4 +---+---+---+---+ could be represented by board(2,4,1,3). How are we going to place the queens? The first idea that springs to mind is to place them one after another, but we can do better than that. Let us maintain a table of (QueenRow/PossibleColumns), and at each step pick the queen with the fewest possible columns, place it, and prune the remaining sets. Let's start by writing a predicate to generate this table. For N=4 it will look like [1/[1,2,3,4], 2/[1,2,3,4], 3/[1,2,3,4], 4/[1,2,3,4]]. */ make_initial_table(N, Table) :- number_list(N, PossibleColumns), % set of all possible columns make_initial_table(N, PossibleColumns, Table). make_initial_table(0, _, []) :- !. make_initial_table(N, PossibleColumns, [N/PossibleColumns|Table]) :- M is N-1, % in C-Prolog we could write succ(M, N) which would eliminate % the need for the cut in the previous clause make_initial_table(M, PossibleColumns, Table). number_list(0, []) :- !. number_list(N, [N|List]) :- M is N-1, % see previous comment number_list(M, List). /* This actually generates the reverse of what I said, so we'd get [4/[4,3,2,1], 3/[4,3,2,1], 2/[4,3,2,1], 1/[4,3,2,1]], but since it was to be a set of number/set pairs, that's ok. We shall only be operating on these sets an element at a time, so it the order doesn't matter. Now the problem is solved if there are no queens left to place. Otherwise, we pick the queen with the fewest possible columns, backtrack over those possible columns, prune the possible columns sets of the remaining queens, and recur. We are given a set of Row/PossCols pairs for the unplaced queens, and we are to return a set of Row-Col pairs saying where we put the queens. */ place([], []). place(UnplacedQueens, [Queen-Col|Placement]) :- least_room_to_move(UnplacedQueens, Queen, Columns, OtherQueens), member(Col, Columns), % backtrack over possible places prune(OtherQueens, Queen, Col, RemainingQueens), place(RemainingQueens, Placement). /* If you haven't done this sort of thing before, least_room_to_move can be quite tricky. The idea is the we wander down the list of pairs, keeping the current best pair apart, and when we find that there is a better pair we have to put the current pair back in the list. But because these are sets, it doesn't matter *where* the pairs go in the list. Note that we don't need a cut in the first clause of place/2 because least_room_to_move will fail on an empty list. */ least_room_to_move([Q/C|Table], Qbest, Cbest, Rest) :- lr2m(Table, Q, C, Qbest, Cbest, Rest). /* This uses accumulator passing. I really have to explain this program to you in person. */ lr2m([], Q, C, Q, C, []). lr2m([NewQ/NewC|Table], OldQ, OldC, MinQ, MinC, [OldQ/OldC|Rest]) :- shorter(NewC, OldC), !, lr2m(Table, NewQ, NewC, MinQ, MinC, Rest). lr2m([Pair|Table], OldQ, OldC, MinQ, MinC, [Pair|Rest]) :- lr2m(Table, OldQ, OldC, MinQ, MinC, Rest). /* shorter(L1, L2) is true when the list L1 is strictly shorter than the list L2 */ shorter([], [_|_]). shorter([_|L1], [_|L2]) :- shorter(L1, L2). /* Now we have to code prune. To prune all the queens, we prune each queen in turn. */ prune([], _, _, []). prune([Queen/Columns|Queens], Row, Col, [Queen/Pruned|RestPruned]) :- prune(Columns, Queen, Row, Col, Pruned), prune(Queens, Row, Col, RestPruned). /* To prune a single queen, we have to eliminate all the positions forbidden by the queen wee have just placed. */ prune([], _, _, _, []). prune([Col2|Cols], Row2, Row1, Col1, Permitted) :- forbidden(Row1, Col1, Row2, Col2), !, prune(Cols, Row2, Row1, Col1, Permitted). prune([Col2|Cols], Row2, Row1, Col1, [Col2|Permitted]) :- prune(Cols, Row2, Row1, Col1, Permitted). /* Finally, since we have ensured that two queens are automatically in different rows, we have only to check rules 2, 3, and 4. */ forbidden(_, Col, _, Col). forbidden(Row1, Col1, Row2, Col2) :- Row2 - Col2 =:= Row1 - Col1. forbidden(Row1, Col1, Row2, Col2) :- Row2 + Col2 =:= Row1 + Col1. /* The last thing left for us to do is to write the top level predicate that ties all the pieces together. Because the 'place' predicate may place the queens in any order, we keysort the list to make it more readable. I'm afraid I had that in mind when I decided that it would be a list of Row-Col pairs. I seem to recommend sorting for everything. Well, it IS a panacea. */ queens(N) :- make_initial_table(N, Table), place(Table, Placement), keysort(Placement, DisplayForm), write(DisplayForm), nl.