Possible different moves at any given board position and taking the OR of their evaluations. This expression, however, can be generalized to check for all valid moves by constructing expressions for each of the 36 To a false, then the whole expression evaluates to a false. The above expression evaluates to true only when p 0.p 14 and q 0.q 14 representīoard states such that performing the move (3, 1, 0) turns board p into board q. Valid(p, q, (3, 1, 0)) = (p3 & ~q3) & (p1 & ~q1) & (~p0 & q0) &įigure 4: Boolean expression for checking move transition. The following boolean expression does the We mustĪlso check that all other states besides holes i, j, and k are not affected. I and j in board p no longer exist in board q and that hole k which was originally empty in p is now filled in q. To do this, we must simply check that pegs initially existing at positions Given applied to board p results in board q. P 0.p 14 and q 0.q 14 and a move (i, j, k), we can test to see if the move Now, let us denote a move by the ordered triple (i, j, k) designating that peg i jumps over peg j and ends up at hole k.įor instance, in the example above, the move performed was (3, 1, 0). If we consider the move from Figure 1, the truth values for p 0.p 14 andįigure 3: Move transition boolean values.
Q j is true if and only if a peg is found at location j after the move has been made. p i is true if and only if a peg is found at location i before the move is made likewise, Let p 0.p 14 be truth values representing the state of the board before a move is made,Īnd let q 0.q 14 be the truth values representing the state of the board after the move Consider the following board numbering scheme, for instance: Transition in the game as a conjunction of several boolean conditions that must be met in order for the move The general idea behind encoding peg solitaire as a boolean expression is to represent each possible move or Turning peg solitaire into a boolean expression Typically in the initial board configuration, all holes have pegs except one ideally, the one initiallyĮmpty hole should be the only peg with a hole in the final state. Below is an example of a board configuration and move transition:įigure 1: Sample board configuration and move. The object of the game is to remove all pegs from theīoard except one. Game ends when no more legal "jumps" may be made.
The original peg is moved to the empty hole and the adjacent "jumped" peg is removed from the board. Select one of the pegs on the board which has an adjacent peg and an empty hole following that adjacent peg.
Peg solitaire describes a general class of peg-jumping games in which a player is initially presented withĪ board containing holes and wooden pegs filling a subset of these holes. An alternative rule-based encoding scheme.Encoding peg solitaire in Conjuctive Normal Form (CNF).Turning peg solitaire into a boolean expression.General Information and Basic Techniques.This page contains information on using SAT solvers such as zChaff to handle simple puzzles such as peg solitaire. Satisfiability and Peg Solitaire Satisfiability and Peg Solitaire
0 kommentar(er)
