用试探回溯法解决N皇后问题

 1 int main()
 2 /*Pre: The user enters a valid board size.
 3 Post: All solutions to the n-queens puzzle for the selected board size
 4 are printed.
 5 Uses: The class Queens and the recursive functionsolve from. */
 6 {
 7     int board_size;
 8     char choice = 'y';
 9     char enter;
10     while (choice == 'y')//由用户决定是否继续
11     {
12         sum = 0;
13         cout << "What is the size of the board?"<<flush;
14         cin >> board_size;
15         if(board_size < 0||board_size > max_board)
16             cout<<"The number must between 0 and "<<max_board<<endl;
17         else
18         {
19             Queens configuration(board_size);//创建size*size的对象
20             
21             cout << "there is total " << solve_from(configuration) << " configurations." << endl;//打印所有解决方案和方案个数
22         }
23         cout << endl << "Would you like to continue? [y/n]" << endl;
24         //回车符的消去
25         fflush(stdin);
26         while ((enter = cin.get()) == '\n')
27         {
28             enter = cin.get();
29         }
30         cin.putback(enter);
31         cin >> choice;//移植了计算器的代码
32     }
33     return 0;
34 }

 1 int sum = 0;//记录解决方案个数
 2 
 3 int solve_from(Queens &configuration)//通过递归、回溯找到所有解决方案并打印
 4 /*Pre: the queens configuration represents a partially completed
 5 arrangement of nonattacking queens on a chessboard.
 6 Post: all n-queens solutions that extend the given configuration are
 7 printed. The configuration is restored to its initial state.
 8 Uses: the class Queens and the function solve_from, recursively.*/
 9 {
10     if (configuration.is_solved())//当生成一种解决方案时打印，sum自增一
11     {
12         sum++;
13         configuration.print();
14         cout <<"================" <<endl;
15     }
16     else
17         for(int col=0; col<configuration.board_size; col++)
18             if(configuration.unguarded(col))
19             {
20                 configuration.insert(col);
21                 solve_from(configuration);//recursively continue to add queens当生成一种解决方案时打印
22                 configuration.remove(col);//return the last row and the last col.试探上一层的下一种方案（无论上一次试探是成功还是失败）
23             }
24     return sum;
25 }

 1 const int max_board = 15;//最大棋盘阶数
 2 using namespace std;
 3 
 4 class Queens
 5 {
 6 public:
 7     Queens(int size);
 8     bool is_solved() const;//判断是否完成一种方案
 9     void print() const;//打印当前方案
10     bool unguarded(int col) const;//判断某格是否可放皇后
11     void insert(int col);//摆放皇后
12     void remove(int col);//移除
13     int board_size;//dimension of board = maximum number of queens
14 private:
15     int count;//current number of queens = first unoccupied row
16     bool queen_square[max_board][max_board];//存放棋盘状态的二维数组
17 };