Data Structures Program #9

CS 153 Data Structures I

Assignment #9

Due: 3/22/01

Purposes: to learn about programming recursively by solving a game puzzle.

Options:

Write the program in 'console mode' (CS 53/74 method. Command line start. No windows.
Write the program using the Dialog window approach

The Game Puzzle: a 7x7 board with 2x2 missing corners.

-	-	X	X	X	-	-
-	-	X	X	X	-	-
X	X	X	X	X	X	X
X	X	X	0	X	X	X
X	X	X	X	X	X	X
-	-	X	X	X	-	-
-	-	X	X	X	-	-

The game is played by jumping a piece (X) over an adjacent piece into an open position (0). Diagonal jumps are not allowed. The game is 'won' when only one piece remains

Hints:

main() should
- set up the board and initialize all required variables
- result = make_jump(move_num)
- if (result == true) the game has been solved
- else a logic error exists in the make_jump function
bool make_jump(move_number) should
- if ( 'terminal condition' )
  - ye ha, the puzzle is solved
  - display the moves made
  - return true
- else
- find the 1st/next legal move
  - make the move (on the board)
  - record the move (for later display)
  - result = make_jump(move_num)
  - if (result == true) return true
  - else
  - UNmake the move
  - repeat the process
- If (no more legal moves) return false