Typoskript-Sudoku-Problem mit teilweise gefüllter Tafel

Question

Ich habe einen js-Sudoku-Generator zum Üben erfolgreich in einen ts-Generator umgewandelt. Das einzige Problem besteht darin, dass er nur das komplette Sudoku-Brett ausgibt. Jetzt erfolgt die Ausgabe unabhängig davon, ob der Datenträger vollständig ist oder nicht, und ich muss aktualisieren, bis ein korrekter Datenträger angezeigt wird.

Ich bin mir nicht sicher, wie ich die folgende Funktion schreiben soll, damit nur die komplette Festplatte ausgegeben wird:

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

    let emptyCell = nextEmptyCell(puzzleArray);

    for (var num in shuffle(numArray)) {
      if (safeToPlace(puzzleArray, emptyCell, numArray[num])) {
        puzzleArray[emptyCell.rowIndex][emptyCell.colIndex] = numArray[num];
        fillBoard(puzzleArray);
      } 
    }

    return puzzleArray;
  }

Das ist mein ganzer Code:

import { Box } from "./Box";

export function Board() {
  let 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 = [
    [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 counter: number = 0;
  let check: number[];
  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 {
    let test = puzzleArray.flat();
    for (let i = emptyCell.colIndex; i < test.length; i += 9) {
      if (test[i] === 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;
  }

  console.log(rowSafe(BLANK_BOARD, { rowIndex: 4, colIndex: 6 }, 5));
  console.log(colSafe(BLANK_BOARD, { rowIndex: 2, colIndex: 3 }, 4));
  console.log(regionSafe(BLANK_BOARD, { rowIndex: 5, colIndex: 6 }, 5));

  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)
    );
  }

  console.log(safeToPlace(BLANK_BOARD, { rowIndex: 5, colIndex: 6 }, 5));

  function nextEmptyCell(puzzleArray: number[][]): {
    colIndex: number;
    rowIndex: number;
  } {
    let emptyCell = { rowIndex: -1, colIndex: -1 };
    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 emptyCell;
  }

  function shuffle(array: number[]): number[] {
    // using Array sort and Math.random

    let shuffledArr = array.sort(() => 0.5 - Math.random());
    return shuffledArr;
  }

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

    let emptyCell = nextEmptyCell(puzzleArray);

    for (var num in shuffle(numArray)) {
      if (safeToPlace(puzzleArray, emptyCell, numArray[num])) {
        puzzleArray[emptyCell.rowIndex][emptyCell.colIndex] = numArray[num];
        fillBoard(puzzleArray);
      } else {
        puzzleArray[emptyCell.rowIndex][emptyCell.colIndex] = 0;
      }
    }

    return puzzleArray;
  }

  console.log(nextEmptyCell(BLANK_BOARD));

  NEW_BOARD = fillBoard(BLANK_BOARD);

  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) => (
        <Box i={item} />
      ))}
    </div>
  );
}

Answer 1

当发现在一个空白单元格中无法添加有效数字时，该函数将返回一个不完整的数独板。

为了解决这个问题，你的函数应该：

• 实现正确的回溯，即撤销一个不成功的移动
• 使函数返回一个布尔值（表示成功/失败）--不需要返回puzzleArray，因为该数组在原地进行了修改，所以调用者可以访问到这些变化。
  • 这也意味着NEW_BOARD = fillBoard(BLANK_BOARD);的副作用是NEW_BOARD和BLANK_BOARD引用了同一个数独板，而且它不再是空白的（所以名称有误导性）。
• 在成功时中断/返回循环。

下面是修改后的实现：

function fillBoard(puzzleArray: number[][]): boolean {
    if (nextEmptyCell(puzzleArray).colIndex === -1) return true; // 布尔值

    let emptyCell = nextEmptyCell(puzzleArray);

    for (var num in shuffle(numArray)) {
      if (safeToPlace(puzzleArray, emptyCell, numArray[num])) {
        puzzleArray[emptyCell.rowIndex][emptyCell.colIndex] = numArray[num];
        if fillBoard(puzzleArray) return true; // 成功时退出
      } 
    }
    puzzleArray[emptyCell.rowIndex][emptyCell.colIndex] = 0; // 撤销
    return false; // 布尔值 - 没有成功
}

调用者应该检查返回值，但如果你从一个空白板开始，保证会得到true作为返回值。所以你可以这样做：

const puzzleArray = BLANK_BOARD.map(row => [...row]); // 深拷贝
const success = fillBoard(puzzleArray); // 返回一个布尔值
// ... 对puzzleArray做一些操作 ...