[分享]八皇后问题的C＋＋源代码

Eastsun

             //这个是我参照严蔚敏的<数据结构>一书上的算法编的
             //虽然是用C++编的,但完全是C风格的程序
#include<iostream.h>
int *data=new int[10000];  //最多支持100*100的棋盘
long count;                //用来记解的个数
void Init()                //数据初始化
{
    count=0;
    for(int k=0;k<10000;k++) data[k]=0;
}//
bool Check(int i,int j,int n)  //检查第I部期是否符合要求
{
        int k,l;
        for(k=i-1;k>0;k--) if(data[(k-1)*n+j-1]>0)return false;
        for(k=i-1,l=j-1;k>0&&l>0;)
        {
                if(data[(k-1)*n+l-1]>0)return false;
                k--;
                l--;
        }
        for(k=i-1,l=j+1;k>0&&l<=n;)
        {
                if(data[(k-1)*n+l-1]>0)return false;
                k--;
                l++;
        }
        return true;
}
void Trial(int i,int n)
{
        if(i>n)
        {
                for(int s=0;s<n;s++)
                {
                        for(int j=0;j<n;j++)
                                cout<<data[s*n+j]<<" ";
                        cout<<endl;
                }
                cout<<endl;
                count++;
        }
        else
        for(int j=1;j<=n;j++)
        {
                data[(i-1)*n+j-1]=1;
                if(Check(i,j,n))Trial(i+1,n);
                data[(i-1)*n+j-1]=0;
        }
}//Trial
void King(int n)
{
        Init();
    Trial(1,n);
        cout<<count<<endl;
        delete[] data;
}//
void main()
{
        int n;
        cout<<"Input N:";
        cin>>n;
        King(n);
}
  

FantasyDR

我还年轻，不想替代CLR-_-b

einsta

改掉用#include <iostream.h>的习惯吧
#include <iostream>

FantasyDR

楼上的说法何以见得？

einsta

事物是进步的，语言也一样
要尽量使用标准库
新标准c++中定义了名字空间,
iostream是被封装了的c＋＋的类库，提供了一些符合ANSI标准的类
你学C++用的什么书？给你推荐本：The C++ Programming Language最好要看英文原版的，要是不行就C++ Primer
国内的一些书技术更新还没跟上，大多用的是iostream.h

Lendy

很不喜欢现在这些所谓“发展了的”C语言，包括封装得很死的C#。

einsta

C和C++是两码事。
C搞底层开发是很NB，网络呢？
C#是.NET平台上的语言，也不可能去开发一个底层驱动程序
各个语言都有自己的特点和用处
封装不好么？安全，高效！！！！

Lendy

我所指的就是C的整个系列，包括C与C++。
没人说封装不好，但要看是哪种“封装”。
有些所谓“封装”不过是想隐藏其底层的东西。
没有给使用者提供任何明显的便利，相反，阻止了使用者了解本质。
所谓C#，不过是MS克隆出来的JAVA。借C之名，搞出不伦不类的C。

einsta

以下是引用Lendy在2005-1-15 11:51:38的发言：
没有给使用者提供任何明显的便利，相反，阻止了使用者了解本质。

所谓C#，不过是MS克隆出来的JAVA。借C之名，搞出不伦不类的C。

有些本质无须了解...
如：MFC
C#不伦不类？
你对C#了解多少？
C和C#除了语法上基本相同，其他完全不同！！包括底层模式，面对对象，internet是趋势，C#在.NET平台上前景非常广...虽然效率有点低，但是很强大
C#不是JAVA，C#有自己的空间，JAVA也一样
我看了你们有个游戏开发的引擎，不也是基于.NET上的？
最后一贴，不吵了，一会又扯到JAVA和C#世纪之争了...汗...

Lendy

How it works和Why it works是两码事。

MFC的本质可以让你了解到一个系统的核心开发思想。

“C和C#除了语法上基本相同，其他完全不同……”

这正是认为C#模仿JAVA的原因。

（当然，我没有鄙视C#的意思，只是对其脱离C系列本质而感到反感。）

算了，只能说各人有各人的喜好……

还有，有些问题只是“严肃”，不是“吵”。

[此贴子已经被作者于2005-1-15 12:35:33编辑过]

FantasyDR

C#……
那个用C#写的简单编译器，开头因为C#没有函数指针，所以代码写的很长……于是很反感C#。
后来发现，不需要函数指针，用了另外一种方式，代码顿时变短了^_^，于是不再反感C#。
感觉到了.NET平台，MS想统一一切，目前看来，还是比较成功的……至少我想做的事情，还没有他不能实现的。以至于现在想实现任何功能，都会翻翻MSDN，看看在.NET Framework里有没有封装好的现成的东西。
越来越懒了……

einsta

楼上的，C#也可以用指针...
关键字unsafe.....
应该说MS基本把所有都压到.NET上了，对于MS的大赌注，我们没理由不跟上
[em01]

FantasyDR

啊？C#可以用指针？

试验先～

好像不同的，和CLR有不一致的地方～～
比较麻烦，还是放弃了-_-b

[此贴子已经被作者于2005-1-17 10:55:58编辑过]

einsta

这要 看怎么说啦，
你要闲它的垃圾自动回收不好，你就自己pointer...
[em31]

Lasly

那玩意到底是什么时候出啊～～我都等不急了～～～

Recallinfor

汗……楼上的，这是C＋＋和C＃语言探讨，不是出游戏……

Eastsun

              //很经典的一个问题，希望对和我一样菜的学C＋＋的人有些帮助

              //在VC6。0下编译通过

#include <list>
#include <stack>
#include <iostream>
using namespace std;

const int NUMBER=8;
const int MINNUM=4;

class CQueen  
{
public:
bool Start();

CQueen(int num);
virtual ~CQueen();

private:
bool FindAllMethod();
bool ReputQueen();
bool PrintQueenPosition();
bool PutQueen(int position);
bool FindNextPosition(int &nextposition);

private:
bool IsSafe(int currntrow,int currentcolumn);
int m_nNum;
const int m_nQueenNum;
stack<int,list<int> >m_StkPosition;
};

CQueen::CQueen(int num=NUMBER):m_nQueenNum(num<MINNUM?NUMBER:num)
{
m_nNum=0;
}

CQueen::~CQueen()
{

}

bool CQueen::FindAllMethod()
{
int position;

PutQueen(0);
while(!m_StkPosition.empty())
{
if(m_StkPosition.size()>=m_nQueenNum)
{
PrintQueenPosition();
m_nNum++;
ReputQueen();
continue;
}

if(FindNextPosition(position))
{
PutQueen(position);
}
else
{
ReputQueen();
}
}

return true;
}

bool CQueen::FindNextPosition(int &nextposition)
{
stack<int,list<int> >qstack;
int currentrow;

currentrow=m_StkPosition.size();
for(int i=0;i<m_nQueenNum;i++)
{
if(IsSafe(currentrow,i))
{
nextposition=i;
return true;
}
}

return false;
}

bool CQueen:utQueen(int position)
{
m_StkPosition.push(position);

return true;
}

bool CQueen:rintQueenPosition()
{
stack<int,list<int> > qstack;
int item;
int i=0;
char ch;

while(!m_StkPosition.empty())
{
item=m_StkPosition.top();
m_StkPosition.pop();
qstack.push(item);
}

while(!qstack.empty())
{
item=qstack.top();
qstack.pop();
m_StkPosition.push(item);

for(i=0;i<m_nQueenNum;i++)
{
ch=i!=item?'0':'1';
cout<<ch<<" ";
}
cout<<endl;

}
cout<<endl;

return true;
}

bool CQueen::ReputQueen()
{
int column;

while(!m_StkPosition.empty())
{
column=m_StkPosition.top()+1;
m_StkPosition.pop();
while(column<m_nQueenNum)
{
if(IsSafe(m_StkPosition.size(),column))
{
PutQueen(column);
return true;
}
column++;
}
}

return true;
}

bool CQueen::Start()
{
FindAllMethod();
cout<<m_nNum<<endl;;

return true;
}

bool CQueen::IsSafe(int currentrow,int currentcolumn)
{
stack<int ,list<int> >qstack=m_StkPosition;
int comparecolumn,comparerow;

while(!qstack.empty())
{
comparerow=qstack.size()-1;
comparecolumn=qstack.top();

if(comparerow==currentrow||comparecolumn==currentcolumn||
comparecolumn+comparerow==currentcolumn+currentrow||
comparecolumn-comparerow==currentcolumn-currentrow)
{
return false;
}
qstack.pop();
}
return true;
}

int main()
{
CQueen queen(8);
queen.Start();

return 0;
}