Math Newsletter number 24; Wednesday, January 5, 2011.
If you send any part of this newsletter to a friend, please
also include this paragraph. To subscribe or unsubscribe,
send a personal email request to kermit@polaris.net
Archive is at
http://www.kermitrose.com/math/NewsLetter/LetterList.html
Eight Queens Problem.
Put eight queens on the chessboard so that no two queens may
attack each other.
This is equivalent to making a permutation of the digits
12345678 such that:
no two digits that have adjacent positions, have themselves,
a difference of 1;
no two digits that have positions differ by 2, have
themselves, a difference of 2;
no two digits that have position differ by 3, have
themselves, a difference of 3;
no two digits that have position differ by 4, have
themselves, a difference of 4;
no two digits that have position differ by 5, have
themselves, a difference of 5;
no two digits that have position differ by 6, have
themselves, a difference of 6;
no two digits that have position differ by 7, have
themselves, a difference of 7.
There are 92 solutions.
One of the two solutions is symmetric with respect to
rotation and reflections of the chessboard.
The symmetric solution is 35281746.
Put the first queen in row 3 of column 1.
Put the second queen in row 5 of column 2.
Put the third queen in row 2 of column 3.
Put the fourth queen in row 8 of column 4.
Put the fifth queen in row 1 of column 5.
Put the sixth queen in row 7 of column 6.
Put the seventh queen in row 4 of column 7.
Put the eighth queen in row 6 of column 8.
Rotating the board clockwise 90 degrees,
will result in seeing the solution,
46827135.
That is, new column 1 has a queen in row 4;
new column 2 has a queen in row 6,
new column 3 has a queen in row 1, etc.
Rotating the board clockwise again 90 degrees,
results in the solution
35281746, the same as the original, since this is
the symmetric solution.
Rotating the board clockwise again 90 degrees,
results in the solution,
46827135, which is the same as the rotation of
the original by 90 degrees.
To get the other two relatives of the symmetric
solution, reflect from either the front of the chessboard
or the back of the chessboard.
This is equivalent to subtracting each digit from 9.
The Four relatives of the symmetric solution:
35281746
64718253
53172864
46827135
The other 88 solutions are related to each other in similar
ways.
The 88 solutions fall into 11 sets of 8 solutions related by
rotation and reflections.
When given this puzzle decades ago, I first found the
symmetric solution. Later I systematically found the other
88.
My systematic method consists of scaning the permutations of
12345678, in numerical order, and skipping over the
permutations that do not corresponds to solutions.
The smallest permutation found to be solution is:
15863724.
The 8 relatives for this permutation are:
15863724
84136275 by subtracting from 9.
57263148 by reversing digits.
42736851 by subtracting from 9.
82417536 by transposing, equivalent to rotation and
reflection.
17582463 by subtracting from 9.
36428571 by reversing digits.
63571428 by subtracting from 9.
Transposing of 42736851 means:
The 1 is in position 8,
the 2 is in position 2,
the 3 is in position 4,
the 4 is in position 1,
the 5 is in position 7,
the 6 is in position 5,
the 7 is in position 3,
the 8 is in position 6,
yielding 82417536.
We have found 4+8=12 of the 92 solutions.
Transform 15863724 by moving the 4 from the end to the
beginning.
This yields 41586372.
This gives 8 more solutions as
41586372
58413627 by subtracting from 9.
72631485 by reversing digits.
27368514 by subtracting from 9.
71386425 by transposing, = rotation and reflection.
28613574 by subtracting from 9.
47531682 by reversing digits.
52468317 by subtracting from 9.
We have found 12+8 = 20 of the 92 solutions.
Transform 82417536 by moving the 6 from the end to the
beginning.
This yields 68241753.
Note that this permutation is not any of the 8 associated
with the 41586372, the first result of the end round
transformation.
From 68241753 we have 8 associations.
68241753
31758246 by subtracting from 9.
64285713 by reversing digits.
35714286 by subtracting from 9.
53847162 by transposing.
46152837 by subtracting from 9.
73825164 by reversing digits.
26174835 by subtracting from 9.
We have found 20+8 = 28 of the 92 solutions.
Transform the 68241753 by moving the 3 from the end to the
beginning.
This yields 36824175.
Note that this permutation is not any previously found.
36824175
63175824 by subtracting from 9.
42857136 by reversing digits.
57142863 by subtracting from 9.
35841726 by transposing.
64158273 by subtracting from 9.
37285146 by reversing digits.
62714853 by subtracting from 9.
We have found 28+8 = 36 of the 92 solutions.
Transform 64158273 by moving the 6 from the beginning to the
end, yielding 41582736.
41582736
58417263 by subtracting from 9.
36271485 by reversing digits.
63728514 by subtracting from 9.
74286135 by transposing.
25713864 by subtracting from 9.
46831752 by reversing digits.
53168247 by subtracting from 9.
We have found 44 of the 92 solutions.
Transform 74286135 by moving the 7 from beginning to end,
yielding 42861357.
42861357
57138642 by subtracting from 9.
24683175 by reversing digits.
75316824 by subtracting from 9.
47382516 by transposing.
52617483 by subtracting from 9.
38471625 by reversing digits.
61528374 by subtracting from 9.
We have found 52 of the 92 solutions.
We seem to have exhausted the finding of new solutions by
moving a digit from one end of the permutation to the other.
Transform the previously found solution 15863724
to 51863724 by reversing the first two digits.
It is a solution.
51863724
48136275 by subtracting from 9.
57263184 by reversing digits.
42736815 by subtracting from 9.
72418536 by transposing.
27581463 by subtracting from 9.
36418572 by reversing digits.
63581427 by subtracting from 9.
We have found 60 of the 92 solutions.
Originally I found the 92 solutions in one afternoon by using
the chessboard to scan a subset of the 8!=40320 permutations
to check if they were solutions. I used the backtracking
shortcut to skip over permutations which had subsections that
were not solutions.
The web page
http://en.wikipedia.org/wiki/Eight_queens_puzzle
gives all the solutions and discusses short cuts to finding
the solutions.
Representatives of the 12 sets of solutions,
11 sets of 8, and 1 set of 4, are
1 24683175
2 17468253
3 17582463
4 41582736
5 51842736
6 31758246
7 51468273
8 71386425
9 51863724
10 57142863
11 63184275
12 53172864