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