C++ - Recursion - and chess
Author
Hello all,
Not sure if anyone has tried this problem before, although it was presented to me at school as a way to enhance my "recursion" attitude. I am having problems with the concepts of recursion, and this was one example my professor threw at me to try and make me "think" in a recursice manner.
While I found the problem intriging, I have as of yet figured, determined a way to figure the solution out recursively. Without further ado, the problem is thus:
Place 8 queens on the chess board in such a way that no one queen can attack any other.
So, I sat down with a chess board, and figured out one solution (which if you choose to go this path, 7 queens is easy, its always the 8th that hurts, lol). Anyhow, if I were to generate a row, col out of the board, here is the solution I (actually my son figured out before me) came up with:
Cols across the board are A-H
Rows down are 0-7
Queen Locations:
0,G
C,1
A,2
F,3
H,4
E,5
B,6
D,7
(Those locations are col, row format).
From that I "derived" that doing mirror images of the board, horizontally, vertically, and diagonally (sp?), across each section, divided into a "cartesian" system would yield 12 solutions (which is what the professor told me were the number of "unique" solutions).
However, the questions I never asked, and never thought about was the "uniqueness" of the solution. By using mirror techniques as I suggested, would actually yield a total of (and I am guessing here, as was my professor), 90 some solutions, not 12 unique solutions.
So, question is, outside of sitting down with a chess board and attempting this, how do I think about the problem recursively, so that in the end I develop 12 unique solutions, that do not involve any reflections of any previous solution?
Thanks for any insight!
Shawn
PS - Another choice he gave me to help me along, was to take a knight and start anywhere on the board, but make that knight visit all 64 squares on the board. I never attempted that solution, but if anyone knows, that would help me too. Condition on that solution is to never visit a square you have previously been in.
On an aside, this is not a classroom assignment, just something that was presented to me by my professor to try and solidify my recursion education. Therefore, post any code you wish, or pseudocode for that matter.
*Edit* - Maybe I should also add to this, that the solution that I came up with above, I decided to try to figure a pattern out with it. I do not know if that has some bearing on the solution, but, again using the cartesian system, and numbering from upper-right, counter-clockwise, I noticed this pattern:
Quad 1 - white white (meaning each queen was on a white square)
Quad 2 - white black
Quad 3 - black white
Quad 4 - black black
I should also add, my understanding of recursion I guess, to nullify any preconceived notions I have. Although I start at position 1 (in this case, the first queen), I cannot validate anything till I reach the position 8 (eighth queen). Is that a correct assumption, in other words, I ultimately have to reach a base "case" in order to complete a solution? I could probably word that better, but I know what I mean, lol.
The 8 queens problem is a classic.
To recursively find all the solutions, what you do is pick a location for first queen in the first column, then the second queen in the second and so on, until either you get a solution or fail. At that point you go back to the previous column and place the queen in another row. If you've already gone through all rows for that column, back to the previous column. The key is always to back up to previous column when you can't continue, either because you've found a solution, there's a conflict, or you've tried all rows for the current column.
How to eliminate the symmetric solutions, that's a bit trickier, but you can do that by eliminating some squares. Like if you try putting the first queen in A1, using H1 later would produce a symmetric solution, so you rule out H1 as a potential square.
To recursively find all the solutions, what you do is pick a location for first queen in the first column, then the second queen in the second and so on, until either you get a solution or fail. At that point you go back to the previous column and place the queen in another row. If you've already gone through all rows for that column, back to the previous column. The key is always to back up to previous column when you can't continue, either because you've found a solution, there's a conflict, or you've tried all rows for the current column.
How to eliminate the symmetric solutions, that's a bit trickier, but you can do that by eliminating some squares. Like if you try putting the first queen in A1, using H1 later would produce a symmetric solution, so you rule out H1 as a potential square.
There is necessarily exactly one queen on each row of the board.
The set of solutions consists of the set of solutions with a queen in the first column of the first row, plus the set with a queen in the second column of the first row, etc. to the eighth.
In general, the set of solutions where the first N rows are specified, is the set where the first N rows are as specified, and the N+1'th has the queen in the first column (if that is possible); plus the set where the first N rows are as specified, and the N+1'th has the queen in the second column, etc.
So, our recursive function accepts a specification of the first N rows (it needs to be able to infer what N is, too), checks if each column is possible for the N+1th row, and makes recursive calls for the valid columns when N < 8; when N == 8, it simply emits a solution (since we have specified all 8 rows and found no violations).
The set of solutions consists of the set of solutions with a queen in the first column of the first row, plus the set with a queen in the second column of the first row, etc. to the eighth.
In general, the set of solutions where the first N rows are specified, is the set where the first N rows are as specified, and the N+1'th has the queen in the first column (if that is possible); plus the set where the first N rows are as specified, and the N+1'th has the queen in the second column, etc.
So, our recursive function accepts a specification of the first N rows (it needs to be able to infer what N is, too), checks if each column is possible for the N+1th row, and makes recursive calls for the valid columns when N < 8; when N == 8, it simply emits a solution (since we have specified all 8 rows and found no violations).
Author
So, your A1-H1, as far as symmetry goes, once I use one square, are you saying I mark all symmetric squares as unavailable in that case? (horizontally, vertically, and diagonally)?
Author
Quote:Original post by Zahlman
There is necessarily exactly one queen on each row of the board.
The set of solutions consists of the set of solutions with a queen in the first column of the first row, plus the set with a queen in the second column of the first row, etc. to the eighth.
In general, the set of solutions where the first N rows are specified, is the set where the first N rows are as specified, and the N+1'th has the queen in the first column (if that is possible); plus the set where the first N rows are as specified, and the N+1'th has the queen in the second column, etc.
So, our recursive function accepts a specification of the first N rows (it needs to be able to infer what N is, too), checks if each column is possible for the N+1th row, and makes recursive calls for the valid columns when N < 8; when N == 8, it simply emits a solution (since we have specified all 8 rows and found no violations).
You sound like my professor, lol. I get lost with it too, lmao. Infer what N is, ummm. that would be 8 to start with, -1 for each row I place (or column since I think, though not sure, I can do it either way right? but use it consistently?)
Quote:Original post by shawnre
So, your A1-H1, as far as symmetry goes, once I use one square, are you saying I mark all symmetric squares as unavailable in that case? (horizontally, vertically, and diagonally)?
That would definitely work. However, it may be possible to identify all the squares that you can rule out beforehand. I'm not sure though.
Author
Umm...ok, I am actually trying to program this now....first question, is it wise to start in a corner, any corner and proceed from there? Obviously the first choice I make has alot of consequences, like where other pieces can be...maybe I am just not getting the recursion concept, I am stuck on the first piece, but, should it not be the last piece I should be worried about? What am I missing here?
Step 1: If you are out of queens, return success.
Step 2: Scan the board looking for a place to put the next queen and then recursively apply this algorithm. If the recursive application of the algorithm returns failure, continue scanning the board for places to put the queen. You run out of posible positions, return failure.
Step 2: Scan the board looking for a place to put the next queen and then recursively apply this algorithm. If the recursive application of the algorithm returns failure, continue scanning the board for places to put the queen. You run out of posible positions, return failure.
The idea is that you just pick some position for the first queen and then proceed to try to place the others and retry systematically if you fail.
So, what you do is you write a function that tries to place a queen on the column X, initially in the first row. If that's blocked by other queens already on the board, the function places it in the next row and so on, until the function manages to place the queen, or runs out of rows.
If the function succeeds in placing the queen, the function calls itself on the next column. Once that recursive call returns, the function still remembers what column it was working on and where it last placed the queen on that column. It then puts the queen on that column (X) into the next row again.
Once the function is out of rows, it returns. You start the program by calling the function on the first column A. So the first thing the program does, is placing the first queen into A1, then the recursive call tries B1, but fails and next goes for B2, fails again. Then B3, which is ok, because the other queen is in A1. Recurse again, and so on.
Because the queens placed on the board 'remember' their rows, you can try out the above on a real board manually first to get a hang of the idea, without needing pencil and paper. To speed things a bit if you do try this, you can pick only 4 queens and stick to the area under A1-D4, making the problem a bit smaller.
[Edit] Another way to tackle recursion is to think of it as making the problem smaller. What if you already had a function that can place 7 queens onto the board or tell you that it's not possible? Once you've figured out how to solve the problem with the help of such a function, you need to figure out where to get that function. Well, what if you then had a function that can place 6 queens?
[Edited by - SnotBob on May 8, 2008 1:43:18 AM]
So, what you do is you write a function that tries to place a queen on the column X, initially in the first row. If that's blocked by other queens already on the board, the function places it in the next row and so on, until the function manages to place the queen, or runs out of rows.
If the function succeeds in placing the queen, the function calls itself on the next column. Once that recursive call returns, the function still remembers what column it was working on and where it last placed the queen on that column. It then puts the queen on that column (X) into the next row again.
Once the function is out of rows, it returns. You start the program by calling the function on the first column A. So the first thing the program does, is placing the first queen into A1, then the recursive call tries B1, but fails and next goes for B2, fails again. Then B3, which is ok, because the other queen is in A1. Recurse again, and so on.
Because the queens placed on the board 'remember' their rows, you can try out the above on a real board manually first to get a hang of the idea, without needing pencil and paper. To speed things a bit if you do try this, you can pick only 4 queens and stick to the area under A1-D4, making the problem a bit smaller.
[Edit] Another way to tackle recursion is to think of it as making the problem smaller. What if you already had a function that can place 7 queens onto the board or tell you that it's not possible? Once you've figured out how to solve the problem with the help of such a function, you need to figure out where to get that function. Well, what if you then had a function that can place 6 queens?
[Edited by - SnotBob on May 8, 2008 1:43:18 AM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
