Suppose I have a row of cells with 2n+1 spaces in it. The first n spaces have white pieces, then there is an empty space, then there are n black pieces. So, if n=2, youd have: Your goal is to reverse the order of the pieces.

The moves you can do are: 1) Move a piece into an empty space. White pieces can only move left, and black pieces can only move right. 2) Jump over a piece of the opposite color into an empty space beyond. So, here is a possible sequence of moves: Starting position: Black moves ahead: White jumps: Black moves ahead: Black jumps: White moves ahead: Stuck!

Your job is to write a program that: - Reads in an integer n from the user. - Sets up the board for the initial state - Writes a recursive backtracking program that either solves the puzzle (and if so, tells you the moves to take), or reports that it cant be solved. When you output the moves to take, you can either output the moves themselves (Jump with the piece on space 3) or the board configurations of the moves (similar to the pictures above), whatever you find easier). Keep in mind that the natural way of doing backtracking will probably generate the moves in reverse order. You should fix things to display the moves in the correct order.

About the algorithm: Note that I am asking you to turn in an algorithm for this program next Monday. (If you manage to write the whole program by next Monday, you dont have to do an algorithm.) What I am looking for here is a description of how the program you are writing will look- your basic strategy without worrying about basic C++ syntax. So, you should be able to answer questions like: - How will you make the initial board? - How will your backtracking function work? What parameters will it take? How will it try different options? What will its recursive calls look like (in the different situations?) What is your base case? (When are you done?) - How will you keep track of the sequence of moves needed to reach the solution?