Dominoes on a Chessboard

This code requires the Exact Cover package.

% dominoes_on_chessboard(MissingCells, N, Cover) is true if Cover is a way of
%   covering all cells except MissingCells on an NxN chessboard, where the 
%   cells are numbered from 1 to NxN. It is required that the list of
%   MissingCells be ordered. On backtracking, all solutions will be found.
% e.g. findall(Cover, dominoes_on_chessboard([3,5,11,13], 4, Cover), Covers)
%   gives Covers=[[[1,2],[4,8],[6,7],[9,10],[12,16],[14,15]]]
dominoes_on_chessboard(MissingCells, N, Cover):-
  is_ordered(MissingCells),
  is_admissible(MissingCells, N, 0),
  N2 is N * N,
  findall(Cell, for(1, N2, Cell), AllCells),
  ord_diff(AllCells, MissingCells, Set),
  findall(Subset, domino(MissingCells, N, Subset), Subsets),
  excov(Set, Subsets, UnsortedCover),
  sort(UnsortedCover, Cover).
   
% is_admissible(MissingCells, N, 0) is true if, on an NxN chessboard, there are
%   the same number of MissingCells of each colour for even N, and one more
%   white MissingCell than black MissingCells for odd N.
% e.g. is_admissible([3,5,11,13], 4, 0) succeeds.
is_admissible([], N, I):-
  I =:= N mod 2.
is_admissible([Cell|MissingCells], N, I):-
  colour(Cell, N, white), !,
  I1 is I + 1,
  is_admissible(MissingCells, N, I1).
is_admissible([_|MissingCells], N, I):-
  I1 is I - 1,
  is_admissible(MissingCells, N, I1).

% colour(Cell, N, Colour) is true if Colour is the colour of the Cell on
%   an NxN chessboard, the first cell being white.
% e.g. colour(21, 8, Colour) gives Colour=white
colour(Cell, N, Colour):-
  ((Cell - 1) // N) mod 2 =:= ((Cell - 1) mod N) mod 2, !,
  Colour = white.
colour(_, _, black).

% domino(MissingCells, N, [A,B]) is true if A and B are adjacent cells on an
%   NxN chessboard, and neither A nor B is a member of MissingCells.
%   On backtracking, all solutions will be found.
% e.g. findall(Subset, domino([5,14], 4, Subset), Subsets) gives
%   Subsets=[[1,2],[2,3],[3,4],[6,7],[7,8],[9,10],[10,11],[11,12],[15,16],
%            [9,13],[2,6],[6,10],[3,7],[7,11],[11,15],[4,8],[8,12],[12,16]]
domino(MissingCells, N, [A,B]):- % Horizontal domino
  N_1 is N - 1,
  N_2 is N - 2,
  for(0, N_1, Row),
  for(0, N_2, Column),
  A is N * Row + Column + 1,
  \+ member(A, MissingCells),
  B is A + 1,
  \+ member(B, MissingCells).
domino(MissingCells, N, [A,B]):- % Vertical domino
  N_1 is N - 1,
  N_2 is N - 2,
  for(0, N_1, Column),
  for(0, N_2, Row),
  A is N * Row + Column + 1,
  \+ member(A, MissingCells),
  B is A + N,
  \+ member(B, MissingCells).

% is_ordered(List) is true if the elements of the List are in ascending
%   order of sequence.
is_ordered([]).
is_ordered([X|Xs]):-is_ordered_1(Xs, X).

is_ordered_1([], _).
is_ordered_1([X|Xs], Y):-X > Y, is_ordered_1(Xs, X).

% ord_diff(Set1, Set2, Difference) is true if Set1 and Set2 are the         
%   ordered representations of two sets and Difference is unified with      
%   the ordered representation of their difference.
ord_diff([], _, []). 
ord_diff([X|Xs], [], [X|Xs]). 
ord_diff([X|Xs], [X|Ys], Ds):-!,
  ord_diff(Xs, Ys, Ds). 
ord_diff([X|Xs], [Y|Ys], [X|Ds]):-
  X < Y, !, ord_diff(Xs, [Y|Ys], Ds). 
ord_diff([X|Xs], [_|Ys], Ds):-
  ord_diff([X|Xs], Ys, Ds). 

% member(X, Xs) is true if the element X is contained in the list Xs.
%member(X, [X|_]).
%member(X, [_|Xs]):-member(X, Xs).

LPA Index     Home Page

Valid HTML 4.01 Strict