当前位置：首页 > 实用文档 > 其他范文> 八皇后问题

八皇后问题

时间：2024-05-01 07:15:14 其他范文收藏本文下载本文

八皇后问题（精选3篇）由网友“范范”投稿提供，这次小编给大家整理过的八皇后问题，供大家阅读参考，也相信能帮助到您。

八皇后问题

篇1：八皇后问题

八皇后问题

八皇后问题，输出了所有情况，不过有些结果只是旋转了90度而已，(回溯算法的典型例题，是数据结构书上算法的具体实现，大家都亲自动手写过这个程序吗?)

#define N 8

int Board[N][N];

int Valid(int i, int j) { // 判断下棋位置是否有效

int k = 1;

for(k=1; i>=k && j>=k;k++)

if(Board[i-k][j-k]) return 0;

for(k=1; i>=k;k++)

if(Board[i-k][j]) return 0;

for(k=1; i>=k && j+k if(Board[i-k][j+k]) return 0;

return 1;

}

void Trial(int i, int n) { // 寻找合适下棋位置

if(i == n) {

for(int k=0; k for(int m=0; m printf(“%d “, Board[k][m]);

printf(“\n”);

}

printf(“\n”);

} else {

for(int j=0; j Board[i][j] = 1;

if(Valid(i,j))

Trial(i+1, n);

Board[i][j] = 0;

}

int main(int argc, char* argv[]) {

Trial(0, N);

}

篇2：poj3239 Solution to the n Queens Puzzle (n皇后问题)

Solution to thenQueens PuzzleTime Limit:1000MSMemory Limit:131072KTotal Submissions:3494Accepted:1285Special Judge

Description

The eight queens puzzle is the problem of putting eight chess queens on an 8 × 8 chessboard such that none of them is able to capture any other. The puzzle has been generalized to arbitraryn×nboards. Givenn, you are to find a solution to thenqueens puzzle.

Input

The input contains multiple test cases. Each test case consists of a single integernbetween 8 and 300 (inclusive). A zero indicates the end of input.

Output

For each test case, output your solution on one line. The solution is a permutation of {1, 2, …,n}. The number in theith place means theith-column queen in placed in the row with that number.

Sample Input

Sample Output

5 3 1 6 8 2 4 7

解题思路：

一、当n mod 6 != 2 或 n mod 6 != 3时：

[2,4,6,8,...,n],[1,3,5,7,...,n-1] (n为偶数)

[2,4,6,8,...,n-1],[1,3,5,7,...,n ] (n为奇数)

二、当n mod 6 == 2 或 n mod 6 == 3时

(当n为偶数,k=n/2；当n为奇数,k=(n-1)/2)

[k,k+2,k+4,...,n],[2,4,...,k-2],[k+3,k+5,...,n-1],[1,3,5,...,k+1] (k为偶数,n为偶数)

[k,k+2,k+4,...,n-1],[2,4,...,k-2],[k+3,k+5,...,n-2],[1,3,5,...,k+1],[n] (k为偶数,n为奇数)

[k,k+2,k+4,...,n-1],[1,3,5,...,k-2],[k+3,...,n],[2,4,...,k+1] (k为奇数,n为偶数)

[k,k+2,k+4,...,n-2],[1,3,5,...,k-2],[k+3,...,n-1],[2,4,...,k+1],[n ](k为奇数,n为奇数)

(上面有六条序列，

poj3239 Solution to the n Queens Puzzle (n皇后问题)

，

一行一个序列，中括号是我额外加上的，方便大家辨认子序列，子序列与子序列之间是连续关系，无视中括号就可以了。第i个数为ai，表示在第i行ai列放一个皇后；... 省略的序列中，相邻两数以2递增。)

参考代码：

#include#includeusing namespace std;int main(int i){ int n; //皇后数 while(cin>>n) { if(!n) break; if(n%6!=2 && n%6!=3) { if(n%2==0) //n为偶数 { for(i=2;i<=n;i+=2) cout<

篇3：C++(八) 类的其他几点问题

一、拷贝构造函数

拷贝构造函数在下列情况下被调用：用已经存在的对象去初始化同一个类的另一个对象；在函数的参数中，以传值方式传递类对象的拷贝；类对象的值被用做函数的返回值，拷贝构造函数和前面说到的转换构造函数有些相似。转换构造函数是把一个类的对象转化为另一个类的对象；拷贝构造函数是用一个已经存在的对象的值实例化该类的一个新对象。

不同对象间的初始化和赋值的区别：赋值操作是在两个已经存在的对象间进行的；而初始化是要创建一个新的对象，并且其初值来源于另一个已存在的对象。编译器会区别这两种情况，赋值的时候调用重载的赋值运算符，初始化的时候调用拷贝构造函数。

如果类中没有拷贝构造函数，则编译器会提供一个默认的。这个默认的拷贝构造函数只是简单地复制类中的每个成员。

#include iostream.h

#include string.h

class Date

{

int mo, da, yr;

char* month;

public:

Date(int m = 0, int d = 0, int y = 0);

Date(const Date&);

~Date();

void display() const;

};

Date::Date(int m, int d, int y)

{

static char* mos[] =

{

January, February, March, April, May, June,

July, August, September, October, November, December

};

mo = m; da = d; yr = y;

if (m != 0)

{

month = new char[strlen(mos[m-1])+1];

strcpy(month, mos[m-1]);

}

else

month = 0;

}

Date::Date(const Date& dt)

{

mo = dt.mo;

da = dt.da;

yr = dt.yr;

if (dt.month != 0)

{

month = new char [strlen(dt.month)+1];

strcpy(month, dt.month);

}

else

month = 0;

}

Date::~Date()

{

delete [] month;

}

void Date::display() const

{

if (month != 0)

cout << month <<' '<< da << , << yr << std::endl;

}

int main()

{

Date birthday(6,24,1940);

birthday.display();

Date newday = birthday;

newday.display();

Date lastday(birthday);

lastday.display();

return 0;

}

本例中，用到了两次拷贝构造函数。一个是使用普通的C++初始化变量的语句：

Date newday = birthday;

另一个是使用构造函数的调用约定，即把初始化值作为函数的参数：

Date lastday(birthday);

二、类的引用

在函数参数和返回值中，如果一定要使用传值方式，那么使用类对象的引用，是一个提高效率的方法，

类的数据成员也可以是一个引用，但必须注意：第一，一个引用必须初始化。通常一个类对象并不会像结构那样用大括号来初始化，而是调用构造函数。因此在构造函数里必须初始化类当中的引用成员。第二，引用是一个别名。尽管类里面的引用在使用方式上看起来和类的一般数据成员没有什么区别，但是作用在其上的操作，实际上是对用来初始化它的那么对象进行的。

#include iostream.h

class Date

{

int da, mo, yr;

public:

Date(int d,int m,int y)

{ da = d; mo = m; yr = y; }

void Display() const

{ cout << da << '/' << mo << '/' << yr; }

};

class Time

{

int hr, min, sec;

public:

Time(int h, int m, int s)

{ hr = h; min = m; sec = s; }

void Display() const

{ cout << hr << ':' << min << ':' << sec; }

};

class DateTime

{

const Date& dt;

const Time& tm;

public:

DateTime(const Date& d, const Time& t) : dt(d), tm(t)

{

//empty

}

void Display() const

{

dt.Display();

cout << ' ';

tm.Display();

}

};

int main()

{

Date today(7,4,2004);

Time now(15,20,0);

DateTime dtm(today, now);

dtm.Display();

return 0;

}

我们来看看这个程序中DateTime的构造函数的格式：冒号操作符引出了一个参数初始化表。必须使用这种格式来初始化引用数据成员，而不可以在函数体内来进行初始化工作。如果构造函数像上例一样不是内联的，那么最好不要在类声明中构造函数的原型上使用冒号和初始化值表，而是像下面这样，把参数初始化表放在定义构造函数的地方：

Class DateTime

{

const Date& dt;

const Time& tm;

public:

DateTime(const Date& d,const Time& t);

}

DateTime::DateTime(const Date& d,const Time& t):dt(d),tm(t)

{

//empty

}

可以使用构造函数的参数初始化表来初始化任何数据成员。特别是常量数据成员，和引用一样，只能在参数初始化表里进行初始化，这是因为不可以在构造函数内部为常量数据成员赋值。