八皇后和骑士游历

八皇后和骑士遍历 作者： 出处： 更新时间： 2005年09月14日 八皇后和骑士遍历　　 　　 八皇后问题是大数学家高斯于1850年提出来的。该问题是在8×8的国际象棋棋盘上放置8个皇后，使得没有一个皇后能"吃掉"任何其他一个皇后，即没有任何两个皇后被放置在棋盘的同一行、同一列或同一斜线上。要求编一个程序求出该问题的所有解。骑士游历问题是放在8×8的国际象棋棋盘上的一个马，按照马走"日"字的规则是否能够不重复地走遍棋盘的每个格。要求编一个程序求出该问题的一个解。 l 解题思路 使用回溯算法求解的问题一般有这样的特征，要求解问题必须分为若干步，每一步都有几种可能的选择，而且往往在某个选择不成功时需要回头再试另外一种选择，如果到达求解目标则每一步的选择构成了问题的解，如果回头到第一步且没有新的选择则问题求解失败。 通用的回溯算法可用PDL语言描述如下： 初始化，做试探的准备 do { 选择当前步的可能求解路线 if (有可能的求解路线) 前进一步 else { 清除当前选择所遗留的痕迹 回溯一步 } } while(没有到最后一步且没有回到初始状态) if (到最后一步) 每一步的选择就是问题的解 else 问题没有解 回溯算法有两个关键的地方，一是要记住每一步的选择以便不重复选择以及最后能够输出整个解，二是在回溯到前一步的时候要消除当前步的影响。 下面具体给出求解八皇后问题的程序，求解骑士游历问题的程序以及快速求解骑士游历问题的程序，最后还给出了一些思考题以便读者巩固和提高。 l 求解八皇后问题 N. Wirth在《程序=算法+数据结构》中指出一个程序实际上包括两个方面，算法和数据结构。在确定使用回溯算法求解该问题之后，我们设计求解问题所需的数据结构。 根据回溯算法，显然要一个数据结构来记住每一步的选择，我们可通过使用一个数组solution记住每一行皇后放置的列位置来反映每一步的选择。为更好地选择下一步放置皇后的列位置，可使用一个二维数组board来模拟棋盘，并记住什么位置放了皇后。 在确定数据结构之后，我们对上述回溯算法作进一步的细化，需要确定几个问题： 1.怎样的状态是初始状态。 2.怎样选择当前步可能的路线 3.怎样表示向前推进一步 4.怎样回溯及清除当前步的痕迹 显然初始状态应该是solution数组中所有的值为一个特定的不可能的选择，例如为-1或n，其中n是棋盘的宽度，可能的选择是0到n-1。还有棋盘board的所有值应该表示没有放皇后。 选择当前步可能的求解路线应该是判断当前行可在哪个列位置放皇后。也就是说求解八皇后问题的每一步就是在每一行选择一个列位置放皇后。这里的关键是要考虑到当前行的状态有两种： 1.当前行在这一次的求解中还没试探过，这时考虑放皇后的列位置应该从0开始。 2.当前行在这一次的求解中已经放过皇后，这时再处在当前行是上一步回溯而来，那么这时再试探当前行放皇后的可能列位置应该从上一次在当前行试过的列位置的下一列开始考虑。 向前推进一步应该是记住当前行放皇后的列位置，并且在棋盘上做标记，然后将当前行加1。这时要记住如果当前行曾经放过皇后，那么要先消除上一次放皇后的标记。 回溯一步应该是置当前行没有放过皇后，然后将当前行减1.这时要记住如果当前行曾经放过皇后，那么要先消除上一次放皇后的标记。 经过这种细化之后，应该很容易写出求出八皇后问题一个解的算法，如果要求出所有的解则可以通过在最后一步再回溯而得到。再回溯的意思是说，在最后一步再从上一个解的列位置的下一位置再考虑放皇后，如果没有下一列位置，那么回溯到上一行。 下面的程序使用一个类QUEEN来封装数组solution、board以及当前行(current_row)和当前列(current_col)。reset()来设置初始状态，select_place()来选择当前行放皇后的位置，forward()向前推进一步，backward()回溯一步。get_first_solution()用来给出八皇后问题的第一个解，get_next_solution()用来给出下一个解，如果没有解返回FALSE，主函数可用一个循环来求出所有解，display_solution()显示一个解。为节省篇幅起见，我们将类的界面、实现及演示放在了同一文件。 程序一：求解八皇后问题的程序 // 文件：QUEEN.CPP // 功能：使用回溯算法来求八皇后问题的所有解 #include 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; } l 求解骑士游历问题 显然求解骑士游历问题的每一步就是马在棋盘上走的一步。在每一步马需要选择一个方向进行游历，这时记住解的每一步需要记住两件事： 1.当前步的行列位置 2.当前步已经试探过哪些方向了，以便回溯回来时能够选择一个新的方向进行试探 所以使用两个数组，数组board记住棋盘的每个位置是在马的第几步到达的，这反映了问题的解，即第几步到哪个位置。数组direction记住在棋盘的某个位置已经试探过的方向，每个位置有八个方向，可按某种顺序对八个方向编号，然后在每个位置按编号顺序试探方向。 在确定数据结构之后，同样需要确定下面几个问题： 1.怎样的状态是初始状态。 2.怎样选择当前步可能的路线 3.怎样表示向前推进一步 4.怎样回溯及清除当前步的痕迹 显然初始状态是棋盘的每个位置都置为第0步到达（即还没有到达），每个位置都还没有选择任何方向（可赋值MAX_DIR(=8)表示没有选择方向）。 选择当前步可能的路线就是在当前位置选择一个方向来游历下一步。在选择的时候同样需要区分是从第0个方向开始考虑还是从上一次的下一个方向开始考虑。为了方便从下一个方向开始考虑，实际上数组direction在某一位置(curr_x, curr_y)的值记住的是从上一位置选择了哪个编号的方向而到达的，这样容易回溯到上一位置，而且容易在回溯到上一位置之后从下个一方向重新试探。 向前推进一步则要根据所选择的方向推进到下一位置，记住到下一位置所选择的方向，下一位置是第几步到达的，然后增加步数。 回溯一步则要标记当前位置没有到达过（将到达的步数置为0），根据上一步到当前位置的所选择的方向（这个方向是记录当前位置所对应的direction数组中）而回溯到上一位置，然后减少步数。 下面程序用类KNIGHT来封装数组board、direction、当前位置(curr_x, curr_y)、当前步数(step)，并且使用last_direction来记住上一位置到当前位置所选择的方向。为了方便计算选择一个方向后从当前推进到下一位置，使用数组var_x和var_y来记住每个方向在x方向和y方向的改变值。这个类中提供的方法的含义与类QUEEN类似。为节省篇幅起见，我们将类的界面、实现及演示放在了同一文件。 程序二：求解骑士游历问题的程序 // 文件：KNIGHT.CPP // 功能：使用回溯算法求解骑士游历问题 #include #include enum BOOLEAN { TRUE = 1, FALSE = 0 }; const int MAX_WIDTH = 30; const int MAX_DIR = 8; class KNIGHT { public: // FUNCTION: 设置初始状态 KNIGHT(int width); // FUNCTION: 用比较直观的方式打印问题的解 // REQUIRE: 必须先调用了成员函数tourist() void print(); // FUCTION: 根据马的起始位置(start_x, start_y)使用回溯算法求骑士游历问题的一个解 // REQUIRE: (start_x, start_y)必需在所设置的棋盘宽度范围内 BOOLEAN tourist(int start_x, int start_y); protected: // FUNCTION: 初始化记录所选方向的数组，将每个值置为MAX_DIR void init_direction(); // FUNCTION: 初始化记录马在第几步到位每个位置的数组，将每个值置为0 void init_chessboard(); // FUNCTION: 设置初始状态，包括初始化方向数组和棋盘数组，并设置马的初始位置 void set_start(int x, int y); // FUNCTION: 在当前位置选择一个方向以推进到下一位置 // RETURN: 如果可选择一个方向推进则返回TRUE，否则返回FALSE // NOTE: 将该函数定义为虚函数，以便下面快速游历的类来重定义该函数而产生动态绑定 virtual BOOLEAN select_direction(); // FUNCTION: 从当前位置回溯到上一位置 // NOTE: 将该函数定义为虚函数，以便下面快速游历的类来重定义该函数而产生动态绑定 virtual void backward(); // FUNCTION: 从当前位置推进到下一位置 // NOTE: 将该函数定义为虚函数，以便下面快速游历的类来重定义该函数而产生动态绑定 virtual void forward(); // FUNCTION: 判断马是否能够走向位置(x, y)。 // RETURN: 如果马已经到过该位置，或该位置超出棋盘范围返回FALSE，否则返回TRUE BOOLEAN is_legal(int x, int y); // FUNCTION: 判断是否回溯到初始状态 // RETURN: 如果步数回到第1步则表示回到初始状态而返回TRUE，否则返回FALSE BOOLEAN back_to_start(); // FUNCTION: 判断是否游历完所有位置 // RETURN: 如果步数等于棋盘格子数则表示游历完所有位置而返回TRUE，否则返回FALSE BOOLEAN is_end(); // 下面两个数组用来记住选择某个方向后，推进到下一位置时x方向和y方向的值的变化 int var_x[MAX_DIR]; int var_y[MAX_DIR]; // 记录马第几步到达某个位置的棋盘数组 int chessboard[MAX_WIDTH][MAX_WIDTH]; // 记录马在某个位置是在上一位置选择第几个方向到达的 int direction[MAX_WIDTH][MAX_WIDTH]; int width; // 棋盘宽度 int curr_x, curr_y; // 马的当前位置 int step; // 已经游历的步数 int last_direction; // 上一位置到当前位置所选的方向 }; KNIGHT::KNIGHT(int width) { this->width = width; init_direction(); total_step = 0; } void KNIGHT::print() { int x, y; cout << " +"; for (x = 0; x < width; x = x + 1) cout << "----+"; cout << '\n'; for (x = 0; x < width; x = x + 1) { cout << " |"; for (y = 0; y < width; y = y + 1) cout << setw(3) << chessboard[x][y] << " |"; cout << '\n'; cout << " +"; for (y = 0; y < width; y = y + 1) cout << "----+"; cout << '\n'; } } BOOLEAN KNIGHT::is_legal(int x, int y) { if (x < 0 || x >= width) return FALSE; if (y < 0 || y >= width) return FALSE; if (chessboard[x][y] > 0) return FALSE; return TRUE; } BOOLEAN KNIGHT::back_to_start() { if (step == 1) return TRUE; else return FALSE; } BOOLEAN KNIGHT::is_end() { if (step > width * width) return TRUE; else return FALSE; } void KNIGHT::set_start(int x, int y) { curr_x = x; curr_y = y; step = 1; chessboard[x][y] = step; step = step + 1; direction[x][y] = MAX_DIR; last_direction = MAX_DIR; } BOOLEAN KNIGHT::select_direction() { int try_x, try_y; // last_direction为MAX_DIR表示当前位置是一个新的位置，在新推进到某个位置(curr_x, curr_y)时， // direction[curr_x][curr_y]会记录上一位置到(curr_x, curr_y)时所选择的方向，这时 // last_direction置为MAX_DIR用来标记该位置是新推进的位置。 if (last_direction == MAX_DIR) last_direction = 0; else last_direction = last_direction + 1; while (last_direction < MAX_DIR) { // 看下一步推进到哪个位置是合法的，如果合法则选择该方向。 try_x = curr_x + var_x[last_direction]; try_y = curr_y + var_y[last_direction]; if (is_legal(try_x, try_y)) break; last_direction = last_direction + 1; } if (last_direction == MAX_DIR) return FALSE; else return TRUE; } void KNIGHT::backward() { step = step - 1; chessboard[curr_x][curr_y] = 0; // 将last_direction置为上一位置到(curr_x, curr_y)所选择的方向 last_direction = direction[curr_x][curr_y]; // 根据这个方向回溯到上一位置，同时回溯到上一位置之后，在上一位置再试探时应该从 // last_direction+1的方向开始。参看成员函数select_direction()。 curr_x = curr_x - var_x[last_direction]; curr_y = curr_y - var_y[last_direction]; } void KNIGHT::forward() { // 在推进时last_direction是当前位置所选择的方向 curr_x = curr_x + var_x[last_direction]; curr_y = curr_y + var_y[last_direction]; chessboard[curr_x][curr_y] = step; step = step + 1; // 这个方向被记录下一位置(这时已经为(curr_x, curr_y))的direction数组中。 direction[curr_x][curr_y] = last_direction; // last_direction的值已经被记录，这时置为MAX_DIR表示当前位置为新推进的位置 last_direction = MAX_DIR; } BOOLEAN KNIGHT::tourist(int start_x, int start_y) { init_chessboard(); set_start(start_x, start_y); do { if (select_direction()) forward(); else backward(); } while (!back_to_start() && !is_end()); if (back_to_start()) return FALSE; else return TRUE; } void KNIGHT::init_direction() { var_x[0] = 2; var_y[0] = 1; var_x[1] = 1; var_y[1] = 2; var_x[2] = -1; var_y[2] = 2; var_x[3] = -2; var_y[3] = 1; var_x[4] = -2; var_y[4] = -1; var_x[5] = -1; var_y[5] = -2; var_x[6] = 1; var_y[6] = -2; var_x[7] = 2; var_y[7] = -1; } void KNIGHT::init_chessboard() { int x, y, dir; for (x = 0; x < width; x = x + 1) { for (y = 0; y < width; y = y + 1) { chessboard[x][y] = 0; } } } int main() { int width = 8; KNIGHT knight(width); int start_x, start_y; cout << "\nProgram begin...\n"; start_x = 4; start_y = 4; if (knight.tourist(start_x, start_y)) { knight.print(); }else { cout << "\nHave not found the solution for: "; cout << "Start: <" << start_x << ", " << start_y << ">, "; cout << "Width: " << width << "\n"; } return 1; } l 骑士游历问题的快速解 上面求解骑士游历问题的程序效率比较低，对于8×8的棋盘将花费相当长一段时间。为此我们可以在选择当前步的可能路线时增加一些启发式规则，使得这个选择从某种意义下来说是比较好的，从而加速问题的求解过程。 对于骑士游历问题一个启发式规则是，在选择当前步的方向时去选择满足下面条件的方向，当按这个方向推进到下一位置时，这个位置所可以再选择的方向最少。也就是说在当前位置优先选一个走起来比?quot;艰难"的方向来推进。加入这种启发式规则之后，从运行的效果看，在求解的过程中几乎不回溯。 为了使用这个启发式规则，我们首先要修改上面的成员函数select_direction()。这时在每个位置选择方向时不再是按照一定的顺序来选择，为了避免在回溯时重复选择方向，必需记住在某个位置哪些方向已经选择过了，我们使用三维数组cannot来记住这件事情，当其值为TRUE时表示某个位置的某个方向已经试探过了，为FALSE表示没有试探过。当从当前位置回溯到上一位置是，要先把当前位置所有方向的cannot值置为FALSE，因为下一次再到达这个位置时所有方向需要重新试探。 为了研究加入启发式规则的效果，要求保留上面不使用启发式规则的程序，这样我们从KNIGHT类派生出一个类FAST_KNIGHT来支持快速求解骑士游历问题。在这个类中增加数组cannot，并且只需要重新定义select_direction(), backward()和forward()就可以了。需要重新定义backward()和forward()是因为在这两个成员函数中需要维护数组cannot的值。其它成员函数不用作任何的修改。我们在KNIGHT类中已经将这几个成员函数定义为虚函数，以便在成员函数tourist()中动态地选择这些函数来调用。读者需要学习完第八章多态性之后才能充分理解动态绑定的含义。 在下面程序中，我们只给出类FAST_KNIGHT的定义，读者很容易修改演示程序以使用类FAST_KNIGHT来求解骑士游历问题。 程序三：快速求解骑士游历问题的程序 // 文件：FASTKNIGHT.CPP // 功能：使用回溯算法快速求解骑士游历问题 class FAST_KNIGHT: public KNIGHT { public: FAST_KNIGHT(int width); protected: // FUNCTION: 初始化cannot数组 void init_cannot(); // FUNCTION: 在当前位置根据启发式规则选择一个方向以推进到下一位置 // RETURN: 如果可选择一个方向推进则返回TRUE，否则返回FALSE // NOTE: 重定义KNIGHT类的select_direction() virtual BOOLEAN select_direction(); // FUNCTION: 从当前位置回溯到上一位置，注意维持cannot数组 // NOTE: 重定义KNIGHT类的backward() virtual void backward(); // FUNCTION: 从当前位置根据所选择的方向推进到下一位置 // NOTE: 重定义KNIGHT类的forward() virtual void forward(); // 用来记住某个位置某个方向是否已经试探过 BOOLEAN cannot[MAX_WIDTH][MAX_WIDTH][MAX_DIR]; }; FAST_KNIGHT::FAST_KNIGHT(int width): KNIGHT(width) { init_cannot(); } void FAST_KNIGHT::init_cannot() { int x, y, dir; for (x = 0; x < width; x = x + 1) for (y = 0; y < width; y = y + 1) for (dir = 0; dir < width; dir = dir + 1) cannot[x][y][dir] = FALSE; } BOOLEAN FAST_KNIGHT::select_direction() { int try_x, try_y, next_x, next_y; int dir_index, next_index; int min_dir, count; min_dir = MAX_DIR; last_direction = MAX_DIR; for (dir_index = 0; dir_index < MAX_DIR; dir_index = dir_index + 1) { // 选择一个方向，使得根据该方向推进到下一位置时，在该位置可选的方向最少 try_x = curr_x + var_x[dir_index]; try_y = curr_y + var_y[dir_index]; if (is_legal(try_x, try_y) && !cannot[curr_x][curr_y][dir_index]) { // 这个位置作为下一位置是合法，那么计算该位置可选的方向 count = 0; for (next_index = 0; next_index < MAX_DIR; next_index++) { next_x = try_x + var_x[next_index]; next_y = try_y + var_y[next_index]; if (is_legal(next_x, next_y)) count = count + 1; } if (count < min_dir) { // 记录具有最少可选方向的下一位置 last_direction = dir_index; min_dir = count; } } } if (last_direction == MAX_DIR) return FALSE; else return TRUE; } void FAST_KNIGHT::backward() { int dir; step = step - 1; chessboard[curr_x][curr_y] = 0; // 从位置(curr_x, curr_y)回溯，那么下一次再到达该位置时所有方向都需要重新试探 for (dir = 0; dir < MAX_DIR; dir = dir + 1) cannot[curr_x][curr_y][dir] = FALSE; last_direction = direction[curr_x][curr_y]; curr_x = curr_x - var_x[last_direction]; curr_y = curr_y - var_y[last_direction]; } void FAST_KNIGHT::forward() { // 该位置的这个方向已经试探过了 cannot[curr_x][curr_y][last_direction] = TRUE; curr_x = curr_x + var_x[last_direction]; curr_y = curr_y + var_y[last_direction]; chessboard[curr_x][curr_y] = step; step = step + 1; direction[curr_x][curr_y] = last_direction; last_direction = MAX_DIR; } l 思考与提高 在充分理解上述三个程序之后，读者可进一步思考下述问题： 1.上述求解八皇后问题的程序中数组board不是必须的，因为根据solution数组完全可算出哪个位置有皇后，修改上述程序使得不需要数组board而给出八皇后问题的所有解。 2.思考快速求解骑士游历问题中的启发式规则为什么能够使得在求解过程中几乎不回溯。进一步类比该启发式规则，考虑在求八皇后问题的一个解时可利用怎样的启发式规则以加速求解过程。 3.使用回溯算法求解迷宫问题，自己给出迷宫问题的进一步陈述，设计所需要的数据结构，并细化上述回溯算法。 4.理解上述快速求解骑士游历问题的程序，体会在设计算法时的自顶向上分解、逐步求精的思想，进一步体会使用面向对象程序设计思想，特别是利用动态绑定的好处。 令附1个骑士遍例算法 #include int f[11][11] int adjm[121][121]; long fgf; void creatadjm(void); void e(int,int,int,int); void travel(int,int); int n,m; int main() { int i,j,k,l; printf("Input n:");scanf("%d",&n); m=n*n; creatadjm(); for(i=1;i<=m;i++) { for(j=1;j<=m;j++) printf("%2d",adjm[i][j]); printf("\n"); } getchar(); printf("Input i,j:"); scanf("%d %d",&i,&j); l=(i-1)*n+j; while ((i>0)||(j>0)) { for(i=1;i<=n;i++) for(j=1;j<=n;j++) f[i][j]=0; k=0; travel(l,k); printf("%d\n",fgf);fgf=0; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) printf("%4d",f[i][j]); printf("\n"); } getchar(); printf("Input i,j:");scanf("%d %d",&i,&j); l=(i-1)*n+j; } return 0; } void creatadjm() { int i,j; for(i=1;i<=n;i++) for(j=1;j<=n;j++) f[i][j]=0; for(i=1;i<=m;i++) for(j=1;j<=m;j++) adjm[i][j]=0; for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(f[i][j]==0) { f[i][j]=1; if((i+2<=n)&&(j+1<=n)) e(i,j,i+2,j+1); if((i+2<=n)&&(j-1>=1)) e(i,j,i+2,j-1); if((i-2>=1)&&(j+1<=n)) e(i,j,i-2,j+1); if((i-2>=1)&&(j-1>=1)) e(i,j,i-2,j-1); if((j+2<=n)&&(i+1<=n)) e(i,j,i+1,j+2); if((j+2<=n)&&(i-1>=1)) e(i,j,i-1,j+2); if((j-2>=1)&&(i+1<=n)) e(i,j,i+1,j-2); if((j-2>=1)&&(i-1>=1)) e(i,j,i-1,j-2); } return; } void travel(int p,int r) { int i,j,q; for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(f[i][j]>r) f[i][j]=0; r=r+1; i=((p-1)/n)+1; j=((p-1)%n)+1; f[i][j]=r; fgf++; //if(r==25)printf("%d\n",p); /* printf("i=%d,j=%d,r=%d\n",i,j,r); getchar(); */ for(q=1;q<=m;q++) { i=((q-1)/n)+1; j=((q-1)%n)+1; if((adjm[p][q]==1)&&(f[i][j]==0)) travel(q,r); } return; } void e(int i1,int j1,int i2,int j2) { adjm[(i1-1)*n+j1][(i2-1)*n+j2]=1; adjm[(i2-1)*n+j2][(i1-1)*n+j1]=1; return; } 再来一个骑士遍历回逆 /* knight.c Knight Traversal by Justin Hou (B990614108) 2001/11/23 * */ #include #define MAX 10 int nRow = 5, nCol = 4; /* count chessboard */ int d[8][2] = {{ 1, 2}, { 2, 1}, { 2,-1}, { 1,-2}, /* next step added */ {-1,-2}, {-2,-1}, {-2, 1}, {-1, 2}}; int flag[MAX][MAX]; int nSolution; void search(int, int); /* search the way */ void main() { int row, col, i, j; //clrscr(); //gotoxy(1, 12); /* init the data */ printf("Input the chessboard width and height (nRow, nCol): "); scanf("%d, %d", &nRow, &nCol); while (nRow > MAX || nRow < 1 || nCol > MAX || nCol < 1) { printf("error! input again: "); scanf("%d, %d", &nRow, &nCol); } printf("Input the start point (row, col): "); scanf("%d, %d", &row, &col); while (row >= nRow || row < 0 || col >= nCol || col < 0) { printf("error! input again: "); scanf("%d, %d", &row, &col); } /* init data end */ for (i = 0; i < nRow; i++) for (j = 0; j < nCol; j++) { //gotoxy(i * 3 + 4, j + 2); printf("."); } flag[row][col] = 1; //gotoxy(row*3+4, col+2); printf("1"); //delay(1000); search(row, col); //gotoxy(1, 20); printf("Solution number is %d", nSolution); return; } void search(int row, int col) { static int step = 1; /* the step count */ int i, nextRow, nextCol; for (i = 0; i < 8; i++) { nextRow = row + d[i][0]; nextCol = col + d[i][1]; if (nextRow < nRow && nextRow >= 0 && nextCol < nCol && nextCol >= 0 && flag[nextRow][nextCol] == 0) { flag[nextRow][nextCol] = 1; //gotoxy(nextRow*3+4, nextCol+2); step++