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

Question

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).

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.

Possible coverage:

4x4 chessboard missing (4, 1):

Does anyone have any idea what the pseudocode could look like?

Answer 1

The algorithm can be as follows:

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.

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.

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.

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>