惠特曼 大路之歌 英文:改一个八皇后程序

<<C & C++ 编程百例>>上的例子

// QUEEN.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream.h>

enum BOOLEAN
{
FALSE = 0,
TRUE = 1
};
enum STATUS
{
EMPTY = 0,
HAVE = 1
};

const int max_length = 20;

class QUEEN
{
public:
QUEEN(int length = 8); // 设置棋盘的宽度
void reset(); // 设置初始状态

// 给出八皇后问题的第一个解
// 如果有解返回TRUE，否则返回FALSE
BOOLEAN get_first_solution();

// 给出八皇后问题的下一个解
// 在第一次调用之前必需先调用get_first_solution()
// 如果有下一个解返回TRUE，否则返回FALSE
BOOLEAN get_next_solution();

// 用直观的方式显示八皇后问题的一个解
// 必需先调用get_first_solution()或get_next_solution
void display_solution();
private:
// 选择当前行(current_row)放皇后的列位置，选择的结果在(current_col)
// 如果有可以放皇后的位置饭后TRUE，否则返回FALSE
BOOLEAN select_place();

void forward(); // 从当前行(current_row)推进到下一行

void backward(); // 从当前行(current_row)推进到下一行

// 判断是否回溯到初始状态
// 如果回到初始状态返回TRUE，否则返回FALSE
BOOLEAN back_to_start();

// 判断是否推进到最后一步
// 如果推进到最后一步返回TRUE，否则返回FALSE
BOOLEAN is_end();

// 判断在第row行、第col列是否能够放皇后
// 如果能够放皇后返回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;
}