日期:2014-05-18  浏览次数:20460 次

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 union
select 0

--将tb表做64次笛卡尔积,产生所有的可能类型
--根据估算,一共有2的64次方种可能,每一种可能在表c中用64个tinyint型的字段保存
--无法保存所有的可能(大约1073741824T)
--一下语句先做迪卡积,然后从结果中筛选
insert into c
select * 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 c64
from
tb 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