TypeScript数独生成器输出不完整棋盘问题及函数修改咨询

你的fillBoard函数核心问题是回溯逻辑不完整，没有正确处理递归的成功/失败状态，导致经常无法填满整个棋盘。以下是修复方案：

修复后的fillBoard函数 #

function fillBoard(puzzleArray: number[][]): boolean {
    const emptyCell = nextEmptyCell(puzzleArray);
    // 没有空单元格，说明棋盘已填满，返回成功
    if (emptyCell.colIndex === -1) return true;

    // 遍历打乱后的数字，尝试填充
    for (const num of shuffle(numArray)) {
        if (safeToPlace(puzzleArray, emptyCell, num)) {
            puzzleArray[emptyCell.rowIndex][emptyCell.colIndex] = num;
            // 递归填充，如果后续成功，直接返回true，终止所有递归
            if (fillBoard(puzzleArray)) {
                return true;
            }
            // 递归失败，回溯：重置当前单元格为0，尝试下一个数字
            puzzleArray[emptyCell.rowIndex][emptyCell.colIndex] = 0;
        }
    }
    // 所有数字都尝试过，无法填充，返回失败
    return false;
}

关键修改点说明 #

1. 返回值改为布尔值：用true/false表示当前路径是否成功填满棋盘，让递归调用能明确判断后续状态，避免无效循环。
2. 避免重复调用nextEmptyCell：一开始就获取空单元格，无需重复执行两次查找逻辑。
3. 用for...of遍历数字：原代码用for (var num in shuffle(numArray))遍历的是数组索引，容易出错；直接遍历打乱后的数字更清晰，且洗牌时会复制原数组，避免污染全局的numArray。
4. 递归成功后立即返回：当递归调用返回true时，说明后续已填满棋盘，直接返回true终止整个递归链，不再尝试其他数字。
5. 正确的回溯逻辑：只有当递归失败时，才把当前单元格重置为0，尝试下一个数字；原逻辑在遇到第一个不合法数字就置0，会破坏已填充的正确值。

调用方式调整 #

原代码直接赋值NEW_BOARD = fillBoard(BLANK_BOARD)，现在因为fillBoard返回布尔值，且会修改传入的数组，需要改为：

// 深拷贝空白棋盘，避免污染原BLANK_BOARD
const boardCopy = JSON.parse(JSON.stringify(BLANK_BOARD));
fillBoard(boardCopy);
NEW_BOARD = boardCopy;

完整修改后的代码 #

import { Box } from "./Box";

export function Board() {
  const BLANK_BOARD = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
  ];

  let NEW_BOARD = JSON.parse(JSON.stringify(BLANK_BOARD));
  const numArray: number[] = [1, 2, 3, 4, 5, 6, 7, 8, 9];

  function rowSafe(
    puzzleArray: number[][],
    emptyCell: { rowIndex: number; colIndex: number },
    num: number
  ): boolean {
    return puzzleArray[emptyCell.rowIndex].indexOf(num) === -1;
  }

  function colSafe(
    puzzleArray: number[][],
    emptyCell: { rowIndex: number; colIndex: number },
    num: number
  ): boolean {
    for (let i = 0; i < 9; i++) {
      if (puzzleArray[i][emptyCell.colIndex] === num) {
        return false;
      }
    }
    return true;
  }

  function regionSafe(
    puzzleArray: number[][],
    emptyCell: { rowIndex: number; colIndex: number },
    num: number
  ): boolean {
    const rowStart: number = emptyCell.rowIndex - (emptyCell.rowIndex % 3);
    const colStart: number = emptyCell.colIndex - (emptyCell.colIndex % 3);

    for (let i = 0; i < 3; i++) {
      for (let j = 0; j < 3; j++) {
        if (puzzleArray[rowStart + i][colStart + j] === num) {
          return false;
        }
      }
    }
    return true;
  }

  function safeToPlace(
    puzzleArray: number[][],
    emptyCell: { rowIndex: number; colIndex: number },
    num: number
  ): boolean {
    return (
      regionSafe(puzzleArray, emptyCell, num) &&
      rowSafe(puzzleArray, emptyCell, num) &&
      colSafe(puzzleArray, emptyCell, num)
    );
  }

  function nextEmptyCell(puzzleArray: number[][]): {
    colIndex: number;
    rowIndex: number;
  } {
    for (let i = 0; i < 9; i++) {
      for (let j = 0; j < 9; j++) {
        if (puzzleArray[i][j] === 0) {
          return { rowIndex: i, colIndex: j };
        }
      }
    }
    return { rowIndex: -1, colIndex: -1 };
  }

  function shuffle(array: number[]): number[] {
    // 用Fisher-Yates洗牌算法，比sort更公平
    const arr = [...array];
    for (let i = arr.length - 1; i > 0; i--) {
      const j = Math.floor(Math.random() * (i + 1));
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
    return arr;
  }

  function fillBoard(puzzleArray: number[][]): boolean {
    const emptyCell = nextEmptyCell(puzzleArray);
    if (emptyCell.colIndex === -1) return true;

    for (const num of shuffle(numArray)) {
      if (safeToPlace(puzzleArray, emptyCell, num)) {
        puzzleArray[emptyCell.rowIndex][emptyCell.colIndex] = num;
        if (fillBoard(puzzleArray)) {
          return true;
        }
        puzzleArray[emptyCell.rowIndex][emptyCell.colIndex] = 0;
      }
    }
    return false;
  }

  // 生成完整棋盘
  const boardCopy = JSON.parse(JSON.stringify(BLANK_BOARD));
  fillBoard(boardCopy);
  NEW_BOARD = boardCopy;

  function fullBoard(puzzleArray: number[][]): boolean {
    return puzzleArray.every((row) => row.every((col) => col !== 0));
  }

  return (
    <div
      style={{
        height: "450px",
        width: "450px",
        display: "inline-grid",
        gap: "10px",
        gridTemplateColumns: "repeat(9,50px)",
        gridTemplateRows: "repeat(9,50px)",
        position: "absolute",
        top: "30px",
        left: "0px",
        right: "0px",
        marginLeft: "auto",
        marginRight: "auto",
      }}
    >
      {NEW_BOARD.flat().map((item, index) => (
        <Box key={index} i={item} />
      ))}
    </div>
  );
}

额外优化说明：

• colSafe函数改为直接遍历行，比flat数组更高效
• 洗牌算法换成Fisher-Yates，避免sort方法的偏序问题
• 给Box组件添加key属性，符合React渲染规范

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