N皇后问题求解


//N皇后问题求解(此处为8皇后)

  1#include <iostream>
  2#include <cstdio>
  3#include <ctime>
  4#include <cmath> 
  5
  6using namespace std; 
  7
  8void queen(int** array, int row, FILE* fp);
  9bool isAvailable(int** array, int y, int x);
 10bool isResult(int** array); 
 11
 12int main(int arg, char** argv) {
 13        int** array;
 14        
 15        // 分配空间
 16        array = new int*[8];
 17        for (int i = 0; i < 8; i++) {
 18                array[i] = new int[8];
 19        }
 20        
 21        // 初始化皇后状态
 22        for (int i = 0; i < 8; i++) {
 23                for (int j = 0; j < 8; j++) {
 24                        array[i][j] = 0;
 25                }
 26        }
 27        
 28        FILE* fp = fopen("data.txt", "w");
 29        queen(array, 0, fp);
 30        fclose(fp);
 31        
 32        // 释放空间
 33        for (int i = 0; i < 8; i++) {
 34                delete[] array[i];
 35        }
 36        delete []array;
 37        array = NULL; 
 38
 39        return 0;
 40} 
 41
 42void queen(int** array, int row, FILE* fp) {
 43        static int size = 1;
 44        if (row > 7) {
 45                return;
 46        }
 47        for (int j = 0; j < 8; j++) {
 48                // 如果合法
 49                if (isAvailable(array, row, j)) {
 50                        array[row][j] = 1;
 51                        
 52                        // 当前位置合法，赋值后，进入下一行
 53                        queen(array, row + 1, fp); 
 54
 55                        // 如果退回来后是结果，则打印出来
 56                        if (isResult(array)) {
 57                                // 把结果写入文件
 58                                fputc('\n', fp);
 59                                fputs("***********************************", fp);
 60                                fprintf(fp, " %d ", size++);
 61                                fputs("***********************************", fp);
 62                                fputc('\n', fp);
 63                                for (int m = 0; m < 8; m++) {
 64                                        for (int n = 0; n < 8; n++) {
 65                                                if (array[m][n] == 1) {
 66                                                        fputc('#', fp);
 67                                                        fputc(' ', fp);
 68                                                        fputc(' ', fp);
 69                                                } else {
 70                                                        fputc('O', fp);
 71                                                        fputc(' ', fp);
 72                                                        fputc(' ', fp);
 73                                                }
 74                                        }
 75                                        fputc('\n', fp); 
 76                                } 
 77
 78                        }
 79                        array[row][j] = 0; 
 80
 81                }
 82        }
 83} 
 84
 85bool isAvailable(int** array, int row, int column) { // 第row行，column列
 86        int i, j; 
 87
 88        // 检查row行
 89        for (i = 0; i < 8; i++) {
 90                if (array[row][i] != 0) {
 91                        return false;
 92                }
 93        } 
 94
 95        // 检columnx列
 96        for (j = 0; j < 8; j++) {
 97                if (array[j][column] != 0) {
 98                        return false;
 99                }
100        } 
101
102        // 检查对角向左上
103        i = row;
104        j = column;
105        while (i >= 0 && j >= 0) {
106                if (array[i][j] != 0) {
107                        return false;
108                }
109                i--;
110                j--;
111        } 
112
113        // 检查对角向右上
114        i = row;
115        j = column;
116        while (i >= 0 && j < 8) {
117                if (array[i][j] != 0) {
118                        return false;
119                }
120                i--;
121                j++;
122        } 
123
124        // 检查对角向左下
125        i = row;
126        j = column;
127        while (i < 8 && j >= 0) {
128                if (array[i][j] != 0) {
129                        return false;
130                }
131                i++;
132                j--;
133        } 
134
135        // 检查对角向右下
136        i = row;
137        j = column;
138        while (i < 8 && j < 8) {
139                if (array[i][j] != 0) {
140                        return false;
141                }
142                i++;
143                j++;
144        } 
145
146        return true;
147} 
148
149bool isResult(int** array) {
150        int size = 0; // 皇后个数 
151
152        // 统计皇后个数
153        for (int i = 0; i < 8; i++) {
154                for (int j = 0; j < 8; j++) {
155                        if (array[i][j] != 0) {
156                                size++;
157                        }
158                }
159        } 
160
161        // 没有８个皇后，说明不是结果 
162
163       // 有8个皇后,因为每个皇后的放置都是在合法位置, 所以只需要简单的计算皇后个数就知道是不是结果.
164        if (size != 8) {
165                return false;
166        } 
167
168        return true;
169}
170

上面代码为大致思路，不一定能能通过编译

posted on 2009-04-01 23:17 弹杯一笑 阅读(393) 评论(0)  编辑 收藏 引用 所属分类: c++笔记


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年3月>
日一二三四五六
22232425262728
1234567
891011121314
15161718192021
22232425262728
2930311234

导航

统计

常用链接

留言簿(2)

随笔分类(7)

随笔档案(4)

搜索

最新评论

阅读排行榜

评论排行榜