Problème de sudoku dactylographié montrant un tableau partiellement rempli

Question

J'ai réussi à convertir un générateur de Sudoku js en un générateur ts pour la pratique. Le seul problème est de savoir comment faire en sorte qu'il ne produise que le tableau Sudoku complet. Désormais, le résultat est affiché, que le disque soit complet ou non, et je dois actualiser jusqu'à ce qu'un disque correct apparaisse.

Je ne sais pas comment écrire la fonction suivante pour qu'elle ne génère que le disque complet :

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

Voici tout mon 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

Lorsqu'il s'avère qu'un numéro valide ne peut pas être ajouté dans une cellule vide, cette fonction renverra un tableau Sudoku incomplet.

Pour résoudre ce problème, votre fonction doit :

• Réaliser un retour en arrière correct, c'est-à-dire annuler un mouvement infructueux
• Fait en sorte que la fonction renvoie une valeur booléenne (indiquant le succès/l'échec) - il n'est pas nécessaire de renvoyer puzzleArray car le tableau est modifié sur place, afin que l'appelant puisse accéder à ces modifications.
  • Cela signifie également que NEW_BOARD = fillBoard(BLANK_BOARD);的副作用是NEW_BOARD和BLANK_BOARDfait référence au même tableau de Sudoku, et qu'il n'est plus vide (le nom est donc trompeur).
• Pause/retour en boucle en cas de réussite.

Voici l'implémentation modifiée :

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; // 布尔值 - 没有成功
}

L'appelant doit vérifier la valeur de retour, mais si vous commencez avec une page vierge, vous êtes assuré d'obtenir true comme valeur de retour. Vous pouvez donc faire ceci :

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