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, you'd have: Your goal is to reverse the order of the pieces, so: 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: 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 can't 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. Sample runs (Note that there is more than one solution to each problem. So if you may not get my exact answer, you might be ok. You should check it and see if you are right). Also notice that I am just outputting the number of the position of the piece to move, starting from 0 on the left. So the " 1 " in the first answer means to move the piece in position 1 (the rightmost black piece) The second 3 means to move the piece in position 3 (the leftmost white piece. Since there is a black piece to its left, the only legal way to move that white piece is with a jump. How many pieces for each color? 2 Sequence of moves: 13434132 How many pieces for each color? 3 Sequence of moves: 245310246531243 How many pieces for each color? 20 171921232526242220181614131517192123252728 262422201816141211131517192123252729302826 28262422201816141210879111315171921232527 1614121086357911131517192123252729313335 3738363432302826242220181614121086421357 9111315171921232527293133353739403836343230 2821262324252227202918311633143512371039838636434232030128326524722920111813151719 1635143712361034832630428226324522720918111613141512171019821423425727929113133 161412108679111315171921232527293133323028 262422201816141210891113151719212325272931 302828262624242222202018181616141412121310151117131915211723192521272326252427222920