下载文档原格式
组合数学中的棋盘问题棋盘问题是组合数学中一个经典而又有趣的问题，它涉及到在一个n × n 的棋盘上放置一定数量的棋子并满足特定的条件。
在本文中，我们将探讨棋盘问题的一些常见形式以及解决方法。
一、八皇后问题八皇后问题是指在一个 8 × 8 的棋盘上放置 8 个皇后，并且每个皇后都不能相互攻击，即任意两个皇后不得处于同一行、同一列或同一对角线上。
这个问题可以通过回溯法来解决。
我们可以逐行放置皇后，并在每一行中使用循环判断每个格子是否满足条件。
如果满足条件，则继续递归下一行；如果不满足条件，则回溯到上一行继续判断。
当所有皇后都放置完毕时，即找到了一种解法。
二、骑士周游问题骑士周游问题是指在一个 n × n 的棋盘上，骑士按照国际象棋中骑士的移动规则进行移动，需要从起始格子出发，经过棋盘的每个格子，最终回到起始格子，且每个格子只能经过一次。
这个问题可以通过深度优先搜索或者广度优先搜索来解决。
我们可以从起始格子开始，按照骑士的移动规则依次遍历所有相邻的格子，并标记已访问的格子。
当所有格子都被访问过，并且最后的格子可以与起始格子连通，则找到了一种解法。
三、数独问题数独问题是指在一个 9 × 9 的棋盘上填入数字，使得每一行、每一列和每一个 3 × 3 的小方格中的数字都是 1 到 9 的不重复数字。
这个问题可以通过回溯法来解决。
我们可以逐格填入数字，并在每个格子中使用循环判断每个数字是否满足条件。
如果满足条件，则继续递归下一个格子；如果不满足条件，则尝试下一个数字。
当所有格子都填满时，即找到了一种解法。
四、六角形拼图问题六角形拼图问题是指在一个六角形的棋盘上，使用特定形状的六角形块填满整个棋盘。
这个问题可以通过搜索算法来解决。
我们可以从一个起始位置开始，依次尝试放置不同形状的六角形块。
每次放置块后，判断是否满足放置要求。
如果满足要求，则继续递归下一个位置；如果不满足要求，则尝试下一个形状的块。
1.引子中国有一句古话，叫做“不撞南墙不回头"，生动的说明了一个人的固执，有点贬义，但是在软件编程中，这种思路确是一种解决问题最简单的算法，它通过一种类似于蛮干的思路，一步一步地往前走，每走一步都更靠近目标结果一些，直到遇到障碍物，我们才考虑往回走。
然后再继续尝试向前。
通过这样的波浪式前进方法，最终达到目的地。
当然整个过程需要很多往返，这样的前进方式，效率比较低下。
2.适用范围适用于那些不存在简明的数学模型以阐明问题的本质，或者存在数学模型，但是难于实现的问题。
3.应用场景在8*8国际象棋棋盘上，要求在每一行放置一个皇后，且能做到在竖方向，斜方向都没有冲突。
国际象棋的棋盘如下图所示：4.分析基本思路如上面分析一致，我们采用逐步试探的方式，先从一个方向往前走，能进则进，不能进则退，尝试另外的路径。
首先我们来分析一下国际象棋的规则，这些规则能够限制我们的前进，也就是我们前进途中的障碍物。
一个皇后q(x,y)能被满足以下条件的皇后q(row,col)吃掉1）x=row(在纵向不能有两个皇后)2) y=col（横向）3）col + row = y+x;（斜向正方向）4) col - row = y-x;（斜向反方向）遇到上述问题之一的时候，说明我们已经遇到了障碍，不能继续向前了。
我们需要退回来，尝试其他路径。
我们将棋盘看作是一个8*8的数组，这样可以使用一种蛮干的思路去解决这个问题，这样我们就是在8*8=64个格子中取出8个的组合，C(64,80) = 4426165368,显然这个数非常大，在蛮干的基础上我们可以增加回溯，从第0列开始，我们逐列进行，从第0行到第7行找到一个不受任何已经现有皇后攻击的位置，而第五列，我们会发现找不到皇后的安全位置了，前面四列的摆放如下:第五列的时候，摆放任何行都会上图所示已经存在的皇后的攻击，这时候我们认为我们撞了南墙了，是回头的时候了，我们后退一列，将原来摆放在第四列的皇后（3，4）拿走，从（3，4）这个位置开始，我们再第四列中寻找下一个安全位置为（7，4），再继续到第五列，发现第五列仍然没有安全位置，回溯到第四列，此时第四列也是一个死胡同了，我们再回溯到第三列，这样前进几步，回退一步，最终直到在第8列上找到一个安全位置（成功）或者第一列已经是死胡同，但是第8列仍然没有找到安全位置为止总结一下，用回溯的方法解决8皇后问题的步骤为：1）从第一列开始，为皇后找到安全位置，然后跳到下一列2）如果在第n列出现死胡同，如果该列为第一列，棋局失败，否则后退到上一列，在进行回溯3）如果在第8列上找到了安全位置，则棋局成功。
八皇后问题：在国际象棋里面皇后可以横走，竖走，斜走。
我们现在有一个8*8的棋盘，怎样摆放8个皇后，而使彼此不冲突，也就是怎样使在同一行，同一列，斜对角线上只存在一个皇后。
解决办法：回溯法回溯法：回溯法有“通用的解题法”之称。
应用回溯法解问题时，首先应该明确问题的解空间。
一个复杂问题的解决往往由多部分构成，即，一个大的解决方案可以看作是由若干个小的决策组成。
很多时候它们构成一个决策序列。
解决一个问题的所有可能的决策序列构成该问题的解空间。
解空间中满足约束条件的决策序列称为可行解。
一般说来，解任何问题都有一个目标，在约束条件下使目标值达到最大（或最小）的可行解称为该问题的最优解。
在解空间中，前k 项决策已经取定的所有决策序列之集称为k 定子解空间。
0 定子解空间即是该问题的解空间。
C语言代码：#include<stdio.h>int count=0;/*计数*/int fit(int (*Q)[8],int i,int j)/*判断是否适合摆放皇后*/{int t,e;for(t=i,e=0;e<8;e++)if(Q[t][e]==1&&e!=j) return 0;/*pan duan hang*/for(e=j,t=0;t<8;t++)if(Q[t][e]==1&&t!=i) return 0 ;/*pan duan lie*/for(e=j,t=i;e>0&&t>0;e--,t--)/*pan duan left up */if(Q[t][e]==1) return 0;for(e=j,t=i;e<8&&t<8;e++,t++)if(Q[t][e]==1) return 0; /*pan duan right down*/for(e=j,t=i;e<8&&t>0;e++,t--)if(Q[t][e]==1) return 0;/*pan duan right up*/for(e=j,t=i;e>0&&t<8;e--,t++)if(Q[t][e]==1) return 0;/*pan duan left down*/return 1;/*if all the conditions are the wrong ,then we will get 1 ,so the queenfunction will be told to make the Q[i][j]=1.we will put a queen on Q[i][j].*/}void queen(int (*Q)[8],int j)/*求8皇后问题的解*/{ int i,k;if(j==8)/*递归判断，当j=8，说明Q【】【7】中摆放了皇后，所以得到一个解*/{for(i=0;i<8;i++){for(k=0;k<8;k++)printf(" %d",Q[i][k]);/*统计摆放的种类，以及输出结果；*/printf("\n");}printf("\n");count++;return;}for(i=0;i<8;i++){if(fit(Q,i,j)>0)/*在生成解空间树的同时进行深度搜索，从而实现减枝*/{Q[i][j]=1;queen(Q,j+1);Q[i][j]=0;/*进行回溯,因为每次会形成不同的基点，然后沿着各基点进行深度搜索，所以每次搜索完要回到例外基点，所以前面搜索的基点必然要归为零*/}}}main(){int Q[8][8],i,j;for(i=0;i<8;i++)for(j=0;j<8;j++)Q[i][j]=0;queen(Q,0);printf("%d",count);}运行的部分结果：。
八皇后实验报告八皇后实验报告引言：八皇后问题是一个经典的数学问题，它要求在一个8x8的国际象棋棋盘上放置8个皇后，使得任意两个皇后都不会互相攻击。
这个问题看似简单，但实际上却充满了挑战。
在本次实验中，我们将探索八皇后问题的解法，并通过编写算法来解决这个问题。
一、问题背景：八皇后问题最早由数学家马克斯·贝瑟尔于1848年提出，它是一道经典的递归问题。
在国际象棋中，皇后可以在同一行、同一列或同一对角线上进行攻击，因此我们需要找到一种方法，使得8个皇后彼此之间不会相互攻击。
二、解决方法：为了解决八皇后问题，我们可以使用回溯法。
回溯法是一种穷举搜索的方法，它通过逐步尝试所有可能的解决方案，直到找到符合要求的解。
具体步骤如下：1. 初始化一个8x8的棋盘，并将所有格子标记为无皇后。
2. 从第一行开始，依次尝试在每一列放置一个皇后。
3. 在每一列中，检查当前位置是否符合要求，即与已放置的皇后不在同一行、同一列或同一对角线上。
4. 如果当前位置符合要求，将皇后放置在该位置，并进入下一行。
5. 如果当前位置不符合要求，尝试在下一列放置皇后。
6. 重复步骤3-5，直到找到一个解或者所有可能的位置都已尝试过。
7. 如果找到一个解，将其输出；否则，回溯到上一行，继续尝试下一列的位置。
三、编写算法：基于上述步骤，我们可以编写一个递归函数来解决八皇后问题。
伪代码如下所示：```function solveQueens(board, row):if row == 8:print(board) # 打印解returnfor col in range(8):if isSafe(board, row, col):board[row][col] = 1solveQueens(board, row + 1)board[row][col] = 0function isSafe(board, row, col):for i in range(row):if board[i][col] == 1:return Falseif col - (row - i) >= 0 and board[i][col - (row - i)] == 1:return Falseif col + (row - i) < 8 and board[i][col + (row - i)] == 1:return Falsereturn Trueboard = [[0]*8 for _ in range(8)]solveQueens(board, 0)```四、实验结果：通过运行上述算法，我们得到了八皇后问题的所有解。
八皇后问题八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。
该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
高斯认为有76种方案。
1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。
对于八皇后问题的实现，如果结合动态的图形演示，则可以使算法的描述更形象、更生动，使教学能产生良好的效果。
下面是用Turbo C实现的八皇后问题的图形程序，能够演示全部的92组解。
八皇后问题动态图形的实现，主要应解决以下两个问题。
（1）回溯算法的实现（a）为解决这个问题，我们把棋盘的横坐标定为i，纵坐标定为j,i和j的取值范围是从１到８。
当某个皇后占了位置(i,j)时，在这个位置的垂直方向、水平方向和斜线方向都不能再放其它皇后了。
用语句实现，可定义如下三个整型数组：a[8],b[15],c[24]。
其中：a[j-1]=1 第j列上无皇后a[j-1]=0 第j列上有皇后b[i+j-2]=1 (i,j)的对角线（左上至右下）无皇后b[i+j-2]=0 (i,j)的对角线（左上至右下）有皇后c[i-j+7]=1 (i,j)的对角线（右上至左下）无皇后c[i-j+7]=0 (i,j)的对角线（右上至左下）有皇后（b）为第i个皇后选择位置的算法如下：for(j=1;j<=8;j++) /*第i个皇后在第j行*/if ((i,j)位置为空)）/*即相应的三个数组的对应元素值为1*/{占用位置（i,j）/*置相应的三个数组对应的元素值为0*/if i<8为i+1个皇后选择合适的位置；else 输出一个解}(2)图形存取在Turbo C语言中，图形的存取可用如下标准函数实现：size=imagesize(x1,y1,x2,y2) ;返回存储区域所需字节数。
并行计算与多核多线程技术课程报告班级__________________学号_____________姓名_________________2014 年11 月26 日目录1. N皇后问题并行算法设计与实现 (1)1.1 功能描述与解决方案 (1)1.1.1功能描述 (1)1.1.2 解决方案 (1)1.2算法设计 (1)1.2.1 串行算法设计 (1)1.2.2 并行算法设计 (2)1.2.3 理论加速比分析（选作） (3)1.3 基于OpenMP的并行算法实现 (3)1.3.1 代码及注释（变量名名字首字母开头） (3)1.3.2 执行结果截图（体现串行时间、并行时间和加速比） (7)1.3.3 遇到的问题及解决方案 (8)1.4 基于MPI的并行算法实现 (9)1.4.1 代码及注释（变量名名字首字母开头） (9)1.4.2 执行结果截图（体现串行时间、并行时间和加速比） (13)1.4.3 遇到的问题及解决方案 (14)1.5 基于Java（Tread或者Runnable）的并行算法实现 (15)1.5.1 代码及注释（变量名名字首字母开头） (15)1.5.2 执行结果截图（体现串行时间、并行时间和加速比） (19)1.5.3 遇到的问题及解决方案 (21)1.6 基于Windows（API或MFC或.net）的并行算法实现 (21)1.6.1 代码及注释（变量名名字首字母开头） (21)1.6.2 执行结果截图（体现串行时间、并行时间和加速比） (26)1.6.3 遇到的问题及解决方案 (27)1.7 基于Linux（fork或pthread）的并行算法实现 (28)1.7.1 代码及注释（变量名名字首字母开头） (28)1.7.2 执行结果截图（体现串行时间、并行时间和加速比） (32)1.7.3 遇到的问题及解决方案 (33)2. 理论基础 (34)2.1 并行计算机体系结构、并行计算模型、并行算法的概念 (34)2.2并行计算机体系结构、并行计算模型、并行算法的关系 (34)2.3实例说明并行计算机体系结构、并行计算模型、并行算法的关系 (34)评价实践效果（正确度/加速比）理论基础难度工作量独立性1. N皇后问题并行算法设计与实现1.1 功能描述与解决方案1.1.1功能描述八皇后问题是十九世纪著名数学家高斯于1850年提出的。
⼋皇后以及N皇后问题分析⼋皇后是⼀个经典问题，在8*8的棋盘上放置8个皇后，每⼀⾏不能互相攻击。
因此拓展出 N皇后问题。
下⾯慢慢了解解决这些问题的⽅法：回溯法：回溯算法也叫试探法，它是⼀种系统地搜索问题的解的⽅法。
回溯算法的基本思想是：从⼀条路往前⾛，能进则进，不能进则退回来，换⼀条路再试。
在现实中，有很多问题往往需要我们把其所有可能穷举出来，然后从中找出满⾜某种要求的可能或最优的情况，从⽽得到整个问题的解。
回溯算法就是解决这种问题的“通⽤算法”，有“万能算法”之称。
N皇后问题在N增⼤时就是这样⼀个解空间很⼤的问题，所以⽐较适合⽤这种⽅法求解。
这也是N皇后问题的传统解法，很经典。
算法描述：1. 算法开始，清空棋盘。
当前⾏设为第⼀⾏，当前列设为第⼀列。
2. 在当前⾏，当前列的判断放置皇后是否安全，若不安全，则跳到第四步。
3. 在当前位置上满⾜条件的情况： 在当前位置放⼀个皇后，若当前⾏是最后⼀⾏，记录⼀个解； 若当前⾏不是最后⼀⾏，当前⾏设为下⼀⾏，当前列设为当前⾏的第⼀个待测位置； 若当前⾏是最后⼀⾏，当前列不是最后⼀列，当前列设为下⼀列； 若当前⾏是最后⼀⾏，当前列是最后⼀列，回溯，即清空当前⾏以及以下各⾏的棋盘，然后当前⾏设为上⼀⾏，当前列设为当前⾏的下⼀个待测位置； 以上返回第⼆步。
4.在当前位置上不满⾜条件： 若当前列不是最后⼀列，当前列设为下⼀列，返回到第⼆步； 若当前列是最后⼀列，回溯，即，若当前⾏已经是第⼀⾏了，算法退出，否则，清空当前⾏以及以下各⾏的棋盘，然后，当前⾏设为上⼀⾏，当前列设为当前⾏的下⼀个待测位置，返回第⼆步。
如何判断是否安全：把棋盘存储为⼀个N维数组a[N]，数组中第i个元素的值代表第i⾏的皇后位置，这样便可以把问题的空间规模压缩为⼀维O(N)，在判断是否冲突时也很简单， ⾸先每⾏只有⼀个皇后，且在数组中只占据⼀个元素的位置，⾏冲突就不存在了， 其次是列冲突，判断⼀下是否有a[i]与当前要放置皇后的列j相等即可。
八皇后问题有多少解八皇后问题有92解。
皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。
如何将8个皇后放在棋盘上（有8 * 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。
对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，‘即a=b1b2…b8，其中bi为相应摆法中第i行皇后所处的列数。
已经知道8皇后问题一共有92组解（即92个不同的皇后串）。
给出一个数b，要求输出第b个串。
串的比较是这样的：皇后串x置于皇后串y之前，当且仅当将x视为整数时比y小。
//输入数据//第1行是测试数据的组数n，后面跟着n行输入。
每组测试数据占1行，包括一个正整数b(1 <= b <= 92)//输出要求//n行，每行输出对应一个输入。
输出应是一个正整数，是对应于b 的皇后串//输入样例//2//1//92//输出样例//15863724//84136275解题思路一因为要求出92种不同摆放方法中的任意一种，所以我们不妨把92种不同的摆放方法一次性求出来，存放在一个数组里。
为求解这道题我们需要有一个矩阵仿真棋盘，每次试放一个棋子时只能放在尚未被控制的格子上，一旦放置了一个新棋子，就在它所能控制的所有位置上设置标记，如此下去把八个棋子放好。
当完成一种摆放时，就要尝试下一种。
若要按照字典序将可行的摆放方法记录下来，就要按照一定的顺序进行尝试。
也就是将第一个棋子按照从小到大的顺序尝试；对于第一个棋子的每一个位置，将第二个棋子从可行的位置从小到大的顺序尝试；在第一第二个棋子固定的情况下，将第三个棋子从可行的位置从小到大的顺序尝试；依次类推。
首先，我们有一个8*8的矩阵仿真棋盘标识当前已经摆放好的棋子所控制的区域。
用一个有92行每行8个元素的二维数组记录可行的摆放方法。
用一个递归程序来实现尝试摆放的过程。
基本思想是假设我们将第一个棋子摆好，并设置了它所控制的区域，则这个问题变成了一个7皇后问题，用与8皇后同样的方法可以获得问题的解。
