高分求4皇后问题详细解法

Question

知道了，做好了，可是好奇怪呀，居然不是递增数列，采用递归很慢的，谁算过n=100的，我的
刚配的电脑算了好久都没完成
Queen(1)= 1
Queen(2)= 0
Queen(3)= 0
Queen(4)= 2
Queen(5)= 10
Queen(6)= 4
Queen(7)= 40
Queen(8)= 92
Queen(9)= 352
Queen(10)= 724

Answer 1

#include "iostream.h"class CQueen
{
private:
int m_num;
int *pCol;
int *pRow;
int *pMD;
int *pSD;
int m_Count;
public:
CQueen(int num=8):m_Count(0),m_num(num)
{
if(num)
{
pCol=new int[num];
pRow=new int[num];
pMD=new int[2*num-1];
pSD=new int[2*num-1];
for(int i=0;i<num;i++)
pCol[i]=pRow[i]=0;
for(i=0;i<2*num-1;i++)
pMD[i]=pSD[i]=0;
}
}
~CQueen()
{
if(m_num)
{
delete []pCol;
delete []pRow;
delete []pMD;
delete []pSD;
}
}
void Print()
{
for(int i=0;i<m_num-1;i++)
cout<<"Row"<<i+1<<":"<<pRow[i]<<"-->";
cout<<"Row"<<i+1<<":"<<pRow[i]<<endl;
} void Queen(int i)
{
if(i==m_num)
{
Print();
m_Count++;
}
else
{
for(int j=0;j<m_num;j++)
{
if(pCol[j]==0&&pMD[m_num+i-j-1]==0&&pSD[i+j]==0)
{
pCol[j]=pMD[m_num+i-j-1]=pSD[i+j]=1;
pRow[i]=j+1;
Queen(i+1);
pCol[j]=pSD[i+j]=pMD[m_num+i-j-1]=0;
pRow[i]=0;
}
}
}
}
void PrintSum()
{
cout<<"Total model:"<<m_Count<<endl;
}
};

Answer 2

我在javad大学教程里做过这道理目，还讨论了各种算法的效率。好长没有碰了，想一下给答案。

Answer 3

我做了一个,结果如下:i=1  perm=1,    0.0 sec valid=1
i=2  perm=2,    0.0 sec valid=0
i=3  perm=6,    0.0 sec valid=0
i=4  perm=24,   0.0 sec valid=2
i=5  perm=120,  0.0 sec valid=10
i=6  perm=720,  0.0 sec valid=4
i=7  perm=5040, 0.0 sec valid=40
i=8  perm=40320,        0.031 sec       valid=92
i=9  perm=362880,       0.422 sec       valid=352
i=10 perm=3628800,      3.016 sec       valid=724
i=11 perm=39916800,     34.562 sec      valid=2680
i=12 perm=479001600,    424.078 sec     valid=14200
i=13 is in calculation...

Answer 4

八皇后问题的java实现 :
http://www.csdn.net/develop/Read_Article.asp?Id=17815

Answer 5

*
 * Created on 2003-3-28
 * n皇后问题算法。
 * 把棋盘看成一个坐标系，以左下角为原点（0,0)。坐标系的每个点为一个Point类。
 * 每个皇后为一个皇后对象Queen。
 * 判断一个点的坐标是否在，一个皇后控制的范围的函数为Queen.isUnderControl(point)。
 * 
 */
package bia.arithmetic;import java.util.Date;/**
 * @author Administrator
 *
 * To change this generated comment go to 
 * Window>Preferences>Java>Code Generation>Code and Comments
 */
public class EightQueen { Queen[] stack = new Queen[8];
 int sp = 0;
 int num = 0; public EightQueen() {
  num = 8;
  stack = new Queen[num];
  sp = 0;
 } public EightQueen(int num) {
  this.num = num;
  stack = new Queen[num];
  sp = 0;
 } /**
  * 打印皇后的坐标列表。
  * @renzc
  *
  */
 public void list() {
  System.out.println("Begin list the stack Point:");
  for (int i = 0; i < sp; i++) {
   stack[i].pos.println();
  }
  System.out.println("End list the stack Point:");
 } /**
  * 主算法流程。
  * @Administrator
  *
  */
 public void calc() {
  sp = 0;
  stack[sp++] = new Queen();
  while (sp >= 0 && sp <= num - 1) {
   Queen queen = getQueen(sp);
   if (null == queen) {
    boolean flag = true;
    while (flag) {
     --sp;
     if (sp < 0)
      break;
     if (stack[sp].pos.y == num - 1) {     }
     else {
      stack[sp++].pos.y++;
      flag = false;
      for (int k = 0; k < sp - 1; k++) {
       if (stack[k].isUnderControl(stack[sp - 1].pos)) {
        flag = true;
        break;
       }
      }
     }
    }   }
   else {
    stack[sp++] = queen;
   }
  }  
 } public Queen getQueen(int x) {
  boolean flag = true;
  int y = 0;
  while (flag) {
   flag = false;
   for (int i = 0; i < x; i++) {
    if (stack[i].isUnderControl(new Point(x, y))) {
     flag = true;
     break;
    }
   }
   if (flag && y <= num - 1) {
    y++;
   }
   else if (y >= num) {
    return null;
   }
  }
  return new Queen(new Point(x, y));
 } public static void main(String[] args) {
  EightQueen a = new EightQueen(20);
  long start = new Date().getTime();
  System.out.println("起始时间：[" + start + "]");
  a.calc();
  long end = new Date().getTime();
  System.out.println("截止时间:[" + end + "]");
  System.out.println("共耗时：[" + (end - start) + "]毫秒");
  if (a.sp > 0) {
   a.list();
  }
  else {
   System.out.println("这个题目无解！");
  }
 }
}class Point {
 int x, y; public void println() {
  System.out.println("The Point is [x,y]=[" + x + "," + y + "]");
 } public Point() {
  x = 0;
  y = 0;
 } public Point(int x, int y) {
  this.x = x;
  this.y = y;
 }
 /**
  * @return int
  */
 public int getX() {
  return x;
 } /**
  * @return int
  */
 public int getY() {
  return y;
 } /**
  * Sets the x.
  * @param x The x to set
  */
 public void setX(int x) {
  this.x = x;
 } /**
  * Sets the y.
  * @param y The y to set
  */
 public void setY(int y) {
  this.y = y;
 }
}class Queen {
 Point pos;
 public Queen() {
  pos = new Point();
 }
 public Queen(Point pos) {
  this.pos = pos;
 }
 public boolean isUnderControl(Point point) {
  boolean ret = true;
  if (point.x != pos.x
   && point.y != pos.y
   && Math.abs(point.x - pos.x) != Math.abs(point.y - pos.y)
   && Math.abs(point.x + point.y) != Math.abs(pos.x + pos.y)) {
   ret = false;
  }
  return ret;
 }
}
//引自CSDN

Answer 6

to alin19(资深爪哇师傅):
  你的十秒钟是找到一个可行的排列还是找到全部可行的排列,我指的是后者.

Answer 7

全部~!你看我的判断合法的方法,每次只要判断前面皇后跟目前皇后有没冲突即可
.应为前面皇后之间也是经过这个方法证明是无冲突的
/**
 * 判断布局是否合法
 * @return 
 */
private boolean legality(int listNo) {
if (listNo == 0)
return true;
//把以前的所有皇后跟listNo列的皇后进行两两比较判断是否合法
for (int i = 0; i < listNo; i++) {
//如果同一行,返回错
if (queenPos[i] == queenPos[listNo])
return false;
//如果为对角,返回错
if (Math.abs(queenPos[i] - queenPos[listNo])
== Math.abs(i - listNo))
return false;
}
return true;
}

Answer 8

to alin19(资深爪哇师傅)
用你的算法，一次结果为：
Queen(1)=1.0
Queen(2)=0.0
Queen(3)=0.0
Queen(4)=2.0
Queen(5)=10.0
Queen(6)=4.0
Queen(7)=40.0
Queen(8)=92.0
Queen(9)=352.0
Queen(10)=724.0
Queen(11)=2680.0
Queen(12)=14200.0
Queen(13)=73712.0
能不能给我讲讲你这个结果的意思是什么？
是不是这样！
n=10 =====>有724种排法!

Answer 9

是呀,n=8=====>92种我的就是递归呀....
/**
* 放置皇后的函数
* @param y 放置皇后的列码(0~n-1)
*/
private void place(int y) {
//递归头,列码已经超出棋盘则中止递归,回溯
if (y == queenNum) {
num++;
} else {
for (int i = 0; i < queenNum; i++) {
                 //第y列皇后在第i行
        queenPos[y] = i;
         //判断当前局面是否合法
if (legality(y))
         place(y + 1);
}
}
}

Answer 10

to alin19(资深爪哇师傅):
我的程序没有错,判断合法性与你的一样,只是我的全排列算法耗时太多.
你的算法解决了我长久以来的一个大问题(恕不详说),谢谢. 请到下列贴子拿分:
http://expert.csdn.net/Expert/topic/1742/1742989.xml?temp=.5669977