八皇后问题
求独立解
编辑
Python语言
编辑
下面采用Python语言在致力保持不可变性原则下，生成八皇后问题的12个独立解：
def queens(n):
def q(pl, r):
def place(c):
return r+c not in pl[1] and r-c not in pl[2]
return ((pl[0]+[c], pl[1]|{r+c}, pl[2]|{r-c}, pl[3]-{c})
for c in pl[3] if place(c))
def pipeline(pl, i):
for ipl in q(pl, i):
if i+1 < n:
yield from pipeline(ipl, i+1)
else:
yield ipl[0]
def toletter(x):
return 'abcdefghijklmnopqrstuvwxyz'[x]
def fund_solut(fl):
def inversed(xl):
return (xl.index(i) for i in range(0, n))
def variants(xl):
rl = [xl]
rl += [[*inversed(x)] for x in rl]
rl += [[*reversed(x)] for x in rl]
rl += [[n-1-i for i in x] for x in rl]
return (''.join(toletter(i) for i in x) for x in rl)
rs = set()
for i in fl:
ks = {*variants(i)}
if rs.isdisjoint(ks):
rs |= ks
yield i
for i in fund_solut(
pipeline(([], set(), set(), {*range(0, n)}), 0)):
rl = sorted(toletter(v)+str(k+1) for k, v in enumerate(i))
print(rl)
queens(8)
这里的算法核心环节是生成器委托yield from。将这段代码保存入queens.py文件中，下面演示其执行结果：
$ python3 ./queens.py
['a1', 'b7', 'c5', 'd8', 'e2', 'f4', 'g6', 'h3']
['a1', 'b7', 'c4', 'd6', 'e8', 'f2', 'g5', 'h3']
['a6', 'b1', 'c5', 'd2', 'e8', 'f3', 'g7', 'h4']
['a4', 'b1', 'c5', 'd8', 'e2', 'f7', 'g3', 'h6']
['a5', 'b1', 'c8', 'd4', 'e2', 'f7', 'g3', 'h6']
['a3', 'b1', 'c7', 'd5', 'e8', 'f2', 'g4', 'h6']
['a5', 'b1', 'c4', 'd6', 'e8', 'f2', 'g7', 'h3']
['a7', 'b1', 'c3', 'd8', 'e6', 'f4', 'g2', 'h5']
['a5', 'b1', 'c8', 'd6', 'e3', 'f7', 'g2', 'h4']
['a5', 'b3', 'c1', 'd7', 'e2', 'f8', 'g6', 'h4']
['a5', 'b7', 'c1', 'd4', 'e2', 'f8', 'g6', 'h3']
['a6', 'b3', 'c1', 'd8', 'e4', 'f2', 'g7', 'h5']
jq语言
编辑
下面采用纯函数式编程语言jq，生成八皇后问题的12个独立解：
def queens(n):
def q: . as $pl
| $pl[4] as $r
| $pl[3] as $cl | $cl[] | . as $c
| ($r+$c | tostring) as $k0
| ($r-$c | tostring) as $k1
| def place:
($k0 | in($pl[1]) | not)
and ($k1 | in($pl[2]) | not);
select(place)
| [$pl[0]+[$c], $pl[1]+{$k0:null},
$pl[2]+{$k1:null}, $cl-[$c], $r+1];
def pipeline(n):
q | if n > 1 then pipeline(n-1) end;
def toletter:
"abcdefghijklmnopqrstuvwxyz"[.:.+1];
def fund_solut(f):
def inverse: . as $xl
| reduce range(0; n) as $i
([]; .+[$xl | index($i)]);
def variants:
[., inverse] | map(., reverse)
| map(., map(n-1-.))
| map(map(toletter) | add);
foreach f as $i
([null, {}]; .[1] as $ml
| ($i | variants) as $nl
| if all($nl[]; in($ml) | not) then
[$i, ($ml | .[$nl[]]=null)]
else
[null, $ml] end;
.[0])
| select (. != null);
fund_solut([[], {}, {}, [range(0; n)], 0]
| pipeline(n) | .[0])
| map(toletter) | to_entries
| map(.value+(.key+1 | tostring)) | sort;
queens(8)
这里的算法核心环节是管道机制。将这段代码保存入queens.jq文件中，下面演示其执行结果：
$ jq -nc -f ./queens.jq
["a1","b7","c5","d8","e2","f4","g6","h3"]
["a1","b7","c4","d6","e8","f2","g5","h3"]
["a6","b1","c5","d2","e8","f3","g7","h4"]
["a4","b1","c5","d8","e2","f7","g3","h6"]
["a5","b1","c8","d4","e2","f7","g3","h6"]
["a3","b1","c7","d5","e8","f2","g4","h6"]
["a5","b1","c4","d6","e8","f2","g7","h3"]
["a7","b1","c3","d8","e6","f4","g2","h5"]
["a5","b1","c8","d6","e3","f7","g2","h4"]
["a5","b3","c1","d7","e2","f8","g6","h4"]
["a5","b7","c1","d4","e2","f8","g6","h3"]
["a6","b3","c1","d8","e4","f2","g7","h5"]
求可行解
编辑
Icon语言
编辑
下面采用Icon语言，生成八皇后问题的92个可行解：
global n
procedure main()
local i, r, s, u, v, x
n := 8
s := "abcdefghijklmnopqrstuvwxyz"
every x := pipeline(1) do {
r := []
every i := 1 to n do put(r, s[x[i]] || i)
u := sort(r)
v := get(u)
every v ||:= "," || !u
write(v)
}
end
procedure pipeline(i)
if i < n then
suspend [q(i)] ||| pipeline(i+1)
else
suspend [q(i)]
end
procedure q(r)
suspend place(r, 1 to n)
end
procedure place(r, c)
static col, up, down
initial {
col := list(n, 0)
down := list(n*2-1, 0)
up := list(n*2-1, 0)
}
if col[c] = 0 = down[r+c-1] = up[r-c+n] then
suspend col[c] <- down[r+c-1] <- up[r-c+n] <- c
end
这里的算法核心环节是可逆赋值运算<-。将这段代码保存入queens.icn文件中，下面演示其执行结果并提取其92个解中的前两个解：
$ icon ./queens.icn | wc -l
92
$ icon ./queens.icn | sed -n '1,2p'
a1,b7,c5,d8,e2,f4,g6,h3
a1,b7,c4,d6,e8,f2,g5,h3
Python语言
编辑
下面采用Python语言基于共享变量，生成八皇后问题的92个可行解：
def queens(n):
col = [False]*n
down = [False]*(n*2-1)
up = [False]*(n*2-1)
def q(r):
def place(c):
return col[c] == False == down[r+c] == up[r-c]
for c in range(0, n):
if place(c):
col[c] = down[r+c] = up[r-c] = True
yield [c]
col[c] = down[r+c] = up[r-c] = False
def pipeline(i):
for r in q(i):
if i+1 < n:
for s in pipeline(i+1):
yield r + s
else:
yield r
def toletter(x):
return 'abcdefghijklmnopqrstuvwxyz'[x]
for i in (pipeline(0)):
rl = sorted(toletter(v)+str(k+1)
for k, v in enumerate(i))
print(rl)
queens(8)
这里的算法核心环节是在生成器之间共享静态变量。将这段代码保存入queens.py文件中，下面演示其执行结果并提取其92个解中的前两个解：
$ python3 ./queens.py | wc -l
92
$ python3 ./queens.py | sed -n '1,2p'
['a1', 'b7', 'c5', 'd8', 'e2', 'f4', 'g6', 'h3']
['a1', 'b7', 'c4', 'd6', 'e8', 'f2', 'g5', 'h3']
这个算法在8个横行上执行纵列选择函数q(r)的次数分别为：[1, 8, 42, 140, 344, 568, 550, 312]，共计1965次，q(r)在每个横行上针对纵列执行函数place(c)的次数都是8，每横行的选择数分别为：[8, 64, 336, 1120, 2752, 4544, 4400, 2496]，总计15720次，其中每横行的成功存乎最终结果者之数分别为：[8, 36, 62, 80, 90, 90, 92, 92]，总计550个。
可以进一步将其写为下面的Python代码，其执行方式和结果同于前述：
def queens(n):
cs = [0]*n
cl = [*range(0, n)]
down = [False]*(n*2-1)
up = [False]*(n*2-1)
def q(r):
def place(c):
return down[r+c] == False == up[r-c]
for i, c in enumerate(cl):
if place(c):
cs[r] = c
del cl[i]
down[r+c] = up[r-c] = True
yield None
cl.insert(i, c)
down[r+c] = up[r-c] = False
def pipeline(i):
for _ in q(i):
if i+1 < n:
yield from pipeline(i+1)
else:
yield cs
def toletter(x):
return 'abcdefghijklmnopqrstuvwxyz'[x]
for i in (pipeline(0)):
rl = sorted(toletter(v)+str(k+1)
for k, v in enumerate(i))
print(rl)
queens(8)
这个算法在8个横行上执行纵列选择函数q(r)的次数分别为：[1, 8, 42, 140, 344, 568, 550, 312]，共计1965次，q(r)在8个横行上针对纵列执行函数place(c)的次数分别为：[8, 7, 6, 5, 4, 3, 2, 1]，每横行的选择数分别为：[8, 56, 252, 700, 1376, 1704, 1100, 312]，总计5508次，其中每横行的成功存乎最终结果者之数分别为：[8, 36, 62, 80, 90, 90, 92, 92]，总计550个。
下面将其写为过程式Python代码，其执行方式和结果同于前述：
def queens(n):
cs = [0]*n
cl = [*range(0, n)]
down = [False]*(n*2-1)
up = [False]*(n*2-1)
rl = ['']*n
toletter = lambda x: \
'abcdefghijklmnopqrstuvwxyz'[x]
def q(r):
if r < n:
for i, c in enumerate(cl):
if down[r+c] == False == up[r-c]:
cs[r] = c
del cl[i]
down[r+c] = up[r-c] = True
q(r+1)
cl.insert(i, c)
down[r+c] = up[r-c] = False
else:
for k, v in enumerate(cs):
rl[k] = toletter(v)+str(k+1)
print(sorted(rl))
q(0)
queens(8)
最后将其写为指令式Python代码，其执行方式和结果同于前述：
def queens(n):
cs = [0]*n
ps = [0]*n
cl = [*range(0, n)]
down = [False]*(n*2-1)
up = [False]*(n*2-1)
rl = ['']*n
toletter = lambda x: \
'abcdefghijklmnopqrstuvwxyz'[x]
r = 0
while r >= 0:
p = ps[r]
if p != 0:
c = cs[r]
cl.insert(p-1, c)
down[r+c] = up[r-c] = False
for i, c in enumerate(cl[p:]):
if down[r+c] == False == up[r-c]:
cs[r] = c
ps[r] = p+i+1
break
if p != ps[r]:
del cl[p+i]
down[r+c] = up[r-c] = True
r += 1
else:
ps[r] = 0
r -= 1
if r == n:
for k, v in enumerate(cs):
rl[k] = toletter(v)+str(k+1)
print(sorted(rl))
r -= 1
queens(8)
C语言
编辑
下面是求解n皇后的C代码，在程序中可以自己设置n个皇后以及选择是否打印出具体解。
#include
#define QUEENS 8 /*皇后数量*/
#define IS_OUTPUT 1 /*(IS_OUTPUT=0 or 1)，Output用于选择是否输出具体解,为1输出，为0不输出*/
int A[QUEENS + 1], B[QUEENS * 3 + 1], C[QUEENS * 3 + 1], k[QUEENS + 1][QUEENS + 1];
int inc, *a = A, *b = B + QUEENS, *c = C;
void lay(int i)
{
int j = 0, t, u;
while (++j <= QUEENS)
if (a[j] + b[j - i] + c[j + i] == 0) {
k[i][j] = a[j] = b[j - i] = c[j + i] = 1;
if (i < QUEENS) lay(i + 1);
else {
++inc;
if (IS_OUTPUT) {
for (printf("(%d)\n", inc), u = QUEENS + 1; --u; printf("\n"))
for (t = QUEENS + 1; --t; ) k[t][u] ? printf("Q ") : printf("+ ");
printf("\n\n\n");
}
}
a[j] = b[j - i] = c[j + i] = k[i][j] = 0;
}
}
int main(void)
{
lay(1);
printf("%d皇后共计%d个解\n", QUEENS, inc);
return 0;
}
使用回溯法进行求解八皇后问题
#include
#define PRINTF_IN 1 //定义是否打印，1：打印，0：不打印
int queens(int Queens)
{
int i, k, flag, not_finish=1, count=0;
//正在处理的元素下标，表示前i-1个元素已符合要求，正在处理第i个元素
int a[Queens+1]; //八皇后问题的皇后所在的行列位置，从1幵始算起，所以加1
i=1;
a[1]=1; //为数组的第一个元素赋初值
printf("%d皇后的可能配置是:",Queens);
while(not_finish){ //not_finish=l:处理尚未结束
while(not_finish && i<=Queens){ //处理尚未结束且还没处理到第Queens个元素
for(flag=1,k=1; flag && k if(a[k]==a[i]) flag=0; for (k=1; flag&&k if( (a[i]==a[k]-(k-i)) || (a[i]==a[k]+(k-i)) ) flag=0; if(!flag){ //若存在矛盾不满足要求，需要重新设置第i个元素 if(a[i]==a[i-1]){ //若a[i]的值已经经过一圈追上a[i-1]的值 i--; //退回一步，重新试探处理前一个元素 if(i>1 && a[i]==Queens) a[i]=1; //当a[i]为Queens时将a[i]的值置1 else if(i==1 && a[i]==Queens) not_finish=0; //当第一位的值达到Queens时结束 else a[i]++; //将a[il的值取下一个值 }else if(a[i] == Queens) a[i]=1; else a[i]++; //将a[i]的值取下一个值 }else if(++i<=Queens) if(a[i-1] == Queens ) a[i]=1; //若前一个元素的值为Queens则a[i]=l else a[i] = a[i-1]+1; //否则元素的值为前一个元素的下一个值 } if(not_finish){ ++count; if(PRINTF_IN){ printf((count-1)%3 ? " [%2d]:" : "\n[%2d]:", count); for(k=1; k<=Queens; k++) //输出结果 printf(" %d", a[k]); } if(a[Queens-1] a[Queens-1]++; //修改倒数第二位的值 else a[Queens-1]=1; i=Queens -1; //开始寻找下一个满足条件的解 } } return count; } int main() { int Num ; printf("输入一个N皇后数值："); scanf("%d" , &Num); printf("\n%d皇后有%d种配置\n",Num,queens(Num)); } Pascal语言 编辑 以下列出尼克劳斯·维尔特的Pascal语言程序[6]。此程序找出了八皇后问题的一个解。 program eightqueen1(output); var i : integer; q : boolean; a : array[ 1 .. 8] of boolean; b : array[ 2 .. 16] of boolean; c : array[ -7 .. 7] of boolean; x : array[ 1 .. 8] of integer; procedure try( i : integer; var q : boolean); var j : integer; begin j := 0; repeat j := j + 1; q := false; if a[ j] and b[ i + j] and c[ i - j] then begin x[ i ] := j; a[ j ] := false; b[ i + j] := false; c[ i - j] := false; if i < 8 then begin try( i + 1, q); if not q then begin a[ j] := true; b[ i + j] := true; c[ i - j] := true; end end else q := true end until q or (j = 8); end; begin for i := 1 to 8 do a[ i] := true; for i := 2 to 16 do b[ i] := true; for i := -7 to 7 do c[ i] := true; try( 1, q); if q then for i := 1 to 8 do write( x[ i]:4); writeln end. Java语言 编辑 使用回溯法进行求解八皇后问题(Java版本)，可直接复制到N-Queens - LeetCode[7]测试。 class Solution { public List List // 使用 char[][] 是为了展示结果时，直接使用 new String(char[])。 // 一般情况下，使用 boolean[][] 即可。 char[][] result = new char[n][n]; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { result[i][j] = '.'; } } backtrack(results, result, 0); return results; } private static void backtrack(List for (int j = 0; j < result.length; ++j) { if (isValid(result, x, j)) { result[x][j] = 'Q'; if (x == result.length - 1) { showResult(results, result); // 可以直接 break } else { // 皇后问题中，不会出现一行出现多个，所以直接跳到下一行 backtrack(results, result, x + 1); } result[x][j] = '.'; } } } private static boolean isValid(char[][] result, int x, int y) { // ... (0, y) // ... ...... // ... (x-1, y) // ... (x, y) for (int i = 0; i < x; ++i) { if (result[i][y] == 'Q') { return false; } } // ... // ... (x-1, y-1) // ... .......... (x, y) for (int i = x - 1, j = y - 1; i >= 0 && j >= 0; --i, --j) { if (result[i][j] == 'Q') { return false; } } // ... // ... ...... (x-1, y+1) // ... (x, y) for (int i = x - 1, j = y + 1; i >= 0 && j < result.length; --i, ++j) { if (result[i][j] == 'Q') { return false; } } return true; } private static void showResult(List List for (char[] value : result) { list.add(new String(value)); } results.add(list); } } C++语言 编辑 #include "iostream" #include "cmath" using namespace std; #define Max 20 //定義棋盤的最大值 int a[Max]; int show(int S) //定義出函數 { int i,p,q; int b[Max][Max]={0}; //定義且初始化b[1][]輸出模組 for(i=1;i<=S;i++) //按橫列順序輸出a[i]的座標 { b[i][a[i]]=1; printf("(%d,%d)\t",i,a[i]); } printf("\n"); for(p=1;p<=S;p++) //按棋盤的橫列的順序標明的位置 { for(q=1;q<=S;q++) { if(b[p][q]==1) //在第p行第q列放置一顆棋子 printf("x"); else printf("o"); } printf("\n"); } return 0; } int check(int k) //定義check函數 { int i; for(i=1;i { if((a[i]==a[k]) || (a[i]-a[k]==k-i)|| (a[i]-a[k]==i-k) ) //檢查是否有多顆棋子在同一個直行上 { return 0; } } return 1; } void check_m(int num) //定義函數 { int k=1,count=0; printf("N皇后問題的所有解(包含經由旋轉的解):\n"); a[k]=1; while(k>0) { if(k<=num && a[k]<=num) //從第k行第一列的位置開始，尋找之後的棋子的位置 { if(check(k)==0) //第k行的a[k]列不能放置棋子 { a[k]++; //繼續試探該前行的下一列：a[k+1] } else { k++; //第K行的位置已經確定完畢，繼續尋找第k+1行棋子的位置 a[k]=1; //從第k+1的第一列開始查找 } } else { if(k>num) //若滿足輸出數組的要求就輸出該數組 { count++; printf("[%d]: ",count); show(num); //調用輸出函數show() } k--; //棋子位置不符合要求則退回前一步 a[k]++; //繼續尋找下一列位置 } } printf("總共有 %d \n",count,"個"); } int main(void) { int N,d; do { printf(" N皇后問題的解(N<20) \n"); printf("請輸入N的值：_"); scanf("%d",&N); printf("\n"); if(N>0&&N<20) { check_m(N); break; } else { printf("輸入錯誤，請重新輸入"); printf("\n\n"); break; } } while(1); system("pause"); return 0; }