#### 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),
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.
I =:= N mod 2.
colour(Cell, N, white), !,
I1 is I + 1,
I1 is I - 1,

% 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).
```