|
N皇后问题
【题目】N皇后问题(含八皇后问题的扩展，规则同八皇后)：在N*N的棋盘上，放置N个皇后，要求每一横行每一列，每一对角线上均只能
放置一个皇后，问可能的方案及方案数。
const max=8;
var i,j:integer;
a:array[1..max] of 0..max; {放皇后数组}
b:array[2..2*max] of boolean; {/对角线标志数组}
c:array[-(max-1)..max-1] of boolean; {\对角线标志数组}
col:array[1..max] of boolean; {列标志数组}
total:integer; {统计总数}
procedure output; {输出}
var i:integer;
begin
write('No.':4,'[',total+1:2,']');
for i:=1 to max do write(a[i]:3);write(' ');
if (total+1) mod 2 =0 then writeln; inc(total);
end;
function ok(i,dep:integer):boolean; {判断第dep行第i列可放否}
begin
ok:=false;
if ( b[i+dep]=true) and ( c[dep-i]=true) {and (a[dep]=0)} and
(col[i]=true) then ok:=true
end;
procedure try(dep:integer);
var i,j:integer;
begin
for i:=1 to max do {每一行均有max种放法}
if ok(i,dep) then begin
a[dep]:=i;
b[i+dep]:=false; {/对角线已放标志}
c[dep-i]:=false; {\对角线已放标志}
col[i]:=false; {列已放标志}
if dep=max then output
else try(dep+1); {递归下一层}
a[dep]:=0; {取走皇后,回溯}
b[i+dep]:=true; {恢复标志数组}
c[dep-i]:=true;
col[i]:=true;
end;
end;
begin
for i:=1 to max do begin a[i]:=0;col[i]:=true;end;
for i:=2 to 2*max do b[i]:=true;
for i:=-(max-1) to max-1 do c[i]:=true;
total:=0;
try(1);
writeln('total:',total);
end.
【测试数据】
n=8 八皇后问题
No.[ 1] 1 5 8 6 3 7 2 4 No.[ 2] 1 6 8 3 7 4 2 5
No.[ 3] 1 7 4 6 8 2 5 3 No.[ 4] 1 7 5 8 2 4 6 3
No.[ 5] 2 4 6 8 3 1 7 5 No.[ 6] 2 5 7 1 3 8 6 4
No.[ 7] 2 5 7 4 1 8 6 3 No.[ 8] 2 6 1 7 4 8 3 5
No.[ 9] 2 6 8 3 1 4 7 5 No.[10] 2 7 3 6 8 5 1 4
No.[11] 2 7 5 8 1 4 6 3 No.[12] 2 8 6 1 3 5 7 4
No.[13] 3 1 7 5 8 2 4 6 No.[14] 3 5 2 8 1 7 4 6
No.[15] 3 5 2 8 6 4 7 1 No.[16] 3 5 7 1 4 2 8 6
No.[17] 3 5 8 4 1 7 2 6 No.[18] 3 6 2 5 8 1 7 4
No.[19] 3 6 2 7 1 4 8 5 No.[20] 3 6 2 7 5 1 8 4
No.[21] 3 6 4 1 8 5 7 2 No.[22] 3 6 4 2 8 5 7 1
No.[23] 3 6 8 1 4 7 5 2 No.[24] 3 6 8 1 5 7 2 4
No.[25] 3 6 8 2 4 1 7 5 No.[26] 3 7 2 8 5 1 4 6
No.[27] 3 7 2 8 6 4 1 5 No.[28] 3 8 4 7 1 6 2 5
No.[29] 4 1 5 8 2 7 3 6 No.[30] 4 1 5 8 6 3 7 2
No.[31] 4 2 5 8 6 1 3 7 No.[32] 4 2 7 3 6 8 1 5
No.[33] 4 2 7 3 6 8 5 1 No.[34] 4 2 7 5 1 8 6 3
No.[35] 4 2 8 5 7 1 3 6 No.[36] 4 2 8 6 1 3 5 7
No.[37] 4 6 1 5 2 8 3 7 No.[38] 4 6 8 2 7 1 3 5
No.[39] 4 6 8 3 1 7 5 2 No.[40] 4 7 1 8 5 2 6 3
No.[41] 4 7 3 8 2 5 1 6 No.[42] 4 7 5 2 6 1 3 8
No.[43] 4 7 5 3 1 6 8 2 No.[44] 4 8 1 3 6 2 7 5
No.[45] 4 8 1 5 7 2 6 3 No.[46] 4 8 5 3 1 7 2 6
No.[47] 5 1 4 6 8 2 7 3 No.[48] 5 1 8 4 2 7 3 6
No.[49] 5 1 8 6 3 7 2 4 No.[50] 5 2 4 6 8 3 1 7
No.[51] 5 2 4 7 3 8 6 1 No.[52] 5 2 6 1 7 4 8 3
No.[53] 5 2 8 1 4 7 3 6 No.[54] 5 3 1 6 8 2 4 7
No.[55] 5 3 1 7 2 8 6 4 No.[56] 5 3 8 4 7 1 6 2
No.[57] 5 7 1 3 8 6 4 2 No.[58] 5 7 1 4 2 8 6 3
No.[59] 5 7 2 4 8 1 3 6 No.[60] 5 7 2 6 3 1 4 8
No.[61] 5 7 2 6 3 1 8 4 No.[62] 5 7 4 1 3 8 6 2
No.[63] 5 8 4 1 3 6 2 7 No.[64] 5 8 4 1 7 2 6 3
No.[65] 6 1 5 2 8 3 7 4 No.[66] 6 2 7 1 3 5 8 4
No.[67] 6 2 7 1 4 8 5 3 No.[68] 6 3 1 7 5 8 2 4
No.[69] 6 3 1 8 4 2 7 5 No.[70] 6 3 1 8 5 2 4 7
No.[71] 6 3 5 7 1 4 2 8 No.[72] 6 3 5 8 1 4 2 7
No.[73] 6 3 7 2 4 8 1 5 No.[74] 6 3 7 2 8 5 1 4
No.[75] 6 3 7 4 1 8 2 5 No.[76] 6 4 1 5 8 2 7 3
No.[77] 6 4 2 8 5 7 1 3 No.[78] 6 4 7 1 3 5 2 8
No.[79] 6 4 7 1 8 2 5 3 No.[80] 6 8 2 4 1 7 5 3
No.[81] 7 1 3 8 6 4 2 5 No.[82] 7 2 4 1 8 5 3 6
No.[83] 7 2 6 3 1 4 8 5 No.[84] 7 3 1 6 8 5 2 4
No.[85] 7 3 8 2 5 1 6 4 No.[86] 7 4 2 5 8 1 3 6
No.[87] 7 4 2 8 6 1 3 5 No.[88] 7 5 3 1 6 8 2 4
No.[89] 8 2 4 1 7 5 3 6 No.[90] 8 2 5 3 1 7 4 6
No.[91] 8 3 1 6 2 5 7 4 No.[92] 8 4 1 3 6 2 7 5
total:92
对于N皇后:
┏━━━┯━━┯━━┯━━┯━━┯━━┯━━┯━━┓
┃皇后 N│ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │ 10 ┃
┠───┼──┼──┼──┼──┼──┼──┼──┨
┃方案数│ 2 │ 10 │ 4 │ 40 │ 92 │352 │724 ┃
┗━━━┷━━┷━━┷━━┷━━┷━━┷━━┷━━┛ |