javascript - How can I modify this Lights Out solver algorithm to account for an arbitrary number of missing tiles? - Stack Over

admin管理员组

文章数量:1124382

My code: /

// based on /?dir=lights-out

var puzzle = [];
var toggle = [];
var solution = [];

// initialize toggle matrix where each cell in puzzle has a corresponding row
// each row in toggle is the same length as the total number of cells in the puzzle
// the true values in each row determain which tiles are toggled when a tile is pressed
// in this case, this is the pressed tile and each tile above, below, left, and right of it
function createToggle(p) {
    let t = Array.from({length: area}, () => Array(area).fill(false));
    for (let y = 0; y < height; y++) {
        for (let x = 0; x < width; x++) {
            for (let yOff = -1; yOff <= 1; yOff++) {
                for (let xOff = -1; xOff <= 1; xOff++) {
                    let [xNew, yNew] = [x + xOff, y + yOff];
                    if (Math.abs(xOff) + Math.abs(yOff) < 2 && 0 <= yNew && yNew < height && 0 <= xNew && xNew < width) {
                        t[x + y * width][xNew + yNew * width] = true;
                    }
                }
            }
        }
    }
    return t
}

// solve the puzzle using its toggle matrix and a bunch of fancy math formulas by people smarter than me
// for a great explanation, check the link at the top
function solve(puzzle, toggle) {

    // initialize s, create new copies of p and t
    let p = puzzle.slice(0);
    let t = toggle.map((arr) => {return arr.slice(0)});
    let s = new Array(area).fill(false);

    // gaussian elimination
    let yNext = 0;
    for (let x = 0; x < area; x++) {

        // find next pivot row
        let pivot = -1;
        for (let y = yNext; y < area; y++) {
            if (t[y][x]) {
                pivot = y;
                break
            }
        }
        if (pivot == -1) continue

        // swap index of pivot row and next row in toggle and puzzle
        [t[pivot], t[yNext]] = [t[yNext], t[pivot]];
        [p[pivot], p[yNext]] = [p[yNext], p[pivot]];
        
        // apply XOR to each row after the pivot with a true value in the same column
        for (let y = pivot + 1; y < area; y++) {
            if (t[y][x]) {
                for (let i = 0; i < area; i++) {
                    t[y][i] = t[y][i] ? !t[yNext][i] : t[yNext][i];

                }
                p[y] = p[y] ? !p[yNext] : p[yNext];
            }
        }

        // increase next row
        yNext++;
    }

    // back substitute
    for (let y = area; y-- > 0;) {

        // find the next pivot column
        let pivot = -1;
        for (let x = 0; x < area; x++) {
            if (t[y][x]) {
                pivot = x;
                break
            }
        }
        if (pivot == -1 && p[y]) {
            return null
        }

        // perform back substitution (more magic)
        s[y] = p[y];
        for (let x = pivot + 1; x < area; x++) {
            s[y] = (s[y] != (t[y][x] && s[x]));
        }
    }

    // end
    return s
}

puzzle = [
    [true, false, true, false, true],
    [false, true, true, false, false],
    [true, true, false, true, true],
    [false, true, false, true, true],
    [false, true, true, true, false]
];
let [width, height] = [puzzle[0].length, puzzle.length];
let area = width * height;
puzzle = puzzle.flat(Infinity);

toggle = createToggle(puzzle);

solution = solve(puzzle, toggle);

console.log("puzzle:\n");
console.log(puzzle);
console.log("\ntoggle:\n");
console.log(toggle);
console.log("\nsolution:\n");
console.log(solution);

本文标签：