Typescript數獨問題顯示部分填滿的棋盤

Question

我已經成功將一個js數獨生成器轉換成了一個ts生成器來練習，唯一的問題是如何讓它只輸出完整的數獨盤面。現在，它無論盤面是否完整都會輸出，我必須刷新直到出現一個正確的盤面。

我不確定如何寫以下函數，以便它只輸出完整的盤面：

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

這是我的所有程式碼：

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做一些操作 ...