棋盘覆盖问题（Java）

棋盘覆盖问题（Java）

1、问题描述

在一个2^k×2^k个方格组成的棋盘中,若恰有一个方格与其他方格不同,则称该方格为一特殊方格,且称该棋盘为一个特殊棋盘。显然特殊方格在棋盘上出现的位置有4^k 种情形.因而对任何k ≥ 0,有4^k种不同的特殊棋盘。如下图中的特殊棋盘是当k = 2时16个特殊棋盘中的一个。

在棋盘覆盖问题中,要用下图所示的4种不同形态的L型骨牌覆盖一个给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。易知，在任何一个2^k×2^k的棋盘覆盖中，用到的L型骨牌个数恰好为(4^k - 1)/3。

2、算法设计思路

使用分治策略，可以设计出解棋盘覆盖问题的简洁算法。

当k>0时，将2^k×2^k棋盘分割为4个2^k-1×2^k-1 子棋盘，如下图(a)所示。

特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如下图(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1×1。

3、代码实现

特殊棋盘我们采用0来表示，同时假设特殊方格的位置为第三行第三列

棋盘一分为四之后，依次覆盖左上角子棋盘、右上角子棋盘、左下角子棋盘、右下角子棋盘。如若特殊方格在子棋盘中，则递归执行该子棋盘的操作；若不在，对于左上角子棋盘、右上角子棋盘、左下角子棋盘、右下角子棋盘而言，用编号为t的L型骨牌依次覆盖右下角、左下角、右上角、左上角的方格。

/**
 * TODO  棋盘覆盖算法 特殊棋盘我们采用0来表示
 *
 */
public class chessBoard {

    static final int SIZE = 4;
    static int[][] board = new int[SIZE][SIZE];
    static int title = 1; // title表示L型骨牌的编号

    public static void main(String[] args) {
        // TODO 假设特殊方格的位置为第三行第三列
        board[2][2] = 0;
        ChessBoard(0, 0, 2, 2, SIZE);

        System.out.println(SIZE + "*" + SIZE + "的L型骨牌棋盘为：");
        for (int i = 0; i < SIZE; ++i) {
            for (int j = 0; j < SIZE; j++) {
                System.out.print(board[i][j] + "  ");
            }
            System.out.println();
        }
    }


    /**
     *
     * @param tr    表示棋盘左上角行号
     * @param tc    表示棋盘左上角列号
     * @param dr    表示特殊棋盘的行号
     * @param dc    表示特殊棋盘的列号
     * @param size  =2^k。棋盘的规格为2^k*2^k
     */
    public static void ChessBoard(int tr, int tc, int dr, int dc, int size) {
        if (size == 1) {
            return;
        }
        int t = title++;    // t表示L型骨牌的编号
        int s = size / 2;   // 分割的子棋盘的规格大小（切分为4个子棋盘）

        // TODO 1.覆盖左上角子棋盘
        if (dr < tr + s && dc < tc + s) {
            // TODO 说明特殊方格在此子棋盘中
            ChessBoard(tr, tc, dr, dc, s);
        } else {
            // TODO 说明特殊方格不在此子棋盘中
            //  用t号L型棋盘覆盖这个子棋盘的右下角
            board[tr + s - 1][tc + s - 1] = t;
            // TODO 覆盖其余棋盘方格
            ChessBoard(tr, tc, tr + s - 1, tc + s - 1, s);
        }

        // TODO 2.覆盖右上角子棋盘
        if (dr < tr + s && dc >= tc + s) {
            ChessBoard(tr, tc + s, dr, dc, s);
        } else {
            // 用t号L型棋盘覆盖这个子棋盘的左下角
            board[tr + s - 1][tc + s] = t;
            ChessBoard(tr, tc + s, tr + s - 1, tc + s, s);
        }

        // TODO 3.覆盖左下角子棋盘
        if (dr >= tr + s && dc < tc + s) {
            ChessBoard(tr + s, tc, dr, dc, s);
        } else {
            // 用t号L型棋盘覆盖这个子棋盘的右上角
            board[tr + s][tc + s - 1] = t;
            ChessBoard(tr + s, tc, tr + s, tc + s - 1, s);
        }

        // TODO 4.覆盖右下角子棋盘
        if (dr >= tr + s && dc >= tc + s) {
            ChessBoard(tr + s, tc + s, dr, dc, s);
        } else {
            // // 用t号L型棋盘覆盖这个子棋盘的左上角
            board[tr + s][tc + s] = t;
            ChessBoard(tr + s, tc + s, tr + s, tc + s, s);
        }

    }
}

4、复杂度分析

设T(k)是算法chessBoard覆盖一个2^k×2^k棋盘所需的时间。从算法的分隔策略可以知道，T(k)满足以下的递归方程：

• 当k = 0时，T(k) = O(1),

• 当k > 0时，T(k) = 4T(k - 1) + O(1)

最终此递归方程可得：T(n) = O(4^k)。
由于覆盖2^k×2^k棋盘所需的L型骨牌个数为(4^k - 1)/3，所以此算法是一个在渐进意义下的最优算法。

5、参考

• 算法分析与设计（第四版）