递归回溯法实现数独求解器出现‘递归调用过多’错误的排查与优化咨询

Hey there! Let's break down why your Sudoku solver is hitting that "too much recursion" error and how to fix it.

First: Why the "Too Much Recursion" Error Happens #

Your core issue has two parts, but the immediate crash comes from missing a base case for unsolvable boards:

When you hit a board that has no valid solution, your code keeps backtracking all the way to the first row (index 0). Once you've exhausted all possible values for the first empty cell and have no more previous changes to undo, your code tries to access addedVals[currentRowIndex - 1]—which is addedVals[-1], an undefined value. This leads to an infinite loop of recursive calls trying to backtrack beyond the start of the board, blowing past recursion limits.

Second, your current implementation has inefficient recursion patterns and helper functions that amplify the problem, causing unnecessary recursive calls even for solvable boards.

Fix 1: Add the "Unsolvable Board" Base Case #

Start by adding a check at the very top of your backtrack function to catch when you've backtracked beyond the first row (meaning no solution exists):

function backtrack(currentRowIndex = 0, currentRow = board[currentRowIndex], testValue = 1, i = 0) {
  // New base case: We've backtracked past the first row—no solution exists
  if (currentRowIndex < 0) {
    console.log("This Sudoku board has no valid solution.");
    return false; // Return false to signal failure
  }

  // Rest of your existing code...
}

Then, update the testValue > 9 branch to handle the first row correctly, instead of trying to access invalid array indices:

} else if (testValue > 9) {
  currentRow[i] = 0;
  // Check if we're at the first row with no changes to undo
  if (currentRowIndex === 0 && addedVals[currentRowIndex].length === 0) {
    return backtrack(-1); // Trigger the unsolvable base case
  } else if (i === 0 || addedVals[currentRowIndex].length === 0) {
    lastPopped = addedVals[currentRowIndex - 1].pop();
    return backtrack(currentRowIndex - 1, board[currentRowIndex - 1], board[currentRowIndex - 1][lastPopped] + 1, lastPopped);
  } else {
    lastPopped = addedVals[currentRowIndex].pop();
    return backtrack(currentRowIndex, currentRow, currentRow[lastPopped] + 1, lastPopped);
  }
}

This will stop the infinite recursion when the board is unsolvable.

Fix 2: Optimize Recursion & Reduce Calls #

Even for solvable boards, your code can be optimized to cut down on recursive calls drastically:

A. Fix Your Helper Functions (Huge Performance Gain) #

Your current getRow, getColumn, and getSubGrid functions do unnecessary work by searching for the current number's index every time. You already know the row and column indices (currentRowIndex and i), so use those directly:

// Get the entire row for a given row index
function getRow(rowIndex) {
  return [...board[rowIndex]]; // Return a copy to avoid modifying the original
}

// Get the entire column for a given column index
function getColumn(colIndex) {
  return board.map(row => row[colIndex]);
}

// Get the 3x3 subgrid for a given cell (row, col)
function getSubGrid(rowIndex, colIndex) {
  const subRowStart = Math.floor(rowIndex / 3) * 3;
  const subColStart = Math.floor(colIndex / 3) * 3;
  const subGrid = [];
  for (let r = subRowStart; r < subRowStart + 3; r++) {
    subGrid.push(board[r].slice(subColStart, subColStart + 3));
  }
  return subGrid;
}

// Check if a value exists in the subgrid of (row, col)
function subGridIncludes(value, rowIndex, colIndex) {
  const subGrid = getSubGrid(rowIndex, colIndex);
  return subGrid.some(row => row.includes(value));
}

This eliminates redundant loops and makes your validity checks way faster, which reduces the number of recursive calls needed.

B. Use "Minimum Remaining Values" Heuristic (Prune Early) #

Instead of filling cells left-to-right, pick the empty cell with the fewest possible valid values first. This cuts down on useless recursive branches early, drastically reducing call counts. For example:

1. Iterate over the board to find all empty cells
2. For each empty cell, calculate how many valid numbers it can take
3. Recursively fill the cell with the smallest number of options first

C. Ditch Global Variables for State Management #

Global variables like lastPopped and addedVals are prone to state corruption during recursion. Pass these values as parameters to the backtrack function instead, or wrap everything in a closure to keep state isolated.

Fix 3: Clean Up Redundant Code (Follow DRY) #

You have repeated logic for moving to the next cell/row. Wrap this in a helper function to avoid duplication:

function getNextCell(rowIndex, colIndex) {
  if (colIndex === 8) {
    return { row: rowIndex + 1, col: 0 };
  } else {
    return { row: rowIndex, col: colIndex + 1 };
  }
}

Then use it in your recursion:

// Replace repeated next cell/row logic with this:
const nextCell = getNextCell(currentRowIndex, i);
backtrack(nextCell.row, board[nextCell.row], 1, nextCell.col);

Final Summary #

1. Immediate Fix: Add the unsolvable board base case to stop infinite recursion.
2. Performance Boost: Optimize helper functions and use pruning heuristics to cut down on recursive calls.
3. Maintainability: Ditch global state and clean up redundant code to make your solver easier to debug.

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