solver.js

/**
 * LinkedIn Zip Puzzle Solver
 *
 * Grid representation:
 * - Use a (2N+1)×(2N+1) matrix for an N×N game grid
 * - Odd indices (1,3,5,7,9,11...) represent actual cells
 * - Even indices (0,2,4,6,8,10,12...) represent walls between cells
 */

class ZipSolver {
    constructor(gridSize = 6) {
        this.rows = gridSize;
        this.cols = gridSize;

        // (2N+1)×(2N+1) matrix to support N×N grid with walls
        const matrixSize = 2 * gridSize + 1;
        this.matrix = Array(matrixSize).fill(0).map(() => Array(matrixSize).fill(0));

        // Store numbered cells: {number: [row, col]}
        this.numberedCells = {};

        // Solution path
        this.path = [];

        // Visited cells during backtracking
        this.visited = new Set();
    }

    /**
     * Set a cell with a specific number
     */
    setNumberedCell(row, col, number) {
        const matrixRow = 2 * row + 1;
        const matrixCol = 2 * col + 1;
        this.matrix[matrixRow][matrixCol] = number;
        this.numberedCells[number] = [row, col];
    }

    /**
     * Add a horizontal wall below cell (row, col)
     * Blocks movement from (row, col) to (row+1, col)
     */
    addWallHorizontal(row, col) {
        const wallRow = 2 * (row + 1);
        const wallCol = 2 * col + 1;
        this.matrix[wallRow][wallCol] = -1; // -1 represents a wall
    }

    /**
     * Add a vertical wall to the right of cell (row, col)
     * Blocks movement from (row, col) to (row, col+1)
     */
    addWallVertical(row, col) {
        const wallRow = 2 * row + 1;
        const wallCol = 2 * (col + 1);
        this.matrix[wallRow][wallCol] = -1; // -1 represents a wall
    }

    /**
     * Check if movement from one cell to another is valid
     */
    isValidMove(fromRow, fromCol, toRow, toCol) {
        // Check bounds
        if (toRow < 0 || toRow >= this.rows || toCol < 0 || toCol >= this.cols) {
            return false;
        }

        // Check if already visited
        const key = `${toRow},${toCol}`;
        if (this.visited.has(key)) {
            return false;
        }

        // Check if there's a wall between cells
        const fromMatrixRow = 2 * fromRow + 1;
        const fromMatrixCol = 2 * fromCol + 1;
        const toMatrixRow = 2 * toRow + 1;
        const toMatrixCol = 2 * toCol + 1;

        // Calculate wall position
        const wallRow = Math.floor((fromMatrixRow + toMatrixRow) / 2);
        const wallCol = Math.floor((fromMatrixCol + toMatrixCol) / 2);

        // Check if wall exists
        if (this.matrix[wallRow][wallCol] === -1) {
            return false;
        }

        return true;
    }

    /**
     * Get the value of a cell (0 if empty, number if numbered)
     */
    getCellValue(row, col) {
        const matrixRow = 2 * row + 1;
        const matrixCol = 2 * col + 1;
        const val = this.matrix[matrixRow][matrixCol];
        return val > 0 ? val : 0;
    }

    /**
     * Solve the Zip puzzle using backtracking
     * Returns array of [row, col] tuples or null if no solution
     */
    solve() {
        console.log('📊 Solver State:');
        console.log('  Grid:', this.rows + 'x' + this.cols);
        console.log('  Matrix size:', this.matrix.length + 'x' + this.matrix[0].length);
        console.log('  Numbered cells:', this.numberedCells);
        console.log('  Total cells to visit:', this.rows * this.cols);
        
        // Display matrix state
        console.log('  Matrix visualization:');
        for (let i = 0; i < this.matrix.length; i++) {
            console.log('    ' + this.matrix[i].map(v => {
                if (v === -1) return '█';  // Wall
                if (v > 0) return v.toString().padStart(2, ' ');
                return '·';  // Empty
            }).join(' '));
        }
        
        // Find starting position (cell with number 1)
        if (!(1 in this.numberedCells)) {
            console.error("❌ No starting cell (number 1) found!");
            return null;
        }

        const [startRow, startCol] = this.numberedCells[1];
        console.log('  Start position:', [startRow, startCol]);

        // Find the maximum number (end position)
        const maxNum = Math.max(...Object.keys(this.numberedCells).map(Number));
        console.log('  Max number:', maxNum);

        // Reset solution state
        this.path = [];
        this.visited = new Set();

        // Start backtracking
        if (this._backtrack(startRow, startCol, 1, maxNum)) {
            return this.path;
        } else {
            return null;
        }
    }

    /**
     * Backtracking helper function
     */
    _backtrack(row, col, nextRequiredNum, maxNum, depth = 0) {
        // Add current cell to path
        this.path.push([row, col]);
        this.visited.add(`${row},${col}`);

        // Debug logging for first few steps
        if (depth < 10) {
            console.log(`  ${'  '.repeat(depth)}Visit (${row},${col}) val=${this.getCellValue(row, col)} need=${nextRequiredNum} pathLen=${this.path.length}`);
        }

        // Check if we've completed the path
        const totalCells = this.rows * this.cols;
        if (this.path.length === totalCells) {
            // Check if last cell has the max number
            if (this.getCellValue(row, col) === maxNum) {
                return true;
            } else {
                // Backtrack
                this.path.pop();
                this.visited.delete(`${row},${col}`);
                return false;
            }
        }

        // Get current cell value
        const currentValue = this.getCellValue(row, col);

        // If current cell has the required number, increment next required
        if (currentValue === nextRequiredNum) {
            nextRequiredNum++;
        }

        // Try all four directions: up, down, left, right
        const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];

        for (const [dr, dc] of directions) {
            const newRow = row + dr;
            const newCol = col + dc;

            if (this.isValidMove(row, col, newRow, newCol)) {
                // Check if next cell satisfies number constraint
                const nextValue = this.getCellValue(newRow, newCol);

                // If next cell has a number, it must be the next required number
                if (nextValue > 0 && nextValue !== nextRequiredNum) {
                    continue;
                }

                // Recurse
                if (this._backtrack(newRow, newCol, nextRequiredNum, maxNum, depth + 1)) {
                    return true;
                }
            }
        }

        // Backtrack
        this.path.pop();
        this.visited.delete(`${row},${col}`);
        return false;
    }
}

// Export for use in other files
if (typeof module !== 'undefined' && module.exports) {
    module.exports = ZipSolver;
}