# HG changeset patch
# User IBBoard <dev@ibboard.co.uk>
# Date 1506884388 -3600
# Node ID 69eb40c4679872506c1a700fc30544c041be7b8c
# Parent  f6fce6a54e945789aa94437126b0ee4201ee0465
Add some "Eight Queens" solving

Still trying to get my head in quite the right space.

diff -r f6fce6a54e94 -r 69eb40c46798 3-Prolog/day3-8queens.pl
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/3-Prolog/day3-8queens.pl	Sun Oct 01 19:59:48 2017 +0100
@@ -0,0 +1,49 @@
+% Eight Queens problem, written from just the rules and a few hints on available approaches
+% which includes the "member/2" and other useful functions.
+% This will be MUCH more succinct than defining the entire board and trying
+% to operate on that! Half of the problem is approaching the problem correctly.
+
+eight_queens(List) :-
+    % Check we've got the right length
+    length(List, 8),
+    % Check our values are all valid positions
+    valid_board(List),
+    % Pull out the rows
+    rows(List, Rows),
+    % Pull out the columns
+    columns(List, Cols),
+    % Pull out the diagonals (North-East/South-West)
+    diagonals_sw_ne(List, Diags1),
+    % Pull out the diagonals (North-West/South-East)
+    diagonals_nw_se(List, Diags2),
+
+    % Make sure we have no duplicates - based on the simple Sudoku solver
+    fd_all_different(Rows),
+    fd_all_different(Cols),
+    fd_all_different(Diags1),
+    fd_all_different(Diags2).
+
+valid_board([]).
+valid_board([Head|Tail]) :- valid_queen(Head), valid_board(Tail).
+
+% Queen location defined as a tuple
+valid_queen((Row, Col)) :-
+    Range = [1,2,3,4,5,6,7,8],
+    member(Row, Range), member(Col, Range).
+
+rows([], []).
+% This is a bit weird - Tail on the left matches and populates Tail on the right
+% Then we invoke the sub-goal and generate RowTail recursively, which populates
+% RowTail on the left. Easier than assignment, and probably tail recursive.
+rows([(Row, _)|Tail], [Row|RowTail]) :- rows(Tail, RowTail).
+
+columns([], []).
+columns([(_, Col)|Tail], [Col|ColTail]) :- columns(Tail, ColTail).
+
+diagonals_nw_se([], []).
+% Diagonals intersec the axis at consistent places, which we can approximate with Row + Col
+diagonals_nw_se([(Row,Col)|Tail], [Diag|DiagTail]) :- Diag is Row + Col, diagonals_nw_se(Tail, DiagTail).
+
+diagonals_sw_ne([], []).
+% Ditto the other diagonal, but use Row - Col because they slope the other way
+diagonals_sw_ne([(Row,Col)|Tail], [Diag|DiagTail]) :- Diag is Row - Col, diagonals_sw_ne(Tail, DiagTail).
\ No newline at end of file