缺陷棋盘问题——寻找伪代码算法(分而治之) [英] Defective chessboard problem - looking for pseudocode algorithm (divide&conquer)

问题描述

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

I should use the divide-and-conquer paradigm to design a recursive algorithm "CBCover", which determines a coverage (as seen in the image below) in runtime O(n^2) (n = 2^k).

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

The entry/ input of CBCover should be (k, a, b), where k defines the size of the chessboard, and (a, b) are the coordinates of the missing field.

可能的覆盖范围:

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

4x4 chessboard missing (4, 1):

有人知道伪代码的样子吗?

推荐答案

算法可以如下:

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

Determine which of the four quadrants has the missing field. Position an L-piece in the centre of the grid such that it occupies one field in each of the three other quadrants. Now you have four quadrants with each a field that cannot be used any more. Solve each of those quadrants recursively, applying the same strategy. The recursion stops when the current grid has no available field, i.e. it is a 1x1 grid consisting of a field that is not available.

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

There are different possible data structures you could use to describe the tessalation. One way is to create a 2D grid, where each cell gets a value that uniquely identifies the shape it belongs to. So cells with the same value belong together.

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

The above algorithm could start with a grid that first assigns a unique value to each cell (0, 1, 2, ...etc), and then copies the value from one cell to another when they must belong to the same shape.

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

Here is an implementation in simple JavaScript. It is interactive, so you can change the input by clicking the buttons, and by hovering the mouse over the grid, you identify the "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>

这篇关于缺陷棋盘问题——寻找伪代码算法(分而治之)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！