Solitaire is a single player game played on a 7x7 board with 2x2 corners omitted. Each position is either full (containing a peg / marble) or empty. With 'O' representing full positions and '.' representing an empty position, a possible board configuration is:
OOO OOO OOO.OOO OOOOOOO OOOOOOO OOO OOO
Each turn the player must jump (orthogonally but not diagonally) a peg over an existing peg and removed the 'jumped' peg. For example, numbering the board from the top left, moving peg (6,3) left would give the following board configuration:
OOO OOO OOOO..O OOOOOOO OOOOOOO OOO OOO
The task is, given an initial board configuration, to find a sequence of the given number of moves.
Input: full/2, empty/2, time/1
Thirty two facts giving the initial board configuration, each of which is either:
full(X,Y). or empty(X,Y).
indicating that position (X,Y) is either full or empty.
A number of time facts, in the form time(i), specifying the number of moves that must be found. These are given as a range of consecutive, ascending integers, starting at 1.
The input facts plus a number of move facts equal to the number of time facts. Each move fact is of the form: move(T,D,X,Y).
indicating that to get to time step T from time step T-1 (the initial conditions are regarded to be time step 0), the peg in position (X,Y) is moved in direction D (up, down, left or right).
Given the input:
time(1). time(2). time(3). time(4). time(5). time(6). time(7). time(8). time(9). time(10). time(11). time(12). time(13). time(14). time(15). time(16). time(17). time(18). time(19). time(20). time(21). time(22). time(23). time(24). full(3,1). full(4,1). full(5,1). full(3,2). full(4,2). full(5,2). full(1,3). full(2,3). full(3,3). full(4,3). full(5,3). full(6,3). full(7,3). full(1,4). full(2,4). full(3,4). empty(4,4). full(5,4). full(6,4). full(7,4). full(1,5). full(2,5). full(3,5). full(4,5). full(5,5). full(6,5). full(7,5). full(3,6). full(4,6). full(5,6). full(3,7). full(4,7). full(5,7).
The output of the solver should look like:
move(1,right,2,4). move(10,down,5,2). move(11,up,4,5). move(12,up,4,7). move(13,right,3,5). move(14,down,5,4). move(15,up,3,7). move(16,down,3,4). move(17,left,7,3). move(18,up,5,7). move(19,left,6,5). move(2,left,5,4). move(20,right,4,3). move(21,down,3,1). move(22,right,1,5). move(23,right,3,5). move(24,left,5,1). move(3,up,5,6). move(4,left,7,5). move(5,right,4,5). move(6,left,6,4). move(7,down,4,3). move(8,right,2,3). move(9,down,4,2).
Additional sample instances: download
Type: Search Competition: Both
Calibration: Generally the fewer pegs remaining on the board, the harder it is to make a move. Thus instances starting with a full or a nearly full board and conduct 27-31 moves are the most difficult. Time is the number of moves required, density is the probability of any given peg being being empty in the initial board position. Note that at least one empty position is required to make the puzzle possible. It may be best to add this by hand.
Notes and Updates
Visualisation: A visualisation script is provided to make development easier. The output of most answer set solvers can be fed into it giving an ascii art visualisation of the moves made.
- Author: Marcello Balduccini, Yuliya Lierler
- Affiliation: Kodak Research Labs and University of Kentucky