queen.cpp

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;
}