现在的位置: 首页 > 综合 > 正文

【深搜】N皇后加强版

2013年03月16日 ⁄ 综合 ⁄ 共 1529字 ⁄ 字号小中大 ⁄ 评论关闭

题目:N皇后加强版 rqnoj589

题目描述

经典问题。
N皇后问题(加强版）

皇后们想知道自己到底有多少种排列方式。

国际象棋中规定：
皇后对角线互能攻击。
有两个皇后位于同一行或者同一列都不符合要求。！

也就是说，把N个棋子被放置在棋盘上，使得每行、每列只有一个，每条对角线(包括两条主对角线的所有对角线)上至多有一个棋子

下面给出一个例子
列号
1 2 3 4 5 6
-------------------------
1 | | O | | | | |
-------------------------
2 | | | | O | | |
-------------------------
3 | | | | | | O |
-------------------------
4 | O | | | | | |
-------------------------
5 | | | O | | | |
-------------------------
6 | | | | | O | |
-------------------------
'O'表示皇后，
这样是一个符合要求的方法。
其中，上面的布局可以用序列2 4 6 1 3 5来描述，第i个数字表示在第i行的相应位置有一个棋子，如下：
行号 1 2 3 4 5 6
列号 2 4 6 1 3 5

我们要求的就是输出方案每个皇后的列号！

输出：前3种排列方案，
共有多少种排列方案！！

输入格式

读入N,其中(4<=N<=13).
表示棋盘是N x N.

输出格式

前3行为N皇后的前3种排列。用空格隔开。
（若不足3种全部输出）
第4行为共有多少种排列。

样例输入

样例输出

2 4 6 1 3 5<br /> 3 6 2 5 1 4<br /> 4 1 5 2 6 3<br /> 4

RT 很经典的问题了（什么加强版，不就是N皇后嘛。。。）

RQ上还有这道题的翻版，一模一样的。。。这里提供Pascal Code 。

Pascal Code

program nq;

var
  n:longint;
  num:longint;
  ans:array[0..100] of longint;
  h,s,z,y:array[-100..100] of boolean;

procedure init;
begin
  assign(input,'rqnoj589.in');
  assign(output,'rqnoj589.out');
  reset(input);
  rewrite(output);
end;
procedure outit;
begin
  close(input);
  close(output);
  halt;
end;

procedure readdata;
begin
  read(n);
end;

procedure dfs(x:longint);
var
  i:longint;
begin
  if x>n then
  begin
    inc(num);
    if num<=3 then
    begin
      for i:=1 to n-1 do  write(ans[i],' ');
      write(ans[n]);
      writeln;
    end;
  end;
  
  for i:=1 to n do
  begin
    if (not h[x])and(not s[i])and(not z[x-i])and(not y[i+x]) then
    begin
      ans[x]:=i;
      h[x]:=true;
      s[i]:=true;
      z[x-i]:=true;
      y[i+x]:=true;
      dfs(x+1);
      h[x]:=false;
      s[i]:=false;
      z[x-i]:=false;
      y[i+x]:=false;
    end;
  end;
end;

procedure main;
begin
  fillchar(h,sizeof(h),0);
  fillchar(s,sizeof(s),0);
  fillchar(z,sizeof(z),0);
  fillchar(y,sizeof(y),0);
  dfs(1);
  writeln(num);
end;

begin
  init;
  readdata;
  main;
  outit;
end.