QuestionQuestion

Transcribed TextTranscribed 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

Solution PreviewSolution Preview

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:")...

By purchasing this solution you'll be able to access the following files:
Solution.PNG, Solution1.PNG, Solution.java and Solution1.java.

$60.00
for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Java Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats