8 queens with recursive method with backtracking Solution Backtracking is an ess

Question

8 queens with recursive method with backtracking

Explanation / Answer

Backtracking is an essential problem solving tool for programs where there is not enough local information to know for certain how to progress toward the desired goal. Unlike, for example, merge sorting (or any other sorting algorithm), where it is known that sorting, and merging will make progress toward the desired result, a backtracking program for searching a solution space tries one way forward: it takes a legal step that extends the partial result obtained so far and does not invalidate the property that must be satisfied. It then makes a recursive call to look for a continuation of the partial result it has just extended. Because the continuation may not exist, however, the search for it may fail. This occurs if the program tries a step forward that is taking it down a dead end street (the example of searching through a maze is a good one to keep in mind here). When a failure to find a continuation is reported, the program tries another legal step if it has one available to it, and looks for a continuation from that point. If all of the possible legal steps that it can try results in failed attempts to find a continuation, then the program must report a failure itself. This result is reported to the program that invoked it, which then, in turn, may have to try another legal step or report failure to its caller. Now that this concept has been explained, I will introduce a problem that I have done between yesterday and today, that is a very good problem to explore for programmers (some of you may have already heard of this). So, another example of backtracking with recursion is the classic problem of placing 8 Queens on a chess board of 8x8 squares in such a way that no queen threatens another (http://en.wikipedia.org/wiki/Eight_queens_puzzle) (http://mathworld.wolfram.com/QueensProblem.html). This problem is not an inherently interesting part of computer science, but it does illustrate the general pattern for these recursive search and backtrack programs. The queen is the most versatile of all chess pieces. It can capture any piece in the same row, in the same column, or along either diagonal from its location on the board. These first two conditions mean that no two queens can have the same row number or the same column number. We must guard, as well, against threats from a diagonal. Q . . . . . . . Q = Queen . . . Q . . . . . Q . . . . . . . . . . Q . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Queens are placed safely in column 1-5 but there is now no safe square in column 6 (sorry for the bad depiction >_>) We begin our solution by placing the first queen in column 1, row 1. The second queen will be places in column 2. It obviously cannot be in row 1, but, because of a diagonal threat from the queen in column 1, it also cannot be row 2. So we place it in row 3 and continue trying to place the next queen in column 3. The smallest row there that is not threatened is row 5. Continuing to column 4, we can place a queen in row 2; in column 5 we can place a queen in row 4. But now in column 6 there is no square that is not threatened (see diagram). And we know that the solution, if there is one, must have a queen in each column. So we must backtrack to column 5 and choose an alternative safe location there, if possible. The only remaining safe location is row 8, so we try again to place a queen in row 6 with this change, and again we fail. So now we must backtrack to row 4 as row 5 has no more options. And so on... To see how recursion can be used to solve the problem, we start by placing a queen in the first column and calling the recursive method to place a queen which, in turn, calls the same method to place the next queen, and so on until we reach the degenerate case where there is no columns in which a queen can be placed. We look for a recursive method that places a queen in a column assuming that queens have been placed successfully in the preceding columns. We do not know whether the most recent placement is a success until we try to place a queen in the next column. If we cannot, we must backtrack. My solution to the Eight Queens problem uses a two dimensional Boolean array to represent the board where, if the value of a square is true it means there is a queen there and if the value of the square is false there is no queen there. I recommend exploring this concept further, and try solving the problem yourself (though there are numerous variations of this kind of problem), and submit anything you have discovered. Here is the complete program in Java (I've been using python/ C++ too often nowadays). Hope you've enjoyed this short tutorial Smile code: import java.util.Scanner; /* * The Queens class. * Places a number of chess queens on a board of a * specified size so that no queen can attack another. */ public class Queens { protected int boardSize; protected boolean[][] board; public Queens (int boardSize) { this.boardSize = boardSize; board = new boolean[boardSize][boardSize]; for (int row = 0; row

Related Questions

Navigate

• Browse (All)
• Browse 8
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.