数独无解如何打印“-1”？

Question

我已经使用 JavaScript 解决了数独问题，但如果给定的数独没有解决方案，我想打印 -1 。我已经使用递归完成了它，并且用尽了我能想到的所有方法。请帮我解决这个无法解决的sudoko问题。

let row = 0;
let col = 0;
let matrix = [
    [0, 4, 0, 0, 0, 0, 1, 7, 9],
    [0, 0, 2, 0, 0, 8, 0, 5, 4],
    [0, 0, 6, 0, 0, 5, 0, 0, 8],
    [0, 8, 0, 0, 7, 0, 9, 1, 0],
    [0, 5, 0, 0, 9, 0, 0, 3, 0],
    [0, 1, 9, 0, 6, 0, 0, 4, 0],
    [3, 0, 0, 4, 0, 0, 7, 0, 0],
    [5, 7, 0, 1, 0, 0, 2, 0, 0],
    [9, 2, 8, 0, 0, 0, 0, 6, 0]
];

function sudoku(matrix, row, col) {
    if (row == 9) {
        console.log(matrix);
        return;
    }

    let next_row = 0;
    let next_col = 0;
    if (col == 8) {
        next_col = 0;
        next_row = row + 1;
    }
    else {
        next_col = col + 1;
        next_row = row;
    }
    if (matrix[row][col] != 0) {
        sudoku(matrix, next_row, next_col);
    }
    else {
        for (let i = 0; i <= 9; i++) {
            if (isSafe(matrix, row, col, i) == true) {
                matrix[row][col] = i;

                sudoku(matrix, next_row, next_col);
                matrix[row][col] = 0;
            }
        }
    }
}

function isSafe(matrix, row, col, value) {

    for (let i = 0; i < matrix.length; i++) {
        if (matrix[i][col] == value) {
            return false;
        }
    }

    for (let i = 0; i < matrix.length; i++) {
        if (matrix[row][i] == value) {
            return false;
        }
    }

    let x = Math.floor(row / 3) * 3;
    let y = Math.floor(col / 3) * 3;

    for (let i = 0; i < 3; i++) {
        for (let j = 0; j < 3; j++) {
            if (matrix[x + i][y + j] == value) {
                return false;
            }
        }
    }
    return true;
}

sudoku(matrix, row, col);

无解数独示例：

let matrix = [
    [0, 0, 0, 0, 5, 4, 3, 0, 6],
    [0, 0, 0, 0, 0, 3, 2, 7, 0],
    [0, 0, 0, 7, 2, 0, 0, 0, 1],
    [9, 0, 0, 0, 7, 0, 0, 5, 3],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [8, 2, 0, 0, 1, 0, 0, 0, 9],
    [3, 0, 0, 0, 6, 1, 0, 0, 0],
    [0, 4, 6, 9, 0, 0, 0, 0, 0],
    [7, 0, 1, 5, 4, 0, 0, 0, 6]
];

Answer 1

如果数独无效，您可以 return 假，如果有效，您可以 return 真。

let row = 0;
let col = 0;
let matrix = [
    [0, 0, 0, 0, 5, 4, 3, 0, 6],
    [0, 0, 0, 0, 0, 3, 2, 7, 0],
    [0, 0, 0, 7, 2, 0, 0, 0, 1],
    [9, 0, 0, 0, 7, 0, 0, 5, 3],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [8, 2, 0, 0, 1, 0, 0, 0, 9],
    [3, 0, 0, 0, 6, 1, 0, 0, 0],
    [0, 4, 6, 9, 0, 0, 0, 0, 0],
    [7, 0, 1, 5, 4, 0, 0, 0, 6]
];

function sudoku(matrix, row, col) {
  if (row == 9) {
    console.log(matrix);
    return true;
  }

  let next_row = 0;
  let next_col = 0;
  if (col == 8) {
    next_col = 0;
    next_row = row + 1;
  } else {
    next_col = col + 1;
    next_row = row;
  }
  if (matrix[row][col] != 0) {
    // Return the result from next empty box
    return sudoku(matrix, next_row, next_col);
  } else {
    for (let i = 0; i <= 9; i++) {
      if (isSafe(matrix, row, col, i) == true) {
        matrix[row][col] = i;
        // If found a valid sudoku, then return true. No need to check further.
        if (sudoku(matrix, next_row, next_col)) return true;
        matrix[row][col] = 0;
      }
    }
  }
  // No valid sudoku found after trying all numbers
  return false;
}

function isSafe(matrix, row, col, value) {

  for (let i = 0; i < matrix.length; i++) {
    if (matrix[i][col] == value) {
      return false;
    }
  }

  for (let i = 0; i < matrix.length; i++) {
    if (matrix[row][i] == value) {
      return false;
    }
  }

  let x = Math.floor(row / 3) * 3;
  let y = Math.floor(col / 3) * 3;

  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      if (matrix[x + i][y + j] == value) {
        return false;
      }
    }
  }
  return true;
}

const isValid = sudoku(matrix, row, col);
console.log(isValid ? "Valid Sudoku" : "Ivalid Sudoku");

数独无解如何打印“-1”？

How to print "-1" if sudoku has no solution?

javascript

recursion

sudoku