Solitaire

Predicates

• Input: full/2, empty/2, time/1

• Output: move/1

Problem Description

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, find a sequence of the given number of moves.

Input format

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, giving the number of moves that must be found. These are given as a range of consecutive, ascending integers, starting at 1.

Output format

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).

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.

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.

./instanceGenerator.pl --time=10 --density=0.1 | cat solitaire.lp - | gringo | clasp | ./visualise-solitaire.lp

Example

Comment

This problem took part in the Second ASP Competition and was proposed by Martin Brain.

Author(s)

• Author: Yuliya Lierler
  • Affiliation: University of Kentucky, USA
• Author: Marcello Balduccini
  • Affiliation: Kodak Research Labs, USA