-1

I'm new to Java and I'm trying to build a sudoku solver programm using backtracking and an int[][] matrix.

Function usage:

  1. isSafeSudoku()

    • this function checks whether the digit (from 1 to 9) is safe to place in correspondance to its row and its column and also its 3x3 grid.
  2. sudokuSolver()

    • this function is recursive and it's the one which calls all other function
  3. sudokuPrint()

    • this function simply prints the sudoku
public class sudoku {
// Function of sudoku solver ---------------------------------------
  public static boolean isSafeSudoku(int sudoku[][], int row, int col, int digit) {
    // is safe for that column ? vertically ?
    for (int i = 0; i < 9; i++) {
      if (sudoku[i][col] == digit) {
        return false;
      }
    }

    // is safe for that row ? horizontally ?
    for (int j = 0; j < 9; j++) {
      if (sudoku[row][j] == digit) {
        return false;
      }
    }

    // is safe for that grid ? that particular 3x3 grid
    int sr = (row / 3) * 3; // sr: starting row
    int sc = (col / 3) * 3; // sc: starting column
    // 3x3 grid
    for (int i = sr; i < sr + 3; i++) {
      for (int j = sc; j < sc + 3; j++) {
        if (sudoku[row][col] == digit) {
          return false;
        }
      }
    }

    return true;

  }

**// this is recursive function**
  public static boolean sudokuSolver(int sudoku[][], int row, int col) {
    // Base case
    if (row == 9) {
      return true;
    }

    // Recursion Part

    // A way to traverse in sudoku from col to col then next row and then again col
    // to col
    int nextRow = row, nextCol = col + 1;
    if (col + 1 == 9) {
      nextRow = row + 1;
      nextCol = 0;
    }

    if (sudoku[row][col] != 0) {
      sudokuSolver(sudoku, nextRow, nextCol);
    }

    // checker, if digit can be placed in the (row, col) or not?
    for (int digit = 1; digit <= 9; digit++) {
      if (isSafeSudoku(sudoku, row, col, digit)) {
        sudoku[row][col] = digit;
        if (sudokuSolver(sudoku, nextRow, nextCol)) { // if solution exist for digit for next row/col then do
          return true;
        }
        sudoku[row][col] = 0;
      }
    }

    return false;

  }

  public static void sudokuPrint(int sudoku[][]) {
    for (int row = 0; row < 9; row++) {
      for (int col = 0; col < 9; col++) {
        System.out.print(sudoku[row][col] + " ");
      }
      System.out.println();
    }
  }

  // Function of sudoku solver ends---------------------------------------

public static void main(String args[]) {

int sudoku[][] = {
        { 0, 0, 8, 0, 0, 0, 0, 0, 0 },
        { 4, 9, 0, 1, 5, 7, 0, 0, 2 },
        { 0, 0, 3, 0, 0, 4, 1, 9, 0 },
        { 1, 8, 5, 0, 6, 0, 0, 2, 0 },
        { 0, 0, 0, 0, 2, 0, 0, 6, 0 },
        { 9, 6, 0, 4, 0, 5, 3, 0, 0 },
        { 0, 3, 0, 0, 7, 2, 0, 0, 4 },
        { 0, 4, 9, 0, 3, 0, 0, 5, 7 },
        { 8, 2, 7, 0, 0, 9, 0, 1, 3 }
    };

    if (sudokuSolver(sudoku, 0, 0)) {
      System.out.println("Solution exist.");
    } else {
      System.out.println("Solution does not exist.");
    }

}

}

1 Answer 1

1

You should try -

if (sudoku[row][col] != 0) {
  return sudokuSolver(sudoku, nextRow, nextCol);
}

the return keyword is missing in your solution. Without which your code flow is going to the next for loop to assign value to sudoku[row][col], even when there is a value ie. not equals to 0.

Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.