StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The purpose of using recursion for these kinds of problems is that they allow you to think in terms of "I have now placed <em>k</em> queens; how can I place the remaining ones if the total number of queens is <em>n</em>?" So the recursive function should take <em>two</em> parameters: the target number of queens, and the number of queens placed so far. When writing the function, your goal is first and foremost to try out different ways of placing the <em>k</em> th queen. But when you have selected a possible placement and found it to be valid, you need to place the remaining <em>n - k - 1</em> queens. How can we do this? The answer: recursion! Call the function (from within itself) with the parameter <em>k - 1</em> to indicate that you want to place the remaining <em>k - 1</em> queens. Whenever you exhaust all possibilities (or find that none are possible), simply return from the function - you will then get back to the previous function call (e.g. the one that tries to place the <em>k</em> th queen).</p> <p>Edit: You will also need to create a two-dimensional array to represent the current state of your board; this array must either be sent as an additional parameter to the recursive function, or be kept as a field of the class that contains the method.</p> <p>As for the backtracking, that is accomplished simply by making sure that the function that gets called with <em>k + 1</em> removes the <em>k + 1</em> th queen from the board before returning; this essentially says "We've now (unsuccessfully) tried all ways of placing the remainder of the queens - <em>based on the positions of the k queens that have already been placed</em>. None of them succeeded, so please adjust the positions of the first <em>k</em> queens (which will be done by the function that was called with <em>k</em>, and the function which called that function, and so on) and try again."</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload