【题目1】N皇后问题（八皇后问题的扩展）.doc

【题目1】N皇后问题（八皇后问题的扩展）.doc【题目1】N皇后问题(八皇后问题的扩展)
【题目2】排球队员站位问题
【题目3】把自然数N分解为若干个自然数之和。
【题目4】把自然数N分解为若干个自然数之积。
【题目5】马的遍历问题。
【题目6】加法分式分解
【题目7】地图着色问题
【题目8】在n*n的正方形中放置长为2,宽为1的长条块,
【题目9】找迷宫的最短路径。(广度优先搜索算法)
【题目10】火车调度问题
【题目11】农夫过河
【题目12】七段数码管问题。
【题目13】把1-8这8个数放入下图8个格中,要求相邻的格(横,竖,对角线)上填的数不连续.
【题目14】在4×4的棋盘上放置8个棋,要求每一行,每一列上只能放置2个.
【题目15】.(深度优先搜索法)
【题目16】一笔画问题
【题目17】城市遍历问题.
【题目18】棋子移动问题
【题目19】求集合元素问题(1,2x+1,3X+1类)
================================================================================
================================================================================
【题目】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