JavaScript版Hexomino 15×15棋盘铺排算法优化求助

Hey there,

Looks like you're hitting a classic combinatorial search bottleneck with your 15×15 hexomino tiling problem—totally makes sense, since the search space explodes exponentially with board size. Let's break down actionable optimizations you can apply to your JavaScript code to get it running efficiently enough to find a solution:

1. Prioritize Constrained Placements First #

Instead of starting from the top-left and placing pieces randomly, use a most constrained first heuristic:

• Always fill the cell with the fewest available neighboring empty cells first (think corners, edges, or cells trapped by already placed pieces). This cuts down the search tree drastically by eliminating invalid paths early.
• Fix the 3×3 square's position upfront (e.g., corner or center) before starting the hexomino search. This reduces variables and shrinks the initial search space.

2. Preprocess & Cache Piece Variants #

Stop calculating rotations/flips on the fly—precompute all unique orientations for each hexomino once at the start:

• For each hexomino, generate all 8 possible rotations/flips, then deduplicate any identical shapes (some hexominoes have fewer unique orientations). Store these precomputed coordinate sets so you don't waste CPU cycles during search.

3. Use Bitmasking for Board State #

Swap your 2D array board representation for a BigInt bitmask (15×15 = 225 bits, which fits perfectly in JavaScript's BigInt):

• Each bit in the mask represents whether a cell is filled (1) or empty (0). Checking if a piece fits and updating the board becomes lightning-fast bitwise operations instead of looping through arrays.
• Example code snippets:

  // Check if a piece can be placed at (x,y)
  function canPlace(boardMask, piece, x, y) {
    let pieceMask = 0n;
    for (const [dx, dy] of piece) {
      const pos = (y + dy) * 15 + (x + dx);
      if (pos < 0 || pos >= 225) return false;
      pieceMask |= 1n << BigInt(pos);
    }
    return (boardMask & pieceMask) === 0n;
  }
  
  // Place the piece and return the new board mask
  function placePiece(boardMask, piece, x, y) {
    let newMask = boardMask;
    for (const [dx, dy] of piece) {
      const pos = (y + dy) * 15 + (x + dx);
      newMask |= 1n << BigInt(pos);
    }
    return newMask;
  }
  

4. Add Smart Pruning Rules #

Cut off impossible search paths before wasting time on them:

• Count-based pruning: If the number of remaining empty cells isn't divisible by 6 (for hexominoes) minus the 9 cells taken by the square, immediately backtrack.
• Isolated cell check: If any empty cell has no adjacent empty cells (and isn't part of a future hexomino placement), backtrack—you can't fill a single cell with a 6-cell piece.
• Duplicate piece pruning: When placing the duplicate hexomino, skip placements that are symmetric to ones you've already tried to avoid redundant work.

5. Parallelize the Search #

Take advantage of multi-core CPUs to split the workload:

• In Node.js, use the worker_threads module to spawn multiple workers, each searching a subset of the initial search space (e.g., different positions for the 3×3 square or duplicate hexomino).
• In the browser, use Web Workers to keep the main thread responsive while offloading the heavy lifting.

6. Sort Pieces by Complexity #

Place hexominoes with fewer unique orientations first (like the ones that can only be rotated 2 ways instead of 8). These more "inflexible" pieces constrain the board early, reducing the number of possible paths later on.

Since you mentioned Python implementations work, you can also look into how those handle state management and pruning—chances are they're using similar optimizations that you can port over to JavaScript.

内容的提问来源于stack exchange，提问作者maratom