Link Search Menu Expand Document
PyCSP3
Models & Data GitHub XCSP3 About
Documentation
XCSP web site is provided by CRIL
This site uses Just the Docs, a documentation theme for Jekyll.
download notebook
CSP  medium 

Problem Black Hole

From WikiPedia: ``Black Hole is a solitaire card game. Invented by David Parlett, this game’s objective is to compress the entire deck into one foundation. The cards are dealt to a board in piles of three. The leftover card, dealt first or last, is placed as a single foundation called the Black Hole. This card usually is the Ace of Spades. Only the top cards of each pile in the tableau are available for play and in order for a card to be placed in the Black Hole, it must be a rank higher or lower than the top card on the Black Hole. This is the only allowable move in the entire game. The game ends if there are no more top cards that can be moved to the Black Hole. The game is won if all of the cards end up in the Black Hole.’’

Illustration of Black Hole (Solitaire). Image from commons.wikimedia.org Solitaire

To build a CSP (Constraint Satisfaction Problem) model, we need first to import the library PyCSP$^3$:

from pycsp3 import *

Then, we need some data. Note that we may want to play with various sizes of piles and various number of cards per suit. For the simplicity of our illustration, we shall only consider 4 cards per suit (instead of 13 cards per suit for example, as used classically).

m = 4  # number of cards per suit (e.g., Ace, Jack, Queen and King)
piles = [[1 ,4 ,13] ,[15 ,9 ,6] ,[14 ,2 ,12] ,[7 ,8 ,5] ,[11 ,10 ,3]]
nCards = 4 * m  # 4 suits (spades, clubs, hearts, diamonds)

For our illustration, we assume that cards are (arbitrarily) numbered as follows:

  • 0 : Ace of Spades
  • 1 : Jack of Spades
  • 2 : Queen of Spades
  • 3 : King of Spades
  • 4 : Ace of Clubs
  • etc.

So, in the first pile above, we find the Jack of Spades (value 1), the Ace of Clubs (value 4) and the Jack of Diamonds (value 13).

We start our CSP model by introducing two arrays $x$ and $y$ of variables (two variables per card), each variable having ${0,1,\dots,15}$ as domain. If we can assign all variables of $x$ (while respecting the rules of the game), we obtain a solution (since we shall have the precise order in which cards from piles are played). The array $y$ gives a reverse point of view (it also allows us to exhibit a solution), and will be useful for posting some constraints.

# x[i] is the value j of the card at position i of the stack
x = VarArray(size=nCards, dom=range(nCards))

# y[j] is the position i (in the stack) of the card whose value is j
y = VarArray(size=nCards, dom=range(nCards))

We can display the structure of the two arrays, as well as the domain of the first variable (remember that all variables have the same domain).

print("Array of variables x: ", x)
print("Array of variables y: ", y)
print("Domain of any variable: ", x[0].dom)

Array of variables x:  [x[0], x[1], x[2], x[3], x[4], x[5], x[6], x[7], x[8], x[9], x[10], x[11], x[12], x[13], x[14], x[15]]
Array of variables y:  [y[0], y[1], y[2], y[3], y[4], y[5], y[6], y[7], y[8], y[9], y[10], y[11], y[12], y[13], y[14], y[15]]
Domain of any variable:  0..15

Concerning the constraints, we start by imposing that the Ace of Spades is the first card of the stack. We just write:

satisfy(
   # the Ace of Spades is the first card of the stack
   y[0] == 0
);

Another rule is that the cards must be played in the order of the piles. For example, when considering the first pile above, we must play the Jack of Spades before the Ace of Clubs, and the Ace of Clubs before the Jack of Diamonds. To impose that rule, we can post a group of constraints Increasing, with the use of the named parameter strict (set to True for imposing a strict order).

satisfy(
   # cards must be played in the order of the piles
   Increasing([y[j] for j in pile], strict=True) for pile in piles
);

Note that the constraint Increasing is mainly an ease of use. Instead, one could have written:

satisfy(
   # cards must be played in the order of the piles
   y[pile[k]] < y[pile[k+1]] for pile in piles for k in range(len(pile)-1)
);

We can display the internal representation of the posted constraints; this way, although a little bit technical, we can see that the piles must be ordered (note that ‘lt’ stands for ‘(strictly) less than’).

print(posted())

intension(function:eq(y[0],0))
ordered(list:[y[1], y[4], y[13]], operator:lt)
ordered(list:[y[15], y[9], y[6]], operator:lt)
ordered(list:[y[14], y[2], y[12]], operator:lt)
ordered(list:[y[7], y[8], y[5]], operator:lt)
ordered(list:[y[11], y[10], y[3]], operator:lt)

Interestingly, by calling the function solve(), we can check that the problem is satisfiable (SAT) at this preliminary step. We can also display the found solution. Here, we call the function values() that collects the values assigned to a specified list of variables.

if solve() is SAT:
    print("Values of x ", values(x))
    print("Values of y ", values(y))

Values of x  [*, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *]
Values of y  [0, 0, 1, 2, 1, 2, 2, 0, 1, 1, 1, 0, 2, 2, 0, 0]

Clearly, the model is incomplete as, for example, we see the presence of the symbol * for the variables of $x$. This is because these variables are involved in no constraint.

Now, to link variables of $x$ and $y$, we post a constraint Channel: $x[i] =j \Leftrightarrow y[j] = i$

satisfy(
   # linking variables of x and y
   Channel(x, y)
);

We can run the solver again:

if solve() is SAT:
    print("Values of x ", values(x))
    print("Values of y ", values(y))

Values of x  [0, 1, 4, 7, 8, 5, 11, 10, 3, 13, 14, 2, 12, 15, 9, 6]
Values of y  [0, 1, 11, 8, 2, 5, 15, 3, 4, 14, 7, 6, 12, 9, 10, 13]

An attentive reader can observe that the proposed “solution” does not respect the following rule: any two cards played in sequence must be separated by one rank.

Interstingly, this can be captured by the following table:

T = [(i, j) for i in range(nCards) for j in range(nCards) if i % m == (j + 1) % m or j % m == (i + 1) % m]

This gives:

print(T)

[(0, 1), (0, 3), (0, 5), (0, 7), (0, 9), (0, 11), (0, 13), (0, 15), (1, 0), (1, 2), (1, 4), (1, 6), (1, 8), (1, 10), (1, 12), (1, 14), (2, 1), (2, 3), (2, 5), (2, 7), (2, 9), (2, 11), (2, 13), (2, 15), (3, 0), (3, 2), (3, 4), (3, 6), (3, 8), (3, 10), (3, 12), (3, 14), (4, 1), (4, 3), (4, 5), (4, 7), (4, 9), (4, 11), (4, 13), (4, 15), (5, 0), (5, 2), (5, 4), (5, 6), (5, 8), (5, 10), (5, 12), (5, 14), (6, 1), (6, 3), (6, 5), (6, 7), (6, 9), (6, 11), (6, 13), (6, 15), (7, 0), (7, 2), (7, 4), (7, 6), (7, 8), (7, 10), (7, 12), (7, 14), (8, 1), (8, 3), (8, 5), (8, 7), (8, 9), (8, 11), (8, 13), (8, 15), (9, 0), (9, 2), (9, 4), (9, 6), (9, 8), (9, 10), (9, 12), (9, 14), (10, 1), (10, 3), (10, 5), (10, 7), (10, 9), (10, 11), (10, 13), (10, 15), (11, 0), (11, 2), (11, 4), (11, 6), (11, 8), (11, 10), (11, 12), (11, 14), (12, 1), (12, 3), (12, 5), (12, 7), (12, 9), (12, 11), (12, 13), (12, 15), (13, 0), (13, 2), (13, 4), (13, 6), (13, 8), (13, 10), (13, 12), (13, 14), (14, 1), (14, 3), (14, 5), (14, 7), (14, 9), (14, 11), (14, 13), (14, 15), (15, 0), (15, 2), (15, 4), (15, 6), (15, 8), (15, 10), (15, 12), (15, 14)]

The first pairs in this table must be understood as:

  • (0,1): the Ace of Spades can be followed by the Jack of Spades
  • (0,3): the Ace of Spades can be followed by the King of Spades
  • (0,5): the Ace of Spades can be followed by the Jack of Clubs
  • (0,7): the Ace of Spades can be followed by the King of Clubs
  • (0,9): the Ace of Spades can be followed by the Jack of Hearts
  • etc.

We can now post a group of binary constraints Extension to impose that rule.

satisfy(
   # each new card put on the stack must be at an immediately higher or lower rank 
   (x[i], x[i + 1]) in T for i in range(nCards - 1)
);

We can run the solver again:

if solve() is SAT:
    print("Values of x ", values(x))
    print("Values of y ", values(y))

Values of x  [0, 1, 4, 7, 8, 5, 14, 11, 2, 13, 10, 15, 12, 9, 6, 3]
Values of y  [0, 1, 8, 15, 2, 5, 14, 3, 4, 13, 10, 7, 12, 9, 6, 11]

This time, we do have a valid solution.

Finally, we give below the model in one piece. Here the data is expected to be given by the user (in a command line).

from pycsp3 import *

m, piles = data
nCards = 4 * m

# x[i] is the value j of the card at position i of the stack
x = VarArray(size=nCards, dom=range(nCards))

# y[j] is the position i of the card whose value is j
y = VarArray(size=nCards, dom=range(nCards))

T = {(i, j) for i in range(nCards) for j in range(nCards)
                if i % m == (j + 1) % m or j % m == (i + 1) % m}

satisfy( 
   # the Ace of Spades is the first card of the stack
   y[0] == 0,

   # cards must be played in the order of the piles
   [Increasing([y[j] for j in pile], strict=True) for pile in piles],

   # linking variables of x and y
   Channel(x, y),

   # each new card put on the stack must be at an immediately higher or lower rank 
   [(x[i], x[i + 1]) in T for i in range(nCards - 1)]
)