|
Size: 2756
Comment:
|
Size: 2708
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 5: | Line 5: |
| == Predicates == * '''Input''': full/2, empty/2, time/1 * '''Output''': move/1 |
|
| Line 14: | Line 8: |
OOO <<BR>> OOO <<BR>> OOO.OOO <<BR>> OOOOOOO <<BR>> OOOOOOO <<BR>> OOO <<BR>> OOO <<BR>> |
{{{ OOO OOO OOO.OOO OOOOOOO OOOOOOO OOO OOO }}} |
| Line 25: | Line 19: |
| {{{ 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. |
|
| Line 26: | Line 30: |
| OOO <<BR>> OOO <<BR>> OOOO..O <<BR>> OOOOOOO <<BR>> OOOOOOO <<BR>> OOO <<BR>> OOO <<BR>> |
== Predicates == |
| Line 34: | Line 32: |
| The task is, given an initial board configuration, find a sequence of the given number of moves. | * '''Input''': {{{full/2, empty/2, time/1}}} * '''Output''': {{{move/1}}} |
| Line 40: | Line 40: |
| full(X,Y). or empty(X,Y). |
{{{full(X,Y).}}} or {{{empty(X,Y).}}} |
| Line 48: | Line 44: |
| 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. |
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. |
| Line 53: | Line 48: |
| 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). |
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)}}}. |
| Line 67: | Line 60: |
| {{{ | |
| Line 69: | Line 62: |
== Example == |
}}} == Example(s) == |
Solitaire
Contents
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.
Predicates
Input: full/2, empty/2, time/1
Output: move/1
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(s)
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