dominopuzzle.pi

/* 

  Domino puzzle in Picat.

  This model based on the B-Prolog model dominopuzzle.pl
  (with some improvements and generalizations).
  """  
  Title: Dominoes
  Solved by: Neng-Fa Zhou (Dec. 2009, adapated using foreach and list comprehension)
  Publication: Dell Logic Puzzles
  Issue: Sep. 2001
  Page: 19
  Stars: 3

  The dominoes of an ordinary double-six set have been scrambled and arranged into 
  the pattern shown below. Each number shows the number of pips in that square, from 
  zero to six, but the boundaries between the dominoes have all been removed. Can you 
  deduce where each domino is, and draw in the lines to show how they are arranged? 
  Each domino is used exactly once. 

  There are 28 dominoes: 0-0, 0-1, 0-2, ... 5-5, 5-6, 6-6. 

  Puzzle pattern:

  3 1 2 6 6 1 2 2
  3 4 1 5 3 0 3 6
  5 6 6 1 2 4 5 0
  5 6 4 1 3 3 0 0 
  6 1 0 6 3 2 4 0
  4 1 5 2 4 3 5 5
  4 1 0 2 4 5 2 0 
  """


  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import sat,util. % sat is much faster than cp, at least for the larger instances

main => go.


go =>
  nolog,
  instances(simple,Simple),
  instances(gecode,Gecode),
  instances(sicstus_simple,SicstusSimple),
  % instances(sicstus_harder,SicstusHarder), % see go2/0
  All = Simple ++ Gecode ++ SicstusSimple, % ++ SicstusHarder,

  Problems = All,
  
  foreach(P in Problems)
    println(p=P),
    time2(do_domino(P)),
    nl
  end,
  nl.


%
% SICStus' harder problems
%
go2 =>
  nolog,
  instances(sicstus_harder,SicstusHarder),     
  foreach(P in SicstusHarder)
    println(p=P),
    time2(do_domino(P)),
    nl
  end,
  nl.

%
% Count the number of solutions
%
go3 ?=>
  nolog,
  instances(sicstus_simple,Problems),
  foreach(P in Problems)
    println(p=P),
    data(P,Config),
    time2(Count = count_all(domino(Config,_,_,_))),
    println(count=Count),
    nl
  end,
  nl.

go3 => true.

go4 =>
  do_domino(empty),
  nl.


go5 ?=>
  do_domino(dell),
  fail,
  nl.
go5 => true.

%
% Wrapper for running and output.
%
do_domino(Problem) =>
    data(Problem,Config),
    print_config(Config),    
    if domino(Config, Map,A,D) then
      print_solution(Config,A,Map),
      if max(Config.flatten) <= 6 then
        print_board2(A,D)
      end
    else
      println(nosolution)
    end,
    nl.

%
% Print problem instance
%
print_config(A) =>
 println("Problem instance:"),
 foreach(I in 1..A.len)
   foreach(J in 1..A[1].len)
     if nonvar(A[I,J]) then
       printf("%3d ",A[I,J])
     else
       print("_   ")     
     end
   end,
   nl
 end,
 nl.

%
% Print the solution
% 
print_solution(Config,A,Map) =>
 % For nicer presentation of the solution
 FStr = "%d-%d",
 if Config.flatten.max > 6 then
   FStr := "%2d-%2d"
 end,
 foreach(I in 1..A.len)
   foreach(J in 1..A[1].len)
     [S,T] = Map.get(A[I,J]),
     printf("%5w ",to_fstring(FStr,S,T))
   end,
   nl
 end,
 nl.


%
% "Gecode representation"
% For the 7x8 problems
% Example:
% 
%   Pieces:
%   10 10  9 27 22  2 14 14
%   20 20  9 27 22  2 21  7
%   26 28 28  8 16 16 21  7
%   26 13  5  8 19  4  4  1
%   25 13  5 18 19 15 24  1
%   25 12 12 18 23 15 24  6
%   11 11  3  3 23 17 17  6
%
%   Gecode's representation:
%   998QL1DD
%   JJ8QL1K6
%   PRR7FFK6
%   PC47I330
%   OC4HIEN0
%   OBBHMEN5
%   AA22MGG5
%
print_board2(A,D) =>
  println("Gecode representation:"),
  S = "0123456789ABCDEFGHIJKLMNOPQR",
  foreach(I in 1..A.len)
    foreach(J in 1..A[1].len)
      nth(Ix,D,A[I,J]),
      % printf("%w (%d)",S[Ix],Ix)
      printf("%w",S[Ix])
    end,
    nl
  end,
  nl.


%
% Solve a domino instance (Config).
%
domino(Config, Map,A,D) =>
    Rows = Config.len,
    Cols = Config[1].len,

    % To handle larger instances (i.e. max val > 9)
    % we have to tweak a little
    MaxVal = max(Config.flatten),
    if MaxVal < 10 then
      ModVal = 10
    else
      ModVal = MaxVal+1
    end,
    println([rows=Rows,cols=Cols]),
    
    A = new_array(Rows,Cols),
    Vars = A.vars,
    
    % Map: Value -> Domino
    Map = new_map([X=[I,J] : I in 0..MaxVal, J in I..MaxVal, X = I*ModVal+J]),  % D=[0,1,6,11,..,16,...,55,56,66]
    println(map),
    D = keys(Map),
    Vars :: D,
    println(d=D),

    % All possible combinations
    Table = [{E,Rem} : E in D, Rem = E mod ModVal] ++ [{E,Div} : E in D, Div = E // ModVal],
    println(table=Table),

    foreach(I in 1..Rows, J in 1..Cols)
      table_in({A[I,J],Config[I,J]}, Table),
      form_domino(A,I,J)
    end,

    Values = [$X-2 : X in D],
    global_cardinality(Vars,Values),
    % foreach(P in D) 
    %   count(P,Vars, #=, 2)
    % end,

    println(solve),
    solve($[ff,split],Vars),
    foreach(Row in A) println(Row) end, nl.
    

%
% Exactly one of A[I,J]'s neighbors is the same as A[I,J]
%
form_domino(A,I,J)=>
  R = A.len,
  C = A[1].len,
  sum([(A[I1,J1]#=A[I,J]) : 
      I1 in I-1..I+1, J1 in J-1..J+1, 
      I1>0, I1=<R, J1>0, J1=<C,
      (I1==I;J1==J), (I,J)!=(I1,J1)]) #= 1.


%
% Most of the instances are in MiniZinc format, i.e. just a single list.
% And since I'm lazy, I convert this representation to a proper matrix.
%
convert_board(R,C,Board0) = Board.array_matrix_to_list_matrix =>
  Board = new_array(R,C),
  foreach(I in 0..R-1, J in 0..C-1)
    Board[I+1,J+1] := Board0[C*I+J+1]
  end.

% collections of instances
instances(simple,[dell,glaeser,eclipse,vaderlind1,vaderlind2,vaderlind3]).
instances(gecode,[gecode0,gecode1,gecode2,gecode3,gecode4,gecode5]).

instances(sicstus_simple,[sicstusa,sicstus51,sicstus71,sicstus72,sicstus81,sicstus82,sicstus91,sicstus101,sicstus111]).
instances(sicstus_harder,[sicstus121,sicstus181,sicstus182,sicstus201,sicstus221,sicstus251]).


data(empty,Board)=>
  Board = [[_,_,_,_,6,_,_,_],
           [_,_,_,_,_,_,_,_],
           [_,_,_,_,_,_,_,_],
           [_,_,_,_,_,_,_,_],
           [_,_,_,_,_,_,_,_],
           [_,_,_,_,_,_,_,_],
           [_,_,_,_,_,_,_,_]].


%
% The Dell Logic Puzzle example from the B-Prolog model
%
data(dell,Board)=>
  Board = [[3,1,2,6,6,1,2,2],
           [3,4,1,5,3,0,3,6],
           [5,6,6,1,2,4,5,0],
           [5,6,4,1,3,3,0,0],
           [6,1,0,6,3,2,4,0],
           [4,1,5,2,4,3,5,5],
           [4,1,0,2,4,5,2,0]].


% From "Glaeser's Dominoes":
% http://www.math.grin.edu/~rebelsky/ProblemSolving/Problems/glaesers-dominoes.html
% """
% [From Thinking Mathematically, p. 172]
% 
% George Glaeser of Strasbourg put a set of dominoes more or less randomly 
% in a flat tray and took a photograph. The exposure was not correct, and 
% although the numbers can be discerned, the positions of the individual 
% dominoes cannot.
% 
% Each domino is a rectangle composed of two adjacent squares, each with a 
% number. In the set there is only one domino with each combination of 
% numbers from the numbers 0 through 6. For example, there is one domino 
% with 2,3, and one with 4,4.
% 
% Can you reconstruct the dominoes? 
% """
% 
% Note: This has 8 rows and 7 columns (it use to be the other way around).
%
data(glaeser,Config) => 
  Config = [
     [3,6,2,0,0,4,4],
     [6,5,5,1,5,2,3],
     [6,1,1,5,0,6,3],
     [2,2,2,0,0,1,0],
     [2,1,1,4,3,5,5],
     [4,3,6,4,4,2,2],
     [4,5,0,5,3,3,4],
     [1,6,3,0,1,6,6]].


%
% From Gecode's examples/domino.cc Example 0
%
data(gecode0,Board) =>
  Board = [[2,1,0,3,0,4,5,5],
         [6,2,0,6,3,1,4,0],
         [3,2,3,6,2,5,4,3],
         [5,4,5,1,1,2,1,2],
         [0,0,1,5,0,5,4,4],
         [4,6,2,1,3,6,6,1],
         [4,2,0,6,5,3,3,6]].

%
% From Gecode's examples/domino.cc Example 1
%
data(gecode1,Board) => 
 R = 7,
 C = 8,
 Board0 = 
    [
      5,1,2,4,6,2,0,5,
      6,6,4,3,5,0,1,5,
      2,0,4,0,4,0,5,0,
      6,1,3,6,3,5,4,3,
      3,1,0,1,2,2,1,4,
      3,6,6,2,4,0,5,4,
      1,3,6,1,2,3,5,2
    ],
 Board = convert_board(R,C,Board0).

%
% From Gecode's examples/domino.cc Example 2
%
data(gecode2,Board) => 
 R = 7,
 C = 8,
 Board0 = 
    [
      4,4,5,4,0,3,6,5,
      1,6,0,1,5,3,4,1,
      2,6,2,2,5,3,6,0,
      1,3,0,6,4,4,2,3,
      3,5,5,2,4,2,2,1,
      2,1,3,3,5,6,6,1,
      5,1,6,0,0,0,4,0
    ],
 Board = convert_board(R,C,Board0).


%
% From Gecode's examples/domino.cc Example 3
%
data(gecode3,Board) => 
 R = 7,
 C = 8,
 Board0 = 
    [
      3,0,2,3,3,4,4,3,
      6,5,3,4,2,0,2,1,
      6,5,1,2,3,0,2,0,
      4,5,4,1,6,6,2,5,
      4,3,6,1,0,4,5,5,
      1,3,2,5,6,0,0,1,
      0,5,4,6,2,1,6,1
    ],
 Board = convert_board(R,C,Board0).


%
% From Gecode's examples/domino.cc Example 4
%
data(gecode4,Board) =>
 R = 7,
 C = 8,
 Board0 = 
    [
      4,1,5,2,4,4,6,2,
      2,5,6,1,4,6,0,2,
      6,5,1,1,0,1,4,3,
      6,2,1,1,3,2,0,6,
      3,6,3,3,5,5,0,5,
      3,0,1,0,0,5,4,3,
      3,2,4,5,4,2,6,0
    ],
 Board = convert_board(R,C,Board0).


%
% From Gecode's examples/domino.cc Example 5
% 
data(gecode5,Board) =>
 R = 7,
 C = 8,
 Board0 = 
    [
      4,1,2,1,0,2,4,4,
      5,5,6,6,0,4,6,3,
      6,0,5,1,1,0,5,3,
      3,4,2,2,0,3,1,2,
      3,6,5,6,1,2,3,2,
      2,5,0,6,6,3,3,5,
      4,1,0,0,4,1,4,5
    ],
 Board = convert_board(R,C,Board0).


%
% From ECLiPSe's example domino.ecl
%
data(eclipse,Board) => 
 R = 7,
 C = 8,
 Board0 = 
     [
      3,1,2,6,6,1,2,2,
      3,4,1,5,3,0,3,6,
      5,6,6,1,2,4,5,0,
      5,6,4,1,3,3,0,0,
      6,1,0,6,3,2,4,0,
      4,1,5,2,4,3,5,5,
      4,1,0,2,4,5,2,0
    ],
 Board = convert_board(R,C,Board0).


%
% From SICStus example dominoes.pl (instance a)
%
data(sicstusa,Board) => 
 R = 7,
 C = 8,
 Board0 = 
     [
      1,6,3,6,0,6,0,2,
      6,2,2,6,6,5,3,1,
      2,4,1,2,4,4,5,0,
      0,5,5,3,0,4,0,3,
      4,1,3,1,4,5,3,3,
      1,5,0,0,1,6,4,2,
      6,2,3,2,1,4,5,5
    ],
 Board = convert_board(R,C,Board0).


%
% From SICStus example dominoes.pl (instance 51)
% It has 110 solutions
%
data(sicstus51,Board) => 
 R = 6,
 C = 7,
 Board0 = 
     [
       3,4,2,1,1,2,0,
       0,4,1,5,1,4,4,
       2,0,0,5,5,3,3,
       4,0,1,3,0,3,2,
       5,0,3,5,4,1,2,
       4,5,2,5,1,3,2
    ],
 Board = convert_board(R,C,Board0).

% From SICStus example dominoes.pl (instance 71)
data(sicstus71,Board) => 
 R = 8,
 C = 9,
 Board0 =
     [
        0,3,1,4,3,6,1,5,3,
        7,4,6,5,4,7,0,0,7,
        2,3,2,4,1,0,5,5,7,
        1,3,3,4,3,2,4,4,0,
        0,4,6,2,6,6,5,3,5,
        5,6,6,1,1,2,2,0,2,
        1,7,7,6,1,7,2,6,2,
        7,1,0,4,5,7,3,5,0
    ],
 Board = convert_board(R,C,Board0).



% From SICStus example dominoes.pl (instance 72)
% This has no solution.
data(sicstus72, Board) => 
 R = 8,
 C = 9,
 Board0 = 
     [
        0,1,1,3,6,0,4,7,3,
        4,7,0,3,0,2,2,0,2,
        1,5,0,2,1,3,4,5,6,
        2,5,5,1,1,6,0,3,1,
        2,1,0,7,5,2,7,6,4,
        3,5,6,6,5,7,4,7,6,
        3,4,2,7,5,7,4,4,5,
        6,6,4,3,2,7,0,1,3
    ],
 Board = convert_board(R,C,Board0).

% From SICStus example dominoes.pl (instance 81)
% (8 solutions)
data(sicstus81,Board) => 
 R = 9,
 C = 10,
 Board0 = 
     [
        5,1,3,1,5,1,6,8,8,5,
        3,8,3,0,5,6,0,2,8,3,
        0,0,8,6,4,4,4,6,6,8,
        0,7,4,3,5,6,4,3,0,0,
        8,5,6,7,2,4,7,4,2,5,
        7,8,1,2,5,3,1,5,2,8,
        7,5,4,3,2,7,7,1,7,1,
        8,0,4,1,0,1,2,1,0,7,
        7,4,3,2,3,6,6,6,2,2

    ],
 Board = convert_board(R,C,Board0).



% From SICStus example dominoes.pl (instance 82)
% (8 solutions)
data(sicstus82,Board) => 
 R = 9,
 C = 10,
 Board0 = 
     [
        6,4,4,1,2,2,8,7,1,1,
        6,7,2,3,8,1,2,1,5,1,
        6,8,3,1,2,5,5,1,6,4,
        6,8,0,0,0,0,0,7,2,5,
        7,7,8,0,0,0,4,3,3,5,
        8,8,8,0,0,1,2,8,4,4,
        4,6,5,6,3,5,3,7,4,7,
        3,8,7,2,3,5,5,6,1,2,
        6,3,5,3,4,4,7,7,2,6

    ],
 Board = convert_board(R,C,Board0).


% From SICStus example dominoes.pl (instance 91)
% (1 solution)
data(sicstus91,Board) => 
 R = 10,
 C = 11,
 Board0 = 
     [
        7,8,9,9,7,4,4,6,3,1,8,
        8,3,0,4,4,9,9,9,3,9,7,
        8,6,5,3,0,4,8,0,2,5,4,
        2,0,4,6,8,7,5,0,8,1,2,
        3,6,5,1,6,3,4,3,3,7,2,
        2,0,2,1,7,8,5,9,1,9,2,
        7,3,3,9,3,5,2,6,6,5,1,
        6,8,4,7,1,5,0,7,0,8,1,
        2,9,6,7,5,0,1,1,2,9,2,
        6,5,8,6,0,4,1,7,5,0,4
    ],
 Board = convert_board(R,C,Board0).





% From SICStus example dominoes.pl (instance 101)
% (8 solutions)
data(sicstus101,Board) => 
 Board = 
     [
        [8, 5,10, 1, 3, 4, 2, 3, 6, 4, 4, 3],
        [5, 6, 9, 2, 7, 3, 1, 8, 1, 3, 4, 3],
        [4, 8, 0, 2, 0, 5, 7, 1, 9, 2, 8, 8],
        [3, 0, 9, 8, 3, 2, 9, 6,10, 9, 4, 7],
        [4, 1,10, 5, 2, 5, 7, 9, 1, 5, 1, 3],
        [1, 0, 1, 0, 4, 7, 3, 9, 7, 6,10, 6],
        [4, 0, 8, 1, 9, 3, 10,8, 8, 0, 2, 6],
        [0, 7, 6, 2, 1,10, 5, 6, 9,10, 7, 0],
        [2, 7, 7, 2, 1, 2, 6, 3, 9, 5, 6, 9],
        [8,10, 4, 5, 0, 7, 2,10,10, 5, 8, 6],
        [0,10, 5, 4, 4, 8, 5, 9,10, 0, 7, 6]].


% From SICStus example dominoes.pl (instance 111)
% (12 solutions)
data(sicstus111,Board) =>
  R = 12,
  C = 13,
  Board0 = 
     [
        1,4,4,8,2,8,3,2,9,11,10,1,7,
        7,0,2,8,8,9,11,0,0,10,5,2,0,
        3,9,2,9,0,1,3,11,8,1,1,7,7,
        1,4,2,10,0,8,7,2,1,11,0,1,7,
        0,11,2,9,6,11,9,5,9,6,10,1,7,
        10,4,9,8,6,5,4,6,10,5,2,7,6,
        6,6,2,6,6,0,6,3,0,10,5,8,11,
        4,9,5,3,0,10,7,7,8,2,3,10,3,
        1,9,0,10,5,7,8,4,9,11,8,8,9,
        4,4,0,10,11,11,2,10,4,7,5,5,11,
        3,6,2,1,6,10,4,3,3,5,6,5,7,
        1,9,3,4,1,5,11,5,3,8,11,3,4

    ],
  Board = convert_board(R,C,Board0).


% From SICStus example dominoes.pl (instance 121)
% (10 solutions)
data(sicstus121,Board) => 
  R = 13,
  C = 14,
  Board0 = 
     [
        4,0,6,8,7,11,4,3,8,3,3,6,3,6,
        10,1,2,2,9,11,7,4,10,12,3,6,10,10,
        8,2,12,0,2,5,5,2,5,1,7,4,3,3,
        6,2,9,4,10,9,3,11,6,11,9,6,7,7,
        7,3,4,2,0,10,12,7,4,9,12,8,1,11,
        7,8,1,7,5,5,10,3,9,1,4,10,8,0,
        12,2,1,1,7,8,8,9,9,9,1,7,12,0,
        5,4,2,0,1,4,5,6,2,0,6,8,8,12,
        0,0,7,10,6,1,11,9,2,8,1,5,4,4,
        6,10,10,12,5,7,10,0,11,2,10,4,9,5,
        6,5,11,12,6,11,11,3,1,2,2,11,8,1,
        9,0,11,5,5,8,12,12,11,1,10,9,5,0,
        3,0,11,9,6,12,4,12,8,3,0,7,3,12

   ],
  Board = convert_board(R,C,Board0).

% From SICStus example dominoes.pl (instance 181)
% (96 solutions)
data(sicstus181,Board) => 
 R = 19,
 C = 20,
 Board0 = 
     [
        16,12,10,18 ,2,15 ,8,14 ,1,17 ,6 ,7 ,9,10 ,0 ,2 ,7,11,13,11,
        18 ,4,18 ,6 ,7 ,3,18,13 ,5 ,7 ,5 ,4 ,5,17,11,11 ,6,18,16 ,1,
        10,10 ,1 ,2,16 ,4 ,6,16,11,13,11 ,6,13 ,5 ,1 ,1 ,3,14,15 ,3,
        13,10 ,8 ,8 ,4,13 ,7 ,0 ,1 ,4,13,18,12,16 ,2 ,4 ,9,13 ,1 ,8,
        0 ,4 ,6 ,3,10 ,8 ,1 ,3 ,0 ,9 ,4,18 ,9 ,2 ,2 ,3,16 ,8,16,18,
        10 ,8 ,7 ,3 ,5 ,5 ,9,12 ,6,18 ,0 ,3 ,9,10,14,14,11,12 ,8,11,
        7,17 ,0 ,8 ,0,13 ,2,11,11,17,13,13 ,8 ,6,15,17,17,12,14 ,0,
        6 ,1 ,0 ,1,18,12 ,5,16,13 ,7 ,1,14,10,12 ,3,18,14,11,16 ,5,
        6 ,3 ,0 ,0,10 ,1 ,2,15 ,9,12 ,7,14,15 ,5 ,8,18 ,9 ,0,16,12,
        16,17,15,16,12 ,4,14 ,6,11 ,4,15,14,15,10 ,2 ,4,15 ,5 ,2 ,3,
        10,12 ,9,13,12,12,17 ,7 ,4,16 ,0 ,1,10 ,9 ,7 ,4 ,5,17 ,9 ,5,
        17 ,0,15 ,6,11,17 ,6,13,14 ,9,17 ,9,12 ,8 ,8,15,16 ,7,12 ,5,
        8 ,3,14,17 ,8,13,16 ,2,15,17 ,2 ,8 ,2,16,14,11,10,15,14 ,0,
        18,12,16,12 ,2 ,5,15 ,0 ,6,14 ,3 ,4,18 ,7,12,11 ,6,18,16,13,
        14,16 ,9,11,18 ,0 ,6,15,15 ,3 ,8,18 ,5,10 ,3,16 ,2 ,3 ,9 ,5,
        11,17 ,9 ,2,13 ,1 ,2,14 ,4 ,7 ,7 ,4,18 ,6 ,9,13,13 ,4 ,3,11,
        0 ,5,14 ,4 ,4,17 ,1 ,7 ,8 ,1 ,9,11 ,2 ,0,18 ,8 ,5 ,9 ,2 ,7,
        7,11,17 ,9,10,15,12,12,15 ,5 ,7,10 ,4 ,6 ,1 ,0,10,13,14 ,7,
        18,14 ,5,17 ,3,10 ,2,15 ,3 ,6,17,17 ,6 ,1 ,1 ,8 ,1,15,10 ,3

  ],
  Board = convert_board(R,C,Board0).



% From SICStus example dominoes.pl (instance 182)
% (2 solutions)
data(sicstus182, Board) => 
 R = 19,
 C = 20,
 Board0 = 
     [
        12,6,15,11,10,9,3,6,0,15,1,13,4,4,16,9,18,5,7,9 ,
        9,4,8,15,4,16,3,1,4,9,0,7,14,18,18,0,8,11,17,17 ,
        0,12,14,8,12,12,13,6,6,8,0,17,5,18,3,18,8,11,15,17 ,
        7,7,8,5,4,3,5,7,0,15,2,2,0,18,0,10,12,0,1,17 ,
        1,14,17,14,10,5,1,16,8,3,15,13,17,1,11,9,6,0,3,18 ,
        8,10,7,6,14,14,3,16,8,10,14,12,11,2,11,17,16,11,14,7 ,
        4,7,13,10,0,5,16,10,14,14,3,9,18,15,15,2,6,11,6,6 ,
        2,11,1,13,18,5,16,18,13,13,7,11,13,10,16,3,3,14,12,9 ,
        2,5,5,4,8,2,9,18,9,16,18,0,11,5,5,13,16,16,11,7 ,
        3,9,4,1,1,11,9,15,18,15,17,2,15,9,6,3,12,11,7,8 ,
        7,1,11,12,12,5,3,16,17,14,8,7,10,17,5,11,1,7,12,16 ,
        18,14,16,17,5,12,6,9,8,14,13,2,8,16,10,16,12,15,5,10 ,
        1,9,10,3,3,10,15,2,5,1,13,13,4,2,2,4,13,18,17,6 ,
        10,7,10,4,3,18,14,1,10,12,18,9,6,1,16,9,4,4,9,13 ,
        2,14,3,16,2,7,0,0,16,2,17,5,13,11,4,15,13,15,4,13 ,
        2,1,15,12,5,4,15,4,15,6,18,6,8,8,17,5,0,12,14,15 ,
        0,0,7,14,0,8,17,0,14,17,6,15,5,6,3,7,9,1,6,14 ,
        10,18,17,10,12,17,11,11,4,0,8,3,10,1,1,2,12,2,13,13 ,
        10,9,16,8,13,12,3,11,6,7,1,12,8,7,2,18,17,6,2,4
  ],
 Board = convert_board(R,C,Board0).



% From SICStus example dominoes.pl (instance 201)
% (16 solutions)
data(sicstus201,Board) => 
 R = 21,
 C = 22,
 Board0 = 
     [
        3,13,0,10,8,18,0,6,11,2,5,1,4,0,13,11,17,8,19,20,5,19 ,
        20,5,0,4,8,0,10,15,0,12,15,20,20,16,11,11,7,14,16,11,4,3 ,
        20,7,0,5,3,10,3,14,4,11,8,18,2,19,7,15,10,0,8,14,7,4 ,
        11,20,4,13,14,4,11,9,17,6,7,7,15,17,9,3,12,20,14,6,8,13 ,
        18,10,14,18,14,2,13,0,17,7,18,19,10,11,12,6,10,16,14,7,9,20 ,
        5,3,6,11,3,1,17,6,15,0,11,0,20,10,13,6,1,19,6,5,5,7 ,
        16,14,10,9,16,15,3,18,14,18,1,8,16,16,6,11,6,20,1,16,18,8 ,
        20,7,6,13,7,18,1,16,4,11,8,9,6,9,3,5,20,6,6,10,2,17 ,
        8,14,4,2,0,9,1,0,9,5,8,9,1,2,8,4,12,2,1,1,16,9 ,
        14,15,17,3,16,13,0,19,9,2,6,1,17,14,3,10,12,6,12,2,4,11 ,
        19,19,16,17,14,17,8,13,2,11,7,3,7,2,0,14,1,13,18,2,12,7 ,
        20,3,9,13,20,10,12,8,16,1,0,15,11,9,17,1,13,16,19,7,19,17 ,
        7,10,19,1,14,10,0,8,11,4,2,12,5,3,20,11,8,2,5,7,14,12 ,
        10,13,9,17,16,6,5,3,19,5,12,9,13,12,5,19,4,20,8,1,11,3 ,
        2,3,20,17,19,18,8,3,17,4,14,13,17,13,10,2,2,15,12,15,19,4 ,
        18,6,18,12,20,5,18,15,17,6,10,13,5,3,7,1,11,18,14,15,5,15 ,
        11,8,1,3,2,19,15,6,18,20,1,17,10,16,2,11,12,4,10,5,7,16 ,
        10,10,16,15,18,1,9,15,4,18,4,4,6,9,9,12,8,18,19,13,15,14 ,
        18,0,9,9,4,18,0,8,2,18,0,7,20,15,17,19,15,3,2,17,1,5 ,
        17,15,9,15,5,14,19,5,9,12,12,19,12,16,12,1,6,12,19,4,20,13 ,
        16,16,7,8,10,20,5,0,16,3,12,4,2,17,14,13,15,13,19,0,7,13

  ],
 Board = convert_board(R,C,Board0).


% From SICStus example dominoes.pl (instance 221)
% (32 solutions)
data(sicstus221, Board) => 
 R = 23,
 C = 24,
 Board0 = 
     [
        13,20,3,12,21,20,1,17,1,18,11,4,9,11,15,22,22,12,11,13,13,15,3,14 ,
        5,15,2,5,9,21,15,21,10,2,15,9,10,18,8,8,15,17,19,19,0,18,8,4 ,
        8,10,17,9,22,15,15,10,2,9,5,15,16,22,2,11,1,12,3,13,1,14,14,17 ,
        8,21,20,14,22,21,5,18,5,21,19,17,4,13,6,9,2,17,17,12,19,22,19,1 ,
        12,16,21,3,6,18,18,9,1,20,2,17,2,4,14,1,12,6,18,20,20,16,16,12 ,
        0,20,13,5,10,3,21,4,10,14,17,16,14,6,14,10,22,10,10,4,21,21,9,10 ,
        6,21,3,22,16,9,17,4,20,12,10,13,9,6,13,14,5,0,7,18,12,6,13,17 ,
        2,6,9,20,19,7,7,3,15,14,20,5,22,15,2,12,1,9,17,15,0,19,0,3 ,
        2,12,11,1,0,12,22,5,2,8,20,19,7,19,1,5,20,18,11,7,2,9,6,7 ,
        14,8,17,8,22,1,1,16,0,13,11,22,16,14,2,0,15,7,11,15,11,21,1,10 ,
        21,12,15,1,14,14,4,17,8,20,13,12,7,12,3,10,19,16,18,9,4,13,10,5 ,
        18,17,22,3,5,20,5,6,14,11,16,2,15,12,13,0,8,11,17,9,22,22,13,1 ,
        5,11,5,19,6,18,6,6,6,1,13,7,17,22,18,11,8,16,7,7,10,8,2,3 ,
        21,0,0,9,8,3,15,3,16,0,18,10,18,20,9,15,17,16,21,0,19,5,22,20 ,
        6,8,11,10,2,2,21,13,11,19,13,6,13,3,7,1,14,13,14,4,10,2,3,4 ,
        7,4,4,19,19,9,21,12,16,2,1,4,2,0,8,8,3,0,6,14,7,21,3,14 ,
        19,16,19,14,22,21,20,9,12,17,4,12,10,10,20,18,12,11,20,0,6,7,8,14 ,
        19,2,9,3,7,6,19,8,4,2,4,6,22,20,13,3,5,8,17,21,17,16,18,4 ,
        5,7,20,18,19,3,20,5,14,7,7,16,16,0,0,9,5,15,1,16,18,13,11,22 ,
        11,18,19,14,2,21,15,7,6,18,1,4,10,11,6,4,11,3,7,5,1,1,20,9 ,
        0,15,10,1,13,0,0,0,9,22,12,22,14,8,16,10,6,22,20,22,4,16,16,18 ,
        17,12,18,4,4,11,16,9,15,13,2,0,8,21,8,7,19,3,19,8,12,0,3,8 ,
        1,18,11,7,15,21,16,6,5,4,10,3,11,13,19,21,11,12,17,5,17,5,15,7
  ],
 Board = convert_board(R,C,Board0).


% From SICStus example dominoes.pl (instance 251)
% (8 solutions)
data(sicstus251,Board) => 
 R = 26,
 C = 27,
 Board0 = 
     [
        16,12,8,18,15,10,7,9,9,10,8,23,22,6,2,7,18,13,24,19,24,8,5,5,0,4,22 ,
        3,0,1,5,14,20,9,17,4,24,12,16,6,20,20,14,5,16,6,21,1,15,21,1,14,10,12 ,
        19,18,25,9,24,3,15,25,2,23,10,3,6,21,22,5,15,7,11,16,22,1,19,11,14,21,25 ,
        13,18,9,11,3,23,4,22,8,22,12,1,7,19,4,22,3,0,10,14,25,21,2,6,1,23,10 ,
        17,2,14,0,20,19,18,18,15,12,15,1,24,17,25,10,14,10,22,9,16,3,17,21,11,21,25 ,
        24,10,12,15,16,22,15,9,1,23,4,12,16,18,4,18,6,3,13,7,10,11,4,20,2,1,25 ,
        0,19,24,6,14,3,15,3,10,21,10,0,7,22,4,4,9,12,19,22,18,20,3,0,17,20,23 ,
        15,14,23,21,18,24,2,12,11,11,2,14,10,2,21,13,11,0,11,24,2,2,2,22,15,16,11 ,
        1,2,25,7,15,22,6,1,11,5,20,19,10,11,14,7,17,8,24,20,7,17,6,16,12,8,9 ,
        25,12,11,12,19,11,5,18,13,10,2,0,0,17,9,25,12,4,7,8,19,21,20,4,1,8,4 ,
        17,24,21,10,17,3,1,1,12,4,14,5,8,23,8,5,5,19,1,10,19,13,11,11,3,25,5 ,
        7,23,20,23,23,25,17,4,17,18,12,6,3,19,17,5,13,7,0,24,5,7,23,8,2,18,4 ,
        6,3,14,17,19,13,2,14,8,16,7,6,13,8,25,22,3,19,21,1,2,18,24,10,3,23,20 ,
        3,15,11,16,11,22,17,23,4,2,18,20,8,17,22,22,3,14,21,17,7,17,5,18,9,2,8 ,
        16,16,1,2,12,14,12,6,4,15,19,13,5,0,14,1,24,16,19,5,11,16,8,5,24,0,11 ,
        16,7,13,8,9,9,12,8,21,7,5,16,19,0,1,16,0,9,2,3,21,5,21,6,13,6,17 ,
        15,4,1,8,4,18,9,23,9,1,10,20,24,16,1,0,18,2,19,15,2,21,12,20,3,12,11 ,
        0,9,16,4,20,17,21,25,9,18,4,22,13,3,4,17,24,13,21,23,14,4,0,7,14,5,23 ,
        24,20,22,16,7,10,0,15,18,11,15,23,5,23,0,14,25,13,2,25,18,12,12,19,13,19,10 ,
        24,8,13,25,7,20,19,11,6,24,22,6,25,13,5,22,20,7,5,7,11,14,13,6,9,9,3 ,
        4,19,23,24,18,9,14,9,15,20,20,8,25,3,3,25,17,5,13,25,19,15,17,9,25,16,8 ,
        6,25,22,10,0,0,0,24,4,3,12,21,6,1,0,10,19,1,12,16,20,4,6,21,16,15,25 ,
        2,23,23,13,21,20,22,6,8,13,6,12,15,20,23,23,21,12,11,6,9,0,13,15,8,20,19 ,
        15,13,15,25,17,6,14,14,2,13,24,21,10,14,18,10,17,24,6,5,17,13,1,21,14,8,1 ,
        8,9,7,0,17,10,24,25,15,6,7,18,3,9,22,10,22,24,11,4,25,18,21,9,20,8,0 ,
        22,2,3,7,14,16,22,12,7,19,1,2,18,23,5,11,18,23,23,16,13,15,24,7,5,16,20

  ],
 Board = convert_board(R,C,Board0).


% From Helmut Simonis' paper
% "Dominoes as a Constraint Problem" 
% page 1
%
data(simonis, Board) => 
 R = 7,
 C = 8,
 Board0 = 
     [
       0,5,2,2,5,4,6,5,
       3,6,2,2,4,4,4,1,
       3,6,1,2,3,4,6,1,
       0,1,4,3,0,2,2,1,
       3,5,3,0,3,1,5,6,
       6,4,0,3,6,0,4,1,
       1,6,0,0,2,5,5,5
     ],
 Board = convert_board(R,C,Board0).



% Problem 1 (figure 28, page 42) from the Swedish puzzle book
% by Paul Vaderlind: 
% "Vaderlinds specialblandning: Sudoku, Kakuro och andra rutiga tankelekar"
% (tr. ~ Vaderlind's special brew: Sudoku, Kakuro, and other squared thought games")
%
data(vaderlind1,Board) => 
 R = 7,
 C = 8,
 Board0 = 
     [
     4,0,3,4,2,2,1,1,
     2,3,5,2,6,6,2,5,
     1,3,0,0,1,3,5,5,
     4,5,5,6,1,5,6,4,
     4,2,3,2,0,5,0,1,
     2,0,1,0,6,6,4,0,
     4,3,4,3,6,6,3,1
    ],
 Board = convert_board(R,C,Board0).



% Problem 2 (figure 29, page 43) from the Swedish puzzle book
% by Paul Vaderlind: 
% "Vaderlinds specialblandning: Sudoku, Kakuro och andra rutiga tankelekar"
% (tr. ~ Vaderlind's special brew: Sudoku, Kakuro, and other squared thought games")
%
data(vaderlind2,Board) => 
 R = 7,
 C = 8,
 Board0 = 
     [
      3,3,2,2,0,4,5,5,
      5,1,5,1,2,3,4,5,
      2,1,6,4,6,0,1,0,
      4,6,5,6,6,1,6,5,
      0,6,1,2,6,2,5,0,
      0,2,2,3,3,1,0,0,
      4,3,3,4,4,4,3,1
    ],
 Board = convert_board(R,C,Board0).



% Problem 3 (figure 30, page 44) from the Swedish puzzle book
% by Paul Vaderlind: 
% "Vaderlinds specialblandning: Sudoku, Kakuro och andra rutiga tankelekar"
% (tr. ~ Vaderlind's special brew: Sudoku, Kakuro, and other squared thought games")
%
data(vaderlind3,Board) => 
 R = 7,
 C = 8,
 Board0 = 
     [
       5,0,6,2,2,6,0,1,
       1,2,2,4,4,4,4,5, 
       2,1,1,0,1,0,6,6,
       3,6,1,4,3,4,5,1,
       3,6,3,2,0,4,5,0, 
       5,6,3,0,0,2,5,3,
       5,6,3,5,2,4,1,3
    ],
 Board = convert_board(R,C,Board0).