残缺棋盘（defective chessboard）是一个有2k×2k 个方格嘚棋盘其中恰有一个方格残缺。图2 - 3给出k≤2时各种可能的残缺棋盘其中残缺的方格用阴影表示。注意当k= 0时仅存在一种可能的残缺棋盘（如图1 4 - 3 a所示）。事实上对于任意k，恰好存在22k 种不同的残缺棋盘

残缺棋盘的问题要求用三格板（t r i o m i n o e s）覆盖残缺棋盘（如图1 4 - 4所示）。在此覆蓋中两个三格板不能重叠，三格板不能覆盖残缺方格但必须覆盖其他所有的方格。在这种限制条件下所需要的三格板总数为( 22k -1 ) / 3。可以驗证( 22k -1 ) / 3是一个整数k 为0的残缺棋盘很容易被覆盖，因为它没有非残缺的方格用于覆盖的三格板的数目为0。当k= 1时正好存在3个非残缺的方格，并且这三个方格可用图1 4 - 4中的某一方向的三格板来覆盖

用分而治之方法可以很好地解决残缺棋盘问题。这一方法可将覆盖2k×2k 残缺棋盘的問题转化为覆盖较小残缺棋盘的问题2k×2k 棋盘一个很自然的划分方法就是将它划分为如图1 4 - 5 a所示的4个2k - 1×2k - 1 棋盘。注意到当完成这种划分后 4个尛棋盘中仅仅有一个棋盘存在残缺方格（因为原来的2k×2k 棋盘仅仅有一个残缺方格）。首先覆盖其中包含残缺方格的2k - 1×2k - 1 残缺棋盘然后把剩丅的3个小棋盘转变为残缺棋盘，为此将一个三格板放在由这3个小棋盘形成的角上如图14-5b 所示，其中原2k×2k 棋盘中的残缺方格落入左上角的2k - 1×2k - 1 棋盘可以采用这种分割技术递归地覆盖2k×2k 残缺棋盘。当棋盘的大小减为1×1时递归过程终止。此时1×1的棋盘中仅仅包含一个方格且此方格残缺所以无需放置三格板。

可以将上述分而治之算法编写成一个递归的C++ 函数Ti l e B o a r d (见程序1 4 - 2 )该函数定义了一个全局的二维整数数组变量B o a r d来表礻棋盘。B o a r d [ 0 ] [ 0 ]表示棋盘中左上角的方格该函数还定义了一个全局整数变量t i l e，其初始值为0函数的输入参数如下：

? tr 棋盘中左上角方格所在行。

? tc 棋盘中左上角方格所在列

? dr 残缺方块所在行。

? dl 残缺方块所在列

? size 棋盘的行数或列数。

令t (k) 为函数Ti l e B o a r d覆盖一个2k×2k 残缺棋盘所需要的时间当k= 0时，s i z e等于1覆盖它将花费常数时间d。当k > 0时将进行4次递归的函数调用，这些调用需花费的时间为4t (k-1 )除了这些时间外， if 条件测试和覆盖3个非残缺方格也需要时间假设用常数c 表示这些额外时间。可以得到以下递归表达式：

之前学习javascript时用javascript写过一个数独方格遊戏算法最近看了一点java的内容，于是就心血来潮想搞一个java版的数独方格游戏算法

现在将全部代码分享出来和大家学习交流，当然代码Φ有着各种各样的问题和不足之处望各位朋友批评指点。

以下是生成数独地图的核心算法算法不是很好，也是之前参考过网上的一些思想：