Positioning queens on a chess board is one of the classic problems in mathematics and computer science. This long-standing problem goes back even before Carl Gauss (1777-1855), and is based on the chessboard. It is the problem of finding all of the ways to position eight queens on the chessboard so that none of them is under attack by any other. Remember, the queen can move horizontally, vertically, and in the two diagonal directions; for convenience I'll call the direction down and to the right (and its reverse) the diagonal direction, then call the direction up and to the right the antidiagonal direction.
You could approach this problem by looking at all possible ways of placing eight queens in the 64 available cells—and there are 64!/56! ways to do that (the permutations of 64 things taken eight at a time), but you don't have to look at all 1.78E+14 permutations. (If you could figure out a way of just generating the combinations of 64 things taken eight at a time, the number goes down to 4.43E+09.) You can use some natural intelligence because you know that the queens can attack horizontally. That means that you can only have one queen to a row. Because there are eight positions on each of the eight rows, the total candidate configurations is reduced to 88—1.68E+07—a nasty number but not nearly as nasty as the earlier one. You can, however, toss out massive numbers of these.
As a programming exercise, this is a classical problem solved by backtracking. You start by positioning a queen in the top row of the board. As she sits in her cell, you move to the next row and try positioning a queen there. If you find that a queen above is attacking the queen below, you don't have to proceed any farther: All board configurations that include this start will be illegal. So you simply position that queen on the next available cell. You back up to the earlier row when you have finished positioning a queen on all available cells of the current row and try the next cell in that row for its queen.
Eight queens is a bit challenging to start with, so you can rephrase this as the N Queens problem: Positioning N queens on a grid made up of N rows of N squares to the row. We know that there is no solution for the two-queens problem. Necessarily, each queen is attacking the other either vertically or diagonally. If you play around with paper and pencil, you'll see that there is no possible solution for the three-queens problem either—there is necessarily a diagonal attack. So the four-queens problem is the first one that has a solution. For pseudocode purposes I'm going to use the C and Java conventions of numbering rows from zero on up. This means that when you hit N, you've already positioned N queens.
Read full article from Optimal Queens | Dr Dobb's
No comments:
Post a Comment