Better Eight Queens program
lambdacalculator opened this issue · 0 comments
lambdacalculator commented
The Eight Queens program included in Examples (citation: O'Keefe, The Craft of Prolog) is unnecessarily complicated and wasteful in its data structure. Here is a much simpler program that uses the same idea (diagonals as lists of logic variables shared with columns), adapted from a program in Chapter 9 of van Roy and Haridi, Concepts, Techniques, and Models of Computer Programming, 2004:
queens(N, Queens) :-
length(Queens, N),
place_queens(N, Queens, _, _).
place_queens(0, _, _, _) :- !.
place_queens(N, Cs, Us, [_|Ds]) :-
M is N - 1,
place_queens(M, Cs, [_|Us], Ds),
place_queen(N, Cs, Us, Ds).
place_queen(N, [N|_], [N|_], [N|_]).
place_queen(N, [_|Cs], [_|Us], [_|Ds]) :-
place_queen(N, Cs, Us, Ds).