|
Size: 2027
Comment:
|
← Revision 5 as of 2011-01-10 10:24:24 ⇥
Size: 1858
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| = Soitaire = | = Solitaire = <<TableOfContents>> |
| Line 4: | Line 6: |
| 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: | |
| Line 5: | Line 8: |
| 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: |
[[attachment:board1.txt]] |
| Line 10: | Line 10: |
| .OO <<BR>> .OO <<BR>> O.OOOOO <<BR>> OOO.OOO <<BR>> OOOOOOO <<BR>> O.O <<BR>> OOO |
Each turn the player must jump a peg over an existing peg and removed the 'jumped' peg. For example, numbering the board from the top left, moving peg (4,2) down would give the following board configuration: |
| Line 24: | Line 12: |
| Each turn the player must jump a peg over an existing peg and removed the 'jumped' peg. For example, numbering the board from the top left, moving peg (4,2) down would give the following board configuration: |
[[attachment:board2.txt]] |
| Line 28: | Line 14: |
| .OO <<BR>> ..O <<BR>> O.O.OOO <<BR>> OOOOOOO <<BR>> OOOOOOO <<BR>> O.O <<BR>> OOO The task is, given an initial board configuration, find a sequence of the given number of moves. |
The task is, given an initial board configuration, find a sequence of the given number of moves. |
| Line 47: | Line 17: |
Thirty two facts giving the initial board configuration, each of which is either: |
Thirty two facts giving the initial board configuration, each of which is either: |
| Line 59: | Line 27: |
| 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 65: | Line 30: |
The input facts plus a number of move facts equal to the number of time facts. Each move fact is of the form: |
The input facts plus a number of move facts equal to the number of time facts. Each move fact is of the form: |
| Line 71: | Line 34: |
| 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). |
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). |
| Line 75: | Line 36: |
| == Example == | |
| Line 77: | Line 39: |
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. |
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. |
| Line 84: | Line 42: |
| Line 87: | Line 44: |
| Line 89: | Line 45: |
| Line 91: | Line 46: |
| * University of Kentucky, USA | * University of Kentucky, USA |
| Line 93: | Line 48: |
| * Kodak Research Labs, USA | * Kodak Research Labs, USA |
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:
Each turn the player must jump a peg over an existing peg and removed the 'jumped' peg. For example, numbering the board from the top left, moving peg (4,2) down would give the following board configuration:
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).
Example
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.
Comment
This problem took part in the Second ASP Competition and was proposed by Martin Brain.
Author(s)
- Yuliya Lierler
- University of Kentucky, USA
- Marcello Balduccini
- Kodak Research Labs, USA