主题:[讨论]n皇后问题(经典回溯问题,大家看看,谢谢!)
怜丹欣∮
[专家分:120] 发布于 2007-07-18 10:54:00
一个n*n(1<=n<=100)的国际象棋棋盘上放置n个皇后,使其不能相互攻击,即任何两个皇后都不能处在棋盘的同一行,同一列,同一条斜线上,试问共有多少种摆法?
输入:n
输出:所有方案.每个方案为n+1行.
格式:方案序号
以下n行,其中第i行(1<=i<=n)为棋盘i行中皇后的列位置.
回复列表 (共8个回复)
沙发
Matodied [专家分:7560] 发布于 2007-07-18 11:39:00
用回朔?
是不是这样:
首先,设立数组queen[n,n],queen[i,j]为TRUE表示这个地方已经有棋子,为FALSE表示没有棋子。每放下一个棋子,就必须判断和它在同行、同列和同斜线(2条斜线)的地方有没有冲突,如果发生冲突,就必须撤掉这个棋子。
那么,怎么判断有没有冲突呢?
首先设立一个循环k从1到n,(假设目前的位置是i,j),检查queen[i,k]和queen[k,j]上有没有棋子,有就表示这里不能再有棋子。
再检查斜行。和queen[i,j]在一个斜行的格子queen[x,y],要么是x+y和i+j相等,要么是x-y和i-j相等,因此还要加上这一条。
板凳
怜丹欣∮ [专家分:120] 发布于 2007-07-18 11:45:00
1楼的方法还可以!只是要实现你所说的这几步,可就难了!恐怕写个程序出来会太长了!
谢谢!
要不你写一下程序中的重要部分?
3 楼
abcwuhang [专家分:1840] 发布于 2007-07-18 12:20:00
{$ A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S+,T-,V+,X+,Y+}
{$M65520,0,655360}
program nqueens;
var i,n,total:longint;
q:boolean;
a:array [1..1000] of boolean;
b:array [2..2000] of boolean;
c:array [1-1000..1000-1] of boolean;
x:array [1..1000] of longint;
procedure print;
var k,kk,kkk:longint;
begin
total:=total+1;
writeln(total);
for k:=1 to n do
for kk:=1 to n do
begin
for kkk:=1 to n do
if x[kk]=kkk then write('1 ')
else write('0 ');
writeln;
end;
writeln;
end;
procedure try(i:longint;var q:boolean);
var j:longint;
begin
j:=0;
repeat
j:=j+1;
q:=false;
if ((a[j]=true) and (b[i+j]=true) and (c[i-j]=true)) then
begin
x[i]:=j;
a[j]:=false;
b[i+j]:=false;
c[i-j]:=false;
if i<n 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 print;
end;
until j=n;
end;{ of try }
{======main======}
begin
readln(n);
total:=0;
for i:=1 to n do
a[i]:=true;
for i:=2 to n*2 do
b[i]:=true;
for i:=1-n to n-1 do
c[i]:=true;
try(1,q);
readln;
end.
未加修改,请看一下...(不知输出标准是否满足题意???)
4 楼
bigchen [专家分:1940] 发布于 2007-07-18 17:01:00
program huanghuo8(input,output);
var l ,k,n,j:integer; x:array[1..100]of integer;
function place(k:integer):boolean;{k为行号也就是第k个皇后,函数值为真时表示能放}
var i:integer;
begin
i:=1;
while i<k do
begin if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k))then{第k个皇后与第i个皇后同一列}
begin place:=false; exit end;{或在同一斜对角线上}
i:=i+1;
end;
place:=true;
end;
begin
write('n=');readln(n);{输入皇后的个数}
l:=0;x[1]:=0;k:=1;{初始化:解的个数l,第一皇后所在列为0,从第一个皇后开始}
while k>0 do{当回溯到没有皇后时停止}
begin
x[k]:=x[k]+1;{穷举第k皇后的位置}
while (x[k]<=n)and(not place(k))do x[k]:=x[k]+1;{不符合条件,穷举下一个位置}
if x[k] <=n then
if k=n then begin{当皇后所穷举的列号没有超出n,并且正好是最后一个皇后}
l:=l+1;{可安置的位置找到}
write('no',l,': ');{输出栈的内容,也就是输出每个皇后所在列号}
for j:=1 to n do write(x[j],' ');
writeln;
end
else begin{当皇后所穷举的列号没有超出n,但还不是最后一个后}
inc(k);x[k]:=0;{找下一个皇后,并初始化所在列号(位置)为0}
end
else k:=k-1;{当皇后所穷举的列号超出n,回溯到前一个皇后}
end;
end.
我的程序
本人不才,欢迎修改
5 楼
qqym710 [专家分:140] 发布于 2007-07-18 19:35:00
program ex;
var n,tj:integer;{tj用来统计方法个数}
a:array[0..1000]of integer;{存下每一步用的数组}
function pd(l:integer):boolean;{判断是否能放}
var i,j:integer;
begin
pd:=true;
for j:=l-1 downto 1 do
begin
if (a[j]=a[l])or(abs(a[l]-a[j])=abs(l-j))
then pd:=false;
end;
end;
procedure init;
begin
readln(n);
end;
procedure main(k:integer);
var i,j:integer;
begin
if k>n then
begin
for j:=1 to n do write(a[j],',');{输出所有方案}
writeln;
inc(tj);{方法数加一}
exit;
end
else
for i:=1 to n do{从一到N找一个能放皇后的地方}
begin
a[k]:=i;
if pd(k)=true then
begin
main(k+1);
a[k]:=0;
end;
end;
end;
begin
init;
tj:=0;
fillchar(a,sizeof(a),0);
main(1);
write(tj);
end.
建议用F7键看看电脑是怎么运行的(+-+!本人就是因为不知道回朔是电脑的运行,至今才学会,半年了!!)
6 楼
qqym710 [专家分:140] 发布于 2007-07-18 19:48:00
四楼的就是强!!交个朋友把,5QQ是183011017或加群42873986
7 楼
Matodied [专家分:7560] 发布于 2007-07-18 21:34:00
我的程序中检查是否有冲突的程序段:
f := TRUE;
FOR k:=1 TO n DO BEGIN
IF queen[i, k] THEN BEGIN
f := FALSE; BREAK;
END;
IF queen[k, j] THEN BEGIN
f := FALSE; BREAK;
END;
END;
IF f THEN BEGIN
s := i + j; m := i - j;
FOR k:=1 TO s - 1 DO BEGIN
IF queen[k,s - k] THEN BEGIN
f := FALSE; BREAK;
END;
IF (k + m < n) AND (k + m > 0) THEN BEGIN
IF queen[k + m, k] THEN BEGIN
f := FALSE; BREAK;
END;
END;
END;
END;
IF f THEN queen[i, j] := TRUE;
8 楼
怜丹欣∮ [专家分:120] 发布于 2007-07-19 20:30:00
谢谢大家了!
我来回复