## Transcribed Text

Recursion Puzzles
Abstract
In this lab you will implement recursive solutions to classic CS questions. One will be a chess problem, and the other is Towers of Hanoi.
1 Backtracking with Recursion - Featuring Chess
Choose and complete one of the two following chess problems. These
problems can be solved using the backtracking algorithm shown below.
boolean solve(board, pos){
if( pos is such that there is nothing left to solve){
return true;
}
for each possible choice {
if(valid(choice)){
mark board at pos with choice;
if(solve(board, pos + 1) == true){
return true;
}
}
}
clear any choices entered at pos on board;
return false; // backtrack
}
1
1.1 The Eight Queens Problem
Write a recursive method which solves the eight queens problem. You must find
a state where you can place eight queens on a chessboard such that no queen
can capture another queen. Queens can move and capture pieces in the same
row, column, or any diagonal.
You may use an 8 × 8 int[][] array to represent your chess board. An
example solution is below.
8 0Z0ZQZ0Z
7 ZQZ0Z0Z0
6 0Z0L0Z0Z
5 Z0Z0Z0L0
4 0ZQZ0Z0Z
3 Z0Z0Z0ZQ
2 0Z0Z0L0Z
1 L0Z0Z0Z0
a b c d e f g h
Hint: only one queen can be placed in each column.
2
1.2 Knight’s Tour (More Challenging)
Write a program to solve the Knight’s Tour. In the Knight’s Tour, we place a
Knight on the chess board and move him until he visits each square of the chess
board exactly once.1 A knight moves two squares horizontally or vertically and
then one square in the axis it did not move it, creating a sort of “L” shaped
(see below). A square counts as visited once the knight lands in it.
8 0Z0Z0Z0Z
7 Z0Z0Z0Z0
6 0Z0Z0Z0Z
5 Z0Z0Z0Z0
4 0Z0Z0Z0Z
3 Z0M0Z0Z0
2 0Z0Z0Z0Z
1 Z0Z0Z0Z0
a b c d e f g h
You may start your knight anywhere you like. Your output should be either
the chess board, but with each square marked by a number to designate the
order in which the square was visited, or by listing the moves the knight makes.
If you can figure out a better way to represent your answer, we are open to that
too.
1Please do not sack Constantinople on your way to the answer.
3
2 Towers of Hanoi (Easier Than it Looks)
Write a recursive method that prints out the individual moves you need to
perform to solve a Towers of Hanoi problem with n rings. Use stacks to represent
your pegs
In Towers of Hanoi, you have three pegs and n disks, each a different size.
The game starts with all the disks places on the left in sorted order, with the
largest disk on the bottom, and the smallest on the top. The objective is to
move all the disks from the leftmost peg to the rightmost peg, with the following
rules in place.
1. You can only move one disk at a time.
2. A move moves the top disk on one peg and places it on top of another
peg.
3. You may not put a larger disk on top of a smaller disk.
4

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction
of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice.
Unethical use is strictly forbidden.

public class EightQueens {

// method to check if state is valid

public static boolean valid(int[] board, int n) {

for (int i = 0; i < n; i++) {

if (board[i] == board[n]) {

return false;

} else if (Math.abs(board[i] - board[n]) == Math.abs(n - i)) {

return false;

}

}

return true;

}

// method to display board (solution)

public static void display(int[] board) {

System.out.println("Solution found:")...