参考blog

棋盘覆盖问题

问题描述

在一个2^k * 2^k个方格组成的棋盘中，有一个方格与其它的不同，若使用以下四种L型骨牌覆盖除这个特殊方格的其它方格，如何覆盖。四个L型骨牌如下图：

L型骨牌

棋盘中的特殊方格如图：

棋盘

        实现的基本原理是将 2^k x 2^k 的棋盘分成四块 2^(k-1) x 2^(k-1)的子棋盘，特殊方格一定在其中的一个子棋盘中，如果特殊方格在某一个子棋盘中，继续递归处理这个子棋盘，直到这个子棋盘中只有一个方格为止如果特殊方格不在某一个子棋盘中，将这个子棋盘中的相应的位置设为骨牌号，将这个无特殊方格的了棋盘转换为有特殊方格的子棋盘，然后再递归处理这个子棋盘。以上原理如图所示：

存在一个方格

棋盘覆盖程序如下：

//2d6 棋盘覆盖问题
#include "stdafx.h"
#include <iostream>     
using namespace std; 

int tile = 1;//全局变量 骨牌编号
int Board[4][4];//棋盘
void ChessBoard(int tr,int tc,int dr,int dc,int size);

int main()
{
    for(int i=0; i<4; i++)
    {
        for(int j=0; j<4; j++)
        {
            Board[i][j] = 0;
        }
    }

    ChessBoard(0,0,2,3,4);

    for(int i=0; i<4; i++)
    {
        for(int j=0; j<4; j++)
        {
            cout<<Board[i][j]<<" ";
        }
        cout<<endl;
    }
}

/**
 * tr : 棋盘左上角的行号，tc棋盘左上角的列号
 * dr : 特殊方格左上角的行号，dc特殊方格左上角的列号
 * size ：size = 2^k 棋盘规格为2^k*2^k
 */
void ChessBoard(int tr,int tc,int dr,int dc,int size)
{
    if(size == 1)
    {
        return;
    }
    int t = tile++;//L型骨牌编号
    int s = size/2;//分割棋盘

    //覆盖左上角子棋盘
    if(dr<tr+s && dc<tc+s)//特殊方格在此棋盘中
    {
        ChessBoard(tr,tc,dr,dc,s);
    }
    else//特殊方格不在此棋盘中
    {
        //用编号为t的骨牌覆盖右下角
        Board[tr+s-1][tc+s-1] = t;
        //覆盖其余方格
        ChessBoard(tr,tc,tr+s-1,tc+s-1,s);
    }

    //覆盖右上角子棋盘
    if(dr<tr+s && dc>=tc+s)//特殊方格在此棋盘中
    {
        ChessBoard(tr,tc+s,dr,dc,s);
    }
    else//特殊方格不在此棋盘中
    {
        //用编号为t的骨牌覆盖左下角
        Board[tr+s-1][tc+s] = t;
        //覆盖其余方格
        ChessBoard(tr,tc+s,tr+s-1,tc+s,s);
    }

    //覆盖左下角子棋盘
    if(dr>=tr+s && dc<tc+s)//特殊方格在此棋盘中
    {
        ChessBoard(tr+s,tc,dr,dc,s);
    }
    else//特殊方格不在此棋盘中
    {
        //用编号为t的骨牌覆盖右上角
        Board[tr+s][tc+s-1] = t;
        //覆盖其余方格
        ChessBoard(tr+s,tc,tr+s,tc+s-1,s);
    }

    //覆盖右下角子棋盘
    if(dr>=tr+s && dc>=tc+s)//特殊方格在此棋盘中
    {
        ChessBoard(tr+s,tc+s,dr,dc,s);
    }
    else//特殊方格不在此棋盘中
    {
        //用编号为t的骨牌覆盖左上角
        Board[tr+s][tc+s] = t;
        //覆盖其余方格
        ChessBoard(tr+s,tc+s,tr+s,tc+s,s);
    }

}

程序运行结果如下：

输出结果

思考

第一步(寻求最小的求解) :

2x2

当只有2x2时，刚好一个L型骨牌 + 特殊方格(任意4个角都可) 。可是暂时看不到如何扩张，所以得考虑4x4的模型。

4x4

棋盘

1.可以分割成4 个 2x2，分别为左上角，右上角，左下角和右下角。
2.右上角可以直接用2x2情况求解，可是其他3块2x2右得按什么 有序步骤 求解？
既然是分治法必然会用到递归，那么大问题必然分解为N个重复可解的小问题(当然小问题的类型个数要可控,一般为1到4个)

---

数学模型：

g(x) = af₁(x) + bf₂(x) + cf₃(x) + df₄(x)， 其中f_i(x)为可解的小问题，a,b,c,d为小问题重复的次数

---

根据公式，我们可以
1.先找各f(x)
2.将f(x)相加成g(x)

---

1.现阶段我们已经分解为2个小问题:

f₁(x) ：存在特殊方格的2x2棋盘的求解
f₂(x) : 3个没有特殊方格的2x2棋盘的求解

2. 当然f₁(x)已经解决，接着考虑f₂(x)。

2.1 考虑f₁(x)在4x4的左上角

f2(x)
如图是f₂(x)求解，
f₂(x)解步骤 ：1.每个2x2先放一个L型骨牌(缺口朝向中央，也只能这样放)，2.在中央放一块L型骨牌(缺口朝向存在特殊方格的2x2棋盘)

2.2 考虑f₁(x)在4x4的其他角落块，同2.1。

第一步 结尾

那么此时我们已经找到了f(x)并都得到了有序解步骤:
f₁(x) ：存在特殊方格的2x2棋盘的求解
f₂(x) : 3个没有特殊方格的2x2棋盘的求解

第二步(组合f(x)来求解g(x)) :

我们将f(x)来接下 8x8时的情况：
分解成4块4x4，存在特殊方格的4x4棋盘同第一步分析求解，可是其他3块4x4不能分解成f₂(x) ,所以现在的f₁(x) 和f₂(x)不满足，从新第一步，求f(x)

重复第一步 :

观察现有的f₁(x) 和f₂(x)
f₁(x) 无法更改
f₂(x) 可考虑。同时在8x8中也是f₂(x)不满足，那么我们得出一套满足各2^k x 2^k有序解步骤

其实有2个解决口：
1.将f₂(x)步骤颠倒试试
2.在2^k x 2^k中分解的每个2^(k-1) x 2^(k-1)棋盘必然应该是相同操作的，那么得出每个2x2棋盘也应该是同f₁(x)，那么就是给没有特殊方格的2x2棋盘各个一个特殊方块(同时3个特殊方块也可以组成一个L型骨牌)

新的f(x)
f₁(x) ：存在特殊方格的2x2棋盘的求解
f₂(x) : 3个没有特殊方格的2x2棋盘各给一个特殊方块(同时3个特殊方块也可以组成一个L型骨牌)，变成f₁(x)的求解

f₂(x) =f₃(x) + 3 *f₁(x)

f₃(x) : 3个没有特殊方格的2x2棋盘各给一个特殊方块(同时3个特殊方块也可以组成一个L型骨牌)

进入第二步

进行归纳法

先证明4x4依据2x2可解，再证明2^k x 2^k 的棋盘依据 2^(k-1) x 2^(k-1)的棋盘可解得出f(x)满足需求

那么递归项就是
f₁(x) +f₂(x) = f₁(x) +f₃(x) + 3 *f₁(x) = f₃(x) + 4 * f₁(x)
在f₁(x) 合并时，要将 f₃(x) 提前，因为有3 *f₁(x) 在 f₃(x) 后

接下来就可以根据有序的解步骤写程序了