huaxiazhihuo

 

C++代码(2)八皇后问题

        八皇后实在太有名了,我也就不废话了。利用回溯算法,不难写出其代码,相信各位同学也都干过了。那这篇文章还有何新意呢?难道是向各位展示在下的代码要比各位好,绝对不是。只因用C++写代码的时候,很容易就陷入各种细节的纠缠中,必须牢记大刀阔斧地砍除无关紧要的细节,始终坚持用C++清晰地表达解决问题的思路,严格遵守单一职责的规则,集中精力解决问题,不卖弄半点花巧。这是在下努力的一种尝试。
        八皇后的解决方案,相信大家也都知道了,请恕我直奔主题了。
        由于长年累月沉浸于C++中,中毒已经甚深了,碰到任何问题,都条件反射地将其大御八块,然后用CLASS来组织。于是,非常自然的,我决定用类QueenGame来表示八皇后这个游戏,用Play来摆弄出一个安全棋局。当然,不用CLASS,也依然可以写出清晰的代码,但是,感觉总是很不习惯。于是,main起来就非常简单了。
int main()
{
    QueenGame game(
8);
    
if(game.Play())
        DisplayQueen(game);
    
return 0;
}

        为何不让DisplayQueens成为QueenGame的成员,那是因为最后的结果不止显示于控制台,也可能要写入文件中,也可能会绘制于窗口上,而且就算于控制台上,也有多种输出方式,种种可能,无穷无尽,QueenGame难道要用一大堆成员函数来应付这些显示要求,这无疑不切合实际,而且也将污染QueenGame的接口。当一个类无法预料一件操作将如何发生的时候,就应该把这个决定交给上层调用来决定好了,这也是C++一贯的作法,既然我不知道怎么办,那就由用户来决定好了。我们要保持清醒,QueenGame的职责只是要摆出让各个Queen和平共处的局面,至于其他的事情,那都不属于自己的事情。不在其位,不谋其政。
        接下来就要思考QueenGame里面有那些东东,除了Play,肯定还有一些其他东东,最起码也应该有些房子来供皇后们居住。最自然的想法是用一个二维的bool数组chessboard来表示棋盘,假如chessboard[i][j]为true,就表示皇后在上面。但是,目前市面上的作法是用数组来储存N个皇后的位置,数组上的元素的索引表示皇后在棋盘上第几行,其值对应皇后在第几列上,这种储存方式相当方便高效,二维数组如何捣鼓,都没它方便。因此,可以这样定义后宫的地点int m_QueenPos[N],代码有点呆板,似乎应该用使用指针或者引入vector,来灵活处理不同数量的N个皇后,但这样做,将引入一些其他的复杂性,对于本道程序,大可以假设皇后不会太多,10个已经足够多了,牺牲一点点空间,来踢开这个细节,换取程序的安全稳定,我非常乐意。
        由于QueenGame可以Play不同数目的皇后,从1个到10个都可以,因此在QueenGame的构造函应该确立皇后的数量,同时,再提供一个函数GetQueenCount,用以获取她们的数目。QueenGame的初版如下:
class QueenGame
{
public:
    
enum {MAX_QUEEN_COUNT = 10};
    QueenGame(
int queenCount);
public:
    
int GetQueenCount()const
    
bool Play();
private:
    
int m_QueenPos[MAX_QUEEN_COUNT];
}
;
有了这些信息,就可以开始实作DisplayQueen了。但在此之前,还要解决一个问题,就是QueenGame如何让外部函数来访问它的棋盘局面呢?我的作法是直接暴露m_QueenPos,这不是公然违背了面向对象的封装规定吗?这样做,我不会感到一丝丝的不安,因为除此之外,没有更好的办法了,其他的种种方案,都属无病呻吟。比如说,仿效标准库作法,typename一个迭代器,然后再捣鼓出一个begin和end的函数,这将要花费多少精力啊,这么做,仅仅是为了取悦封装要求,而与原本要解决的问题根本是风马牛不相及。那么采用GetQueenPos返回m_QueenPos的地址呢?这与直接访问m_QueenPos并没有多大的区别,如果以为这样就可以满足封装,就可以享受封装带来的好处,纯属在自欺欺人罢了。还是一个办法,就是让DisplayQueens成为QueenGame的friend,这样就可以不破坏封装性,但如DisplayQueens不要为QueenGame的函数成员类似,既然DisplayQueens要为友元,那么WriteQueens也应为friend了,ShowQueens也应为friend了,为了满足封装,搞出这么多花招,画蛇添足。……,但是,这样直接暴露内部状态,总是不安全的,那也没什么,只要订下规则,类外的一切函数不允许修改类的数据成员就OK了。总之,我不想在如何访问m_QueenPos这个小细节上耗费一丁点精力了,我的精力应该集中在原本要解决的问题上。
void DisplayQueen(const QueenGame& game)
{
    
using namespace std;
    
int count = game.GetQueenCount();
    
for (int n = 0; n<count; n++)
    
{
        
for (int i=1; i<=count; i++)
        
{
            
if (game.m_QueenPos[n] == i)
                cout 
<< "Q";
            
else
                cout 
<< "+";
        }

        cout 
<< endl;
    }

    cout 
<< endl;
}
        好了,做足准备工作了,终于来到问题核心了,实作QueenGame的Play函数。这可不是一件容易的事情,起码不像前面的代码那么容易好写。来回顾一下我们聪明的大脑是如何处理这个问题的。面对着棋盘,我们手里拿着8个皇后,先把第1个皇后摆到第1行的第1列上开始,然后按照规则摆放第2个,也即是在第1个皇后的淫威之外给第2个皇后寻找第1个安身之所(总共有6个),然后再在第1、2个皇后的势力范围之外给第3个皇后谋求第1个住所,可知越往后,皇后们的生存空间将越来越狭窄,以至于在第N个皇后的时候,已无安身之所,说明第N-1个皇后的位置不恰当,将她挪到下一个地方,然后再尝试摆上第N个皇后,如果尝试遍了第N-1个皇后的住所,都无法给第N个皇后提供一个去处,说明第N-1个皇后的位置不当,回溯到第N-2个皇后上,然后摆上第N-1个皇后,用这个方法,最后终究能安顿好8个皇后。接下来,就是将其转换成代码,很明显,这里出现了递归。代码的关键在于,当摆上了第N个皇后时,如何表达第N+1个皇后的摆法,当无法摆上时,又该如何回溯到第N-1个皇后上去。当然,该如何停止递归,也不能不考虑。
bool QueenGame::Play()
{
    
int& lastPos = m_QueenPos[m_nLast];
    
while (++lastPos <= m_nQueenCount)
    
{
        
if (testNewQueen())
            
break;
    }

    
if (lastPos > m_nQueenCount)
    
{
        m_nLast
--;
        
if (m_nLast<=0 && m_QueenPos[0> m_nQueenCount)
            
return false;
    }

    
else
    
{
        
if (m_nLast+1 == m_nQueenCount)
            
return true;
        m_nLast
++;
        m_QueenPos[m_nLast] 
= 0;    
    }

    
return Play();
}

        代码用m_nLast纪录Play到第几行了。其实这个变量可以省掉的,只要重新再写一个Play的辅助函数PlayHelper,其带有m_nLast的参数,内部递归调用自己。但是,在下写代码的原则是,能少写函数就少写函数,而且用了m_nLast之后,这个程序还有一个新的功能。于是,QueenGame的定义如下。
class QueenGame
{
public:
    
enum {MAX_QUEEN_COUNT = 10};

    QueenGame(
int queenCount)
    
{
        assert(queenCount 
> 0 && queenCount <= MAX_QUEEN_COUNT );
        m_nQueenCount 
= queenCount;
        m_nLast 
= 0;
        m_QueenPos[m_nLast] 
= 0;
    }


public:
    
int GetQueenCount()const
    
{
        
return m_nQueenCount;
    }

    
bool Play();

    
int m_QueenPos[MAX_QUEEN_COUNT];

private:
    
bool testNewQueen();

    
int m_nQueenCount;
    
int m_nLast;
}
;
        私有函数testNewQueen用以最后的位置是否适合第N个皇后居住,分别从纵向和斜向上予以考察,横向就不用再考虑了,你应该知道WHY的。     
bool QueenGame::testNewQueen()
{
    
int lastPos = m_QueenPos[m_nLast];
    
for (int i=0; i<m_nLast; i++)
    
{
        
if (m_QueenPos[i] == lastPos || abs(m_QueenPos[i]-lastPos)==(m_nLast-i))
            
return false;
    }

    
return true;
}

        激动人心的一刻来临了,程序终于可以跑起来了。再次审视代码的时候,我们惊喜地发现QueenGame的Play函数可以遍历所有的解,只要将main中的if改成while就可以了,非常棒。这都是坚持分离代码的操作与输出,并序将八皇后问题封装成类所带来的好处。
        显然,这里采用了深度优先的搜索算法,代码也可以写成不用递归的形式,还有,这里也可以用宽度优先搜索法,这一切就有待各位尝试了。
        又,程序采用了一点点匈牙利的命名习惯,这是MFC用久了所沾染上的恶习,没办法改了,偶也知道匈牙利命名的种种弊端。

posted on 2011-07-13 19:12 华夏之火 阅读(2273) 评论(4)  编辑 收藏 引用

评论

# re: C++代码(2)八皇后问题[未登录] 2011-07-14 21:14 cexer

楼主你的文章质量都不错,就是有点偏离群众口味。  回复  更多评论   

# re: C++代码(2)八皇后问题 2011-07-15 08:45 华夏之火

@cexer
谢谢,这是一个系列,打算用C++清晰地表达一些玩具程序,干点实事,而不是整天用C++玩弄一些华而不实的语言技巧
  回复  更多评论   

# re: C++代码(2)八皇后问题 2011-07-15 09:15 Paw

我很喜欢这个系列,LZ的编程能力很NX。。。很喜欢看  回复  更多评论   

# re: C++代码(2)八皇后问题 2011-07-15 10:34 黑莓掌

C++这种程序,从技术上来讲,挺高级的.  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

统计

常用链接

留言簿(3)

随笔分类

随笔档案

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜