Gauss thinks there are 76 schemes. In 1854, different authors published 40 different solutions in chess magazines in Berlin, and then calculated 92 results by graph theory.
For the realization of the eight queens problem, if combined with dynamic graphic demonstration, the description of the algorithm can be more vivid and the teaching can produce good results. The following is the graphic program of the Eight Queens problem realized by the author with Turbo C, which can demonstrate all 92 solutions. The realization of dynamic graphics of the Eight Empresses problem should mainly solve the following two problems.
Implementation of (1) backtracking algorithm
(1) In order to solve this problem, we set the abscissa of the chessboard as I and the ordinate as J, and the range of values of I and J is 1 to 8. When a queen occupies position (I, J), other queens cannot be placed in the vertical direction, horizontal direction and diagonal direction of the position. Using the statement, three integer arrays can be defined as follows: A [8], B [15] and C [24]. These include:
A [j-1] =1There is no queen on the column.
A [j-1] = There is a queen on the column of 0J.
B[i+j-2]= 1 (i, J) There is no queen on the diagonal (upper left to lower right).
B[i+j-2]=0 (i, J) There is a queen on the diagonal (upper left to lower right).
There is no queen on the diagonal (top right to bottom left) of c[i-j+7]= 1 (i, j).
C[i-j+7]=0 (i, J) There is a queen on the diagonal (top right to bottom left).
(b) The algorithm for selecting the location for the i-th queen is as follows:
for(j = 1； j & lt=8; J++) /* The I-th queen is in line J */
If ((i, j) position is empty))/* That is, the corresponding element values of the three arrays are 1*/
{occupated position(I, j) /* Sets the corresponding element values of three arrays to 0*/
If I'm < eight
Choose a suitable location for i+ 1 queen;
Otherwise output a solution.
}
(2) Graphic access
In Turbo C, access to graphics can be achieved by the following standard functions:
size=imagesize(x 1，y 1，x2，y2)； Returns the number of bytes required for the storage area.
Arrow=malloc (size); Creates a dynamic area bitmap of the specified size and sets the pointer arrow.
getimage(x 1，y 1，x2，y2，arrow)； Stores the bitmap of the specified area in the buffer.
Putimage(x, y, arrow, copy) uses (x, y) to place the bitmap in the upper left corner of the screen.
(3) The program list is as follows
# include & ltgraphics.h & gt
# include & ltstdlib.h & gt
# include & ltstdio.h & gt
# include & ltdos.h & gt
char n[3]={'0 '，' 0 ' }； /* Used to record which set of solutions */
int a[8]，b[ 15]，c[24]，I；
int h[8]={ 127， 177，227，277，327，377，427，477 }； /* Row coordinates of each queen */
int l[8]= { 2522 17 182 147 1 127742，7 }； /* Column coordinates of each queen */
Void * arrow;
void try(int i)
{ int j；
for(j = 1； j & lt=8; j++)
If (a [j-1]+b [I+j-2]+c [I-j+7] = = 3)/* If the j row of column I is empty */
{ a[j- 1]= 0； b[I+j-2]= 0； c[I-j+7]= 0； /* occupy column I and row J */
putimage(h[i- 1]，l[j- 1]，arrow，COPY _ PUT)； /* Show Queen's pattern */
Delay (500); /* Delay */
If (I<8) try (I+1);
Else /* output a set of solutions */
{ n[ 1]++； if (n[ 1]>9 '){ n[0]++； n[ 1]= ' 0 '； }
Bar (260,300,390,340); /* Display the nth solution */
outtextxy(275，300，n)；
Delay (3000);
}
a[j- 1]= 1； b[I+j-2]= 1； c[I-j+7]= 1；
putimage(h[i- 1]，l[j- 1]，arrow，XOR _ PUT)； /* Eliminate the queen and continue to find the next set of solutions */
Delay (500);
}}
int main(void)
{int gdrive=DETECT，gmode，errorcode。
Unsigned int size;
init graph(& amp； g drive & amp； gmode，“”；
error code = graph result()；
if (errorcode！ =grOk)
{printf ("Graphic error \ n"); Exit (1); }
Rectangular (50,5,100,40);
Rectangular (60, 25, 90, 33);
/* Draw a crown */
Lines (60, 28, 90, 28); Line (60, 25, 55,15);
Line (55, 15, 68, 25); Line (68, 25, 68,10);
Line (68, 10, 75, 25); Line (75, 25, 82,10);
Line (82, 10, 82, 25); Line (82, 25, 95,15);
Line (95, 15, 90, 25);
size=imagesize(52，7，98，38)； Arrow=malloc (size);
Getimage(52, 7, 98, 38, arrow); /* Save crown to buffer */
clear viewport()；
settextstyle(TRIPLEX_FONT，HORIZ_DIR，4)；
setusercharsize(3， 1， 1， 1)；
setfillstyle( 1，4)；
for(I = 0； I < = 7; i++)a[I]= 1；
for(I = 0； I<= 14; i++)b[I]= 1；
for(I = 0； I < = 23; i++)c[I]= 1；
for(I = 0； I < = 8; I++) line (125, i*35+5,525, I * 35+5); /* Draw a chessboard */
for(I = 0； I < = 8; I++) line (125+I * 50,5,125+I * 50,285);
Try (1); /* Call recursive function */
Delay (3000);
closegraph()；
Freedom (arrow);
}