Final Project: Playing Solitaire

###
Final Project: Playing Solitaire

Before you tackle the homework, remind yourself of our General Advice, Advice on Homeworks, and Grading Guidelines. Above all, keep your work neat and honest.

Background Solitaire is a board game for individuals. The board comes in various shapes. The two most common shapes are:

    	      o
    	     o o
    	    o x o
    	   o o o o

and

          = = o o o = =
          = = o o o = =
          o o o o o o o
          o o o x o o o
          o o o o o o o
          = = o o o = =
          = = o o o = =

The red x represents an unoccupied hole; the `o`s are little pegs sticking in holes; and `=` stands for the surrounding wood.

The goal of the game is to eliminate the pegs one by one until only one peg is left. A player can eliminate a peg if it one of the neighboring holes is unoccupied and if there is a peg in the hole in the opposite direction. In that case, the second peg can jump over the first one and the first one is eliminated.

For example, in the above triangle shape, no peg can be eliminated. But, if the initial hole is on the side like this:

    	      o
    	     o o
                o o x
    	   o o o o

then the blue and the cyan peg could jump. If the player decides to move the blue one, the next configuration is

    	      x
    	     o x
                o o o
    	   o o o o

Problem: Develop a program that solves a Solitaire problem for different sizes of the equilateral triangle. The size of the triangle should be specified by a definition at the top of the program. The hole should always be placed at the right-most position in the second row. At the bottom of the program, you should have apply the procedure `solitaire` to whatever arguments are necessary. In short, your program should have the following outline while you develop it:

      (define NUMBER-OF-ROWS 4)
      ...
      (solitaire ...)

The function `solitaire` should return false, if the given problem is not solvable. Otherwise, it should produce a list of moves that specifies in what order the pegs must be moved to solve the given Solitaire problem. When you're finished, you may wish to encapsulate the code into a single definition:

      ;; solitaire-for-triangle : num -> (listof ...)
      (define (solitaire-for-triangle NUMBER-OF-ROWS)
        (local (...
                ...)
          (solitaire ...)))

Product: You must turn in the following:

1. a concise explanation of what the representation of a move relates to in the real world of pegs and Solitaire boards
2. a concise description of the program design, i.e.,
   1. the board representation
   2. the global problem-solving strategy
   3. the program's key problem solving steps (with respect to the chosen board representation and global strategy)
3. the program with
   1. a contract for each definition
   2. a block comment with tests
   3. (optional) any other intermediate material you used to develop the individual procedures

Hint: You may wish to start the development by representing the input board with lists as follows:

    (define InputBoard
      '(( o = = = )
        ( o o = = )
        ( o x o = )
        ( o o o o )))

Your program can then translate the board into the preferred representation. Figure out later how to translate the number of rows into this shape.

Challenge: Modify the program so that it solves Solitaire for the rectangular shape. If you used the hint, you should be able to specify the initial board via a quoted list of lists. You should modify your program so it computes two variants of the solution. In the first case, only vertical and horizontal jumps are allowed, i.e., pegs cannot jump diagonally. In the second case, pegs can move in a diagonal manner. [The difference are five lines of code.]

Note: program my (MF) could only solve the second case in an overnight run (at least more than 4 hours, on a 166Mz, Linux laptop).

The challenge carries no credit.

Matthias Felleisen | Last modified at