1、用回溯法解决16皇后问题（以下算法均用java语言实现）
·一个答案用一个一维数组来存储，其中数组的下标表示所在行数，下标对应的值表示所在列数。
例如：4皇后的一个解（3,1,4,2）表示的答案是：
（3,1,4,2）对应的答案
·判断函数：判断数组中某个位置的值是否合法（合法即表示跟已有答案不在同一列，且不在一条斜线上），
若合法，函数返回true，否则就返回false。
代码：
判断函数
·核心算法：首先要有一个大小为17的一维数组（因为java语言的下标是从1开始的），
和一个计数器i，用于表示当前要计算哪个下标上的数字。
步骤如下：
1、数组中的每一个元素都要从1开始试数，如果判断函数返回当前数合法，则计数器+1，
如果一直到16都没有合法的数，则计数器-1。
2、重复步骤1方法，直至计数器到达16。我们就得到了一个答案。
3、重复步骤1和2，直至计数器小于1，就可以得出所有答案。
代码：
·改进：上述算法跑出所有的答案需要180-190秒左右（cpu:intel i5）。
我们可以把所有答案分为16组，即：
第一个元素摆在第一列的为一组，
第一个元素摆在第二列的为一组
...
第一个元素摆在第16列的为一组。
考虑到答案的对称性，我们又可以把分组减为8组。
事实上，我们只要算出前八组可以得到所有答案。
而这些组的计算并不互相依赖，在这样的前提下，每一组答案都可以单独开一个线程来计算，
那么计算的耗时就是耗时最长的线程的耗时。
而且由于数组的第一个元素已经赋值，使得每一个答案的得出都减少了一次循环。
线程代码：
线程
同样运行环境下，随着每组答案的个数的增多，耗时也增加。
统计结果如下：
第一个元素及倒数第一个元素摆放在第1列的答案的个数有：872456个，耗时20s
第一个元素及倒数第一个元素摆放在第2列的答案的个数有：1139062个，耗时22s
...
第一个元素及倒数第一个元素摆放在第8列的答案的个数有：2581662个，耗时30s
总答案为14772512个。
按理论来说，每个线程是不会互相干扰，所以总耗时应该是耗时最长的线程的耗时，即30s左右。但是在主函数中，我循环new出16个线程来计算的时候，每一个线程的时间却大大增加。最大的增加到88s-95s左右，所以整个计算过程居然耗时90s左右。好费解啊！
网友评论