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

I have solved the sudoku using JavaScript but I want to print -1 if the given sudoku has no solution. I have done it using recursion and have exhausted all the ways that I could think of. Please help me solve this question for unsolvable sudoko's.

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

Example of sudoku with no solution:

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

CodePudding user response：

You can return false if the Sudoku is invalid and return true if it is valid.

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");