0

好的，所以我查看了堆栈溢出站点并发现了一些类似的问题，但似乎没有一个可以解决我的问题。如果我是正确的，数组和对象会在 JavaScript 和 TypeScript 中通过引用自动传递，所以我似乎无法弄清楚为什么它不起作用。

这是我的完整代码：我正在为面试学习算法和数据结构

/**
 * sudoku Problem Board
 */
let sudokuBoard: Array<Array<number>> = [
  [0, 9, 5, 0, 0, 3, 0, 0, 2],
  [0, 0, 0, 0, 0, 1, 0, 0, 0],
  [6, 0, 2, 0, 0, 0, 0, 0, 9],
  [9, 0, 0, 7, 0, 0, 4, 0, 1],
  [0, 0, 0, 0, 0, 0, 5, 0, 0],
  [8, 0, 0, 0, 0, 0, 0, 3, 0],
  [0, 0, 7, 1, 0, 0, 0, 5, 0],
  [0, 1, 0, 8, 6, 0, 0, 2, 0],
  [3, 0, 0, 0, 0, 4, 0, 0, 0],
];

/**
 * Function to print the layout of sudoku board and its solution
 */
let printBoard = (sudokuBoard: Array<Array<number>>) => {
  for (let i: number = 0; i < sudokuBoard.length; i++) {
    if (i % 3 === 0 && i !== 0) {
      console.log("-----------------------");
    }
    let output = ``;
    for (let j: number = 0; j < sudokuBoard[0].length; j++) {
      if (j % 3 === 0 && j !== 0) {
        output += ` | `;
      }
      if (j === 8) {
        output += `${sudokuBoard[i][j]}`;
      } else {
        output += `${sudokuBoard[i][j]} `;
      }
    }
    console.log(output);
  }
  console.log("\n");
};

/**
 * Find the empty cell within the board
 * @param sudokuBoard board for which empty cell is to be found
 */
let findEmptyCell = (sudokuBoard: Array<Array<number>>): Array<number> => {
  for (let i: number = 0; i < sudokuBoard.length; i++) {
    for (let j: number = 0; j < sudokuBoard[0].length; j++) {
      if (sudokuBoard[i][j] === 0) {
        return [i, j];
      }
    }
  }
  return [-1, -1];
};

/**
 * Main Function to call while passing the entire sudoku board to solve
 * @param sudokuBoard
 */
let sudokuSolver = (sudokuBoard: Array<Array<number>>) => {
  const emptyCellPos: Array<number> = findEmptyCell(sudokuBoard);
  if (emptyCellPos[0] !== -1 && emptyCellPos[1] !== -1) {
    const row: number = emptyCellPos[0];
    const col: number = emptyCellPos[1];
    solveCell(row, col, sudokuBoard);
  }
};

/**
 * Function to fill the values in the board
 * @param row starting row index
 * @param col starting col index
 * @param sudokuBoard sudoku board to solve
 */
let solveCell = (
  row: number,
  col: number,
  sudokuBoard: Array<Array<number>>
): boolean => {
  let emptyEntry: number = 0; // value to fill when backtracking is done to restore the wrong cell with default value

  /**
   * Check if column and row bounds are intact and take actions accordingly
   * When col bound is met, change the row
   * When row bound is met, we have finished the board
   */
  if (col === sudokuBoard[row].length) {
    col = 0;
    row++;
    if (row === sudokuBoard.length) {
      return true;
    }
  }

  /**
   * If number present already, recurse for next cell in the row
   */
  if (sudokuBoard[row][col] !== emptyEntry) {
    return solveCell(row, col + 1, sudokuBoard);
  }

  /**
   * If empty cell is found, make a choice from decision set following the required constraint
   * We loop from 1 to board length as all numbers that lie within, will be our decision space
   * We then check each value whether it's suitable for that cell or not
   * If yes, we place it in that cell and check the move for next cell, If it proceeds with true, we do nothing, otherwise we empty that cell with our default 'emptyEntry'
   */
  for (let value: number = 1; value < sudokuBoard.length; value++) {
    let placeValue: number = value;

    if (placeCellValue(sudokuBoard, row, col, placeValue)) {
      sudokuBoard[row][col] = value;

      if (solveCell(row, col + 1, sudokuBoard)) {
        return true;
      }
      sudokuBoard[row][col] = emptyEntry;
    }
  }
  return false;
};

/**
 * Check constraints for value before placing it in the given cell
 * @param sudokuBoard sudoku board to solve
 * @param row row index
 * @param col col index
 * @param placeValue value to place in the given sudokuboard[row][col] cell
 */
let placeCellValue = (
  sudokuBoard: Array<Array<number>>,
  row: number,
  col: number,
  placeValue: number
): boolean => {
  /**
   * Check for the row whether the value is already present
   */
  for (let j: number = 0; j < sudokuBoard[0].length; j++) {
    if (sudokuBoard[row][j] === placeValue) {
      return false;
    }
  }

  /**
   * Check for the column whether the value is already present
   */
  for (let i: number = 0; i < sudokuBoard.length; i++) {
    if (sudokuBoard[i][col] === placeValue) {
      return false;
    }
  }

  /**
   * Check if the value is present in the subgrid
   */
  const regionSize = Math.sqrt(sudokuBoard.length);
  const box_row = Math.floor(row / 3);
  const box_col = Math.floor(col / 3);
  const top_left_box_row = box_row * regionSize;
  const top_left_box_col = box_col * regionSize;

  for (let i: number = 0; i < regionSize; i++) {
    for (let j: number = 0; j < regionSize; j++) {
      if (
        sudokuBoard[top_left_box_row + i][top_left_box_col + j] === placeValue
      ) {
        return false;
      }
    }
  }
  return true;
};

console.log("\nSudoku Problem:\n");
printBoard(sudokuBoard);
sudokuSolver(sudokuBoard);
console.log("\nSudoku Solution:\n");
printBoard(sudokuBoard);

两种 printBoard 方法都在打印相同的东西。另一个附加信息，我直接在终端中使用 deno 运行这个 TS 文件。它会自动编译打字稿，我觉得这非常适合这项任务。

任何帮助将不胜感激。谢谢。

4

0 回答 0