Good Old Country-Style Optimization

In an odd way, Imre Polik's recent post, How to solve puzzles? Peg solitaire with optimization, reminded me of one more reason why I like to eat at Cracker Barrel, an American chain of country-style restaurants.

A Relaxing Place to Stop

For those who aren't U.S. residents, Cracker Barrel has locations in 42 states and features home-style cooking, a big porch with rocking chairs, checkerboards, and an attached "general store." Cracker Barrel restaurants hearken back to a "small-town America" atmosphere that only some of us ever experienced directly but many find comforting. Sure, it's a slightly formulaic approach, but during a long automobile trip it can provide a relaxing break. I especially like these restaurants because I can eat okra (delightful) without having to prepare it (really NOT delightful). In the general store, I never leave without buying at least a couple of these:

I love these peppermint sticks (who can't love a candy that's bold enough to advertise itself as "pure sugar?"), and I seem to have plenty of company among the Cracker Barrel clientele, because I always find them prominently displayed next to the cash registers. I stock up twice a year, when we stop during our trips from North Carolina to Maryland to visit my side of the family.

Just about the biggest attraction at Cracker Barrel for me, though, is the optimization problem that sits on every single table.

Optimization? Really?

Yes! And I'm not talking about a classical diet optimization problem lurking in the menu. On every table in every Cracker Barrel restaurant that I've visited, there's one of these:

These triangular peg (technically, golf tee) solitaire puzzles are a very minor variation on the pentagonal solitaire puzzle that Imre discussed. As always, you move a peg over another peg in a straight line, landing in an empty hole on the other side and thus "capturing" the jumped peg, removing it from the board. The goal is to end with just one peg on the board, and it's not as easy as it might seem. The clever folks at Cracker Barrel decided, I'm betting, that tinkering with this puzzle occupies diners' minds as they wait for their food to arrive. For me, it's another opportunity to apply optimization, in this case to answer some questions that would take an absurdly large number of dinners to tackle:

• You nearly always start with the top hole in the puzzle empty, but can you win and have the last peg located in ANY hole?
• Can you finish with the last peg in the top hole?
• Just how many different ways are there to win with this puzzle?
• Can I memorize a set of winning moves and impress my family?

Short and Long Answers

The answers, briefly, are no, yes, a whole lot, and I hope so--that's one reason why I've written this. That is, I hope you can memorize the moves. Whether it impresses your family or not--that depends on the family. Teenage family members, in my experience, are almost impossible to impress!

Digging Deeper

Now for the details. First, just as Imre explained in his post, we need to impose a coding on the locations in this puzzle. Let's keep it simple. The top hole is A, the second row, left to right, is B and C, and so on--down to location O in the lower right corner. It looks like this:

Now we need to define the possible moves for this puzzle, and again, I'll imitate what Imre did. Move X-Y-Z means that the peg in location X jumps to the empty location Z and captures the peg at location Y. Because we can specify just half the moves and let the OPTMODEL procedure in SAS/OR create the corresponding moves in the other direction, I'll include just the moves that proceed from left to right or from top to bottom. The moves start with A-B-D, A-C-F, and B-D-G, and finish with K-L-M, L-M-N, and M-N-O, for 18 moves in all. OPTMODEL generates the reverse of each of these moves, for a total of 36 moves.

Practical Implications

What does this mean, practically speaking? In the SAS code, you specify the empty location to start (typically, A) and the desired ending location (any of A through O). If OPTMODEL finds a solution, then it reports the moves in that solution. Here's where it gets more interesting, though. If OPTMODEL finds that the problem is infeasible, then you can never start with your chosen starting location empty and win with the last peg in the ending location you chose. Surprisingly, this happens for most of the locations on the board. For example, if you choose to start with location A empty, then you can win only with the last peg in location A, G, J, or M.

Taking this analysis a good bit further, if you choose to start with location E empty, all winning paths leave the last peg in location M. If you start with location B empty, you can win and finish at location B, F, K, or N. Starting with location D empty gives you the greatest selection of ending locations; there are winning paths leading to location C, D, I, L, or O. Owing to the symmetry in this puzzle, the location A results are applicable also to locations K and O, the location B results hold for locations C, G, L, J, and N, the location E results apply to locations H and I, and the location D results apply to locations F and M. In all of these cases, re-map the noted ending locations according to the change in the starting location.

A Thousand (Minus 998) Ways to Solve...

Turning back to solutions that start with location A empty, that's two questions answered. You can find a solution for some cases, but for any such case, how many winning plays are there? You have a choice in solving this problem, as of SAS/OR 13.2. You can use the MILP (mixed integer linear programming) solver and find one solution, or you can use the experimental CLP (constraint logic programming) solver and find many solutions--or all of them, if you like. Of course, you can always effectively find more ways to solve with either approach by altering the formulation, so there really might be a thousand ways to solve this problem.

Let's look at the case of starting with location A empty and winning with the last peg in location M. Here's one solution from the MILP solver, courtesy of OPTMODEL:

...and Thousands of Solutions!

How many A-to-M solutions are there in total? I ran the CLP solver with the FINDALLSOLNS option, which does just what its name suggests. It turns out that there are 16,128 winning moves that put the last peg in location M. Admittedly, some of these are minor variations on a common theme, reordering many of the same moves. This happens because after the board has been cleared out a bit, the same set of moves will clear the remaining pegs even if you shuffle the order of those moves slightly. Still, there are also many solutions that use distinct sets of moves.

If you solve for the other possible ending locations, you'll find that 6,816 solutions end at position A, 3,408 solutions end at position G, and and (due to symmetry in the puzzle) another 3,408 end at position J. Thus, a total of 29,760 solutions exist for this puzzle! And just for fun, if you ate every lunch and dinner at a Cracker Barrel restaurant and found, say, 2 solutions per meal, it'd take you over 20 years to run through all of these solutions. If you're going to show that kind of commitment, though, perhaps you should part with the $2.99 it takes to buy the puzzle, and run through the solutions from the comfort of your home. After all, just how much okra do you want to eat?

What's In It for You?

The good news is that you need to memorize only one solution. In addition to the solution shown above, ending at position M, here's a solution that places the final peg in location J, on the right side of the board, with each step in the solution illustrated. The images progress from left to right and then from top to bottom. Whether you memorize better from text or from graphics, you're covered.

So one way to impress your family is to memorize a solution and speed through it the next time you eat at a Cracker Barrel. Taking it up a notch, memorize one solution for each of the four possible ending locations (after you run the SAS code), challenge your family to pick an ending point, and then show a solution that ends there. If they don't believe that all ending points except for A, G, J, and M are impossible, you can challenge them to show you a solution ending somewhere else.

Special bonus (perhaps a bit cruel): if your kids are a little too jittery, bouncy, etc., ask them to find a solution that begins with A empty and ends at somewhere other than A, G, J, or M. You'll have peace for the entire meal---unless one of your kids has a talent for optimization and a laptop running SAS, in which case there could be trouble.

PROC OPTMODEL Code, and Acknowledgements

Here's the SAS code (borrowing very heavily from Imre) that I used to build and solve this problem using PROC OPTMODEL. To replicate the single A-to-M solution shown above, use the MILP solver. To solve for other ending locations, change the value of the "END=" parameter toward the end of the program, just above the SOLVE command. To start with the empty space at a location other than "A," change the value of the "START=" parameter in the preceding line.

To find all solutions for specified starting and ending locations, comment out the SOLVE statement that invokes the MILP solver (insert an asterisk at the start of the line) and remove the comment tag from the SOLVE statement that invokes the CLP solver. If you wish, you can replace the FINDALLSOLNS option with the MAXNSOLNS= option and specify the maximum number of solutions that you'd like to see.

Many thanks to Imre Polik for his original post and SAS code, and to Rob Pratt, who not only assisted Imre with the original SAS code for peg solitaire but also contributed to the code shown here that creates output data for single or multiple solutions. Rob also explained why so many solutions reorder the same sets of moves. Thanks also to Gehan Corea and Lindsey Puryear from SAS/OR R&D, creators of the SAS/OR CLP solver, for their advice on solver settings.

 
/* This is a data set of possible (half) moves */
data moves;
   input from $ take $ to $;
	datalines;
A B D
A C F
B D G
B E I
C E H
C F J
D G K
D H M
E H L
E I N
F I M
F J O
D E F
G H I
H I J
K L M
L M N
M N O 
;
proc optmodel;
   /* We fill up the entire board with 0 and 1 */
   set CELLS = /A B C D E F G H I J K L M N O/;
   num boardstart{CELLS} init 1;
   num boardend{CELLS}   init 0;
 
   /* The status of the board before a round */
   /* A binary variable for each cell        */
   /*   1 if there is a peg in the cell,     */
   /*   0 if the cell is empty               */
   num numrounds = 13;
   set ROUNDS = 0..numrounds;
   var board{ROUNDS, CELLS} binary;
 
   /* A binary variable for all 36 possible moves in each round */
   /* A 1 value indicates that the move is used in the round    */
   set OBS;
   set MOVES init OBS;
   var move{ROUNDS diff {numrounds}, MOVES} binary;
 
   /* A data matrix on what each move is              */
   /* This will be filled in later                    */
   /* It details the effects of each move             */
   /*   on the nodes involved in the move (see below) */
   num edge{CELLS, MOVES} init 0;
 
   /* Where a move begins */
   str from{MOVES};
 
   /* Which cell a move takes */
   str take{MOVES};
 
   /* Where a move ends */
   str to{MOVES};
 
   /* Read the three columns from the input data into our arrays */
   read data moves into OBS=[_N_] from take to;
 
   /* Double these to get all of the possible moves */
   num cardOBS = card(OBS);
   MOVES = 1..2*cardOBS;
   for {i in OBS} do;
      from[i+cardOBS] = to[i];
      to[i+cardOBS]   = from[i];
      take[i+cardOBS] = take[i];
   end;
 
   /* Now we fill in the edge matrix           */
   /* For any (from take to) triplet we have   */
   /*   edge[from,move] = -1                   */
   /*   edge[take,move] = -1                   */
   /*   edge[to,move] = +1                     */
   for {i in MOVES} do;
      edge[from[i],i] = -1;
      edge[take[i],i] = -1;
      edge[to[i],i]   =  1;
   end;
 
   /* Raw starting position */
   con startcon{i in CELLS} : board[0,i] = boardstart[i];
 
   /* Raw final position */
   con endcon{i in CELLS} : board[numrounds,i] = boardend[i];
 
   /* In each round the board changes due to the moves in that round... */
   con round{i in ROUNDS diff {numrounds}, j in CELLS} :
      board[i+1, j] - board[i,j] = sum{k in MOVES} edge[j,k] * move[i,k];
 
   /* ...but only one move is permitted in each round */
   con onemove{i in ROUNDS diff {numrounds}} : 
      sum{k in MOVES} move[i,k] = 1;
 
   /* Refine the starting and ending positions */
   /* At the start, cell START is empty        */
   /* At the end, cell END has the last piece  */
   str START = 'A';
   str END   = 'M';
   boardstart[START] = 0;
   boardend[END] = 1;
 
   min Zero = 0; /* objective is optional in 13.2 */
 
   /* Solve the problem */
   solve with milp;
   *solve with clp / findallsolns varselect=minrmaxc;
 
   /* Create the solution table */
   str solution{ROUNDS diff {numrounds}, 1..3, 1.._NSOL_};
   for {k in (1.._NSOL_)} do;
      for {i in ROUNDS diff {numrounds}} do;
         for {j in MOVES: move[i,j].sol[k] > 0.5} do;
            solution[i,1,k] = from[j];
            solution[i,2,k] = take[j];
            solution[i,3,k] = to[j];
            leave;
         end;
      end;  
   end;
   create data solution_data from [k]=(1.._NSOL_)
      {i in ROUNDS diff {numrounds}} 
      <col('move_'||i+1)=(cat(solution[i,1,k],solution[i,2,k],solution[i,3,k]))>;
quit;
 
/* Print the solution(s) found */
proc print data=solution_data; run;

Have fun, and if you stop at Cracker Barrel, be sure to get some peppermint sticks!