Cracker Barrel
August 19, 2014
We number the holes as shown below, and start with the initial vacancy at hole 1:
1
2 3
4 5 6
7 8 9 10
11 12 13 14 15
A move is written as a list containing the from hole, jump hole and to hole, so the two possible starting moves are (4 2 1) and (6 3 1). A board is a list of occupied holes followed by a list of moves taken to reach the board (most recent move first). For instance, after starting with (4 2 1), continuing with (6 5 4) and then (1 3 6), the board looks like this: ((4 6 7 8 9 10 11 12 13 14 15) (4 2 1) (6 5 4) (1 3 6)). There are 36 possible moves:
(define possibles '((1 2 4) (1 3 6) (2 4 7) (2 5 9) (3 5 8)
(3 6 10) (4 2 1) (4 5 6) (4 7 11) (4 8 13) (5 8 12) (5 9 14)
(6 3 1) (6 5 4) (6 9 13) (6 10 15) (7 4 2) (7 8 9) (8 5 3)
(8 9 10) (9 5 2) (9 8 7) (10 6 3) (10 9 8) (11 7 4)
(11 12 13) (12 8 5) (12 13 14) (13 8 4) (13 9 6) (13 12 11)
(13 14 15) (14 9 5) (14 13 12) (15 10 6) (15 14 13)))
(define init '((2 3 4 5 6 7 8 9 10 11 12 13 14 15)))
A move is feasible if the from hole is occupied, the jump hole is occupied, and the to hole is vacant:
(define (feasible? board move)
(and (member (car move) (car board))
(member (cadr move) (car board))
(not (member (caddr move) (car board)))))
A jump takes a board and a move and returns a new board, if the move is feasible, or #f:
(define (jump board move)
(and (feasible? board move)
(cons (insert (caddr move)
(remove (car move)
(remove (cadr move) (car board))))
(cons move (cdr board)))))
Function all-jumps returns a list of all boards resulting from the possible jumps on a given board:
(define (all-jumps board)
(filter identity
(map (lambda (move) (jump board move))
possibles)))
Now our solution iterates 13 times, collecting after each round all possible boards:
(define (solve init)
(do ((k 13 (- k 1))
(boards (list init) (mappend all-jumps boards)))
((zero? k) boards)))
We find 29760 solutions, of which 6816 end with the peg in the initially-vacant hole:
> (let ((solutions (solve init)))
(display (length solutions)) (newline)
(display (length (filter (lambda (x) (equal? (car x) '(1))) solutions))) (newline)
(display (list-ref solutions 17493)) (newline))
29760
6816
((13) (11 12 13) (14 13 12) (6 9 13) (2 5 9) (7 4 2) (15 10 6) (3 6 10) (13 9 6) (1 2 4) (12 8 5) (10 6 3) (4 5 6) (6 3 1))
You can run the program at http://programmingpraxis.codepad.org/HjimquyE, where you will also see the contributions from the Standard Prelude. There is more to this puzzle than we have discussed here; if you are interested, look at George Bell’s site. We may return to this puzzle in future exercises.
Programming Praxis 
That’s amusing. About a month and a half ago, I came across another site that had the same challenge, so I worked it out then:
Cracker Barrel Peg Game – framework and basic solver
Cracker Barrel Peg Game, Part 2 – which solutions are most solvable
Cracker Barrel Peg Game, Part 3 – interactive command line game
Although I will admit I don’t have anything that will end in a specific win state. It should be only a single line to add though.
(All three in Racket.)
I remember writing a solver for that puzzle long ago. I was still living with my parents, and I was writing in C, so that dates it around 1981-84. Of course, the code is long gone.
use strict; use warnings; my $possible_moves = [ [ [1,3],[2,5] ], [ [3,6],[4,8] ], [ [4,7],[5,9] ], [ [1,0],[4,5],[6,10],[7,12] ], [ [7,11],[8,13] ], [ [2,0],[4,3],[8,12],[9,14] ], [ [3,1],[7,8] ], [ [4,2],[8,9] ], [ [4,1],[7,6] ], [ [5,2],[8,7] ], [ [6,3],[11,12] ], [ [7,4],[12,13] ], [ [7,3],[8,5],[11,10],[13,14] ], [ [8,4],[12,11] ], [ [9,5],[13,12] ], ]; solve_grid( q(011111111111111), [] ); sub solve_grid { my ( $grid, $moves ) = @_; if( @{$moves} == 13 && $grid eq q(100000000000000) ) { print "@{$moves}\n"; return; } foreach my $i (0..14) { next unless substr $grid, $i, 1; foreach my $m (@{$possible_moves->[$i]}) { next if substr $grid, $m->[1], 1; next unless substr $grid, $m->[0], 1; my $g = $grid; substr $g, $i, 1, 0; substr $g, $m->[0],1, 0; substr $g, $m->[1],1, 1; solve_grid( $g, [@{$moves},"$i->$m->[1]"] ); } } return; }I think this is slightly slower – but slight more compact code…
use strict; use warnings; use feature qw(say); my $possible_moves = [ [0,1,3], [0,2,5], [1,3,6], [1,4,8], [2,4,7], [2,5,9], [3,1,0], [3,4,5], [3,6,10], [3,7,12], [4,7,11],[4,8,13], [5,2,0], [5,4,3],[5,8,12],[5,9,14], [6,3,1], [6,7,8], [7,4,2], [7,8,9], [8,4,1], [8,7,6], [9,5,2], [9,8,7], [10,6,3], [10,11,12], [11,7,4],[11,12,13], [12,7,3],[12,8,5],[12,11,10],[12,13,14], [13,8,4],[13,12,11], [14,9,5],[14,13,12], ]; solve_grid( q(011111111111111), q() ); sub solve_grid { my ( $grid, $moves ) = @_; return say $moves if $grid eq q(100000000000000); foreach (@{$possible_moves}) { my $g = $grid; next if ! substr( $g, $_->[0],1, 0 ) || ! substr( $g, $_->[1],1, 0 ) || substr( $g, $_->[2],1, 1 ); solve_grid( $g, $moves."$_->[0]->$_->[2] " ); } return; }In Python.
BOARD_INIT = [0] + [1] * 14 MOVE_MASKS = [(0, 1, 3), (0, 2, 5), (1, 3, 6), (1, 4, 8), (2, 4, 7), (2, 5, 9), (3, 4, 5), (3, 6, 10), (3, 7, 12), (4, 7, 11), (4, 8, 13), (5, 8, 12), (5, 9, 14), (6, 7, 8), (7, 8, 9), (10 ,11, 12), (11, 12, 13), (12, 13, 14)] def find_moves(board): """move: tuple with (from, over, to)""" for m1, m2, m3 in MOVE_MASKS: if board[m2]: if board[m1] and not board[m3]: yield m1, m2, m3 elif board[m3] and not board[m1]: yield m3, m2, m1 def do_move(move, board): board = list(board) m1, m2, m3 = move board[m1], board[m2], board[m3] = 0, 0, 1 return board def solve(board=BOARD_INIT, movs=[]): """generate all movesequences that result in one peg""" if sum(board) == 1: yield movs else: for m in find_moves(board): for g in solve(do_move(m, board), movs + [m]): yield g print sum(1 for moves in solve() if moves[-1][-1] == 0) # 6816 print sum(1 for moves in solve()) # 29760Recursive backtracking solution with memoization, using a bitset for the board. I was going to keep track of the moves in a tree structure, but thought it would be more fun to output a .dot file – see http://matthewarcus.files.wordpress.com/2014/08/puzzle.png for the (2Mb) result.
#include <stdint.h> #include <stdio.h> #include <vector> std::vector<uint16_t> moves; std::vector<uint16_t> masks; std::vector<int16_t> memo((1<<15)-1,-1); void add(int a, int b, int c) { uint16_t move1 = (1<<a)|(1<<b); uint16_t move2 = (1<<b)|(1<<c); uint16_t mask = move1|move2; moves.push_back(move1); masks.push_back(mask); moves.push_back(move2); masks.push_back(move1|move2); } int solve(std::vector<uint16_t> &game, int n) { if (memo[game[n]] >= 0) return memo[game[n]]; int result = 0; for (int i = 0; i < (int)moves.size(); i++) { if ((game[n] & masks[i]) == moves[i]) { game[n+1] = game[n]^masks[i]; int t = solve(game,n+1); if (t > 0) printf(" x%X -> x%X;\n", game[n], game[n+1]); result += t; } } memo[game[n]] = result; return result; } int main() { add(0,1,3); add(0,2,5); add(1,3,6); add(1,4,8); add(2,4,7); add(2,5,9); add(3,4,5); add(3,6,10); add(3,7,12); add(4,7,11); add(4,8,13); add(5,8,12); add(5,9,14); add(6,7,8); add(7,8,9); add(10,11,12); add(11,12,13); add(12,13,14); std::vector<uint16_t> game(15); memo[1] = 1; // Prime the pump game[0] = 0x7ffe; printf("digraph g {\n"); fprintf(stderr,"%d\n", solve(game,0)); printf("}\n"); }That should have been:
(Last minute “improvement” – means the same of course).
The solution that you posted above seems to timeout on my machine and on codepad. I also have a scheme solution that is timing out at the moment, attempting to debug it.
It is slow because it must form all possible solutions. It times out at both codepad and ideone, but runs to completion on my machine at work:
Petite Chez Scheme Version 8.4 Copyright (c) 1985-2011 Cadence Research Systems > (define (identity x) x) > (define (mappend f . xss) (apply append (apply map f xss))) > (define (filter pred? xs) (let loop ((xs xs) (ys '())) (cond ((null? xs) (reverse ys)) ((pred? (car xs)) (loop (cdr xs) (cons (car xs) ys))) (else (loop (cdr xs) ys))))) > (define (remove x xs) (let loop ((xs xs) (zs '())) (cond ((null? xs) (reverse zs)) ((equal? (car xs) x) (loop (cdr xs) zs)) (else (loop (cdr xs) (cons (car xs) zs)))))) > (define (insert x xs) (if (null? xs) (list x) (if ( (define possibles '((1 2 4) (1 3 6) (2 4 7) (2 5 9) (3 5 8) (3 6 10) (4 2 1) (4 5 6) (4 7 11) (4 8 13) (5 8 12) (5 9 14) (6 3 1) (6 5 4) (6 9 13) (6 10 15) (7 4 2) (7 8 9) (8 5 3) (8 9 10) (9 5 2) (9 8 7) (10 6 3) (10 9 8) (11 7 4) (11 12 13) (12 8 5) (12 13 14) (13 8 4) (13 9 6) (13 12 11) (13 14 15) (14 9 5) (14 13 12) (15 10 6) (15 14 13))) > (define init '((2 3 4 5 6 7 8 9 10 11 12 13 14 15))) > (define (feasible? board move) (and (member (car move) (car board)) (member (cadr move) (car board)) (not (member (caddr move) (car board))))) > (define (jump board move) (and (feasible? board move) (cons (insert (caddr move) (remove (car move) (remove (cadr move) (car board)))) (cons move (cdr board))))) > (define (all-jumps board) (filter identity (map (lambda (move) (jump board move)) possibles))) > (define (solve init) (let loop ((k (- (length (car init)) 1)) (boards (list init))) (if (zero? k) boards (loop (- k 1) (mappend all-jumps boards))))) > (time (let ((solutions (solve init))) (display (length solutions)) (newline) (display (length (filter (lambda (x) (equal? (car x) '(1))) solutions))) (newline) (display (list-ref solutions 17493)) (newline))) 29760 6816 ((13) (11 12 13) (14 13 12) (6 9 13) (2 5 9) (7 4 2) (15 10 6) (3 6 10) (13 9 6) (1 2 4) (12 8 5) (10 6 3) (4 5 6) (6 3 1)) (time (let ((...)) ...)) 214 collections 13634 ms elapsed cpu time, including 1484 ms collecting 13655 ms elapsed real time, including 1471 ms collecting 1804614480 bytes allocated, including 1815872208 bytes reclaimedI didn’t think that you were wrong, was just curious. I was using the mit-scheme interpreter, which apparently has very low memory limits. Switch to Gauche the program ran fine.
My C++ program takes about 1.5ms to generate the .dot file (perf reckons about 2000000 cycles). As well as the obvious left-right symmetry, there’s also a forward and backward symmetry, swapping pegs for holes, which might save some time.
So I was having trouble with my scheme implemenation, it got to the point where I was just swapping in all of the functions that you wrote and I ran them and was still getting the incorrect answer. It turns out it was the way that I was encoding the data. If you run your program with data that marks the first peg as position 0 the results are skewed. Still haven’t figured out why.
Results:
40520
5736
((14) (12 13 14) (10 11 12) (5 8 11) (6 7 8) (11 12 13) (0 2 5) (1 3 6) (9 8 7) (5 4 3) (14 13 12) (6 3 1) (12 7 3) (3 1 0))
(define possible-moves
‘((0 1 3) (0 2 5)
(1 3 6) (1 4 8)
(2 4 7) (2 5 9)
(3 1 0) (3 4 5) (3 6 10) (3 7 12)
(4 7 11) (4 8 13)
(5 2 0) (5 4 3) (5 8 11) (5 9 14)
(6 3 1) (6 7 8)
(7 4 2) (7 8 9)
(8 4 1) (8 7 6)
(9 5 2) (9 8 7)
(10 6 3) (10 11 12)
(11 7 4) (11 12 13)
(12 7 3) (12 8 5) (12 11 10) (12 13 14)
(13 12 11) (13 8 4)
(14 9 5) (14 13 12)))
The initial board is also different due to the zero encoding:
(define init ‘((1 2 3 4 5 6 7 8 9 10 11 12 13 14)))
That (5 8 11) should be (5 8 12)
…………………………………………. That is what I get for drawing a shoddy triangle in my notes. Thank you.
Pleasure. Here’s some general code for the lower to higher moves:
#include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]) { int N = atoi(argv[1]); for (int i = 0, n = 0; i < N; i++) { for (int j = 0; j <= i; j++,n++) { if (i+2 < N) { printf("%d %d %d\n",n,n+i+1,n+i+i+3); printf("%d %d %d\n",n,n+i+2,n+i+i+5); } if (j+2 <= i) { printf("%d %d %d\n",n,n+1,n+2); } } } }Awesome, here is a solution using your standard prelude but with the data format a little more compressed:
;; we can see from above that many of these triplets share the same ;; middle digit, we can use these to reduce the size of our list of moves ;; (0 1 3) <=> (3 1 0) ;; (0 2 5) <=> (5 2 0) ;; (1 4 8) <=> (8 4 1) ;; (2 4 7) <=> (7 4 2) ;; (2 5 9) <=> (9 5 2) ;; (3 4 5) <=> (5 4 3) ;; (3 6 10) <=> (10 6 3) ;; (3 7 12) <=> (12 7 3) ;; we can now say that a triplet (a b c) represents both the moves ;; (a b c) AND (c b a) ;; this allows us to reduce our list of moves from 36 -> 18 (define compressed-possible-moves '((0 1 3) (0 2 5) (1 3 6) (1 4 8) (2 4 7) (2 5 9) (3 4 5) (3 6 10) (3 7 12) (4 7 11) (4 8 13) (5 8 12) (5 9 14) (6 7 8) (7 8 9) (10 11 12) (11 12 13) (12 13 14))) (define initial-board '((1 2 3 4 5 6 7 8 9 10 11 12 13 14))) (define (can-move? board move) (let ((from (car move)) (over (cadr move)) (to (caddr move)) (b (car board))) (and (member from b) (member over b) (not (member to b))))) (define (flip-move move) (list (caddr move) (cadr move) (car move))) (define (make-move board move) (cons (insert (caddr move) (remove (car move) (remove (cadr move) (car board)))) (cons move (cdr board)))) (define (move board move) (letrec ((move2 (flip-move move)) (canmove1 (can-move? board move)) (canmove2 (can-move? board move2))) (cond ((and canmove1 canmove2) (cons (make-move board move) (make-move board move2))) (canmove1 (make-move board move)) (canmove2 (make-move board move2)) (else #f)))) (define (all-moves board) (filter identity (map (lambda (m) (move board m)) compressed-possible-moves))) (define (solve init) (let loop ((k 13) (boards (list init))) (if (= 0 k) boards (loop (- k 1) (mappend all-moves boards))))) (let ((solutions (solve initial-board))) (display (length solutions)) (newline) (display (length (filter (lambda (x) (equal? (car x) '(0))) solutions))) (newline) (display (list-ref solutions 17493)) (newline)) ;; 29760 ;; 6816 ;; ((0) (3 1 0) (12 7 3) (14 13 12) (6 3 1) (5 4 3) (11 12 13) (1 3 6) (0 2 5) (13 8 4) (10 6 3) (9 5 2) (3 4 5) (5 2 0))So here is my code. It’s rough but it’s correct.
__author__ = ‘Christophe De Troyer’
# Define the the puzzle with 14 pegs and 1 hole.
# 0 = no peg, 1 = peg
INITIAL_BOARD = [0] + [1] * 14
# Define all possible moves.
moves = [
[0, 1, 3],
[0, 2, 5],
[1, 3, 6],
[1, 4, 8],
[2, 4, 7],
[2, 5, 9],
[3, 4, 5],
[3, 6, 10],
[3, 7, 12],
[4, 7, 11],
[4, 8, 13],
[5, 8, 12],
[5, 9, 14],
[6, 7, 8],
[7, 8, 9],
[10, 11, 12],
[11, 12, 13],
[12, 13, 14],
]
TOTALMOVES = []
global total_solutions
total_solutions = 0
global total_with_zero_peg
total_with_zero_peg = 0
for m in moves:
# Add initial move.
TOTALMOVES.append(m)
# Swap the move.
m2 = list(m)
temp = m2[0]
m2[0] = m2[2]
m2[2] = temp
TOTALMOVES.append(m2)
# A move can be made iff the right index in the list contains a False value in
# the list (puzzle).
def can_make_move(move, board):
if board[move[0]] == 1 and board[move[1]] == 1 and board[move[2]] \
== 0:
return True
return False
# A move is made by marking the index contained in the 2nd position of the move
# as true in the puzzle list and the first position as false.
def make_move(move, board):
new_board = list(board)
# Move the peg.
new_board[move[2]] = 1
new_board[move[0]] = 0
# Remove the peg that just got jumped over.
new_board[move[1]] = 0
return new_board
# A game is finished once the sum of the list is 1.
def is_finished(board):
return sum(board) == 1
# Returns a list of all the moves we can make in the current game state.
def yield_moves(board):
for move in TOTALMOVES:
if can_make_move(move, board):
yield move
def solve(board=INITIAL_BOARD, moves_done=[]):
# If the game is done, print out the moves.
global total_solutions, total_with_zero_peg
if is_finished(board):
total_solutions += 1
if board[0] == 1:
total_with_zero_peg += 1
else:
for move in yield_moves(board):
solve(make_move(move, board), moves_done + [m])
solve(INITIAL_BOARD, [])
print ‘Total solutions found: {0}:’.format(total_solutions)
print ‘Total solutions found with a peg in the zero hole: {0}’.format(total_with_zero_peg)
Another solution using Java Fork/Join framework:
/****************************************************************************** * Cracker Barrel * @author : Christophe De Troyer * Last edit: 8-sep-2014 10:43:22 * Full source can be found on GitHub ******************************************************************************/ import java.util.ArrayList; import java.util.Date; import java.util.concurrent.ForkJoinPool; import java.util.concurrent.RecursiveTask; public class MoveTask extends RecursiveTask<ArrayList<Results>> { /** The Constant serialVersionUID. */ private static final long serialVersionUID = 9026570098669274448L; private final ArrayList<int[]> moves_todo; private final int[] gameboard; private int first; private int last; private ArrayList<int[]> movesDone; private final static int[][] MOVES = new int[][] { new int[] { 0, 1, 3 }, new int[] { 0, 2, 5 }, new int[] { 1, 3, 6 }, new int[] { 1, 4, 8 }, new int[] { 2, 4, 7 }, new int[] { 2, 5, 9 }, new int[] { 3, 4, 5 }, new int[] { 3, 6, 10 }, new int[] { 3, 7, 12 }, new int[] { 4, 7, 11 }, new int[] { 4, 8, 13 }, new int[] { 5, 8, 12 }, new int[] { 5, 9, 14 }, new int[] { 6, 7, 8 }, new int[] { 7, 8, 9 }, new int[] { 10, 11, 12 }, new int[] { 11, 12, 13 }, new int[] { 12, 13, 14 } }; /** * Instantiates a new move task. */ public MoveTask(final int[] gameboard, ArrayList<int[]> initial_moves, ArrayList<int[]> movesDone) { this(gameboard, initial_moves, 0, initial_moves.size() - 1, movesDone); } /** * Instantiates a new move task. */ public MoveTask(final int[] gameboard, final ArrayList<int[]> moves_todo, int first, int last, ArrayList<int[]> movesDone) { this.gameboard = gameboard; this.moves_todo = moves_todo; this.first = first; this.last = last; this.movesDone = movesDone; } /** * Flips the move's direction. */ public static int[] flipMove(int[] move) { return new int[] { move[2], move[1], move[0] }; } /** * This function checks if a certain move is valid for a given gameboard. */ public static boolean canMakeMove(int[] move, int[] board) { return board[move[0]] == 1 && board[move[1]] == 1 && board[move[2]] == 0; } /** * Applies a move to the board and returns a copy of the board. */ public static int[] makeMove(int[] move, int[] board) { int[] new_board = board.clone(); new_board[move[2]] = 1; new_board[move[0]] = 0; new_board[move[1]] = 0; return new_board; } /** * Returns true if there is only one more peg left on the gameboard. */ public static boolean isFinished(int[] board) { int sum = 0; for (int hole : board) sum += hole; return sum == 1; } /** * Returns a list of all possible moves in this gamestate. * * @param board * the board * @return the moves to do */ public static ArrayList<int[]> getMovesToDo(int[] board) { ArrayList<int[]> moves = new ArrayList<int[]>(); for (int[] move : MOVES) { if (canMakeMove(move, board)) moves.add(move); if (canMakeMove(flipMove(move), board)) moves.add(flipMove(move)); } return moves; } /* * (non-Javadoc) * * @see java.util.concurrent.RecursiveTask#compute() */ @Override protected ArrayList<Results> compute() { int currentDataWidth = this.last - this.first; if (isFinished(this.gameboard)) { return new ArrayList<Results>() {{ add(new Results(movesDone, gameboard)); }}; } if(this.moves_todo.size() < 1) return new ArrayList<Results>(); // We can only make one move. // We make the move and then start the process all over again. if (currentDataWidth == 0) { int[] newBoard = makeMove(moves_todo.get(this.first), gameboard); ArrayList<int[]> movesToDo = getMovesToDo(newBoard); movesDone.add(moves_todo.get(this.first)); return new MoveTask(newBoard, movesToDo, movesDone).compute(); } else { int halfway = this.first + currentDataWidth / 2; // Create the left and right tasks. MoveTask left = new MoveTask(this.gameboard, this.moves_todo, this.first, halfway, movesDone); MoveTask right = new MoveTask(this.gameboard, this.moves_todo, halfway + 1, this.last, movesDone); // Execute the tasks. left.fork(); ArrayList<Results> right_result = right.compute(); ArrayList<Results> left_result = left.join(); right_result.addAll(left_result); return right_result; } } /** * The main method. */ public static void main(String[] args) { long before = new Date().getTime(); int[] gameboard = new int[]{0,1,1,1,1,1,1,1,1,1,1,1,1,1,1}; ArrayList<int[]> initial_moves = MoveTask.getMovesToDo(gameboard); ArrayList<Results> result = execute(gameboard, initial_moves); // Count the number of games where the top hole has a peg in it. int pegInTop = 0; for(Results res : result) if(res.gameboard[0] == 1) pegInTop++; System.out.println(String.format("Total solutions: %s \nTotal solutions with peg in top hole: %s\n", result.size(), pegInTop)); System.out.println("duration: "+(new Date().getTime()-before)); } public static ArrayList<Results> execute(int[] gameboard, ArrayList<int[]> initial_moves){ // Initiate the F/J Pool. ForkJoinPool forkJoinPool = new ForkJoinPool(4); return forkJoinPool.invoke(new MoveTask(gameboard, initial_moves, new ArrayList<int[]>())); } }Total solutions: 29760
Total solutions with peg in top hole: 6816
duration: 244
This is similar to the solver I wrote in the early 1980s.
I’d been sitting on this trying to get access to a fast server for some benchmarking. But I didn’t get the server, and it doesn’t matter. Suffice it to say that this solver runs in milliseconds.
#include <stdbool.h> #include <stdio.h> // Peg numbering: // 0 // 1 2 // 3 4 5 // 6 7 8 9 // A B C D E #define A 0xA #define B 0xB #define C 0xC #define D 0xD #define E 0xE #define HOLE_COUNT 15 typedef short peg_mask; // 15 pegs, fits in a signed short (-: const peg_mask initial_state = 0x7ffe; // all except 0 const char triangle[5][5] = { { 0 }, { 1,2 }, { 3,4,5 }, { 6,7,8,9 }, { A,B,C,D,E } }; typedef struct move { peg_mask mask; peg_mask old; peg_mask new; } move; typedef struct solver_state { peg_mask prev_state [1 << HOLE_COUNT]; move possible_moves [6 * HOLE_COUNT]; // oversize bool print_answer; } solver_state; static inline bool is_winning_state(peg_mask state) { // win when single peg remains. return (state & (state - 1)) == 0; } void add_move(solver_state *p, int *pi, int row, int col, int dr, int dc) { int from = triangle[row][col]; int over = triangle[row += dr][col += dc]; int to = triangle[row += dr][col += dc]; peg_mask fm = 1 << from; peg_mask om = 1 << over; peg_mask tm = 1 << to; move *mp = &p->possible_moves[*pi]; mp->mask = fm | om | tm; mp->old = fm | om; mp->new = tm; ++*pi; } void precalc_possible_moves(solver_state *p) { int i = 0; for (int row = 0; row < 5; row++) { for (int col = 0; col <= row; col++) { if (row >= 2) { if (col >= 2) { // Jump NW from r/c add_move(p, &i, row, col, -1, -1); } if (col <= row - 2) { // Jump NE from r/c add_move(p, &i, row, col, -1, 0); } if (col >= 2) { // Jump E from r/c add_move(p, &i, row, col, 0, -1); } if (col <= row - 2) { // Jump W from r/c add_move(p, &i, row, col, 0, +1); } } if (row < 5 - 2) { // Jump SE from r/c add_move(p, &i, row, col, +1, 0); // Jump SW from r/c add_move(p, &i, row, col, +1, +1); } } } } void print_path(peg_mask state, const solver_state *p) { if (state != initial_state) print_path(p->prev_state[state], p); for (int row = 0; row < 5; row++) { printf("%*s", 4 - row, ""); for (int col = 0; col <= row; col++) printf(" %c", state & (1 << triangle[row][col]) ? 'X' : '_'); printf("\n"); } printf("\n"); } // Given a board configuration, explore all possible moves from there. peg_mask gen_moves(peg_mask state, solver_state *p) { if (is_winning_state(state)) return state; for (const move *mp = p->possible_moves; mp->mask; mp++) { if ((state & mp->mask) == mp->old) { peg_mask next_state = (state & ~mp->mask) | mp->new; p->prev_state[next_state] = state; peg_mask winner = gen_moves(next_state, p); if (winner) return winner; } } return 0; } void solve(solver_state *p, bool print_answers) { precalc_possible_moves(p); peg_mask winner = gen_moves(initial_state, p); if (print_answers) print_path(winner, p); }