= Solitaire =

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

== Predicates ==

 * '''Input''': {{{full/2, empty/2, time/1}}}

 * '''Output''': {{{move/4}}}

== 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, 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.

== 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(s) ==
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: [[https://www.mat.unical.it/aspcomp2013/files/samples/solitaire_sample.zip|download]]


== Problem Peculiarities ==

'''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(s) ==
 * Author: Marcello Balduccini, Yuliya Lierler
  * Affiliation: Kodak Research Labs and University of Kentucky