Board Games & Classic Puzzles

class TicTacToe {
  constructor(n) {
    this.n = n;
    this.rows = new Array(n).fill(0);  // Running scores per row
    this.cols = new Array(n).fill(0);  // Running scores per col
    this.diag = 0;                     // Main diagonal
    this.antiDiag = 0;                 // Anti-diagonal
  }

  move(row, col, player) {
    // Player 1 = +1, Player 2 = -1
    const score = player === 1 ? 1 : -1;

    this.rows[row] += score;
    this.cols[col] += score;
    if (row === col) this.diag += score;            // Main diagonal
    if (row === this.n - col - 1) this.antiDiag += score;  // Anti-diagonal

    // Check if this move won the game
    if (Math.abs(this.rows[row]) === this.n ||
        Math.abs(this.cols[col]) === this.n ||
        Math.abs(this.diag) === this.n ||
        Math.abs(this.antiDiag) === this.n) {
      return player;
    }
    return 0;  // No winner yet
  }
}

function validTicTacToe(board) {
  let xCount = 0, oCount = 0;
  for (const row of board) {
    for (const cell of row) {
      if (cell === 'X') xCount++;
      if (cell === 'O') oCount++;
    }
  }

  // Rule 1: X goes first, so X is always >= O
  if (oCount > xCount || xCount > oCount + 1) return false;

  // Rule 2: Check if X wins
  const xWin = checkWin(board, 'X');
  const oWin = checkWin(board, 'O');

  // Rule 3: Both can't win simultaneously
  if (xWin && oWin) return false;

  // Rule 4: If X wins, X must have exactly one more than O
  if (xWin && xCount !== oCount + 1) return false;

  // Rule 5: If O wins, counts must be equal (O just played)
  if (oWin && xCount !== oCount) return false;

  return true;
}

function checkWin(board, player) {
  // Check rows, cols, diagonals
  const lines = [
    [0,0,0,1,0,2], [1,0,1,1,1,2], [2,0,2,1,2,2],  // rows
    [0,0,1,0,2,0], [0,1,1,1,2,1], [0,2,1,2,2,2],  // cols
    [0,0,1,1,2,2], [0,2,1,1,2,0],                   // diags
  ];
  for (const [r1,c1,r2,c2,r3,c3] of lines) {
    if (board[r1][c1] === player &&
        board[r2][c2] === player &&
        board[r3][c3] === player) return true;
  }
  return false;
}

function gameOfLife(board) {
  const rows = board.length, cols = board[0].length;

  // Directions: 8 neighbors
  const dirs = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];

  // Pass 1: Encode new state in bit 1
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      let live = 0;
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
          live += board[nr][nc] & 1;  // Read old state (bit 0)
        }
      }

      const old = board[r][c] & 1;
      if (old === 1) {
        // Cell is alive: survives with 2-3 neighbors
        if (live === 2 || live === 3) board[r][c] = 3;  // 11
      } else {
        // Cell is dead: born with exactly 3 neighbors
        if (live === 3) board[r][c] = 2;  // 10
      }
    }
  }

  // Pass 2: Shift to extract new state
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      board[r][c] >>= 1;  // New state is now in bit 0
    }
  }

  return board;
}

class SnakeGame {
  constructor(width, height, food) {
    this.width = width;
    this.height = height;
    this.food = food;
    this.foodIndex = 0;
    this.snake = new Queue();
    this.snake.enqueue([0, 0]);       // Initial head at (0,0)
    this.body = new Set(["0,0"]);     // Set for O(1) body collision
    this.score = 0;
  }

  move(direction) {
    // Get current head position
    const [headR, headC] = this.snake.peekLast();

    // Compute new head position
    let [newR, newC] = [headR, headC];
    if (direction === "U") newR--;
    else if (direction === "D") newR++;
    else if (direction === "L") newC--;
    else if (direction === "R") newC++;

    // Check wall collision
    if (newR < 0 || newR >= this.height ||
        newC < 0 || newC >= this.width) return -1;

    // Check if eating food
    const eating = this.foodIndex < this.food.length &&
      newR === this.food[this.foodIndex][0] &&
      newC === this.food[this.foodIndex][1];

    // Remove tail if NOT eating (FIFO)
    if (!eating) {
      const [tailR, tailC] = this.snake.dequeue();
      this.body.delete(tailR + "," + tailC);
    } else {
      this.foodIndex++;
      this.score++;
    }

    // Check body collision (after tail removal for edge case)
    const key = newR + "," + newC;
    if (this.body.has(key)) return -1;

    // Move head
    this.snake.enqueue([newR, newC]);
    this.body.add(key);

    return this.score;
  }
}

function solveNQueens(n) {
  const solutions = [];
  const board = Array.from({ length: n }, () => new Array(n).fill("."));

  // Constraint tracking — O(1) checks
  const cols = new Array(n).fill(false);         // Column guard
  const diag1 = new Array(2 * n - 1).fill(false); // Main diagonal (row - col)
  const diag2 = new Array(2 * n - 1).fill(false); // Anti-diagonal (row + col)

  function backtrack(row) {
    if (row === n) {
      solutions.push(board.map(r => r.join("")));
      return;
    }

    for (let col = 0; col < n; col++) {
      const d1 = row - col + n - 1;  // Offset to make index non-negative
      const d2 = row + col;

      // Check all three guards
      if (cols[col] || diag1[d1] || diag2[d2]) continue;

      // Place queen
      board[row][col] = "Q";
      cols[col] = diag1[d1] = diag2[d2] = true;

      backtrack(row + 1);

      // Remove queen (backtrack)
      board[row][col] = ".";
      cols[col] = diag1[d1] = diag2[d2] = false;
    }
  }

  backtrack(0);
  return solutions;
}

function totalNQueens(n) {
  let count = 0;
  const cols = new Array(n).fill(false);
  const diag1 = new Array(2 * n - 1).fill(false);
  const diag2 = new Array(2 * n - 1).fill(false);

  function backtrack(row) {
    if (row === n) { count++; return; }
    for (let col = 0; col < n; col++) {
      const d1 = row - col + n - 1;
      const d2 = row + col;
      if (cols[col] || diag1[d1] || diag2[d2]) continue;
      cols[col] = diag1[d1] = diag2[d2] = true;
      backtrack(row + 1);
      cols[col] = diag1[d1] = diag2[d2] = false;
    }
  }

  backtrack(0);
  return count;
}

function isValidSudoku(board) {
  const rows = Array.from({ length: 9 }, () => new Set());
  const cols = Array.from({ length: 9 }, () => new Set());
  const boxes = Array.from({ length: 9 }, () => new Set());

  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      const val = board[r][c];
      if (val === ".") continue;

      const boxIdx = Math.floor(r / 3) * 3 + Math.floor(c / 3);

      if (rows[r].has(val) || cols[c].has(val) || boxes[boxIdx].has(val)) {
        return false;
      }

      rows[r].add(val);
      cols[c].add(val);
      boxes[boxIdx].add(val);
    }
  }
  return true;
}

function solveSudoku(board) {
  // Pre-compute bitmasks for O(1) validation
  const rows = new Array(9).fill(0);
  const cols = new Array(9).fill(0);
  const boxes = new Array(9).fill(0);

  // Initialize: mark filled cells in bitmasks
  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      if (board[r][c] !== ".") {
        const val = 1 << (board[r][c] - "0");
        const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);
        rows[r] |= val;
        cols[c] |= val;
        boxes[b] |= val;
      }
    }
  }

  function backtrack() {
    for (let r = 0; r < 9; r++) {
      for (let c = 0; c < 9; c++) {
        if (board[r][c] !== ".") continue;

        const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);

        for (let num = 1; num <= 9; num++) {
          const bit = 1 << num;
          // O(1) validity with bit masks!
          if ((rows[r] & bit) || (cols[c] & bit) || (boxes[b] & bit)) continue;

          // Place digit
          board[r][c] = String(num);
          rows[r] |= bit;
          cols[c] |= bit;
          boxes[b] |= bit;

          if (backtrack()) return true;

          // Backtrack
          board[r][c] = ".";
          rows[r] ^= bit;
          cols[c] ^= bit;
          boxes[b] ^= bit;
        }
        return false;  // No valid digit for this cell
      }
    }
    return true;  // All cells filled
  }

  backtrack();
}

function slidingPuzzle(board) {
  const target = "123450";
  const start = board.flat().join("");

  // If already solved
  if (start === target) return 0;

  // All 6 possible blank positions (0-5) and their neighbors
  const neighbors = {
    0: [1, 3], 1: [0, 2, 4], 2: [1, 5],
    3: [0, 4], 4: [1, 3, 5], 5: [2, 4]
  };

  // BFS on STATE SPACE — each node is a board string
  const queue = [[start, 0]];
  const visited = new Set([start]);

  while (queue.length) {
    const [state, moves] = queue.shift();

    for (const next of getNextStates(state, neighbors)) {
      if (next === target) return moves + 1;
      if (!visited.has(next)) {
        visited.add(next);
        queue.push([next, moves + 1]);
      }
    }
  }

  return -1;  // Unsolvable
}

function getNextStates(state, neighbors) {
  const blankIdx = state.indexOf("0");
  const results = [];
  for (const neighbor of neighbors[blankIdx]) {
    const arr = state.split("");
    [arr[blankIdx], arr[neighbor]] = [arr[neighbor], arr[blankIdx]];
    results.push(arr.join(""));
  }
  return results;
}

// Word Search I — Simple backtracking
function exist(board, word) {
  const rows = board.length, cols = board[0].length;

  function dfs(r, c, idx) {
    if (idx === word.length) return true;
    if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
    if (board[r][c] !== word[idx]) return false;

    // Mark visited
    const temp = board[r][c];
    board[r][c] = "#";  // Mark as visited

    // Explore 4 directions
    const found = dfs(r+1, c, idx+1) ||
                  dfs(r-1, c, idx+1) ||
                  dfs(r, c+1, idx+1) ||
                  dfs(r, c-1, idx+1);

    // Restore
    board[r][c] = temp;
    return found;
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (dfs(r, c, 0)) return true;
    }
  }
  return false;
}

// Word Search II — Trie optimization
function findWords(board, words) {
  // Build a Trie from the word list
  const root = {};
  for (const word of words) {
    let node = root;
    for (const ch of word) {
      if (!node[ch]) node[ch] = {};
      node = node[ch];
    }
    node.word = word;  // Mark end of word
  }

  const result = [];
  const rows = board.length, cols = board[0].length;

  function dfs(r, c, node) {
    if (node.word) {
      result.push(node.word);
      node.word = null;  // Avoid duplicates
    }

    const temp = board[r][c];
    board[r][c] = "#";  // Mark visited

    for (const [dr, dc] of [[0,1],[0,-1],[1,0],[-1,0]]) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
          board[nr][nc] !== "#" && node[board[nr][nc]]) {
        dfs(nr, nc, node[board[nr][nc]]);
      }
    }

    board[r][c] = temp;  // Restore
  }

  // Start DFS from every cell
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (root[board[r][c]]) {
        dfs(r, c, root[board[r][c]]);
      }
    }
  }

  return result;
}

function squareIsWhite(coordinates) {
  // Column letter: a=0, b=1, c=2, d=3, e=4, f=5, g=6, h=7
  // Row number: 1-indexed from bottom
  // Color is dark if (col + row) % 2 === 0, white if odd
  const col = coordinates.charCodeAt(0) - 97;  // 'a' -> 0
  const row = parseInt(coordinates[1]) - 1;     // '1' -> 0
  return (col + row) % 2 === 1;
}