Homework #6 Searching in Wonderland Solution



In Wonderland, there are n n chessboards. For each such chessboard there are n queens each of whom sits proudly on her square so that when she looks down her row, her column, or her diagonals she can see no other queen. Alice’s assignment was to nd out how many such boards of each size there were in all of Wonderland. While she was searching for the chessboards, Alice met the White Knight who told her that there was no need to roam about because he had discovered that no two boards were rotations or re ections of one another, and except for these restrictions and the restrictions on the placement of the queens, all possible boards with n < 10 existed in Wonderland, and since there were only a nite number of such boards, he was able to calculate the number of chessboards in Wonderland. Unfortunately he had misplaced his calculations while attending a tea party.

Your assignment is to write a computer program which carries out the Knight’s calculations and nds all of the nonisomorphic legal placements of n queens on an n n chessboard. You will run your program for n = 1 through 9, report one member of each isomorphism class, and discover the total number of chessboards in Wonderland.

error: Content is protected !!