8queue4.cpp

《数据结构-使用C语言》第三版

// 文件：QUEEN.CPP 
// 功能：使用回溯算法来求八皇后问题的所有解 
#include <iostream.h> 
enum BOOLEAN { 
FALSE = 0, 
TRUE = 1 
}; 
// 表示棋盘状态的枚举类型 
enum STATUS { 
EMPTY = 0, 
HAVE = 1 
}; 
const int max_length = 20; 
class QUEEN { 
public: 
// FUNCTION: 设置棋盘的宽度，即皇后的个数，并设置初始状态。 
QUEEN(int length = 8); 
// FUNCTION: 设置初始状态 
void reset(); 
// FUNCTION: 给出八皇后问题的第一个解 
// RETURN: 如果有解返回TRUE，否则返回FALSE 
BOOLEAN get_first_solution(); 
// FUNCTION: 给出八皇后问题的下一个解 
// REQURE: 在第一次调用之前必需先调用get_first_solution() 
// RETURN: 如果有下一个解返回TRUE，否则返回FALSE 
BOOLEAN get_next_solution(); 
// FUNCTION: 用直观的方式显示八皇后问题的一个解 
// REQURE: 必需先调用get_first_solution()或get_next_solution 
void display_solution(); 
private: 
// FUNCTION: 选择当前行(current_row)放皇后的列位置，选择的结果在(current_col) 
// RETURN: 如果有可以放皇后的位置饭后TRUE，否则返回FALSE 
BOOLEAN select_place(); 
// FUNCTION: 从当前行(current_row)推进到下一行 
void forward(); 
// FUNCTION: 从当前行(current_row)回溯到上一行 
void backward(); 
// FUNCTION: 判断是否回溯到初始状态 
// RETURN: 如果回到初始状态返回TRUE，否则返回FALSE 
BOOLEAN back_to_start(); 
// FUNCTION: 判断是否推进到最后一步 
// RETURN: 如果推进到最后一步返回TRUE，否则返回FALSE 
BOOLEAN is_end(); 
// FUNCTION: 判断在第row行、第col列是否能够放皇后 
// RETURN: 如果能够放皇后返回TRUE，否则返回FALSE 
BOOLEAN check(int row, int col); 
// 模拟棋盘及皇后放置的情况 
STATUS board[max_length][max_length]; 
// 记住每行放皇后的列位置 
int solution[max_length]; 
// 当前正在试探的行和列 
int current_row; 
int current_col; 
// 皇后的个数及棋盘的宽度 
int length; 
}; 
QUEEN::QUEEN(int length) 
{ 
if (length > max_length) length = max_length; 
QUEEN::length = length; 
reset(); 
} 
void QUEEN::reset() 
{ 
int i, j; 
for (i = 0; i < length; i++) 
for (j = 0; j < length; j++) board[i][j] = EMPTY; 
for (i = 0; i < length; i++) solution[i] = length; 
current_row = 0; 
current_col = 0; 
} 
void QUEEN::display_solution() 
{ 
int row, col; 
for (col = 0; col < length; col++) cout << "+---"; cout << "+\n"; 
for (row = 0; row < length; row++) { 
for (col = 0; col < length; col++) { 
if (col == solution[row]) cout << "| Q "; 
else cout << "| "; 
} 
cout << "|\n"; 
for (col = 0; col < length; col++) cout << "+---"; cout << "+\n"; 
} 
} 
BOOLEAN QUEEN::get_first_solution() 
{ 
reset(); 
return get_next_solution(); 
} 
BOOLEAN QUEEN::get_next_solution() 
{ 
// 从上一解回溯，实际上这里的条件current_row >= length为永真 
if (current_row >= length) current_row = length - 1; 
// 使用回溯算法求问题的一个解 
do { 
if (select_place()) forward(); 
else backward(); 
} while (!back_to_start() && !is_end()); 
if (back_to_start()) return FALSE; 
else return TRUE; 
} 
BOOLEAN QUEEN::select_place() 
{ 
if (solution[current_row] >= length) current_col = 0; // 当前行没有试探过，从第0列开始 
else current_col = solution[current_row] + 1; // 从上一次试探的下一列重新开始 
// 选择在当前行可放皇后的列 
while (!check(current_row, current_col) && current_col < length) { 
current_col = current_col + 1; 
} 
if (current_col >= length) return FALSE; // 当前行没有可放皇后的列位置 
else return TRUE; 
} 
void QUEEN::forward() 
{ 
if (solution[current_row] < length) { 
// 当前行在上一次试探时放过皇后，要清除上一次放皇后的标记 
board[current_row][solution][current_row]] = EMPTY; 
} 
solution[current_row] = current_col; // 记住当前行放皇后的列 
board[current_row][current_col] = HAVE; // 标记该位置放置了皇后 
current_row = current_row + 1; // 推进到下一行 
} 
void QUEEN::backward() 
{ 
if (solution[current_row] < length) { 
// 当前行曾经放过皇后，清除放皇后的标记 
board[current_row][solution][current_row]] = EMPTY; 
// 标记该行没有试探过，或者说要从第0列再重新试探 
solution[current_row] = length; 
} 
current_row = current_row - 1; // 回溯到上一行 
} 
BOOLEAN QUEEN::back_to_start() 
{ 
if (current_row < 0) return TRUE; 
else return FALSE; 
} 
BOOLEAN QUEEN::is_end() 
{ 
if (current_row >= length) return TRUE; 
else return FALSE; 
} 
BOOLEAN QUEEN::check(int row, int col) 
{ 
int temp_row, temp_col; 
// 判断同一列是否已经放置皇后 
for (temp_row = row; temp_row >= 0; temp_row = temp_row - 1) 
if (board[temp_row][col] == HAVE) return FALSE; 
// 判断左上斜线是否已经放置皇后 
for (temp_row = row, temp_col = col; 
temp_row >= 0 && temp_col >= 0; 
temp_row = temp_row - 1, temp_col = temp_col - 1) { 
if (board[temp_row][temp_col] == HAVE) return FALSE; 
} 
// 判断右上斜线是否已经放置皇后 
for (temp_row = row, temp_col = col; 
temp_row >= 0 && temp_col < length; 
temp_row = temp_row - 1, temp_col = temp_col + 1) { 
if (board[temp_row][temp_col] == HAVE) return FALSE; 
} 
return TRUE; 
} 
int main() 
{ 
QUEEN queen(8); 
int count = 0; // 记录解的数目 
if (queen.get_first_solution()) { // 求第一解 
queen.display_solution(); 
count++; 
} else cout << "Can not find any solution!\n"; 
while (queen.get_next_solution()) { // 通过不断地求下一个解来得到所有解 
queen.display_solution(); 
count++; 
} 
cout << "Find " << count << " solutions!\n"; 
return 0; 
}