试图用打字稿和回溯解决数独的问题

Question

我正在编码算法，为了测试回溯，我决定在打字稿中实现数独求解器。

我正在使用一个简单的回溯实现，没什么特别的，但是不起作用：

export type SudokuBoard  = Array<Array<number>>;
export type Location = [number, number];

const UNASSIGNED = 0;

// Functions
export const range = (start: number, end: number): Array<number> =>
  Array.from({ length: end - start + 1 }, (_, i) => start + i);

function findEmptyLocation(board: SudokuBoard): Location {
  for (const row of range(0, 8))
    for (const col of range(0, 8))
      if (board[row][col] === UNASSIGNED) {
        return [row, col];
      }
  return null;
}

function usedInRow(board: SudokuBoard, row: number, value: number): boolean {
  for (const i of range(0, 8))
    if (board[row][i] === value)
      return true;

  return false;
}

function usedInCol(board: SudokuBoard, col: number, value: number): boolean {
  for (const i of range(0, 8))
    if(board[i][col] === value)
      return true;

  return false;
}

function usedInBox(board: SudokuBoard, row: number, col: number, value: number): boolean {
  for (const i of range(0, 2))
    for (const j of range(0, 2))
      if (board[i + row][j + col] === value)
        return true;

  return false;
}

const checkIsSafeLocation = (board: SudokuBoard, row: number, col: number, value: number) =>
  !usedInRow(board, row, value) && !usedInCol(board, col, value) && !usedInBox(board, row, col, value);


export function solveSudoku(board: SudokuBoard): boolean {
  const emptyLocation = findEmptyLocation(board);

  if (!emptyLocation)
    return true; // sudoku is solved!!

  const [row, column] = emptyLocation;

  for (const value of range(1, 9)) {
    // if looks promising (empty position)
    if (checkIsSafeLocation(board, row, column, value)) {
      console.log(`Position: (${row}, ${column}) accepts value: ${value}`);
      board[row][column] = value;

      if (solveSudoku(board)) // if is solved returns!!!
        return true;

      // not solved, reset location and try again
      board[row][column] = UNASSIGNED;
    }
  }

  return false;
}


// EXECUTION

console.clear();
console.log(solveSudoku([
    [0, 1, 6, 5, 7, 8, 4, 9, 2],
    [5, 2, 9, 1, 3, 4, 7, 6, 8],
    [4, 8, 7, 6, 2, 9, 5, 3, 1],
    [2, 6, 3, 4, 1, 5, 9, 8, 7],
    [9, 7, 4, 8, 6, 3, 1, 0, 5],
    [8, 5, 1, 7, 9, 2, 6, 4, 3],
    [1, 3, 8, 9, 4, 7, 2, 5, 6],
    [6, 9, 0, 3, 5, 1, 8, 7, 4],
    [7, 4, 5, 2, 8, 6, 3, 1, 0],
  ]));

您可以在这里查看：stackblitz

我的代码中的错误是错误的，因为这不起作用，但是我没有发现问题。

您能帮我吗？

Answer 1

我发现了问题。

框的计算错误。

谢谢。