The eight queens problem
My program 8QUEENS.PRG included with SIM41.ZIP allows to find
all positions for eight queens over a chessboard where nothing queen
can capture another.
Example:
In order to describe each position I used a eight digits number where the
first digit is the position of the first queen within the first chessboard
column, the second digit is the position of the second queen within the
second column, and so on until the eight column.
The preceding position, for example, is 15863724.
The one in the first digit means that the queen of the first column is positioned
over the first row , the five in the second digit means that the queen of the
second column is positioned over the fifth row counting from up to down. The eight
in the third digit means that the third queen is positioned over the eight row,
and so on until the eight digit.
The program can begins the search from a partial initial position. For Example: 135
If you don't give this data , the program begins puting the first queen over the first upper
row of the first column. The other queens are out of the board at the beginning
and enter to the board from left to right, each queen searching in her assigned
column a row where can not capture to the preceding queens.
If is not possible to put a queen over a row in her assigned column, the queen does not
enter to the board and the program moves the queen in the preceding left column
to the following row down where the preceding queen will can not capture the other
queens at her left and again the program try to put a queen in the current column.
If it's successfull the program try to put a new queen in the following right
column. If the program reachs the eight column and achieves to put a queen in
that column , the position is shown on the calculator display.
Example: Search positions from partial initial position = 158
1) Execute sim41.exe
Calculator Keyboard PC Keyboard Display
------------------- ----------- -------
[XEQ]8QUEENS [K]8QUEENS[PC_ENTER_KEY] XEQ 8QUEENS
PUBLISH?
YES[R/S] YES[!] (Run in Alpha mode is !)
INITIAL POSITION?
158[R/S] 158[R] (Run in normal mode is R)
.....Wait a few seconds while the calculator searchs for the position.....
CODES:11432133
(My own codes for catalog the position's point of view.
I will explain it later)
[R/S] [R]
POSITION1=15863724
[R/S] [R]
ROTATION?
NO[R/S] NO[!]
(The position can be viewed from several view points if you answer YES.
I will explain it later)
...... Wait a few seconds while the calculator searchs for a new position ...
CODES:11432133
(The same point of view for a different position)
[R/S] [R]
POSITION2=16837425
[R/S] [R]
ROTATION?
NO[R/S] NO[!]
...... Wait a few seconds while the calculator searchs for a new position ...
CODES:11432133
[R/S] [R]
POSITION3=17468253
[R/S] [R]
ROTATION?
NO[R/S] NO[!]
...... Wait a few seconds while the calculator searchs for a new position ...
and so on.
Each position can be seen from four viewpoints: From the chessboard left side,
right side, from up side or from down side. I assume that the default side
for view and annotate the position is from downside.
For example, the position 15863724 can be viewed and annotated in the
following manner:
In the chessboard there are several simmetry axis:
You can use translations around the horizontal and vertical simmetry axis for
generate new positions from someone position. Also you can apply double translations:
first around the vertical axis and later around the horizontal axis.
The double translation first around the vertical axis and later around the horizontal
axis is equivalent to the double translation first around the horizontal axis
and later around the vertical axis.
Then, each chessboard position generates four positions depending the viewpoint,
other four positions if we make a translation around the horizontal axis, other
four positions if we make a translation around the vertical axis and other four
positions if we use a double translation.
Example: The initial position 15863724 generates the following positions:
Without rotations: 15863724, 36428571, 57263148, 82417536
With a rotation around the horizontal axis: 84136275, 17582463, 42736851, 63571428
With a rotation around the vertical axis: 42736851, 63571428, 84136275, 17582463
With double rotation around both axis: 57263148, 82417536, 15863724, 36428571
Note: I am assigning equal meaning to the words translation and rotation.
Theoretically each position generates sixteen positions but if you look at the
positions generated, each position is repeated two times. Then , each position
only produces eight positions: The original position and other seven
new positions.
One exception: There is one position with complete simmetry with reference to the
central point of the chessboard. This position only generates three new positions.
Try to find it using the program.
It's possible to find 92 different positions in a 8x8 chessboard
There
are 11 independent positions that generate seven new positions and one independent position
that generates only three new positions. (11*8+1*4 = 92 )
If you answer YES to the question ROTATION? in the program, the seven new positions associated with the current position are shown.
I assigned the code 11 to the original position viewed from downside, code 12 to the original position viewed from right side, code 13 to the original position viewed from up side and code 14 to the original position viewed from leftside.
The code 21 is the original position rotated around the horizontal axis and viewed from downside, 22 is the same position viewed from right side, 23 is the position viewed from upside and 24 means viewed from left side.
Code 31 means the original position rotated around the vertical axis and viewed from downside, codes 32, 33 and 34 mean this position viewed from leftside, upside and rightside respectively.
Codes 41, 42 , 43 and 44 mean the original position rotated around both axis and viewed from downside, leftside, upside and rightside respectively.
If you wish to find all positions it's enough that the queen in the first column will be put in the range from file 1 to file 4 because the positions obtained with the first queen in files 5 to 8 can be reached with a rotation around the horizontal axis.
The 8QUEENS program obtained 46 positions with the first queen varying from file 1 to file 4.
I named the "Associated position" to the position generated by rotating the original obtained position around the horizontal axis. The 8QUEENS program shows codes as four pairs of two digits numbers. The first two pairs correspond to two viewpoints in the original position and the last two pairs correspond to two viewpoints in the associated position.
Example: For the position: 15863724, CODES=11432133 mean that the original position can be viewed from viewpoint 11 and viewpoint 43 and the associated position 84136275 generates 15863724 from viewpoint 21 and viewpoint 33.
Get your own Free Home Page