回 帖 发 新 帖 刷新版面

主题:[讨论]n皇后问题(经典回溯问题,大家看看,谢谢!)

一个n*n(1<=n<=100)的国际象棋棋盘上放置n个皇后,使其不能相互攻击,即任何两个皇后都不能处在棋盘的同一行,同一列,同一条斜线上,试问共有多少种摆法?
  输入:n
  输出:所有方案.每个方案为n+1行.
       格式:方案序号
            以下n行,其中第i行(1<=i<=n)为棋盘i行中皇后的列位置.

回复列表 (共8个回复)

沙发

用回朔?

是不是这样:

首先,设立数组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相等,因此还要加上这一条。

板凳

1楼的方法还可以!只是要实现你所说的这几步,可就难了!恐怕写个程序出来会太长了!
 谢谢!
要不你写一下程序中的重要部分?

3 楼

{$ 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 楼


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 楼

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 楼

四楼的就是强!!交个朋友把,5QQ是183011017或加群42873986

7 楼

我的程序中检查是否有冲突的程序段:
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 楼

谢谢大家了!

我来回复

您尚未登录,请登录后再回复。点此登录或注册