正好练习题有个八皇后，顺便就做了一下，第一种算法只考虑到求一种解，并且思路不是很清晰，用双重循环很难来做求全部解，所以第二种解法就换了一种思路，欢迎拍砖。递归本质上和栈是一致的，不过面对稍微复杂的逻辑，用递归并不是很好写。
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 }