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个女人的位置吧

以上ヾ(๑╹◡╹)ノ”

One Reply to “N个女人的老死不相往来——n皇后问题”

  1. 来挖个千年老坟
    个人觉得,「上知天文、下知地理」确实是理想的知识结构,也是我自己所向往的目标。也许是因为我本科时所受教育思想的影响吧。
    但是对于使用工具改变世界的那些人来说,最重要的大概不是思想有多精妙、理解有多深刻吧。
    人类思想的火花可以十分绚烂,但那是少数人拥有的特权。大多数精妙绝伦令人叹为观止的算法实际上并不是一般人能随意发现的;也不可能要求所有人接触全新领域时都要先知根知底再开始行动。
    会有别的方法的,用普适性的工具找出特殊算法、替代专业知识的方法。我觉得人类的未来将会向这个方向发展。
    ——虽然就我个人而言,觉得有些遗憾便是了。

Leave a Reply to シズキ Cancel reply

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