国产主播精品在线,国产亚洲永久域名,亚洲一区免费在线观看

N皇后問題求解

//N皇后問題求解(此處為8皇后)

#include <iostream>
2

#include <cstdio>
3

#include <ctime>
4

#include <cmath>
5

using namespace std;
7

void queen(int** array, int row, FILE* fp);
9

bool isAvailable(int** array, int y, int x);
10

bool isResult(int** array);
11

int main(int arg, char** argv) {
13

int** array;
14

// 分配空間
16

array = new int*[8];
17

for (int i = 0; i < 8; i++) {
18

array[i] = new int[8];
19

}
20

// 初始化皇后狀態(tài)
22

for (int i = 0; i < 8; i++) {
23

for (int j = 0; j < 8; j++) {
24

array[i][j] = 0;
25

}
26

}
27

FILE* fp = fopen("data.txt", "w");
29

queen(array, 0, fp);
30

fclose(fp);
31

// 釋放空間
33

for (int i = 0; i < 8; i++) {
34

delete[] array[i];
35

}
36

delete []array;
37

array = NULL;
38

return 0;
40

}
41

void 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

// 當(dāng)前位置合法，賦值后，進(jìn)入下一行
53

queen(array, row + 1, fp);
54

// 如果退回來后是結(jié)果，則打印出來
56

if (isResult(array)) {
57

// 把結(jié)果寫入文件
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

}
79

array[row][j] = 0;
80

}
82

}
83

}
84

bool isAvailable(int** array, int row, int column) { // 第row行，column列
86

int i, j;
87

// 檢查row行
89

for (i = 0; i < 8; i++) {
90

if (array[row][i] != 0) {
91

return false;
92

}
93

}
94

// 檢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

149

bool isResult(int** array) {
150

int size = 0; // 皇后個數(shù)
151

152

// 統(tǒng)計皇后個數(shù)
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

// 沒有８個皇后，說明不是結(jié)果
162

163

// 有8個皇后,因為每個皇后的放置都是在合法位置, 所以只需要簡單的計算皇后個數(shù)就知道是不是結(jié)果.
164

if (size != 8) {
165

return false;
166

}
167

168

return true;
169

}
170

上面代碼為大致思路，不一定能能通過編譯

posted on 2009-04-01 23:17 彈杯一笑閱讀(433) 評論(0) 編輯收藏引用所屬分類: c++筆記

只有注冊用戶登錄后才能發(fā)表評論。
【推薦】100%開源！大型工業(yè)跨平臺軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: struct 與class 的區(qū)別 C/C++: 控制臺輸入密碼, 用*號掩藏 N皇后問題求解如何設(shè)計一個范型算法

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

N皇后問題求解

導(dǎo)航

統(tǒng)計

常用鏈接

留言簿(2)

隨筆分類(7)

隨筆檔案(4)

搜索

最新評論

閱讀排行榜

評論排行榜