%------------------------------------------------------------------------% % 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 % % 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 "globals.mzn"; % Table of matching pairs of cards array[1..416, 1..2] of int: neighbours; %------------------------------------------------------------------------% % 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 :: is_output; % 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 constraint forall(i in 1..51) ( table([x[i], x[i+1]], neighbours) ); % 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; %------------------------------------------------------------------------% % Parameters %------------------------------------------------------------------------% % Neighbours table neighbours = array2d(1..416, 1..2, [ 1, 2, 1, 13, 1, 15, 1, 26, 1, 28, 1, 39, 1, 41, 1, 52, 2, 1, 2, 3, 2, 14, 2, 16, 2, 27, 2, 29, 2, 40, 2, 42, 3, 2, 3, 4, 3, 15, 3, 17, 3, 28, 3, 30, 3, 41, 3, 43, 4, 3, 4, 5, 4, 16, 4, 18, 4, 29, 4, 31, 4, 42, 4, 44, 5, 4, 5, 6, 5, 17, 5, 19, 5, 30, 5, 32, 5, 43, 5, 45, 6, 5, 6, 7, 6, 18, 6, 20, 6, 31, 6, 33, 6, 44, 6, 46, 7, 6, 7, 8, 7, 19, 7, 21, 7, 32, 7, 34, 7, 45, 7, 47, 8, 7, 8, 9, 8, 20, 8, 22, 8, 33, 8, 35, 8, 46, 8, 48, 9, 8, 9, 10, 9, 21, 9, 23, 9, 34, 9, 36, 9, 47, 9, 49, 10, 9, 10, 11, 10, 22, 10, 24, 10, 35, 10, 37, 10, 48, 10, 50, 11, 10, 11, 12, 11, 23, 11, 25, 11, 36, 11, 38, 11, 49, 11, 51, 12, 11, 12, 13, 12, 24, 12, 26, 12, 37, 12, 39, 12, 50, 12, 52, 13, 1, 13, 12, 13, 14, 13, 25, 13, 27, 13, 38, 13, 40, 13, 51, 14, 2, 14, 13, 14, 15, 14, 26, 14, 28, 14, 39, 14, 41, 14, 52, 15, 1, 15, 3, 15, 14, 15, 16, 15, 27, 15, 29, 15, 40, 15, 42, 16, 2, 16, 4, 16, 15, 16, 17, 16, 28, 16, 30, 16, 41, 16, 43, 17, 3, 17, 5, 17, 16, 17, 18, 17, 29, 17, 31, 17, 42, 17, 44, 18, 4, 18, 6, 18, 17, 18, 19, 18, 30, 18, 32, 18, 43, 18, 45, 19, 5, 19, 7, 19, 18, 19, 20, 19, 31, 19, 33, 19, 44, 19, 46, 20, 6, 20, 8, 20, 19, 20, 21, 20, 32, 20, 34, 20, 45, 20, 47, 21, 7, 21, 9, 21, 20, 21, 22, 21, 33, 21, 35, 21, 46, 21, 48, 22, 8, 22, 10, 22, 21, 22, 23, 22, 34, 22, 36, 22, 47, 22, 49, 23, 9, 23, 11, 23, 22, 23, 24, 23, 35, 23, 37, 23, 48, 23, 50, 24, 10, 24, 12, 24, 23, 24, 25, 24, 36, 24, 38, 24, 49, 24, 51, 25, 11, 25, 13, 25, 24, 25, 26, 25, 37, 25, 39, 25, 50, 25, 52, 26, 1, 26, 12, 26, 14, 26, 25, 26, 27, 26, 38, 26, 40, 26, 51, 27, 2, 27, 13, 27, 15, 27, 26, 27, 28, 27, 39, 27, 41, 27, 52, 28, 1, 28, 3, 28, 14, 28, 16, 28, 27, 28, 29, 28, 40, 28, 42, 29, 2, 29, 4, 29, 15, 29, 17, 29, 28, 29, 30, 29, 41, 29, 43, 30, 3, 30, 5, 30, 16, 30, 18, 30, 29, 30, 31, 30, 42, 30, 44, 31, 4, 31, 6, 31, 17, 31, 19, 31, 30, 31, 32, 31, 43, 31, 45, 32, 5, 32, 7, 32, 18, 32, 20, 32, 31, 32, 33, 32, 44, 32, 46, 33, 6, 33, 8, 33, 19, 33, 21, 33, 32, 33, 34, 33, 45, 33, 47, 34, 7, 34, 9, 34, 20, 34, 22, 34, 33, 34, 35, 34, 46, 34, 48, 35, 8, 35, 10, 35, 21, 35, 23, 35, 34, 35, 36, 35, 47, 35, 49, 36, 9, 36, 11, 36, 22, 36, 24, 36, 35, 36, 37, 36, 48, 36, 50, 37, 10, 37, 12, 37, 23, 37, 25, 37, 36, 37, 38, 37, 49, 37, 51, 38, 11, 38, 13, 38, 24, 38, 26, 38, 37, 38, 39, 38, 50, 38, 52, 39, 1, 39, 12, 39, 14, 39, 25, 39, 27, 39, 38, 39, 40, 39, 51, 40, 2, 40, 13, 40, 15, 40, 26, 40, 28, 40, 39, 40, 41, 40, 52, 41, 1, 41, 3, 41, 14, 41, 16, 41, 27, 41, 29, 41, 40, 41, 42, 42, 2, 42, 4, 42, 15, 42, 17, 42, 28, 42, 30, 42, 41, 42, 43, 43, 3, 43, 5, 43, 16, 43, 18, 43, 29, 43, 31, 43, 42, 43, 44, 44, 4, 44, 6, 44, 17, 44, 19, 44, 30, 44, 32, 44, 43, 44, 45, 45, 5, 45, 7, 45, 18, 45, 20, 45, 31, 45, 33, 45, 44, 45, 46, 46, 6, 46, 8, 46, 19, 46, 21, 46, 32, 46, 34, 46, 45, 46, 47, 47, 7, 47, 9, 47, 20, 47, 22, 47, 33, 47, 35, 47, 46, 47, 48, 48, 8, 48, 10, 48, 21, 48, 23, 48, 34, 48, 36, 48, 47, 48, 49, 49, 9, 49, 11, 49, 22, 49, 24, 49, 35, 49, 37, 49, 48, 49, 50, 50, 10, 50, 12, 50, 23, 50, 25, 50, 36, 50, 38, 50, 49, 50, 51, 51, 11, 51, 13, 51, 24, 51, 26, 51, 37, 51, 39, 51, 50, 51, 52, 52, 1, 52, 12, 52, 14, 52, 25, 52, 27, 52, 38, 52, 40, 52, 51 ]);