有缺陷的棋盘问题——寻找伪代码算法（分而治之）

Question

我应该使用分而治之的范式来设计一个递归算法"CBCover"，它在运行时确定覆盖率（如下图所示）O(n^2) (n = 2 ^k).

CBCover的entry/input应该是(k,a,b)，其中k定义了棋盘的大小，(a,b)是缺失字段的坐标。

可能的覆盖范围：

缺少 4x4 棋盘 (4, 1)：

有谁知道伪代码会是什么样子？

Answer 1

算法可以如下：

确定四个象限中的哪个象限缺少字段。将一个 L 形件放在网格的中心，使其在其他三个象限中的每个象限中占据一个区域。现在您有四个象限，每个象限都有一个不能再使用的字段。递归地解决每个象限，应用相同的策略。当当前网格没有可用字段时递归停止，即它是由一个不可用字段组成的 1x1 网格。

您可以使用不同的数据结构来描述镶嵌。一种方法是创建一个 2D 网格，其中每个单元格都有一个唯一标识其所属形状的值。所以具有相同值的单元格属于一起。

上述算法可以从一个网格开始，该网格首先为每个单元格（0、1、2 等）分配一个唯一值，然后在它们必须属于另一个单元格时将值从一个单元格复制到另一个单元格一样的形状。

这是一个简单的实现 JavaScript。它是交互式的，因此您可以通过单击按钮更改输入，并将鼠标悬停在网格上，您可以识别 "missing field":

// Main algorithm:
function tile(k, a, b) {
    let length = 2**k;
    // Create a grid where each cell has a unique value
    let grid = [];
    for (let y = 0; y < length; y++) {
        let row = [];
        for (let x = 0; x < length; x++) {
             row.push(y*length + x); // unique value
        }
        grid.push(row);
    }
    a = a % length;
    b = b % length;
    
    function recur(length, a, b, top, left) {
        if (length == 1) return;
        let half = length / 2;
        let midrow = top + half;
        let midcol = left + half;
        let quadrant = (a >= midrow) * 2 + (b >= midcol);
        let val = -1;
        for (let i = 0; i < 4; i++) {
            let quadTop = i >= 2 ? midrow : top;
            let quadLeft = i % 2 ? midcol : left;
            let row, col;
            if (quadrant == i) {
                row = a;
                col = b;
            } else {
                row = midrow - 1 + (i >> 1);
                col = midcol - 1 + (i % 2);
                // Add this cell to an L-shape
                if (val == -1) val = grid[row][col];
                else grid[row][col] = val; // join with neighboring cell
            }
            recur(half, row, col, quadTop, quadLeft);
        }
    }
    
    recur(length, a, b, 0, 0);
    return grid;
}

// Parameters of the problem
let k, a, b;

// I/O handling:

function solve(newK, newA, newB) {
    if (newK <= 0) return; // grid must be at least 2x2
    k = newK;
    a = newA;
    b = newB;
    let grid = tile(k, a, b);
    display(grid);
}

let table = document.querySelector("table");

function display(grid) {
    table.innerHTML = "";
    for (let y = 0; y < grid.length; y++) {
        let tr = table.insertRow();
        for (let x = 0; x < grid.length; x++) {
            let val = grid[y][x];
            cls = "";
            if (y && val === grid[y-1][x]) cls += " up";
            if (grid[y+1] && val === grid[y+1][x]) cls += " down";
            if (val === grid[y][x-1]) cls += " left";
            if (val === grid[y][x+1]) cls += " right";
            if (cls === "") cls = "gap";
            tr.insertCell().className = cls.trim();
        }
    }
}

// Allow user to select gap with a click on a cell:
table.addEventListener("mousemove", (e) => {
    let td = e.target;
    if (td.tagName !== "TD") return;
    solve(k, td.parentNode.rowIndex, td.cellIndex);
});

// Allow user to change the size of the grid:
document.querySelector("#dbl").addEventListener("click", () => solve(k+1, a, b));
document.querySelector("#hlf").addEventListener("click", () => solve(k-1, a, b));

// Create, solve and display initial grid
solve(2, 0, 0);

table { border-collapse: collapse }
td { border: 1px solid; width: 10px; height: 10px }
.gap { background: silver }
.up { border-top-color: transparent }
.down { border-bottom-color: transparent }
.left { border-left-color: transparent }
.right { border-right-color: transparent }

<button id="dbl">Increase size</button><button id="hlf">Decrease size</button><br><br>
<table></table><br>

有缺陷的棋盘问题——寻找伪代码算法（分而治之）

Defective chessboard problem - looking for pseudocode algorithm (divide&conquer)

algorithm

recursion

pseudocode

divide-and-conquer