数据结构课程设计报告-8皇后问题

数据结构课程设计报告-8皇后问题 数据结构课程设计报告-8皇后问题是通过使用回溯法和栈来解决八皇后问题的报告。八皇后问题是指在8x8的国际象棋棋盘上，安放8个皇后，要求没“”有一个皇后能够吃掉任何其他一个皇后，即没有两个或两个以上的皇后占据棋盘上的同一行、同一列或同一条对角线。 在解决八皇后问题时，使用了栈来保存曾经到达的每一个状态，栈顶的状态即为回退的第一站。算法的基本思想是从第1行起逐行放置皇后，每放置一个皇后均需要依次对第1，2…，8列进行试探，并尽可能取小的列数。若当前试探的列位置是安全的，即不与已放置的其他皇后冲突，则将该行的列位置保存在栈中，然后继续在下一行上寻找安全位置；若当前试探的列位置不安全，则用下一列进行试探，当8列位置试探完毕都未找到安全位置时，就退栈回溯到上一行，修改栈顶保存的皇后位置，然后继续试探。 在程序设计中，使用了结构体定义来存放皇后的列号和栈顶指针，函数定义了place函数来测试某个位置是否与1~i-1皇后有冲突，queen函数来解决n皇后问题，main函数作为主函数。程序块的分析表明，在解决八皇后问题时，需要使用栈来保存曾经到达的每一个状态，以便回溯到上一行继续寻找安全位置。 知识点： 1. 回溯法：一种解决问题的方法，在一定的约束条件下试探地搜索前进，若前进中受阻，则回头另择通路继续搜索。 2. 栈的应用：在解决八皇后问题时，使用栈来保存曾经到达的每一个状态，以便回溯到上一行继续寻找安全位置。 3. 结构体定义：在程序设计中，使用结构体定义来存放皇后的列号和栈顶指针。 4. 函数定义：在程序设计中，定义了place函数来测试某个位置是否与1~i-1皇后有冲突，queen函数来解决n皇后问题，main函数作为主函数。 5. 算法设计：解决八皇后问题的算法设计思路是从第1行起逐行放置皇后，每放置一个皇后均需要依次对第1，2…，8列进行试探，并尽可能取小的列数。