要用数组的~把对角和上下线用/0禁止就行
最好写出每个步骤的意义
谢了~
要求设为n*n的棋盘 用户输入n的值
八皇后问题各种语言版本：
http://baike.baidu.com/view/698719.htm
#include<iostream.h>
const int n = 15 ; //15皇后问题.改动n可变成N皇后问题
const int n_sub = n - 1 ;
int queen[n] ; //N个棋子.N对应每一列,如n=0的棋子只下在0列,1下1....类推
bool row[n] ; //棋局的每一行是否有棋,有则为1,无为0 ;
bool passive[2*n-1] ; //斜率为1的斜线方向上是不是有皇后
bool negative[2*n-1] ; //斜率为负1的斜线方向上是不是有皇后.
//之所以用全局变量,因全局数组元素值自动为0
int main()
{
int cur = 0 ;//游标,当前移动的棋子(哪一列的棋子)
bool flag = false ; //当前棋子位置是否合法
queen[0] = -1 ; //第0列棋子准备,因一开始移动的就是第0列棋子
int count = 0 ; //一共有多少种下法 ;
cout<<"============================Starting============================="<<endl ;
while(cur>=0)
{
while(cur>=0 && queen[cur]<n && !flag) //当还不确定当前位置是否可下
{
queen[cur]++ ;
// cout<<"第"<<cur<<"列棋子开始走在第"<<queen[cur]<<"行"<<endl ;
// cin.get() ;
if(queen[cur] >= n) { //如果当前列已经下完(找不到合法位置)
// cout<<"当前行是非法行,当前列棋子走完,没有合法位置,回溯上一列棋子"<<endl ;
// cin.get() ;
queen[cur] = -1 ; //当前列棋子置于准备状态
cur-- ; //回溯到上一列的棋子
if(cur>=0) {
row[queen[cur]] = false ;
passive[queen[cur] + cur] = false ;
negative[n_sub + cur - queen[cur]] = false ;
}
//由于要移下一步,所以回溯棋子原位置所在行应该没有棋子啦.置row[]为false
//并且棋子对应的斜线的标志位passive[cur]和negative[cur]也应该要设为false ;
}
else {
//先判断棋子所在行没有棋子
if(row[queen[cur]] == false) { //当前行没有棋子
// cout<<"棋子"<<cur<<"所在行没有其他棋子,正在检查斜线"<<endl ;
flag = true ; // 暂设为true,或与之前棋子斜交,则再设为false ;
//以下检查当前棋子是否与之前的棋子斜线相交
if( passive[queen[cur] + cur] == true || negative[n_sub + cur - queen[cur]] == true) {
flag = false ;
// cout<<"出现斜线相交,该位置不合法"<<endl ;
}
else
flag = true ;
if(flag) { //没有斜交,位置合法
// cout<<"斜线也没有相交,该位置合法"<<endl ;
if(cur == n-1) //如果是最后一个棋子
{
// cout<<"棋子走完一轮,总走法加1"<<endl ;
count++ ; //总走法加一 ;
}
row[queen[cur]] = true ;// 当前行设为有棋子
passive[queen[cur] + cur] = true ;//当前行正斜率方向有棋子
negative[n_sub + cur - queen[cur]] = true ; //当前行负斜率方向上也有棋子
cur++ ;
if(cur >= n) {
cur-- ;
row[queen[cur]] = false ;
passive[queen[cur] + cur] = false ;
negative[n_sub + cur - queen[cur]] = false ;//原理同回溯
}
flag = false ;
}
}
}//else
}
}
cout<<n<<"皇后问题一共有"<<count<<"种解法"<<endl ;
return 0 ;
}
你自己修改一下吧。
http://baike.baidu.com/view/698719.htm
#include<iostream.h>
const int n = 15 ; //15皇后问题.改动n可变成N皇后问题
const int n_sub = n - 1 ;
int queen[n] ; //N个棋子.N对应每一列,如n=0的棋子只下在0列,1下1....类推
bool row[n] ; //棋局的每一行是否有棋,有则为1,无为0 ;
bool passive[2*n-1] ; //斜率为1的斜线方向上是不是有皇后
bool negative[2*n-1] ; //斜率为负1的斜线方向上是不是有皇后.
//之所以用全局变量,因全局数组元素值自动为0
int main()
{
int cur = 0 ;//游标,当前移动的棋子(哪一列的棋子)
bool flag = false ; //当前棋子位置是否合法
queen[0] = -1 ; //第0列棋子准备,因一开始移动的就是第0列棋子
int count = 0 ; //一共有多少种下法 ;
cout<<"============================Starting============================="<<endl ;
while(cur>=0)
{
while(cur>=0 && queen[cur]<n && !flag) //当还不确定当前位置是否可下
{
queen[cur]++ ;
// cout<<"第"<<cur<<"列棋子开始走在第"<<queen[cur]<<"行"<<endl ;
// cin.get() ;
if(queen[cur] >= n) { //如果当前列已经下完(找不到合法位置)
// cout<<"当前行是非法行,当前列棋子走完,没有合法位置,回溯上一列棋子"<<endl ;
// cin.get() ;
queen[cur] = -1 ; //当前列棋子置于准备状态
cur-- ; //回溯到上一列的棋子
if(cur>=0) {
row[queen[cur]] = false ;
passive[queen[cur] + cur] = false ;
negative[n_sub + cur - queen[cur]] = false ;
}
//由于要移下一步,所以回溯棋子原位置所在行应该没有棋子啦.置row[]为false
//并且棋子对应的斜线的标志位passive[cur]和negative[cur]也应该要设为false ;
}
else {
//先判断棋子所在行没有棋子
if(row[queen[cur]] == false) { //当前行没有棋子
// cout<<"棋子"<<cur<<"所在行没有其他棋子,正在检查斜线"<<endl ;
flag = true ; // 暂设为true,或与之前棋子斜交,则再设为false ;
//以下检查当前棋子是否与之前的棋子斜线相交
if( passive[queen[cur] + cur] == true || negative[n_sub + cur - queen[cur]] == true) {
flag = false ;
// cout<<"出现斜线相交,该位置不合法"<<endl ;
}
else
flag = true ;
if(flag) { //没有斜交,位置合法
// cout<<"斜线也没有相交,该位置合法"<<endl ;
if(cur == n-1) //如果是最后一个棋子
{
// cout<<"棋子走完一轮,总走法加1"<<endl ;
count++ ; //总走法加一 ;
}
row[queen[cur]] = true ;// 当前行设为有棋子
passive[queen[cur] + cur] = true ;//当前行正斜率方向有棋子
negative[n_sub + cur - queen[cur]] = true ; //当前行负斜率方向上也有棋子
cur++ ;
if(cur >= n) {
cur-- ;
row[queen[cur]] = false ;
passive[queen[cur] + cur] = false ;
negative[n_sub + cur - queen[cur]] = false ;//原理同回溯
}
flag = false ;
}
}
}//else
}
}
cout<<n<<"皇后问题一共有"<<count<<"种解法"<<endl ;
return 0 ;
}
你自己修改一下吧。
温馨提示：答案为网友推荐，仅供参考
第1个回答 2009-04-07
报错是因为你使用数组越界（vector就相当于数组）
一下是修改后的程序，修改地方建注释：
#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;
//const int Normalize=9;
int Num;
int number;
vector<int>q;
vector<bool>C;
vector<bool>L;
vector<bool>R;
int normalize; //const int normalize=number; (1)这
//时候number的值只是由编译器给的初始值0，所以这个当i<j的时候就出现楼主所给的异常,所以要在main哪里赋值
void Try (int i)
{
int j;
int k;
for(j=1;j<=number;j++)
{
if ((C[j]==true)&&(L[i-j+normalize]==true)
&&(R[i+j])==true)
{
q[i]=j;
C[j]=false;
L[i-j+normalize]=false;
R[i+j]=false;
if(i<number)
{
Try(i+1);
}
else
{
Num++;
cout<<"方案"<<Num<<":";
for(k=1;k<=number;k++)
cout<<q[k]<<" ";
cout<<endl;
}
C[j]=true;
L[i-j+normalize]=true;
R[i+j]=true;
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{cin>>number;
//(2)这里这样定义的只能是局部参数，这样try函数使用的全局变量就是没有初始值的，所以会导致异常，需要注释掉，使得所有使用的都是全局变量
//vector<int>q;
//vector<bool>C;
//vector<bool>L;
//vector<bool>R;
/*将数组初始化*/
for(int i=0;i<=number+1;i++)
{q.push_back(0);
}
for(int i=0;i<=number*2+1;i++)
{C.push_back(0);}
for(int i=0;i<=number*2+1;i++)
{L.push_back(0);}
for(int i=0;i<=number*2+1;i++) //(3)LR如果左右的话，应该一样是+1才对
{R.push_back(0);}
int i;
Num=0;
for (i=0;i<number+1;i++)
C[i]=true;
for (i=0;i<number*2+1;i++) //(3)LR如果左右的话，应该一样是+1才对
L[i]=R[i]=true;
normalize=number; //参见(1)的说明
Try(1);
return 0;
}
一下是修改后的程序，修改地方建注释：
#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;
//const int Normalize=9;
int Num;
int number;
vector<int>q;
vector<bool>C;
vector<bool>L;
vector<bool>R;
int normalize; //const int normalize=number; (1)这
//时候number的值只是由编译器给的初始值0，所以这个当i<j的时候就出现楼主所给的异常,所以要在main哪里赋值
void Try (int i)
{
int j;
int k;
for(j=1;j<=number;j++)
{
if ((C[j]==true)&&(L[i-j+normalize]==true)
&&(R[i+j])==true)
{
q[i]=j;
C[j]=false;
L[i-j+normalize]=false;
R[i+j]=false;
if(i<number)
{
Try(i+1);
}
else
{
Num++;
cout<<"方案"<<Num<<":";
for(k=1;k<=number;k++)
cout<<q[k]<<" ";
cout<<endl;
}
C[j]=true;
L[i-j+normalize]=true;
R[i+j]=true;
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{cin>>number;
//(2)这里这样定义的只能是局部参数，这样try函数使用的全局变量就是没有初始值的，所以会导致异常，需要注释掉，使得所有使用的都是全局变量
//vector<int>q;
//vector<bool>C;
//vector<bool>L;
//vector<bool>R;
/*将数组初始化*/
for(int i=0;i<=number+1;i++)
{q.push_back(0);
}
for(int i=0;i<=number*2+1;i++)
{C.push_back(0);}
for(int i=0;i<=number*2+1;i++)
{L.push_back(0);}
for(int i=0;i<=number*2+1;i++) //(3)LR如果左右的话，应该一样是+1才对
{R.push_back(0);}
int i;
Num=0;
for (i=0;i<number+1;i++)
C[i]=true;
for (i=0;i<number*2+1;i++) //(3)LR如果左右的话，应该一样是+1才对
L[i]=R[i]=true;
normalize=number; //参见(1)的说明
Try(1);
return 0;
}
参考资料：
