Today, let's write something simple - solving the 8 Queens problem in C language. I believe friends who have learned C language must be familiar with this classic problem. There are multiple solutions, mainly backtracking and recursion. Today, we will discuss the backtracking + recursion method, which may not be very efficient but is easy to understand.
Problem: Can we place 8 queens on a standard chessboard in such a way that they cannot attack each other? Specifically, on an 8x8 chessboard, queens can move in all directions. To prevent them from attacking each other, they must not be on the same line.
Specific solution: Start placing chess pieces from the position of the first row and the first column (assuming column priority), then record the numbers of the rows and diagonals occupied by the chess pieces. Then place the second chess piece, choosing a valid position while excluding the numbers occupied by all previous chess pieces. Continue this process until all 8 chess pieces are placed.
The code is as follows:
/*
* Eight Queens Algorithm Problem
* author CG
* 2008 12 22
*/
#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
#define N 8 /* Set the number of queens to 8 */
int a[N], b[2*N + 1], c[2*N +1];/* Three arrays record the queens in each direction */
int count = 0;/* Counter */
int Queen(int row) {
int col; /* Local variable */
for (col = 1 ; col < = N ; col++){
if (a[col - 1] + b[row + col - 2] + c[row - col + N - 1] == 0) {
/*
* This part is very important, used to determine whether the queen's position meets the conditions.
* Only when there are no queens on all straight lines can it meet the conditions.
* a[col-1] records whether there is a queen in column col, 1 means yes.
* b[row+col-2] records whether there is a queen on the line with slope 1, counting from the top left.
* c[row-col+N-1] records whether there is a queen on the line with slope -1, counting from the top right.
*/
a[col - 1] = 1; /* Change the data */
b[row + col - 2] = 1;
c[row - col + N - 1] = 1;
gotoxy(col \* 2 , row);/\* Draw the queen \*/
putch('Q');
if (row < N){/\* If not all rows have been traversed \*/
Queen(row + 1); /\* Continue \*/
}
else {/\* Recursive end \*/
count++; /\* Counter +1 \*/
gotoxy(1 , N + 2);
printf("Solution No %d ", count);
getch();
}
a\[col - 1\] = 0; /\* Clear the data \*/
b\[row + col - 2\] = 0;
c\[row - col + N-1\] = 0;
gotoxy(col \* 2 , row); /\* Clear the image \*/
putch('.');
}/\*if \*/
}/*for */
return 0;
}/*Queen */
int main()
{
int i, j;
clrscr();/*Clear the screen*/
for(i = 1 ; i <= N ; i++){/* Draw the chessboard */
for(j = 1 ; j <= N ; j++){
gotoxy(i * 2 , j);/* Pay attention to the character spacing, uppercase Q and dot take up two character spaces */
putch('.');
}/*for*/
}/*for*/
Queen(1); /* Start the backtracking algorithm */
gotoxy(1 , N + 3); /* Display the final result */
printf("%d Solution(s)n", count);
system("pause");
}/*main*/