残缺棋盘

韩冰

<b>残缺棋盘</b>
<>残缺棋盘（defective chessboard）是一个有2k×2k 个方格的棋盘，其中恰有一个方格残缺。图2 - 3给出k≤2时各种可能的残缺棋盘，其中残缺的方格用阴影表示。注意当k= 0时，仅存在一种可能的残缺棋盘（如图1 4 - 3 a所示）。事实上，对于任意k，恰好存在22k 种不同的残缺棋盘。
' w0 f! R% O' H8 N
残缺棋盘的问题要求用三格板（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中的某一方向的三格板来覆盖。
4 y! j: k  }4 D( z6 _: J
; a9 B# G+ T6 m用分而治之方法可以很好地解决残缺棋盘问题。这一方法可将覆盖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。函数的输入参数如下：

( _4 F+ \8 C5 ^% p! r1 f, J, E- w? tr 棋盘中左上角方格所在行。
6 k' F; f; i( N( |
? tc 棋盘中左上角方格所在列。

? dr 残缺方块所在行。
& {. ~2 {% R0 v
? dl 残缺方块所在列。

9 Z  Y  y( T( p  O$ n; a( z  _? size 棋盘的行数或列数。

5 f: c" J7 \* E& T7 MTi l e B o a r d函数的调用格式为Ti l e B o a r d（0,0, dr, dc,size)，其中s i z e = 2k。覆盖残缺棋盘所需要的三格板数目为( s i z e2 -1 ) / 3。函数TileBoard 用整数1到( s i z e2-1 ) / 3来表示这些三格板，并用三格板的标号来标记被该三格板覆盖的非残缺方格。

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

程序14-2 覆盖残缺棋盘

void TileBoard(int tr, int tc, int dr, int dc, int size)

2 ^; e$ ^+ E5 N" c4 `/ j{// 覆盖残缺棋盘

5 U$ P: x7 w5 I; R0 y( K, W! Gif (size == 1) return;

int t = tile++, // 所使用的三格板的数目

s = size/2; // 象限大小
/ Q; l4 ]1 j, A& X! d- i
/ /覆盖左上象限

if (dr &lt; tr + s &amp;&amp; dc &lt; tc + s)
% ], A6 i. [; [# `5 v
8 p$ y& p$ o# T' w2 ?// 残缺方格位于本象限
1 D6 i3 F' h$ m: Y
Ti l e B o a r d ( t r, tc, dr, dc, s);
. ^# F# D; T2 Y9 }+ `, O" i
else {// 本象限中没有残缺方格
  t  g0 Y  m9 Q% M# q8 B: O
// 把三格板t 放在右下角

. e2 I; f2 @- BBoard[tr + s - 1][tc + s - 1] = t;

1 l/ j0 z* n+ K2 O2 ]2 `3 S: e// 覆盖其余部分

- d2 ?$ k+ @& P7 @* _: TTi l e B o a r d ( t r, tc, tr+s-1, tc+s-1, s);}
( i5 I0 ?% M3 G1 t$ O9 P+ c" y
/ /覆盖右上象限
- b7 P; m- J- B+ R+ v
if (dr &lt; tr + s &amp;&amp; dc &gt;= tc + s)
/ [" k! W4 P7 B5 A1 p1 \
// 残缺方格位于本象限

Ti l e B o a r d ( t r, tc+s, dr, dc, s);
) f3 H5 G* Y# X5 q
; j0 y8 G7 y0 l$ Selse {// 本象限中没有残缺方格
; S( p6 w- ~" H' ?$ E" d$ `
// 把三格板t 放在左下角

Board[tr + s - 1][tc + s] = t;

// 覆盖其余部分
9 y+ D" j: a! ]3 g: }
% {) y" b+ I1 m# W$ D; j% \Ti l e B o a r d ( t r, tc+s, tr+s-1, tc+s, s);}

% ?% l- O/ v2 d/ /覆盖左下象限

if (dr &gt;= tr + s &amp;&amp; dc &lt; tc + s)

2 Q" r0 h3 ]0 J6 q3 `// 残缺方格位于本象限
( X2 o2 N3 `0 c2 b
" V2 G4 ^1 u3 p' vTileBoard(tr+s, tc, dr, dc, s);
: @0 O: D. w% s$ _: R+ Z& V, a
else {// 把三格板t 放在右上角

! X; u1 u2 N; F$ k, _Board[tr + s][tc + s - 1] = t;
7 n( D! g) Y9 `# X8 ?4 P: t
7 F" w- t: g8 S5 h3 f1 B// 覆盖其余部分
" n  A3 d; {9 b% g$ l% Y2 O
TileBoard(tr+s, tc, tr+s, tc+s-1, s);}

2 Y+ u+ \% {* [0 ]6 Y) ]$ W// 覆盖右下象限
/ s3 y2 x& L& ~' z9 N+ x  H
if (dr &gt;= tr + s &amp;&amp; dc &gt;= tc + s)
* O6 d$ {2 K/ S, I/ D# `  `- I& X7 T
* R2 S! j8 {, d% D4 y* ?2 F// 残缺方格位于本象限

TileBoard(tr+s, tc+s, dr, dc, s);

- m3 e7 o- j# F# ]$ Ielse {// 把三格板t 放在左上角

9 P6 b1 f# a, h) l9 u! _3 r: U. zBoard[tr + s][tc + s] = t;
3 D* W" z. m& g3 i& K% f' M
// 覆盖其余部分
0 R5 {; d; |# z: u
! {2 W) F0 T3 z6 b$ w  UTileBoard(tr+s, tc+s, tr+s, tc+s, s);}

}

void OutputBoard(int size)
% h' Q( Y- n7 b7 L9 G/ B2 \, e( J
{
9 D+ ~) W, F% x2 R4 m  o
for (int i = 0; i &lt; size; i++) {
/ C6 ~( n- G! o' F( u$ w% h$ a
for (int j = 0; j &lt; size; j++)
2 I6 U$ E1 M, x
cout &lt;&lt; setw (5) &lt;&lt; Board[j];

: o# n: q/ n! J( A" I! X, j! V' Hcout &lt;&lt; endl;

}

  D% Z# j5 i" r}

可以用迭代的方法来计算这个表达式（见例2 - 2 0），可得t (k )= ( 4k )= （所需的三格板的数目）。由于必须花费至少( 1 )的时间来放置每一块三格表，因此不可能得到一个比分而治之算法更快的算法。</P>

yammay

<>太感谢啦。找了好久才找到这个程序。真是真是太感谢啦。有点激动</P>

wendy28

我们学过了,很经典的一道题！

cupidvenus

没看明白，图呢？