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

Note that the last one shown is the symmetric solution, recognized by the reversal of digits is the same as subtracting from 9.