solver.js

const ROW0_MASK = 0x00000000000000FFn;
const ROW7_MASK = 0xFF00000000000000n;
const COL0_MASK = 0x0101010101010101n;
const COL7_MASK = 0x8080808080808080n;
const NOT_COL7_MASK = 0x7F7F7F7F7F7F7F7Fn;
const NOT_COL0_MASK = 0xFEFEFEFEFEFEFEFEn;
const MASK_64 = 0xFFFFFFFFFFFFFFFFn;
const INF = 10000;
const MAX_BIDIR_GOALS = 12000;
const MAX_BIDIR_STATES = 3000000;
let REVERSE_LINE_TABLE = null;
let LINE_BITBOARDS = null;
function shiftU(x) { return x >> 8n; }
function shiftD(x) { return (x << 8n) & MASK_64; }
function shiftL(x) { return (x >> 1n) & NOT_COL7_MASK; }
function shiftR(x) { return (x << 1n) & NOT_COL0_MASK & MASK_64; }

function ctzll(n) {
    if (n === 0n) return 64;
    let count = 0;
    while ((n & 1n) === 0n) {
        count++;
        n >>= 1n;
    }
    return count;
}

function popcount8(x) {
    x -= (x >> 1) & 0x55;
    x = (x & 0x33) + ((x >> 2) & 0x33);
    return (x + (x >> 4)) & 0x0f;
}

function stepLineBits(bits, walls, dir) {
    let moving = bits & ~walls;

    for (let iter = 0; iter < 8; iter++) {
        let blocked = 0;
        const stationary = bits ^ moving;

        for (let i = 0; i < 8; i++) {
            const bit = 1 << i;
            if ((moving & bit) === 0) continue;

            const next = dir === 2 ? i - 1 : i + 1;
            if (next < 0 || next >= 8) {
                blocked |= bit;
                continue;
            }

            const nextBit = 1 << next;
            if ((walls & nextBit) || (stationary & nextBit)) {
                blocked |= bit;
            }
        }

        if (blocked === 0) break;
        moving ^= blocked;
    }

    let out = bits ^ moving;
    for (let i = 0; i < 8; i++) {
        const bit = 1 << i;
        if ((moving & bit) === 0) continue;
        out |= 1 << (dir === 2 ? i - 1 : i + 1);
    }

    return out & 0xff;
}

function getReverseLineTable() {
    if (REVERSE_LINE_TABLE) return REVERSE_LINE_TABLE;

    const table = [null, null, new Array(256 * 256), new Array(256 * 256)];
    for (let dir = 2; dir <= 3; dir++) {
        for (let wall = 0; wall < 256; wall++) {
            for (let result = 0; result < 256; result++) {
                table[dir][wall * 256 + result] = [];
            }

            for (let bits = 0; bits < 256; bits++) {
                if (bits & wall) continue;
                const result = stepLineBits(bits, wall, dir);
                table[dir][wall * 256 + result].push(bits);
            }
        }
    }

    REVERSE_LINE_TABLE = table;
    return table;
}

function getLineBitboards() {
    if (LINE_BITBOARDS) return LINE_BITBOARDS;

    const rows = Array.from({ length: 8 }, () => new Array(256));
    const cols = Array.from({ length: 8 }, () => new Array(256));

    for (let line = 0; line < 8; line++) {
        for (let bits = 0; bits < 256; bits++) {
            let rowBoard = 0n;
            let colBoard = 0n;

            for (let i = 0; i < 8; i++) {
                if ((bits & (1 << i)) === 0) continue;
                rowBoard |= 1n << BigInt(line * 8 + i);
                colBoard |= 1n << BigInt(i * 8 + line);
            }

            rows[line][bits] = rowBoard;
            cols[line][bits] = colBoard;
        }
    }

    LINE_BITBOARDS = { rows, cols };
    return LINE_BITBOARDS;
}

function combinationCount(n, k, limit) {
    if (k < 0 || k > n) return 0;
    k = Math.min(k, n - k);
    let count = 1;
    for (let i = 1; i <= k; i++) {
        count = (count * (n - k + i)) / i;
        if (count > limit) return count;
    }
    return count;
}

class FlatQueue {
    constructor() {
        this.capacity = 1 << 20;
        this.id = new Int32Array(this.capacity);
        this.g = new Uint16Array(this.capacity);
        this.f = new Uint16Array(this.capacity);
        this.size = 0;
    }
    grow() {
        this.capacity *= 2;
        let new_id = new Int32Array(this.capacity); new_id.set(this.id); this.id = new_id;
        let new_g = new Uint16Array(this.capacity); new_g.set(this.g); this.g = new_g;
        let new_f = new Uint16Array(this.capacity); new_f.set(this.f); this.f = new_f;
    }
    push(id, g, f) {
        if (this.size >= this.capacity) this.grow();
        let idx = this.size++;
        while (idx > 0) {
            const parentIdx = (idx - 1) >> 1;
            const p_f = this.f[parentIdx];
            const p_g = this.g[parentIdx];
            if (f > p_f || (f === p_f && g <= p_g)) break;
            this.id[idx] = this.id[parentIdx];
            this.g[idx] = p_g;
            this.f[idx] = p_f;
            idx = parentIdx;
        }
        this.id[idx] = id;
        this.g[idx] = g;
        this.f[idx] = f;
    }
    pop() {
        const top_id = this.id[0];
        const top_g = this.g[0];
        const top_f = this.f[0];
        this.size--;
        if (this.size > 0) {
            const bottom_id = this.id[this.size];
            const bottom_g = this.g[this.size];
            const bottom_f = this.f[this.size];
            let idx = 0;
            const halfLength = this.size >> 1;
            while (idx < halfLength) {
                let leftChildIdx = (idx << 1) + 1;
                let rightChildIdx = leftChildIdx + 1;
                let swapIdx = leftChildIdx;
                if (rightChildIdx < this.size) {
                    if (this.f[rightChildIdx] < this.f[leftChildIdx] || (this.f[rightChildIdx] === this.f[leftChildIdx] && this.g[rightChildIdx] > this.g[leftChildIdx])) {
                        swapIdx = rightChildIdx;
                    }
                }
                if (bottom_f < this.f[swapIdx] || (bottom_f === this.f[swapIdx] && bottom_g > this.g[swapIdx])) break;
                this.id[idx] = this.id[swapIdx];
                this.g[idx] = this.g[swapIdx];
                this.f[idx] = this.f[swapIdx];
                idx = swapIdx;
            }
            this.id[idx] = bottom_id;
            this.g[idx] = bottom_g;
            this.f[idx] = bottom_f;
        }
        return { id: top_id, g: top_g, f: top_f };
    }
    isEmpty() { return this.size === 0; }
}

class StateMap {
    constructor(capacityLog2) {
        this.capacity = 1 << capacityLog2;
        this.mask = this.capacity - 1;
        this.keys = new BigUint64Array(this.capacity);
        this.vals = new Uint16Array(this.capacity);
        this.used = new Uint8Array(this.capacity);
        this.size = 0;
        this.vals.fill(65535);
    }
    hash(k) {
        let h = Number((k ^ (k >> 32n)) & 0xFFFFFFFFn);
        h ^= h >>> 16;
        h = Math.imul(h, 0x85ebca6b);
        h ^= h >>> 13;
        h = Math.imul(h, 0xc2b2ae35);
        h ^= h >>> 16;
        return h & this.mask;
    }
    set(k, v) {
        if ((this.size + 1) * 10 > this.capacity * 7) this.grow();
        let idx = this.hash(k);
        while (true) {
            if (this.used[idx] === 0) {
                this.keys[idx] = k;
                this.vals[idx] = v;
                this.used[idx] = 1;
                this.size++;
                return;
            }
            if (this.keys[idx] === k) {
                this.vals[idx] = v;
                return;
            }
            idx = (idx + 1) & this.mask;
        }
    }
    get(k) {
        let idx = this.hash(k);
        while (true) {
            if (this.used[idx] === 0) return 65535;
            if (this.keys[idx] === k) return this.vals[idx];
            idx = (idx + 1) & this.mask;
        }
    }
    grow() {
        const oldKeys = this.keys;
        const oldVals = this.vals;
        const oldUsed = this.used;
        this.capacity *= 2;
        this.mask = this.capacity - 1;
        this.keys = new BigUint64Array(this.capacity);
        this.vals = new Uint16Array(this.capacity);
        this.used = new Uint8Array(this.capacity);
        this.vals.fill(65535);
        const oldSize = this.size;
        this.size = 0;
        for (let i = 0; i < oldUsed.length; i++) {
            if (oldUsed[i]) this.set(oldKeys[i], oldVals[i]);
        }
        this.size = oldSize;
    }
}

class History {
    constructor() {
        this.capacity = 1 << 20;
        this.state = new BigUint64Array(this.capacity);
        this.parent = new Int32Array(this.capacity);
        this.dir = new Uint8Array(this.capacity);
        this.size = 0;
    }
    grow() {
        this.capacity *= 2;
        let new_state = new BigUint64Array(this.capacity); new_state.set(this.state); this.state = new_state;
        let new_parent = new Int32Array(this.capacity); new_parent.set(this.parent); this.parent = new_parent;
        let new_dir = new Uint8Array(this.capacity); new_dir.set(this.dir); this.dir = new_dir;
    }
    add(state, parent, dir) {
        if (this.size >= this.capacity) this.grow();
        let id = this.size++;
        this.state[id] = state;
        this.parent[id] = parent;
        this.dir[id] = dir;
        return id;
    }
}

class Solver {
    constructor(bgGrid, fgGrid) {
        this.bgGrid = bgGrid;
        this.fgGrid = fgGrid;
        this.WALLS = this.encodeBg('#');
        this.TARGET = this.encodeBg('T');
        this.start_state = this.encodeFg('Y');
        this.dist_table = new Array(64).fill(INF);
        this.targetCells = [];
        this.blockCount = this.popcount(this.start_state);
        this.targetCount = this.popcount(this.TARGET);
        this.rowWalls = new Uint8Array(8);
        this.colWalls = new Uint8Array(8);
        this.initLineWalls();
        this.initHeuristicTable();
    }

    encodeBg(targetChar) {
        let bitboard = 0n;
        for (let r = 0; r < 8; ++r) {
            for (let c = 0; c < 8; ++c) {
                if (this.bgGrid[r][c] === targetChar) {
                    bitboard |= (1n << BigInt(r * 8 + c));
                }
            }
        }
        return bitboard;
    }

    encodeFg(targetChar) {
        let bitboard = 0n;
        for (let r = 0; r < 8; ++r) {
            for (let c = 0; c < 8; ++c) {
                if (this.fgGrid[r][c] === targetChar) {
                    bitboard |= (1n << BigInt(r * 8 + c));
                }
            }
        }
        return bitboard;
    }

    initLineWalls() {
        for (let r = 0; r < 8; r++) {
            this.rowWalls[r] = Number((this.WALLS >> BigInt(r * 8)) & 0xffn);
        }

        for (let c = 0; c < 8; c++) {
            let mask = 0;
            for (let r = 0; r < 8; r++) {
                if ((this.WALLS >> BigInt(r * 8 + c)) & 1n) {
                    mask |= 1 << r;
                }
            }
            this.colWalls[c] = mask;
        }
    }

    initHeuristicTable() {
        const q = [];
        for (let i = 0; i < 64; ++i) {
            if ((this.TARGET >> BigInt(i)) & 1n) {
                this.dist_table[i] = 0;
                this.targetCells.push(i);
                q.push(i);
            }
        }

        let head = 0;
        while (head < q.length) {
            const curr = q[head++];
            const nextDist = this.dist_table[curr] + 1;
            const r = curr >> 3;
            const c = curr & 7;
            const neighbors = [];
            if (r > 0) neighbors.push(curr - 8);
            if (r < 7) neighbors.push(curr + 8);
            if (c > 0) neighbors.push(curr - 1);
            if (c < 7) neighbors.push(curr + 1);

            for (let i = 0; i < neighbors.length; i++) {
                const nxt = neighbors[i];
                if (((this.WALLS >> BigInt(nxt)) & 1n) || this.dist_table[nxt] <= nextDist) continue;
                this.dist_table[nxt] = nextDist;
                q.push(nxt);
            }
        }
    }

    getHeuristic(state) {
        if (this.targetCount !== this.blockCount) return INF;
        if (this.blockCount === 0) return 0;

        let h = 0;
        let sumBlockMin = 0;
        let temp = state;
        while (temp > 0n) {
            let idx = ctzll(temp);
            const blockMin = this.dist_table[idx];
            if (blockMin === INF) return INF;
            sumBlockMin += blockMin;
            if (blockMin > h) h = blockMin;
            temp &= (temp - 1n);
        }

        h = Math.max(h, Math.ceil(sumBlockMin / this.blockCount));
        return h;
    }

    isSolved(state) {
        return (state & this.TARGET) === state;
    }

    countOnTargets(state) {
        return this.popcount(state & this.TARGET);
    }

    pathToResult(path, message) {
        const states = [this.start_state];
        let state = this.start_state;
        const dirChars = ['U', 'D', 'L', 'R'];

        for (let i = 0; i < path.length; i++) {
            const dir = dirChars.indexOf(path[i]);
            state = this.moveBitboard(state, dir);
            states.push(state);
        }

        return {
            success: true,
            message: message || `Solution in ${path.length} steps`,
            path: path.split(''),
            states: states
        };
    }

    solveBeam(deadline, width = 12000, maxDepth = 128) {
        const dirChars = ['U', 'D', 'L', 'R'];
        const dirOrder = [1, 3, 0, 2];
        let beam = [{ state: this.start_state, path: '', score: this.getBeamScore(this.start_state) }];
        const seen = new Set([this.start_state]);

        if (this.isSolved(this.start_state)) {
            return this.pathToResult('', 'Solution in 0 steps');
        }

        for (let depth = 0; depth < maxDepth && Date.now() <= deadline; depth++) {
            const candidates = [];

            for (let i = 0; i < beam.length; i++) {
                const node = beam[i];

                for (let j = 0; j < dirOrder.length; j++) {
                    const dir = dirOrder[j];
                    const nextState = this.moveBitboard(node.state, dir);
                    if (nextState === node.state || seen.has(nextState)) continue;

                    const nextPath = node.path + dirChars[dir];
                    if (this.isSolved(nextState)) {
                        return this.pathToResult(nextPath, `Alternate solution in ${nextPath.length} steps (not proven optimal)`);
                    }

                    const h = this.getHeuristic(nextState);
                    if (h === INF) continue;

                    seen.add(nextState);
                    candidates.push({
                        state: nextState,
                        path: nextPath,
                        score: this.getBeamScore(nextState, h)
                    });
                }
            }

            if (candidates.length === 0) break;
            candidates.sort((a, b) => a.score - b.score || a.path.length - b.path.length);
            beam = candidates.slice(0, width);
        }

        return { success: false, message: "No solution found within the time limit. Try increasing the effort.", path: [], states: [] };
    }

    getBeamScore(state, h = this.getHeuristic(state)) {
        return h * 10 - this.countOnTargets(state);
    }

    getGoalStates(limit = MAX_BIDIR_GOALS) {
        const total = combinationCount(this.targetCount, this.blockCount, limit);
        if (total > limit) return null;

        const goals = [];
        const cells = this.targetCells;
        const choose = this.blockCount;

        const visit = (start, remaining, state) => {
            if (remaining === 0) {
                goals.push(state);
                return;
            }

            const lastStart = cells.length - remaining;
            for (let i = start; i <= lastStart; i++) {
                visit(i + 1, remaining - 1, state | (1n << BigInt(cells[i])));
            }
        };

        visit(0, choose, 0n);
        return goals;
    }

    rowBits(state, row) {
        return Number((state >> BigInt(row * 8)) & 0xffn);
    }

    colBits(state, col) {
        let bits = 0;
        for (let row = 0; row < 8; row++) {
            if ((state >> BigInt(row * 8 + col)) & 1n) bits |= 1 << row;
        }
        return bits;
    }

    forEachPredecessor(state, dir, visit) {
        const reverseTable = getReverseLineTable();
        const bitboards = getLineBitboards();
        const choices = new Array(8);

        if (dir === 2 || dir === 3) {
            for (let row = 0; row < 8; row++) {
                const resultBits = this.rowBits(state, row);
                const rowChoices = reverseTable[dir][this.rowWalls[row] * 256 + resultBits];
                if (rowChoices.length === 0) return true;
                choices[row] = rowChoices;
            }

            const combineRows = (row, acc) => {
                if (row === 8) return visit(acc);
                const rowBoards = bitboards.rows[row];
                const rowChoices = choices[row];
                for (let i = 0; i < rowChoices.length; i++) {
                    if (combineRows(row + 1, acc | rowBoards[rowChoices[i]]) === false) {
                        return false;
                    }
                }
                return true;
            };

            return combineRows(0, 0n);
        }

        const lineDir = dir === 0 ? 2 : 3;
        for (let col = 0; col < 8; col++) {
            const resultBits = this.colBits(state, col);
            const colChoices = reverseTable[lineDir][this.colWalls[col] * 256 + resultBits];
            if (colChoices.length === 0) return true;
            choices[col] = colChoices;
        }

        const combineCols = (col, acc) => {
            if (col === 8) return visit(acc);
            const colBoards = bitboards.cols[col];
            const colChoices = choices[col];
            for (let i = 0; i < colChoices.length; i++) {
                if (combineCols(col + 1, acc | colBoards[colChoices[i]]) === false) {
                    return false;
                }
            }
            return true;
        };

        return combineCols(0, 0n);
    }

    buildBidirectionalResult(meet, forwardParent, backwardParent, pathLength) {
        const dirChars = ['U', 'D', 'L', 'R'];
        const prefix = [];
        const suffix = [];

        let state = meet;
        while (forwardParent.has(state)) {
            const parent = forwardParent.get(state);
            prefix.push(parent.dir);
            state = parent.prev;
        }
        prefix.reverse();

        state = meet;
        while (backwardParent.has(state)) {
            const parent = backwardParent.get(state);
            suffix.push(parent.dir);
            state = parent.next;
        }

        const path = prefix.concat(suffix).map(dir => dirChars[dir]).join('');
        return this.pathToResult(path, `Optimal solution in ${pathLength} steps`);
    }

    solveBidirectional(deadline, maxVisited = MAX_BIDIR_STATES) {
        const goals = this.getGoalStates();
        if (!goals) {
            return { success: false, incomplete: true, message: "Too many target combinations for exact bidirectional search.", path: [], states: [] };
        }

        const forwardDepth = new Map([[this.start_state, 0]]);
        const backwardDepth = new Map();
        const forwardParent = new Map();
        const backwardParent = new Map();
        let forwardFrontier = [this.start_state];
        let backwardFrontier = [];
        let fDepth = 0;
        let bDepth = 0;

        for (let i = 0; i < goals.length; i++) {
            const goal = goals[i];
            if (forwardDepth.has(goal)) {
                return this.buildBidirectionalResult(goal, forwardParent, backwardParent, 0);
            }
            backwardDepth.set(goal, 0);
            backwardFrontier.push(goal);
        }

        let bestLen = Infinity;
        let bestMeet = null;

        const rememberBest = (state, len) => {
            if (len < bestLen) {
                bestLen = len;
                bestMeet = state;
            }
        };

        while (forwardFrontier.length > 0 && backwardFrontier.length > 0) {
            if (bestMeet !== null && fDepth + bDepth + 1 >= bestLen) {
                return this.buildBidirectionalResult(bestMeet, forwardParent, backwardParent, bestLen);
            }

            if (Date.now() > deadline) {
                return { success: false, incomplete: true, message: "Bidirectional search timed out.", path: [], states: [] };
            }
            if (forwardDepth.size + backwardDepth.size > maxVisited) {
                return { success: false, incomplete: true, message: "Bidirectional search reached the state limit.", path: [], states: [] };
            }

            const expandForward = forwardFrontier.length <= backwardFrontier.length;
            if (expandForward) {
                const nextFrontier = [];
                const nextDepth = fDepth + 1;

                for (let i = 0; i < forwardFrontier.length; i++) {
                    const state = forwardFrontier[i];

                    for (let dir = 0; dir < 4; dir++) {
                        const next = this.moveBitboard(state, dir);
                        if (next === state || forwardDepth.has(next)) continue;

                        forwardDepth.set(next, nextDepth);
                        forwardParent.set(next, { prev: state, dir });

                        const otherDepth = backwardDepth.get(next);
                        if (otherDepth !== undefined) rememberBest(next, nextDepth + otherDepth);

                        nextFrontier.push(next);
                    }

                    if ((i & 2047) === 0 && Date.now() > deadline) {
                        return { success: false, incomplete: true, message: "Bidirectional search timed out.", path: [], states: [] };
                    }
                }

                forwardFrontier = nextFrontier;
                fDepth = nextDepth;
            } else {
                const nextFrontier = [];
                const nextDepth = bDepth + 1;

                for (let i = 0; i < backwardFrontier.length; i++) {
                    const state = backwardFrontier[i];

                    for (let dir = 0; dir < 4; dir++) {
                        const keepGoing = this.forEachPredecessor(state, dir, prev => {
                            if (prev === state || backwardDepth.has(prev)) return true;

                            backwardDepth.set(prev, nextDepth);
                            backwardParent.set(prev, { next: state, dir });

                            const otherDepth = forwardDepth.get(prev);
                            if (otherDepth !== undefined) rememberBest(prev, nextDepth + otherDepth);

                            nextFrontier.push(prev);
                            return true;
                        });

                        if (keepGoing === false) break;
                    }

                    if ((i & 255) === 0 && Date.now() > deadline) {
                        return { success: false, incomplete: true, message: "Bidirectional search timed out.", path: [], states: [] };
                    }
                }

                backwardFrontier = nextFrontier;
                bDepth = nextDepth;
            }
        }

        if (bestMeet !== null) {
            return this.buildBidirectionalResult(bestMeet, forwardParent, backwardParent, bestLen);
        }

        return { success: false, message: "No solution exists for this board.", path: [], states: [] };
    }

    popcount(state) {
        let count = 0;
        while (state > 0n) {
            count++;
            state &= state - 1n;
        }
        return count;
    }

    shiftU(x) { return x >> 8n; }
    shiftD(x) { return (x << 8n) & MASK_64; }
    shiftL(x) { return (x >> 1n) & NOT_COL7_MASK; }
    shiftR(x) { return (x << 1n) & NOT_COL0_MASK; }

    moveStepBitboard(state, dir) {
        let moving = state; 
        
        for (let i = 0; i < 8; ++i) {
            let edge_blocked_src = 0n;
            if (dir === 0) edge_blocked_src = moving & ROW0_MASK;
            else if (dir === 1) edge_blocked_src = moving & ROW7_MASK;
            else if (dir === 2) edge_blocked_src = moving & COL0_MASK;
            else if (dir === 3) edge_blocked_src = moving & COL7_MASK;
            let dest = 0n;
            if (dir === 0) dest = this.shiftU(moving);
            else if (dir === 1) dest = this.shiftD(moving);
            else if (dir === 2) dest = this.shiftL(moving);
            else if (dir === 3) dest = this.shiftR(moving);
            let stationary = state ^ moving;
            let blocked_dest = dest & (this.WALLS | stationary);
            let blocked_src = edge_blocked_src;
            if (dir === 0) blocked_src |= this.shiftD(blocked_dest) & moving;
            else if (dir === 1) blocked_src |= this.shiftU(blocked_dest) & moving;
            else if (dir === 2) blocked_src |= this.shiftR(blocked_dest) & moving;
            else if (dir === 3) blocked_src |= this.shiftL(blocked_dest) & moving;
            if (blocked_src === 0n) break;
            moving ^= blocked_src;
        }

        let final_dest = 0n;
        if (dir === 0) final_dest = this.shiftU(moving);
        else if (dir === 1) final_dest = this.shiftD(moving);
        else if (dir === 2) final_dest = this.shiftL(moving);
        else if (dir === 3) final_dest = this.shiftR(moving);

        return (state ^ moving) | final_dest;
    }

    moveBitboard(state, dir) {
        return this.moveStepBitboard(state, dir);
    }

    solve(maxNodes = 20000000, maxMillis = 9500) {
        const finalDeadline = maxMillis > 0 ? Date.now() + maxMillis : Infinity;
        const exactDeadline = maxMillis > 0 ? Date.now() + Math.min(1000, maxMillis) : Infinity;
        const open_list = new FlatQueue();
        const best_g = new StateMap(20);
        const history = new History();
        
        const dirChars = ['U', 'D', 'L', 'R'];

        if (this.targetCount !== this.blockCount) {
            const blockWord = this.blockCount === 1 ? 'block' : 'blocks';
            const targetWord = this.targetCount === 1 ? 'target' : 'targets';
            return { success: false, message: `Unsolvable: target count must equal block count (${this.blockCount} ${blockWord}, ${this.targetCount} ${targetWord}).`, path: [], states: [] };
        }
        
        let start_h = this.getHeuristic(this.start_state);
        if (start_h === INF) {
            return { success: false, message: "Unsolvable: Block is trapped.", path: [], states: [] };
        }

        if (this.isSolved(this.start_state)) {
            return this.pathToResult('', 'Optimal solution in 0 steps');
        }

        const bidirectionalResult = this.solveBidirectional(finalDeadline, Math.min(maxNodes, MAX_BIDIR_STATES));
        if (bidirectionalResult.success || !bidirectionalResult.incomplete) {
            return bidirectionalResult;
        }

        if (Date.now() > finalDeadline) {
            return { success: false, message: `Stopped after ${maxMillis}ms without finding a solution.`, path: [], states: [] };
        }

        if (this.blockCount >= 8) {
            return this.solveBeam(finalDeadline);
        }
        
        let start_id = history.add(this.start_state, -1, 0);
        open_list.push(start_id, 0, start_h);
        best_g.set(this.start_state, 0);

        let nodes_explored = 0;

        while (!open_list.isEmpty()) {
            const curr = open_list.pop();
            const curr_state = history.state[curr.id];
            
            if (curr.g > best_g.get(curr_state)) continue;
            nodes_explored++;

            if (nodes_explored > maxNodes) {
                return { success: false, message: `Explored ${maxNodes} nodes without finding a solution.`, path: [], states: [] };
            }
            if ((nodes_explored & 4095) === 0 && Date.now() > exactDeadline) {
                return this.solveBeam(finalDeadline);
            }

            if (this.isSolved(curr_state)) {
                const path = [];
                const states = [];
                let node_id = curr.id;
                while (node_id !== -1) {
                    let d = history.dir[node_id];
                    if (history.parent[node_id] !== -1) path.push(dirChars[d]);
                    states.push(history.state[node_id]);
                    node_id = history.parent[node_id];
                }
                path.reverse();
                states.reverse();
                
                return { 
                    success: true, 
                    message: `Optimal solution in ${curr.g} steps`,
                    path: path,
                    states: states
                };
            }

            for (let i = 0; i < 4; ++i) {
                const next_state = this.moveBitboard(curr_state, i);
                if (next_state === curr_state) continue;

                const next_g = curr.g + 1;
                if (best_g.get(next_state) <= next_g) continue;

                const h = this.getHeuristic(next_state);
                if (h === INF) continue;

                best_g.set(next_state, next_g);
                let next_id = history.add(next_state, curr.id, i);
                open_list.push(next_id, next_g, next_g + h);
            }
        }
        return { success: false, message: "No solution exists for this board.", path: [], states: [] };
    }
}