Solving Détrak with brute force

Overview

  The solver uses branch-and-bound with backtracking to find optimal domino placements on a 5×5 grid. The problem is combinatorially
  explosive (~10^18 nodes without pruning), so heavy optimization is required.

  ---
  Core Algorithm (Pseudo-code)

  function solve(startSymbol, dominoes):
      grid = new Grid(startSymbol at [0,0])
      bestSolution = null
      bestScore = -∞

      # Phase 1: Quick greedy to get initial bound
      greedySolution = greedySearch(grid, dominoes, beamWidth=3)
      if greedySolution:
          bestScore = score(greedySolution)

      # Phase 2: Full search with pruning
      stack = [{depth: 0, placements: generatePlacements(grid, dominoes[0])}]

      while stack not empty:
          frame = stack.top()

          if frame.depth == 12:  # All dominoes placed
              if grid.score > bestScore:
                  bestScore = grid.score
                  bestSolution = grid.copy()
              backtrack()
              continue

          # Pruning checks
          if upperBound(grid, remainingDominoes) <= bestScore:
              backtrack()
              continue

          if transpositionTable.has(grid.hash) with better result:
              backtrack()
              continue

          if not hasValidTiling(grid):  # Constraint propagation
              backtrack()
              continue

          # Try next placement
          placement = frame.nextPlacement()
          if placement:
              grid.place(placement)
              stack.push({depth+1, generatePlacements(...)})
          else:
              backtrack()

  ---
  Zobrist Hashing

  A technique for incrementally computing a unique hash of the grid state:

  # Initialization (once)
  ZOBRIST[25][7] = random 64-bit values  # position × symbol

  # Grid hash update (O(1) per cell change)
  function setCell(idx, newValue):
      if oldValue != null:
          hash ^= ZOBRIST[idx][oldValue]   # Remove old
      hash ^= ZOBRIST[idx][newValue]       # Add new

  # Lookup
  transpositionTable[hash] = {bestScore, depth, flag}

  Why it works: XOR is its own inverse, so placing/removing a symbol toggles the same bits. Two identical grid states always produce the
   same hash.

  ---
  Optimization Techniques
  ┌────────────────────────┬──────────────────────────────────────────────────────────────────────┐
  │       Technique        │                             Description                              │
  ├────────────────────────┼──────────────────────────────────────────────────────────────────────┤
  │ Transposition Table    │ Cache explored states by Zobrist hash; skip re-exploration           │
  ├────────────────────────┼──────────────────────────────────────────────────────────────────────┤
  │ Upper Bound Pruning    │ Estimate max possible score for remaining cells; prune if ≤ best     │
  ├────────────────────────┼──────────────────────────────────────────────────────────────────────┤
  │ Constraint Propagation │ Reject states with isolated empty cells or odd empty count           │
  ├────────────────────────┼──────────────────────────────────────────────────────────────────────┤
  │ Beam Search            │ Limit to top 20 moves per depth by heuristic score                   │
  ├────────────────────────┼──────────────────────────────────────────────────────────────────────┤
  │ Move Ordering          │ Prioritize: killer moves (500×), history heuristic, greedy potential │
  ├────────────────────────┼──────────────────────────────────────────────────────────────────────┤
  │ Incremental Scoring    │ Track per-line scores; O(1) total score lookup                       │
  ├────────────────────────┼──────────────────────────────────────────────────────────────────────┤
  │ Domino Ordering        │ Try doubles first, then by symbol frequency                          │
  └────────────────────────┴──────────────────────────────────────────────────────────────────────┘
  ---
  Move Ordering Heuristics (Pseudo-code)

  function scorePlacement(placement):
      score = 0

      # Greedy: matching neighbors
      score += countMatchingNeighbors(pos1, sym1) * 2
      score += countMatchingNeighbors(pos2, sym2) * 2

      # Doubles bonus (guaranteed 2-run)
      if sym1 == sym2: score += 3

      # Killer move (caused cutoff at this depth before)
      if placement in killerMoves[depth]: score *= 500

      # History heuristic (led to good solutions globally)
      score += historyTable[placementKey]

      return score

  ---
  Upper Bound Calculation

  function upperBound(grid, remainingDominoes):
      total = 0
      for each line (5 rows + 5 cols + 1 anti-diag):
          if line complete:
              total += actualScore(line)
          else:
              # Best possible: fill remaining with optimal symbols
              total += maxPossibleScore(line, remainingDominoes)

      total += antiDiagonalScore  # Counted twice (×2 rule)
      return total

  ---
  Constraint Propagation

  function hasValidTiling(grid):
      emptyCells = grid.countEmpty()

      # Must be even (dominoes cover 2 cells)
      if emptyCells % 2 != 0: return false

      # No isolated cells (would be impossible to fill)
      for each empty cell:
          if all 4 neighbors are filled:
              return false

      return true

  ---
  Performance Tricks

  - Flat arrays: 25-cell Int8Array instead of 2D array (cache locality)
  - Typed arrays: Int32Array for scores in worker (no GC)
  - Packed move keys: idx1*1000000 + idx2*10000 + sym1*100 + sym2 for fast hashing
  - Batch processing: Process 3000 nodes, then yield to UI with setTimeout(..., 0)
  - Web Worker: Full search runs off main thread

  ---
  Scoring Table
  ┌────────────┬───────┐
  │ Run Length │ Score │
  ├────────────┼───────┤
  │ 0-1        │ -5    │
  ├────────────┼───────┤
  │ 2          │ +2    │
  ├────────────┼───────┤
  │ 3          │ +3    │
  ├────────────┼───────┤
  │ 4          │ +8    │
  ├────────────┼───────┤
  │ 5          │ +10   │
  └────────────┴───────┘
  Anti-diagonal scores count double.