1 #include <stdio.h>
  2 #include <math.h>
  3 #include <stdlib.h>
  4 
  5 #define TRUE 1
  6 #define FALSE 0
  7 
  8 struct _position{
  9     int x;
 10     int y;
 11 };
 12 
 13 typedef struct _position position;
 14 
 15 #define MAX_SIZE 100
 16 position pos[MAX_SIZE];
 17 int stack_index = 0;
 18 
 19 int isEmpty(){
 20     if(stack_index == 0){
 21         return TRUE;
 22     }else{
 23         return FALSE;
 24     }
 25 }
 26 
 27 void push(position p){
 28     if(stack_index < MAX_SIZE){
 29         pos[stack_index++] = p;
 30     }else{
 31         printf("stack is full");
 32     }
 33 }
 34 
 35 position pop(){
 36     if(isEmpty()){
 37         printf("stack is empty");
 38         position p = {-1, -1};
 39         return p;
 40     }else{
 41         return pos[--stack_index];
 42     }
 43 }
 44 
 45 position getTop(){
 46     if(!isEmpty()){
 47         return pos[stack_index-1];
 48     }else{
 49         printf("stack is empty");
 50         position p = {-1, -1};
 51         return p;
 52     }
 53 }
 54 
 55 
 56 #define QUEEN_SIZE 8
 57 void printQueen();
 58 
 59 int condition(position p){
 60     int i;
 61     for(i=0; i<stack_index; i++){
 62         int incline = abs(p.y-pos[i].y);
 63         int inclinetemp = abs(p.x-pos[i].x);
 64         if(inclinetemp==incline || pos[i].y==p.y){
 65             return FALSE;
 66         }
 67     }
 68     return TRUE;
 69 }
 70 
 71 int pushed = FALSE;
 72 void arrangeQueen(){
 73     int i;
 74     int j = 0;
 75     for(i=0; i>=0 && i<QUEEN_SIZE; ){
 76         for(; j<QUEEN_SIZE; j++){
 77             position node;
 78             node.x = i;
 79             node.y = j;
 80             if(condition(node)){
 81                 push(node);
 82                 pushed = TRUE;
 83                 break;
 84             }
 85         }    
 86         if(j == QUEEN_SIZE && !pushed){
 87             position p = pop();
 88             i = p.x;
 89             j = p.y+1;
 90         }else{
 91             j = 0;
 92             i++;
 93             pushed = FALSE;
 94         }    
 95         
 96         //printQueen();
 97     }
 98 }
 99 
100 
101 int queenrule(int x, int y){
102     int i;
103     for(i=0; i<stack_index; i++){
104         int incline = abs(y-pos[i].y);
105         int inclinetemp = abs(x-pos[i].x);
106         if(inclinetemp==incline || pos[i].y==y){
107             return FALSE;
108         }
109     }
110     return TRUE;
111 }
112 
113 int nextX = 0;
114 int nextY = 0;
115 int hasNext(position p, int start){
116     if (p.x==-1 && p.y==-1) {
117         return FALSE;
118     }
119     if(p.x+1 >= QUEEN_SIZE){
120         return FALSE;
121     }else{
122         int j=start;
123         for(;j<QUEEN_SIZE; j++){
124             if(queenrule(p.x+1, j)){
125                 nextY = j;
126                 nextX = p.x+1;
127                 return TRUE;
128             }
129         }
130         return FALSE;
131     }
132 }
133 
134 int count = 0;
135 void makeQueen(){
136     position header = {0, 0};
137     push(header);
138     
139     int j = 0;
140     int next;
141     while((next=hasNext(getTop(), j))||!isEmpty()){
142         if(next){
143             position p = {nextX, nextY};
144             push(p);
145             j = 0;
146         }else{
147             j = pop().y+1;
148             if(isEmpty()){
149                 if(j<QUEEN_SIZE){
150                     header.x = 0;
151                     header.y = j;
152                     push(header);
153                     j = 0;
154                 }else{
155                     return;
156                 }
157             }
158         }
159         
160         if(stack_index == QUEEN_SIZE){
161             printQueen();
162             count++;
163         }
164     }
165 }
166 
167 void printQueen(){
168     int i,j;
169     for(i=0; i<QUEEN_SIZE; i++){
170         for(j=0; j<QUEEN_SIZE; j++){
171             if(pos[i].y == j && i<stack_index){
172                 printf("Q ");
173             }else{
174                 printf("1 ");
175             }
176         }
177         printf("\n");
178     }
179     printf("\n\n");
180 }
181 
182 int main(void){
183     /*
184      //第一種做法
185      arrangeQueen();
186      printQueen();
187      */
188     
189     makeQueen();
190     
191     printf("共有%d種解\n",count);
192     return 0;
193 }