残缺棋盘问题
卡通动漫图片-月圆夜
残缺棋盘问题的VC++实现
1. 问题分析
残缺棋盘（defective chessboard）是一个有2
k
×2
k
个方格的棋盘，其中恰有一
个方格残缺。图1给出k≤2时各种可能的残缺棋盘，其中残缺的
方格用阴影表示。
注意当k=0时，仅存在一种可能的残缺棋盘（如图1a所示）。事实上，对于任意k
，
恰好存在2
2k
种不同的残缺棋盘。
残缺棋盘的问题是：要求用三格板（
triominoes）覆盖残缺棋盘（如图2所示）。
在此覆盖中，两个三格板不能重叠，三格板不能
覆盖残缺方格，但必须覆盖其他
所有的方格。在这种限制条件下，所需要的三格板总数为(2
2
k
-1)3。可以验证
(2
2k
-1)3是一个整数。k为0的残缺棋盘很容
易被覆盖，因为它没有非残缺的方格，
用于覆盖的三格板的数目为0。当k=1时，正好存在3个非残缺
的方格，并且这三
个方格可用图2中的某一方向的三格板来覆盖。
用分而治之方法可以很好地
解决残缺棋盘问题。这一方法可将覆盖2k×2k
残缺棋盘的问题转化为覆盖较小残缺棋盘的问题。2k
×2k棋盘一个很自然的划分
方法就是将它划分为如图3a所示的4个2k-1×2k-1棋盘。注意到
当完成这种划分
后，4个小棋盘中仅仅有一个棋盘存在残缺方格。首先覆盖其中包含残缺方格的
2k-1×2k-1残缺棋盘，然后把剩下的3个小棋盘转变为残缺棋盘，为此将一个三
格板放在由这3
个小棋盘形成的角上，如图3b所示，其中原2k×2k棋盘中的残缺
方格落入左上角的2k-1×2k
-1棋盘。可以采用这种分割技术递归地覆盖2k×2k残
缺棋盘。当棋盘的大小减为1×1时，递归过
程终止。此时1×1的棋盘中仅仅包含
一个方格且此方格残缺，所以无需放置三格板。
图1
图2
图3
2.
算法选择
用分而治之方法解决此问题，即为了解决一个大的问题，可以：1)把它分成
两个或
多个更小的问题；2)分别解决每个小问题；3)把各小问题的解答组合起来，
即可得到原问题的解答。
小问题通常与原问题相似，可以递归地使用分而治之策
略来解决。选用递归算法，先构造一个函数，专门
用与递归实现棋盘补充问题。
入口参数分别为棋盘左上角点坐标，棋盘右下角点坐标，棋盘残缺点坐标。
这三
个参数与每次调用它们的棋盘的阶数有关。第一步，取棋盘中点，先判断残缺点
的X，Y在
哪一个区域，同时可覆盖三个小方格，即四个区域分别设定每一个区域
的左上角，右下角和缺点.将它们
分别存入一个数组中。棋盘划分一次，棋子增
加3个，棋盘减少一个，同时又新增加4个棋盘。递归函数
调用，直至所有的子棋
盘都被覆盖。
3. 方案设计
(1)功能部分
本
程序的工作除了在View类中实现游戏的开始，暂停，停止外，主要是
设计了残缺棋盘类CDefBo
ard。在残缺棋盘类CDefBoard中主要实现了：递归
算法实现， 自动创建棋盘，自动创建缺
点，棋盘绘制，缺点绘制等(手动创
建棋盘部分只让k在1-4间取值，是为了既说明了
问题，又可以达到界面美观
的目的)。
(2)界面美化部分
本程序的界面美化部分主要包括：
1) 启动登陆画面的添加；
2)
工具条图标实现了真彩化，精心找得图标，尽量使其达到美观的目的。
4．编程实现
(1)
功能实现：
1) 残缺棋盘类CDefBoard
成员变量：
(a)
tricount变量表示三角板个数；
(b)
m_Size为边长属性，m_DefectR与m_DefectC为缺点的行值与列值。
(c)
Apoint，Bpoint，Cpoint三个数组分别存储每块三角板的第一块、第二
块、第三块的
行列值。
成员函数：
(a) SuanFa()函数是递归算法的具体体现；
(b) AutoBoard()和AutoDefect()函数用于被视图类中自动生成棋盘函数的
调用，实现对随机生成棋盘边长和缺点位置并先后画到视图区中。
(c)
DrawDefect(CDC *pDC)和MyDraw(CDC *pDC)函数用于画缺点和棋盘；
(d) Serialize(CArchive& ar)实现棋盘的存储，即分别将Apoint，
Bpoint，
Cpoint三个数组串行储存于文件中，需要时再串行输出。
2)
视图类CDefChessBView
成员变量：
(a)
AddDefectFlag是否加缺点的标志位；
(b)
BoardFlag是否生成棋盘的标志位；
(c) DefectFlag是否创建缺点的标志位；
(d) StopFlag是否停止的标志位；
(e)
PauseFlag是否暂停的标志位；
(f) StartFlag是否开始的标志位；
(g) AutoFlag是否自动生成残缺棋盘的标志位。
成员函数：
(a) OnAutocreat()函数用于响应用户指令“自动创建棋盘及缺点”；
(b) OnCreatboard()函数用于响应“手动生成棋盘”；
(c)
OnCreatdefect()函数用于响应“手动创建缺点”；
(d) OnStart()函数
为开始消息，启动后先打开定时器，并使手动自动创建
按钮不可用，选择一定的入口参数调用my_bo
ard的SuanFa()函数，并将
所有的三角板存于my_board的三个数组中；
(e) OnPause()函数为暂停消息，取消定时器；
(f) OnStop()函数
为停止消息，启动后清定时器，将累计三角板数置零，并
将存储三角板的三个数组的所有元素置零，后刷
新绘制棋盘；
(g)
Triominoes()函数完成单个三角板的绘制，判别
三角板的形状，针对不
同的方向画出颜色不同的四种三角板；
(h) 以上(a)-(f)的
函数响应UPDATE_COMMAND_UI消息，以实现标志位之间互
相制约。
(2)
界面美化部分
1) 启动画面：通过添加对话框以及在对话框中贴位图来
实现；
2) 工具条图标实现了真彩化：参见MainFrame类中的OnCreate()函数。