%------------------------------------------------------------------------%
% Solving the Black Hole Patience game
%------------------------------------------------------------------------%
%
%  The model of the problem is taken from "Search in the Patience Game
%  'Black Hole'", by Ian P. Gent, Chris Jefferson, Tom Kelsey, Inês
%  Lynce, Ian Miguel, Peter Nightingale, Barbara M. Smith, and
%  S. Armagan Tarim. It only implements the basic model. The instances
%  are generated by the black hole patience model in the Gecode
%  distribution.
%
%  This model uses the following global constraints
%    - inverse
%    - table
%
%  Main authors:
%     Mikael Zayenz Lagerkvist <lagerkvist@gecode.org>
%
%  Copyright:
%     Mikael Zayenz Lagerkvist, 2009
%
%  Permission is hereby granted, free of charge, to any person obtaining
%  a copy of this software and associated documentation files (the
%  "Software"), to deal in the Software without restriction, including
%  without limitation the rights to use, copy, modify, merge, publish,
%  distribute, sublicense, and/or sell copies of the Software, and to
%  permit persons to whom the Software is furnished to do so, subject to
%  the following conditions:
%
%  The above copyright notice and this permission notice shall be
%  included in all copies or substantial portions of the Software.
%
%  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
%  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
%  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
%  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
%  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
%  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
%  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
%
%------------------------------------------------------------------------%

include "table.mzn";
include "inverse.mzn";

%------------------------------------------------------------------------%
% Parameters
%------------------------------------------------------------------------%

% Piles
array[1..17, 1..3] of int: layout;

% Data
%layout = array2d(1..17,1..3, [
%31, 30, 8,
%45, 50, 19,
%37, 12, 47,
%24, 9, 18,
%16, 40, 20,
%38, 36, 49,
%11, 33, 51,
%39, 10, 14,
%3, 27, 46,
%29, 2, 35,
%4, 32, 17,
%15, 13, 5,
%23, 34, 28,
%48, 21, 52,
%22, 6, 42,
%44, 41, 26,
%25, 43, 7
%]);


%------------------------------------------------------------------------%
% Variables
%------------------------------------------------------------------------%

% Card at position
array[1..52] of var 1..52: x;
% Position of card
array[1..52] of var 1..52: y;


%------------------------------------------------------------------------%
% Constraints
%------------------------------------------------------------------------%

% Ace of Spades is first card
constraint x[1] == 1;

% Consecutive cards match
predicate adjacent(var 1..52: a, var 1..52: b) :: presolve(autotable)
= ((a-b) in {13*i+1 | i in -4..3} union {13*i-1 | i in -3..4}) :: domain;

constraint forall(i in 1..51) ( adjacent(x[i], x[i+1]) );

% Link x and y
constraint inverse(x, y) :: domain;


% A card must be played before the one under it.
constraint
	forall(i in 1..17, j in 1..2) (
		 y[layout[i,j]] < y[layout[i,j+1]]
	);


%------------------------------------------------------------------------%
% Search
%------------------------------------------------------------------------%

solve :: int_search(x,
      	            input_order,
		    indomain_min,
		    complete)
satisfy;


output [ "black-hole: ", show(x), "\n" ];