The Solitaire Board Game (solitaire)

Run LPL Code  ,  PDF Document

Problem

The Solitaire Board Game is most commonly played on a 33 point board in a cross shape with 32 pegs, marbles or pieces (see Figure 1), other shapes are common too.

The game is set up so that 32 pieces fill every hole except for the middle hole. The objective then is to remove every piece except for one, with the final piece ending up in the center hole. Solitaire is played by one person and is therefore technically not a game at all, but a puzzle.

The player makes successive capturing moves, removing a single piece each turn until is it impossible to make any more capturing moves. Each turn, the player captures (removes) a piece by jumping over that piece from one adjacent point to the vacant adjacent point on the other side (see 3). Therefore, the first turn can be made only by jumping a piece into the middle hole from one of 4 possible points.

---

---

The problem we consider here is to decide whether a given goal configuration can be reached from a given initial configuration (see Figure 2). The black points are the pieces that can be moved. A move in the game is defined as a jump of a piece over another vertical or horizontal neighbor piece into an empty grid location, as explained above (see Figure 3 for a particular move).

---

---

The first question is the feasibility of a path between the initial and the goal configuration. The second question is – if feasible – to specify the path to reach the goal configuration. We treat the first question here, the feasibility problem.

---

---

It has been shown that all configurations can be partitioned into 16 equivalence classes, and that the game is solvable only if the initial and the goal configuration belong to the same class. This is a good filter to find quickly most insolvable games. Unfortunately, this is a necessary but not a sufficient condition. Figure 2 displays an example where the initial and the goal configuration belong to the same equivalence class, but the goal configuration cannot be reached from the initial configuration by any sequence of moves.

A better filter has been developed 1961 by J.M. Boardman and J.H. Conway at the University of Cambridge. The method is based on a valuation function N(C) of a configuration. We define a configuration a set of occupied and empty fields. Figure 2, for example, displayed two different configurations. The problem can be formulated as an LP problem. The idea is the following: Assign a value (positive or negative) x_f to each field f in the grid. These values must fulfil the following two conditions:

where q, r, and s are consecutive vertical or horizontal fields in the grid with r in the middle. We define N(C) = ∑ _fx_fc_f, with f being an index of all fields and c_f is 1, if the field f is occupied by a piece and 0 otherwise.

Then a goal configuration Z cannot be reached from a initial configuration A, if N(Z) > N(A). Unfortunately, this is still a necessary, not a sufficient condition. However, it seems to be a very good “filter”. (See [1] for further references and theoretical aspects).

Modeling Steps

To model these requirements as an LP, we first introduce a set of columns and rows with names i and j with dimension 7, giving a grid of 7 × 7 cells.

1. The unknown valuation of a grid cell is defined as a variable x_i,j, which can have positive or negative values.

2. We define the initial configuration A_i,j and goal configuration Z_i,j as two data matrixes (parameters) with 0 and 1, where 1 means the configuration is occupied by a piece and 0 otherwise.

3. The two conditions – developed above – are mapped as constraints. Since the conditions are defined vertically and horizontally, we get four constraints.

4. We minimize N(Z) – N(A). If the optimum is strictly positive, then the game is unsolvable as explained above.

model Solitaire "The Solitaire Board Game"; 
    set 
      i,j := [1..7] "Seven rows and seven columns"; 
      r{i,j}:=  3<=i<=5  or 3<=j<=5 
        "Grid points that are used in the game"; 
    parameter 
      A{i,j}:= [. . 0 0 0 . . 
                . . 0 1 0 . . 
                0 0 1 1 1 0 0 
                0 1 1 1 1 1 0 
                1 1 1 1 1 1 1 
                . . 1 1 1 . . 
                . . 1 1 1 . .] "Initial configuration"; 
      Z{i,j}:= [. . 1 0 1 . . 
                . . 0 0 0 . . 
                0 0 0 0 0 0 0 
                0 0 0 0 0 0 0 
                0 0 0 0 0 0 0 
                . . 0 0 0 . . 
                . . 0 0 0 . .] "Goal configuration"; 
    variable x{i,j|r} [-3..3]   "Value in each (i,j) point"; 
    constraint 
      H1{i,j|r and r[i,j+1] and r[i,j+2]}: 
                      x[i,j]+x[i,j+1] >= x[i,j+2]; 
      H2{i,j|r and r[i,j+1] and r[i,j+2]}: 
                      x[i,j+2]+x[i,j+1] >= x[i,j]; 
      V1{i,j|r and r[i,j+1] and r[i+2,j]}: 
                      x[i,j]+x[i+1,j] >= x[i+2,j]; 
      V2{i,j|r and r[i+1,j] and r[i+2,j]}: 
                      x[i+2,j]+x[i+1,j] >= x[i,j]; 
    maximize obj: sum{i,j} Z*x - sum{i,j} A*x; 
    if obj>0 then Write('The problem is infeasible' n'); 
    else Write('The problem may be possible, but I am not sure' n'); end; 
  end

Solution

A solution of the configurations in Figure 2 is given in Figure 4, for which N(A) = 4 and N(Z) = 6, which proves the infeasibility of the game.

---

---

Questions

1. Is there a path of the game where the initial configuration is given by Figure 1 and the goal configuration is a single marble in the center of the board ?

Answers

1. Replace the data of the initial and goal configuration as follows: Then solve again. A solution might be possible. (I know there is a path from the initial to the goal configuration, because I played the game once.)

      A{i,j}:= [. . 1 1 1 . . 
                   . . 1 1 1 . . 
                   1 1 1 1 1 1 1 
                   1 1 1 0 1 1 1 
                   1 1 1 1 1 1 1 
                   . . 1 1 1 . . 
                   . . 1 1 1 . .]; 
         Z{i,j}:= [. . 0 0 0 . . 
                   . . 0 0 0 . . 
                   0 0 0 0 0 0 0 
                   0 0 0 1 0 0 0 
                   0 0 0 0 0 0 0 
                   . . 0 0 0 . . 
                   . . 0 0 0 . .];

References