首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 数据库 > SQL Server >

8皇后有关问题的select解法

2012-01-24 
8皇后问题的select解法8皇后问题简单描述就是8*8的棋盘上每个方向上最多只有一个棋子,对于这种需要穷举的

8皇后问题的select解法
8皇后问题简单描述就是8*8的棋盘上每个方向上最多只有一个棋子,对于这种需要穷举的问题,一般都是递归,一个位置一个位置的试。现在给大家介绍一种简单,直观,高效的select 解法。
  给棋盘上每一个位置从1开始编号,一直可以编到64.一个有多少种可能呢?2的64次方。最初是想先把这些可能全保存在一张表里,字段有64个,用占内存最小的数据类型(tinyint byte),后来计算发现,这是不可能的的任务。
  每一种可能的组合要占用64字节,一共有2的64次方中可能,那就是18446744073709551616*64字节,1073741824T!。假设有这样大的盘,改盘每秒写1T的数据,那也要12427天。当时算到这里想放弃了。后来突然想到如果不保存,直接组合sql语句来计算会怎么样呢?select * from (select ...) a where ...。a表产生所有可能的组合。这些组合用cross join 来产生。
先建一个表,字段一个,tinyint类型,保存0和1,然后用该表和自己做64次的cross join.写起来很长,但是看着很简单,当然,这么长肯定不想用手写,写段代码组合字符串吧。这样书写的问题就解决了。下面是具体的sql语句。后面的组合字符串的代码有些有点问题,会漏掉几个c,不过不多,我直接在select 语句中加上了,那些代码不想改了。后来又想了一下,横和竖的in(0,1)应该为=1.估计用的时间会更少。有兴趣的朋友可以试一下。

SQL code
--该表保存结果create table c(c1 tinyint, c2 tinyint, c3 tinyint, c4 tinyint, c5 tinyint, c6 tinyint, c7 tinyint, c8 tinyint, c9 tinyint, c10 tinyint, c11 tinyint, c12 tinyint, c13 tinyint, c14 tinyint, c15 tinyint, c16 tinyint, c17 tinyint, c18 tinyint, c19 tinyint, c20 tinyint, c21 tinyint, c22 tinyint, c23 tinyint, c24 tinyint, c25 tinyint, c26 tinyint, c27 tinyint, c28 tinyint, c29 tinyint, c30 tinyint, c31 tinyint, c32 tinyint, c33 tinyint, c34 tinyint, c35 tinyint, c36 tinyint, c37 tinyint, c38 tinyint, c39 tinyint, c40 tinyint, c41 tinyint, c42 tinyint, c43 tinyint, c44 tinyint, c45 tinyint, c46 tinyint, c47 tinyint, c48 tinyint, c49 tinyint, c50 tinyint, c51 tinyint, c52 tinyint, c53 tinyint, c54 tinyint, c55 tinyint, c56 tinyint, c57 tinyint, c58 tinyint, c59 tinyint, c60 tinyint, c61 tinyint, c62 tinyint, c63 tinyint, c64 tinyint)--该表做笛卡尔积create table tb(t tinyint)insert into tb select 1 unionselect 0--将tb表做64次笛卡尔积,产生所有的可能类型--根据估算,一共有2的64次方种可能,每一种可能在表c中用64个tinyint型的字段保存--无法保存所有的可能(大约1073741824T)--一下语句先做迪卡积,然后从结果中筛选insert into cselect * from(select tb1.t c1 ,tb2.t c2 ,tb3.t c3 ,tb4.t c4 ,tb5.t c5 ,tb6.t c6 ,tb7.t c7 ,tb8.t c8 ,tb9.t c9 ,tb10.t c10,tb11.t c11,tb12.t c12,tb13.t c13,tb14.t c14,tb15.t c15,tb16.t c16,tb17.t c17,tb18.t c18,tb19.t c19,tb20.t c20,tb21.t c21,tb22.t c22,tb23.t c23,tb24.t c24,tb25.t c25,tb26.t c26,tb27.t c27,tb28.t c28,tb29.t c29,tb30.t c30,tb31.t c31,tb32.t c32,tb33.t c33,tb34.t c34,tb35.t c35,tb36.t c36,tb37.t c37,tb38.t c38,tb39.t c39,tb40.t c40,tb41.t c41,tb42.t c42,tb43.t c43,tb44.t c44,tb45.t c45,tb46.t c46,tb47.t c47,tb48.t c48,tb49.t c49,tb50.t c50,tb51.t c51,tb52.t c52,tb53.t c53,tb54.t c54,tb55.t c55,tb56.t c56,tb57.t c57,tb58.t c58,tb59.t c59,tb60.t c60,tb61.t c61,tb62.t c62,tb63.t c63,tb64.t c64fromtb tb1  cross join tb tb2 cross join tb tb3 cross join tb tb4 cross join tb tb5 cross join tb tb6 cross join tb tb7 cross join tb tb8 cross join tb tb9 cross join tb tb10 cross join tb tb11 cross join tb tb12 cross join tb tb13 cross join tb tb14 cross join tb tb15 cross join tb tb16 cross join tb tb17 cross join tb tb18 cross join tb tb19 cross join tb tb20 cross join tb tb21 cross join tb tb22 cross join tb tb23 cross join tb tb24 cross join tb tb25 cross join tb tb26 cross join tb tb27 cross join tb tb28 cross join tb tb29 cross join tb tb30 cross join tb tb31 cross join tb tb32 cross join tb tb33 cross join tb tb34 cross join tb tb35 cross join tb tb36 cross join tb tb37 cross join tb tb38 cross join tb tb39 cross join tb tb40 cross join tb tb41 cross join tb tb42 cross join tb tb43 cross join tb tb44 cross join tb tb45 cross join tb tb46 cross join tb tb47 cross join tb tb48 cross join tb tb49 cross join tb tb50 cross join tb tb51 cross join tb tb52 cross join tb tb53 cross join tb tb54 cross join tb tb55 cross join tb tb56 cross join tb tb57 cross join tb tb58 cross join tb tb59 cross join tb tb60 cross join tb tb61 cross join tb tb62 cross join tb tb63 cross join tb tb64) a where --横c1 +c2 +c3 +c4 +c5 +c6 +c7 +c8  in(0,1) and c9 +c10+c11+c12+c13+c14+c15+c16 in(0,1) and c17+c18+c19+c20+c21+c22+c23+c24 in(0,1) and c25+c26+c27+c28+c29+c30+c31+c32 in(0,1) and c33+c34+c35+c36+c37+c38+c39+c40 in(0,1) and c41+c42+c43+c44+c45+c46+c47+c48 in(0,1) and c49+c50+c51+c52+c53+c54+c55+c56 in(0,1) and c57+c58+c59+c60+c61+c62+c63+c64 in(0,1) and--竖c1 +c9 +c17+c25+c33+c41+c49+c57 in(0,1) and c2 +c10+c18+c26+c34+c42+c50+c58 in(0,1) and c3 +c11+c19+c27+c35+c43+c51+c59 in(0,1) and c4 +c12+c20+c28+c36+c44+c52+c60 in(0,1) and c5 +c13+c21+c29+c37+c45+c53+c61 in(0,1) and c6 +c14+c22+c30+c38+c46+c54+c62 in(0,1) and c7 +c15+c23+c31+c39+c47+c55+c63 in(0,1) and c8 +c16+c24+c32+c40+c48+c56+c64 in(0,1) and--左斜c1  in(0,1) and c16+c23+c30+c37+c44+c51+c58 in(0,1) and c2 +c9  in(0,1) and c24+c31+c38+c45+c52+c59 in(0,1) and c3 +c10+c17 in(0,1) and c32+c39+c46+c53+c60 in(0,1) and c4 +c11+c18+c25 in(0,1) and c40+c47+c54+c61 in(0,1) and c5 +c12+c19+c26+c33 in(0,1) and c48+c55+c62 in(0,1) and c6 +c13+c20+c27+c34+c41 in(0,1) and c56+c63 in(0,1) and c7 +c14+c21+c28+c35+c42+c49 in(0,1) and c64 in(0,1) and c8 +c15+c22+c29+c36+c43+c50+c57 in(0,1)  and--右斜c1 +c10+c19+c28+c37+c46+c55+c64 in(0,1) and c9 +c18+c27+c36+c45+c54+c63 in(0,1) and c2 +c11+c20+c29+c38+c47+c56 in(0,1) and c17+c26+c35+c44+c53+c62 in(0,1) and c3 +c12+c21+c30+c39+c48 in(0,1) and c25+c34+c43+c52+c61 in(0,1) and c4 +c13+c22+c31+c40 in(0,1) and c33+c42+c51+c60 in(0,1) and c5 +c14+c23+c32 in(0,1) and c41+c50+c59 in(0,1) and c6 +c15+c24 in(0,1) and c49+c58 in(0,1) and c7 +c16 in(0,1) and c57 in(0,1) and c8  in(0,1)  and--八皇后c1+c2+c3+c4+c5+c6+c7+c8+c9+c10+c11+c12+c13+c14+c15+c16+c17+c18+c19+c20+c21+c22+c23+c24+c25+c26+c27+c28+c29+c30+c31+c32+c33+c34+c35+c36+c37+c38+c39+c40+c41+c42+c43+c44+c45+c46+c47+c48+c49+c50+c51+c52+c53+c54+c55+c56+c57+c58+c59+c60+c61+c62+c63+c64=8--00:00:36  (92 行受影响) 


   
   
   


[解决办法]
吱吱.
[解决办法]
强悍 学习..
[解决办法]
探讨
帖子内容太长。
我的沙发。


SQL code
--
--以下语句打印结果
declare cur cursor for select * from c
declare @c1 int, @c2 int, @c3 int, @c4 int, @c5 int, @c6 int, @c7 int, @c8 int, @c9 int, @c10 int, @c11 ……

[解决办法]
算法?接分.
[解决办法]
看头晕,关注。
[解决办法]

[解决办法]
JF...
[解决办法]
lz,八皇后剪枝后挺快的,有专门的算法,建议lz找相关的书看一看。符合条件的组合必为全排列的一种情况,枚举8!次。逐步枚举时继续剪枝,例如第一行为选了1,第二行选2,第三到第八行就不需要再算了,像这样剪枝后效率灰快。不会sql,不知道合不合用,所以以上仅供参考
[解决办法]
顶楼主一个。
[解决办法]
顶楼主一个。
[解决办法]
来了接分,莫急~
[解决办法]
强大!
[解决办法]
good
[解决办法]
吱吱.
[解决办法]
先帮顶,晚上再研究。
[解决办法]
棋盘用一个64bit的数据存储就可以了
组合数也不过8的8次方而已
8KB*8^8/1024/1024 = 64MB
[解决办法]
强悍啊,学习了。
[解决办法]
太牛了,学习
[解决办法]
强悍 学习..
[解决办法]
太强了。呵呵
[解决办法]
厉害,学习了
[解决办法]
不错的想法,很有意思,学习了!!
[解决办法]
犀利。

热点排行