八皇后问题解

				// QUEEN.cpp : Defines the entry point for the console application.
				//
				
				#include "stdafx.h"
				#include 
				
				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 					for (row = 0; row < length; row++) 
					{
						for (col = 0; col < length; col++) 
						{
							if (col == solution[row]) 
								cout 							else 
								cout 						}
						cout 						for (col = 0; col < length; col++) 
							cout 					}
				}
				
				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 				
					while (queen.get_next_solution()) 	//通过不断地求下一个解来得到所有解
					{ 	
						queen.display_solution();
						count++;
					}
				
					cout 					return 0;
				}