CODEWITHSUNDEEP
javascriptmathlinear-algebrasolver
TheDudeofDC
TheDudeofDC

Reputation: 39

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

My code: https://jsfiddle.net/03t2wdrq/

// based on https://www.keithschwarz.com/interesting/code/?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);

I explain what it does, but a better explanation is from where I based my program off of: https://www.keithschwarz.com/interesting/code/?dir=lights-out

My goal is to modify it so that it can return a solution to a puzzle where an arbitrary amount of the tiles in the n*n puzzle matrix are null or some other value other than true or false. These null tiles have no Boolean value, do not affect the solution, and do not detect inputs.

A more polished version of this program I created demonstrates the idea I have when you choose the "walls" option in the input selection: https://jsfiddle.net/5x2as7yq/

// inRange function: Alexander (via Stack Overflow)
// Lesson: Keith Schwarz (via keithschwarz.com)

// Walls do not work, otherwise perfect!

// Shorthand Key:
// p = puzzle
// t = toggle
// x = horizontal index / column number
// y = vertical index / row number
// w = temporary width
// h = temporary height
// i = index
// j = jindex
// next = next free row


//
// Variables
//

// initial matrices
var puzzle = [];
var toggle = [];
var solution = [];
// initial variables
var width = 0;
var height = 0;
var area = 0;
var inputMode = 0;
// elements
const table = document.querySelector("tbody");
const form = document.getElementById("options");
const submit = document.querySelector("caption");
const select = document.querySelector("select");

// 
// Matrix Functions
// 

// check if coords (x, y) are in bounds
function inBounds(x, y) {
    return 0 <= y && y < height && 0 <= x && x < width
}

//
// Create the puzzle and its corresponding arrays
//

// update width, height, and area
function update() {
    let formData = new FormData(form);
    for (const entry of formData.entries()) {
        if (entry[0] == "width") width = Math.round(entry[1]);
        if (entry[0] == "height") height = Math.round(entry[1]);
        if (entry[0] == "mode") inputMode = entry[1];
    }
    area = width * height;
}

// update dimensions, populate display
function populate() {
    select.value = "lights";
    update();

    // populate
    table.replaceChildren();
    puzzle = Array(area).fill(true);
    toggle = Array.from({ length: area }, () => Array(area).fill(false));
    for (let y = 0; y < height; y++) {
        table.insertRow();
        for (let x = 0; x < width; x++) {
            let i = x + y * width;

            // table, puzzle
            table.rows[y].insertCell().addEventListener("click", function () {
                update();
                let cells = table.querySelectorAll("td")
                this.classList.remove("solution");
                if (inputMode == "lights") {
                    this.classList.toggle("off");
                    puzzle[i] = !cells[i].classList.contains("off");
                } else if (inputMode == "walls") {
                    this.classList.toggle("wall");
                    puzzle[i] = cells[i].classList.contains("wall") ? null : cells[i].classList.contains("off");
                } else if (inputMode == "play") {
                    for (let j = 0; j < toggle[y].length; j++) {
                        if (toggle[i][j]) {
                            cells[j].classList.toggle("off");
                            puzzle[j] = !cells[j].classList.contains("off");
                        }
                    }
                }
            });

            // toggle
            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 && inBounds(xNew, yNew)) {
                        toggle[x + y * width][xNew + yNew * width] = true;
                    }
                }
            }
        }
    };
}

//
// Find Solution
// 

// return the solution to a puzzle array using a toggle matrix
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
}

//
// Controls
//

form.addEventListener("submit", function (e) {
    e.preventDefault();
    populate();
});

submit.addEventListener("click", function () {
    solution = solve(puzzle, toggle);

    // show solution
    if (solution == null) {
        submit.innerHTML = "No Solution";
    } else {
        submit.innerHTML = "Done";
        select.value = "play";
        for (let i = 0; i < area; i++) {
            if (solution[i]) {
                table.querySelectorAll("td")[i].classList.add("solution");
            }
        }
    }
    update();
    setTimeout(() => submit.innerHTML = "Solve", 1000);
});

populate();
body {
    /* base size */
    --mult: 30px;
    /* margins */
    --margin: calc(var(--mult) * 0.1);
    --margin2: calc(var(--margin) * 0.5);
    /* space between elements */
    --gap: calc(var(--mult) * 0.3);
    /* input heights */
    --input: calc(var(--mult) * 1.5);
    --select: calc(var(--input) * 0.5);
    /* colors */
    --main-bg: rgb(245, 245, 245);
    --ui-bg-on: rgb(235, 235, 235);
    --ui-bg-off: rgb(195, 195, 195);
    /* default border */
    --border: var(--margin) solid rgb(155, 155, 155);
    --solution: var(--margin) solid rgb(255, 0, 0);
    /* font style */
    font-size: 30px;
    font-family: Arial, Helvetica, sans-serif;

    margin: 0;

    #lightsOut {
        width: fit-content;
        background: var(--main-bg);
        border: var(--border);
        display: flex;
        line-height: var(--input);

        #display {
            margin: var(--margin);
            border-collapse: collapse;

            tbody {
                tr {
                    z-index: 0;

                    td {
                        cursor: pointer;
                        position: relative;
                        box-sizing: border-box;
                        z-index: 0;
                        width: var(--input);
                        height: var(--input);
                        background: var(--ui-bg-on);
                        border: var(--border);

                        &.off {
                            background: var(--ui-bg-off);
                        }

                        &.solution::after {
                            width: var(--gap);
                            height: var(--gap);
                            content: "";
                            display: flex;
                            position: relative;
                            margin: auto;
                            border-radius: 100%;
                            background-color: black;
                        }

                        &.wall {
                            background: none;
                            border: none;
                        }
                    }
                }
            }

            caption {
                cursor: pointer;
                box-sizing: border-box;
                caption-side: bottom;
                width: 100%;
                height: var(--input);
                font-size: var(--mult);
                background: var(--ui-bg-on);
                margin-top: var(--margin);
                border: var(--border);
                user-select: none;
            }
        }

        #options {
            margin: var(--margin);
            margin-left: 0;
            margin-top: calc(var(--margin) + var(--margin2));

            label {
                box-sizing: border-box;
                height: var(--input);
                font-size: var(--mult);
                margin: var(--margin2), 0;
                display: flex;
                user-select: none;
                gap: var(--gap);

                input[type=number],
                select {
                    flex: right;
                    width: var(--input);
                    height: var(--mult);
                    font-size: var(--mult);
                    text-align: center;
                    margin-left: auto;
                    padding: 0;
                    margin-top: auto;
                    margin-bottom: auto;
                }

                select {
                    font-size: var(--select);
                    text-align: left;
                    width: auto;
                }
            }

            button {
                cursor: pointer;
                height: var(--input);
                font-size: var(--mult);
                background: var(--ui-bg-on);
                border: var(--border);
                margin: var(--margin2), 0;
                user-select: none;
                width: 100%;
                display: block;
            }
        }
    }
}

input[type=number]::-webkit-inner-spin-button,
input[type=number]::-webkit-outer-spin-button {
    opacity: 1;
}
<!DOCTYPE html>

<html>

<body>
    <div id="lightsOut">
        <table id="display">
            <tbody>
            </tbody>
            <caption>
                Solve
            </caption>
        </table>
        <form id="options">
            <label>
                Width:
                <input name="width" type="number" value="3" min="3" max="9" required>
            </label>
            <label>
                Height:
                <input name="height" type="number" value="3" min="3" max="9" required>
            </label>
            <button>
                Reset
            </button>
            <label>
                Input:
                <select name="mode">
                    <option value="lights">Lights</option>
                    <option value="walls">Walls</option>
                    <option value="play">Play</option>
                </select>
            </label>
        </form>
    </div>
</body>

<head>
    <link rel="stylesheet" href="LO.css">
    <script src="LO.js"></script>
</head>

</html>

Obviously, introducing walls into the mix would make the number of solvable puzzles much lower, but my goal is to be able to generate solutions for the ones that are.

Please let me know if you need any further info about the programs or question.

Upvotes: 0

Views: 38

Answers (0)

Related Questions