N个女人的老死不相往来——n皇后问题

知乎问题链接:如何用C++10行内写出八皇后

前日闲暇之余乱逛,看到了这个问题,觉得蛮有意思。
也顺便想改进一下通行的官方解法,就认真写了一下,
顺便也把自己作为外行人的一点感想列在下面。

n皇后问题,较早为八皇后问题,出现于1848年。
Max Bezzel讨论的是“在国际象棋上出现8个后时,
应该如何排列,才可使她们不会相爱相杀。”

(八皇后问题的其中一个解)

虽然依照升变原则,同棋盘上可以出现17个后,
(一方全升变,一方被吃过路兵一次,加上初始两个)
但是真正走出来的可能性是微乎其微的。
况且这个问题没有考虑黑白方关系,
在象棋上也就是趣味的一问而已。
——直到图论和函数式编程思想出现,
穷举法和递归思想使得92个解终于呼之即出。

前面说到,n皇后问题的解法都是穷举法及递归,
加上回溯算法实现。这对于刚入门的傻喵来讲,
是很好的练习题目了——

' n queens cast by go basic
[loop]
input "How many queens (N>=4)";n
if n < 4 then
 print "Must be greater than 4"
 goto [loop]
end if
 
dim plot$(100,100)
dim q(n+20)
dim e(n+20)
dim o(n+20)
r=n mod 6
if r<>2 and r<>3 then 
  gosub [samp]
  goto [shoBoard]
end if
for i=1 to int(n/2)
  e(i) = 2 * i
next
for i=1 to int((n/2)+.5)
 o(i) = 2 *i-1
next
if r = 2 then gosub [edt2]
if r = 3 then gosub [edt3]
s = 1
for i=1 to n
  if e(i)>0 then 
    q(s) = e(i)
    s    = s+1
  end if
next
for i=1 to n
  if o(i) > 0 then 
    q(s) = o(i)
    s    = s + 1
  end if
next
' print board
[shoBoard]
cls
for i = 1 to n
  plot$(i,26-q(i)) = "*"
  plot$(i,24-n)    = chr$(96+i)
  plot$(n+1,26-i)  = str$(i)
next i
for ii = 1 to 100
 for jj = 1 to 100
  print left$(plot$(jj,ii)+" ",1);
 next jj
print
next ii
end
 
' the simple case
[samp] 
p = 1
for i = 1 to n
  if i mod 2=0 then 
    q(p) = i
    p    = p + 1
  end if
next i
for i = 1 to n
  if i mod 2 then 
    q(p) = i
    p    = p + 1
  end if
next
return
' edit list when remainder is 2
[edt2]
for i=1 to n
  if o(i) = 3 then 
    o(i) = 1 
   else 
    if o(i)=1 then o(i) = 3
  end if
  if o(i) = 5 then 
    o(i)= o(i) -1 
   else 
    if o(i) = 0 then 
      o(i) = 5
      return
    end if
  end if
next
 
' edit list when remainder is 3
[edt3]
for i = 1 to n
  if e(i) = 2 then 
    e(i)  = e(i)-1 
   else 
    if e(i) = 0 then 
      e(i) = 2
      goto [more]
    end if
  end if
next i
' edit list some more
[more]
for i = 1 to n
  if (o(i)=1 or o(i)=3) then 
    o(i) = o(i)-1 
   else 
    if o(i) = 0 then 
      o(i)   = 1
      o(i+1) = 3
      return
    end if
  end if
next

或是这样的尝试——

# Brute force permutations for 8 queens by R

safe <- function(p) {
  n <- length(p)
  for (i in seq(1, n - 1)) {
    for (j in seq(i + 1, n)) {
      if (abs(p[j] - p[i]) == abs(j - i)) return(F)
    }
  }
  return(T)
}
 
queens <- function(n) {
  p <- 1:n
  k <- 0
  while (!is.null(p)) {
    if(safe(p)) {
      cat(p, "\n")
      k <- k + 1
    }
    p <- next.perm(p)
  }
  return(k)
}
 
queens(8)

在好多人的口中,递归+穷举已然成为了8皇后问题的标准答案。
但是时代还是会变的,人的能力也是在随着问题进步的。
当面临N皇后问题时,传统的方法则捉襟见肘。

虽然有人推荐直接向上抽象,利用已有的库来简化方法,
但是私以为,练习归练习,学习归学习,但不能只会做一个传道者,
迷信工具,迷信顶层,而没有透彻的基础认识。
工具看了手册谁都会用,为什么用,怎么用,好不好则更加重要。
就像是学习语言或是诊断学,迷信书本只知所以然是万万不可的。
——只会利用工具的人,终究会被工具抛弃。

回到问题上来。

N皇后问题中,穷举法的复杂度为(n!),
但若是采用和某些逻辑题一样的算法,则可以大大简化代码。

首先,国际象棋的后拥有两种攻击方式:
好似城堡的十字攻击以及骑士的对角攻击,攻击范围无限制:

从而得出两个预结论——
1 N皇后于NxN棋盘上,若老死不相往来,则绝不在同一行列。
2 攻击范围有重叠时,绝非边与边重叠,只可相交,且相交仅会出现一次。
于是便可以将棋盘格子赋予是否安全的属性,1为受到攻击位置,0安全。
从第一条边向第八条边推进,标注所有可能的攻击位置,发现0则置子,
发现一个以上的安全位置,则从一个方向起下子,深度优先遍历。

于是使用位运算,将n~1横列化为n个二进制数,指定0位安全;
由预结论1,不考虑所下子横行上的攻击(下子后必然全为1);
由预结论1,copy下子所在竖列的状态至下一行;
利用位移运算符定义两种对角攻击模式。
以上图第4横行为例,下子状态标注为 0001 0000
(计算第5横行时,下子状态保留为 0001 0000,
攻击范围则将下子状态左移/右移一位,
分别是 0010 0000 和 0000 1000。
将三个状态列取或运算,则结果中的0位为安全位置。

于是——

#include <iostream>

// total:记录解;finishline:确认的行
int total = 0, finishline = 1;

// row:竖直攻击; ls:斜杠攻击; rs:反斜杠攻击
void trying(long row, long ls, long rs)
{
	if (row != finishline) // 开始新行
	{
		long position = finishline & ~(row | ls | rs);
		while(position) // 若行间无位可放...
		{
			long pointline = position & -position;
			position -= pointline;
			trying(row + pointline, (ls + pointline) << 1, (rs + pointline) >> 1);
		}
	}
	else 
	{
		total++;
	}
}

using namespace std;

int main(int argc, char *argv[]) {
	int grid = 8; // 修改grid的话,1~31皇后都能解w

finishline = (finishline << grid) - 1;

trying(0, 0, 0);

cout << total << endl;

return 0;

}

事就这么成了。

回到最早的知乎问题上去。我真的不明白为什么要限制行数,
而不是限制时间和内存,
但也因为这个问题看似哗众取宠,
便在想是不是某种形式的软广告。

不过最有意思的事情是问题下面百花齐放的代码。
有人简化变量名到一个字符,有人省略头文件,
有人把所有的东西挤成一行,自然注释都没有。
不用说美感,就连维护都是问题。
自己都看不懂了,就为了10行,图啥?
可谓是为完成任务而完成任务了的哗众取宠了。
还有人直接就import <8queens>,
抑或是贬损除了暴力枚举之外的其他算法,
真的是不知道什么逻辑了。

学习计算机科学到现在,傻喵越来越觉得,
好多东西都是如此相通的——
会用工具却拘泥于工具的人;
认为掌握工具便算精通的人;
知道规则便想创造规则的人;
末法心态的,实用主义的人。
希望我不会变成他们那样。。。

更愿意从数学汇编一步步学起,
就像当年从解剖学一步步学起,
就像当年从桥本文法开始学起,
就像当年从吹长音一步步学起,
这样,我想算是专业的负责吧。

不管。总之先把题答了——

#include <iostream>
int total = 0, finishline = 1;
void trying(long row, long ls, long rs){
if (row != finishline) { long position = finishline & ~(row | ls | rs);
while(position) { long pointline = position & -position; position -= pointline; trying(row + pointline, (ls + pointline) << 1, (rs + pointline) >> 1); }} else {total++;}} 
using namespace std;
int main(int argc, char *argv[]) {
int grid = 8; // 修改grid的话,1~31皇后都能解w
finishline = (finishline << grid) - 1; trying(0, 0, 0); cout << total << endl;
return 0;}

嗯。能看得懂,10行也就差不多这样了。

不过,如果八皇后问题真的会在项目里用到,
我则绝不会使用上面的所有程序,而会——

// 此处需使用八皇后算法,但忽略计算过程,仅使用答案节省时间。
// 八皇后解枚举数据头在******
void 8queensAnswers (0, 0, 0, 0)
//在里面做一个调用92个答案的接口,传参出去给大结构体
//保存各个答案类似于[91, 0, 4, 7, 5, 2, 6, 1, 3]这样
//或者n皇后的话[0,1][1,0][2,0][3,2][4,10][5,40]...这样

复杂度为1或是常数n,为啥不用?多好。

至于说怎么显示N皇后问题的解的话w
手动艾特@CocoaOikawa~

N皇后问题——记录下那些老死不相往来的N个女人的位置吧

以上ヾ(๑╹◡╹)ノ”

Leave a Reply

Your email address will not be published. Required fields are marked *