Use the stack structure in C to implement the Eight Queens problem

Concerning.

data[top]==data[i] to determine whether it is in the same column.

abs(data[top]-data[i]))==(top-i) determines whether it is diagonal or not.

I think i 0 7 can be understood as the 0 7 lines (of 8 lines) from top to bottom.

data[i], which stores the position of the queen, is not the same as data[i]!

That is to say, when the data is full of 8 numbers, it is a successful pendulum, for example, see the 'first pendulum' below:

In this case, the number in the data is , and only the position of the queen in each row is recorded.

In this way, the position of the queen can be represented like this :(row i, column data[i]) and the coordinate point is in the upper left corner.

Looking at the top again, the mechanism of this algorithm is that when judging a position, it will press into this position (use it as top), and then compare the position with the queens who exist itself.

When data[top]=data[i], the column of the queen to be judged is the same as the previous queen, so this judgment returns false

Then judging the diagonal, the solution to this problem is very simple, comparing the two positions of (top,data[top]),i,data[i]).

i.e. (row top, column data[top]) and (row i, column data[i]) compare positions.

top-i represents: how many rows differ between these two positions, and data[top]-data[i]) represents: how many columns differ between these two positions (possibly negative).

The abs() function takes the absolute value.

abs(data[top]-data[i]) == (top-i)

If the number of rows apart and the number of columns apart, then these two positions are on the diagonal, don't believe you draw you.

Under verbose conditions, it is generally judged like this (no matter which angle the coordinate point is in, the following takes the mathematical coordinate axis as an example):

For one point p1(x1,y1) and p2(x2,y2).

If x1+x2 = x2+y2, it means a collision along a diagonal (top left to bottom right).

If x1-y2 = x2-y2, it means a collision along the opposing diagonal (top right to bottom left).

After watching it for a long time, I think your algorithm is very good, and I learned it.

if(data[top]==data[i]||abs(data[top]-data[i]))==(top-i))

It is to determine whether the queen placed in the current row is on the same vertical line or diagonal as the queen of the previous row.

The data array stores the following: data[i] means that the queen of row i is placed on column data[i].

In addition, spray me on the top of the drop 2 goods, this method is very good, with recursion is a rookie approach, write programs to focus on efficiency.

He said that if you use a stack, you really use a stack??

#include

#include

int judge(int *p, int j) to determine whether the current position of the piece is in accordance with the rules, if it is a good order, it returns 1, otherwise it slides back to 0;

int i;

for(i=0;iif(p[j]==p[i]) return 0;

if(abs(p[j]-p[i])=j-i) return 0;

return 1;

int main()

int a[8];a[i] indicates the position after row i (a[3]=0 means that the queen in row 3 is in column 0).

int i=0,j=0,k=0;

for(a[0]=0;a[0]<8;j=0,a[j]++for(a[++j]=0;a[j]<8;j=1,a[j]++if(judge(a,j))

for(a[++j]=0;a[j]<8;j=2,a[j]++if(judge(a,j))

for(a[++j]=0;a[j]<8;j=3,a[j]++if(judge(a,j))

for(a[++j]=0;a[j]<8;j=4,a[j]++if(judge(a,j))

for(a[++j]=0;a[j]<8;j=5,a[j]++if(judge(a,j))

for(a[++j]=0;a[j]<8;j=6,a[j]++if(judge(a,j))

for(a[++j]=0;a[j]<8;a[j]++if(judge(a,j))

for(i=0;i. "Quarrel 8; i++)printf("%d",a[i]);

printf("%3s","

if(!(k%7)) printf("");

printf("There are a total of %d solutions",k);

return 0;

Downstairs** is a bit of a problem.,That's the case.,Just tested and debugged through it, if there is still a problem, I 523117894 it.

#include

enum boolean ;

enum boolean a[9] ,b[17] ,c[17] ;Check if there is a conflict between the queens.

int s[9];

void main()

elsefor(i=1;i<=8;i++)

printf("");}

** As follows, there is a problem hi me.

#include

enumboolean;

enumbooleana[9],b[17],c[17];Check if there is a conflict between the queens.

ints[9];

voidmain()

elsefor(i=1;i<=8;i++)

printf("");}

This topic uses a recursive approach, like the one upstairs.

Here are the 8 queen programs:

#include

#include

void eightqueen(int a[99],int n);

void print(int a[99]);

int up(int a[99],int row,int col);

int down(int a[99],int row,int col);

int left(int a[99],int row,int col);

int right(int a[99],int row,int col);

int num=0;

main()

n;Place the queen's position in a two-dimensional array, a[i][j]=1 means that there is a queen at that position.

eightqueen(a,0);

system("pause");

return 0;

void print(int a[99]) outputs a reasonable way to do so.

printf("");

printf("");

void eightqueen(int a[99],int row) calculates the move of 8 queens by backtracking.

elsea[row][col]=0;}}

Determine if there are other queens in the same ranks.

int up(int a[99],int row,int col)

return 0;

Determine if there are other queens on the same line.

int down(int a[99],int row,int col)

return 0;

Determine if there are other queens on the docking line from top left to bottom right.

int left(int a[99],int row,int col)

if(((row-i)>=0)&&col-i)>=0))}

return 0;

Determine if there are other queens on the docking line from bottom left to top right.

int right(int a[99],int row,int col)

if(((row-i)>=0)&&col+i)<8)) There's something wrong with the judgment here, }

return 0;}

The method is given below, I don't know if it complies with it.

Method: Backtracking method.

After thinking about it, it is not difficult to find that there happens to be a queen in each row and column. If c[x] is used to denote the column number of the queen in line x, the rook problem becomes a full permutation generation problem. 0-7 full row has eight factorial = 40320 enumeration no more than it.

Write a recursive enumeration program (the recursive process already uses the stack).

When the main program reads n, tot is the number (cleared) and search(0) is called

void search(int cur)

if(ok) search(cur+1);Legitimate, continue recursively}}

Check the conflict mainly because the queen is horizontal, vertical, and oblique can not be opposed, you can figure it out yourself, and tot is a global variable.

Here is just to find out how many ways to place, and there is no set to print**, you can figure it out yourself.

(1) Full arrangement.

The natural number 1 n is arranged to form n!The medium arrangement is called the full arrangement.

For example, the full permutation of 3 is 2 1 of 3!= 6 kinds.

2) 8 queens (or n queens).

Ensure that the 8 queens cannot attack each other, that is, ensure that each horizontal row, each vertical row, and each diagonal row can have a maximum of one queen.

Let's put aside the third condition, if there is only one queen for every horizontal row and every vertical row.

Mark the 8*8 board with coordinates. Let's discuss one of these solutions:

q - q -

q - q -

q - q - q -

q - If expressed in coordinates, it is: (1,8) (2,4) (3,1) (4,3) (5,6) (6,2) (7,7) (8,5).

Arrange the abscissa in order, and the ordinate is 8 4 1 3 6 2 7 5. That's a full permutation of 1 8.

We put the full permutation of 1 8 into input a(a[0] a[7]), and then the coordinates of the 8 queens are (i+1,a[i]), where i is 0 7.

This will ensure that any two will not be on the same row or column.

Placed in a diagonal line, you know, the absolute value of the slope of the line between two points is 1 or -1, which is the same oblique line, and the sufficient condition is |x1-x2|=|y1-y2|(The coordinates of the two points are (x1,y1)(x2,y2)). We make a judgment when outputting it, and if any two points meet the above equation, it will be judged as a failure and will not be output.

Attached below: Add the necessary comments, where the fully arranged implementation should be understandable by looking at the comments:

#include

#include

#include

#include

int printed;

This function is used for drawing and is omitted here to save space.

The reader only needs to add draw(a,k); Remove the annotations to draw a picture.

void draw(int* a,int k)

int i,j;

for(i=0;i

#include

#include

#define max 8

int queen[max],sum=0;

void show()

printf(")");

sum;int place(int n) prevents max queens from being in the same column and on the same diagonal.

return 1;

void nqueens(int n)

else}}

int main(void)