亚洲免费在线观看视频,国产一区二区三区在线播放免费观看,欧美日韩一区二区三区四区五区

彈杯一笑

N皇后問題求解

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

1

#include <iostream>
2

#include <cstdio>
3

#include <ctime>
4

#include <cmath>
5

6

using namespace std;
7

8

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

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

bool isResult(int** array);
11

12

int 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

42

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

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

85

bool 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

149

bool 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 彈杯一笑閱讀(439) 評論(0) 編輯收藏引用所屬分類: c++筆記

只有注冊用戶登錄后才能發表評論。


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

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

<

2009年3月

>

日

一

二

三

四

五

六

22

23

24

25

26

27

28

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

3

4

統計

隨筆 - 4
文章 - 0
評論 - 0
引用 - 0

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

N皇后問題求解

導航

統計

常用鏈接

留言簿(2)

隨筆分類(7)

隨筆檔案(4)

搜索

最新評論

閱讀排行榜

評論排行榜