|
65
|
1 % Eight Queens problem, written from just the rules and a few hints on available approaches
|
|
|
2 % which includes the "member/2" and other useful functions.
|
|
|
3 % This will be MUCH more succinct than defining the entire board and trying
|
|
|
4 % to operate on that! Half of the problem is approaching the problem correctly.
|
|
|
5
|
|
|
6 eight_queens(List) :-
|
|
|
7 % Check we've got the right length
|
|
|
8 length(List, 8),
|
|
|
9 % Check our values are all valid positions
|
|
|
10 valid_board(List),
|
|
|
11 % Pull out the rows
|
|
|
12 rows(List, Rows),
|
|
|
13 % Pull out the columns
|
|
|
14 columns(List, Cols),
|
|
|
15 % Pull out the diagonals (North-East/South-West)
|
|
|
16 diagonals_sw_ne(List, Diags1),
|
|
|
17 % Pull out the diagonals (North-West/South-East)
|
|
|
18 diagonals_nw_se(List, Diags2),
|
|
|
19
|
|
|
20 % Make sure we have no duplicates - based on the simple Sudoku solver
|
|
|
21 fd_all_different(Rows),
|
|
|
22 fd_all_different(Cols),
|
|
|
23 fd_all_different(Diags1),
|
|
|
24 fd_all_different(Diags2).
|
|
|
25
|
|
|
26 valid_board([]).
|
|
|
27 valid_board([Head|Tail]) :- valid_queen(Head), valid_board(Tail).
|
|
|
28
|
|
|
29 % Queen location defined as a tuple
|
|
|
30 valid_queen((Row, Col)) :-
|
|
|
31 Range = [1,2,3,4,5,6,7,8],
|
|
|
32 member(Row, Range), member(Col, Range).
|
|
|
33
|
|
|
34 rows([], []).
|
|
|
35 % This is a bit weird - Tail on the left matches and populates Tail on the right
|
|
|
36 % Then we invoke the sub-goal and generate RowTail recursively, which populates
|
|
|
37 % RowTail on the left. Easier than assignment, and probably tail recursive.
|
|
|
38 rows([(Row, _)|Tail], [Row|RowTail]) :- rows(Tail, RowTail).
|
|
|
39
|
|
|
40 columns([], []).
|
|
|
41 columns([(_, Col)|Tail], [Col|ColTail]) :- columns(Tail, ColTail).
|
|
|
42
|
|
|
43 diagonals_nw_se([], []).
|
|
|
44 % Diagonals intersec the axis at consistent places, which we can approximate with Row + Col
|
|
|
45 diagonals_nw_se([(Row,Col)|Tail], [Diag|DiagTail]) :- Diag is Row + Col, diagonals_nw_se(Tail, DiagTail).
|
|
|
46
|
|
|
47 diagonals_sw_ne([], []).
|
|
|
48 % Ditto the other diagonal, but use Row - Col because they slope the other way
|
|
|
49 diagonals_sw_ne([(Row,Col)|Tail], [Diag|DiagTail]) :- Diag is Row - Col, diagonals_sw_ne(Tail, DiagTail). |
