Java Sudoku Solver: Backtracking Algorithm Implementation

Building a Sudoku Solver in Java with Backtracking

This document presents a Java implementation of a Sudoku solver, utilizing a classic backtracking algorithm. The code demonstrates how to represent a Sudoku board, check for valid moves, and recursively find a solution to the puzzle.

Initial Sudoku Puzzle Setup

The Sudoku board is represented as a 2D integer array. A value of 0 indicates an empty cell that needs to be filled.

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

Implementing the Sudoku Solving Algorithm

The core of the solver is the solve method, which employs a recursive backtracking strategy. It iterates through each cell, attempting to place a valid number. If a number leads to a solution, it returns true; otherwise, it backtracks by resetting the cell and trying the next number.

private static boolean solve(int[][] board) {
  for (int row = BOARD_START_INDEX; row < BOARD_SIZE; row++) {
    for (int column = BOARD_START_INDEX; column < BOARD_SIZE; column++) {
      if (board[row][column] == NO_VALUE) {
        for (int k = MIN_VALUE; k <= MAX_VALUE; k++) {
          board[row][column] = k;
          if (isValid(board, row, column) && solve(board)) {
            return true;
          }
          board[row][column] = NO_VALUE; // Backtrack
        }
        return false; // No valid number found for this cell
      }
    }
  }
  return true; // Board is solved
}

Note: Constants like BOARD_START_INDEX (0), BOARD_SIZE (9), NO_VALUE (0), MIN_VALUE (1), MAX_VALUE (9), and SUBSECTION_SIZE (3) are assumed for a standard 9x9 Sudoku board.

Ensuring Valid Sudoku Moves

Before placing a number, the solver must verify that it adheres to Sudoku rules. The isValid method orchestrates these checks by calling three constraint functions:

private boolean isValid(int[][] board, int row, int column) {
  return (rowConstraint(board, row)
    && columnConstraint(board, column)
    && subsectionConstraint(board, row, column));
}

Checking Row, Column, and Subsection Rules

Each constraint method ensures that no duplicate numbers exist within its respective scope.

Row Constraint Verification

This method checks if the number placed in the current row is unique within that row.

private boolean rowConstraint(int[][] board, int row) {
  boolean[] constraint = new boolean[BOARD_SIZE];
  return IntStream.range(BOARD_START_INDEX, BOARD_SIZE)
    .allMatch(column -> checkConstraint(board, row, constraint, column));
}

Column Constraint Verification

Similarly, this method verifies the uniqueness of the number within its column.

private boolean columnConstraint(int[][] board, int column) {
  boolean[] constraint = new boolean[BOARD_SIZE];
  return IntStream.range(BOARD_START_INDEX, BOARD_SIZE)
    .allMatch(row -> checkConstraint(board, row, constraint, column));
}

Subsection Constraint Verification

This method checks the 3x3 subgrid (or "subsection") to ensure the number is unique within that block.

private boolean subsectionConstraint(int[][] board, int row, int column) {
  boolean[] constraint = new boolean[BOARD_SIZE];
  int subsectionRowStart = (row / SUBSECTION_SIZE) * SUBSECTION_SIZE;
  int subsectionRowEnd = subsectionRowStart + SUBSECTION_SIZE;
  int subsectionColumnStart = (column / SUBSECTION_SIZE) * SUBSECTION_SIZE;
  int subsectionColumnEnd = subsectionColumnStart + SUBSECTION_SIZE;
  for (int r = subsectionRowStart; r < subsectionRowEnd; r++) {
    for (int c = subsectionColumnStart; c < subsectionColumnEnd; c++) {
      if (!checkConstraint(board, r, constraint, c)) return false;
    }
  }
  return true;
}

The checkConstraint Helper Function

The checkConstraint method is a utility function used by all constraint checks. It takes a boolean array (constraint) to track numbers already encountered in a row, column, or subsection. If a number is encountered twice, it indicates a violation.

boolean checkConstraint(
  int[][] board,
  int row,
  boolean[] constraint,
  int column) {
  if (board[row][column] != NO_VALUE) {
    if (!constraint[board[row][column] - 1]) {
      constraint[board[row][column] - 1] = true;
    } else {
      return false; // Duplicate found
    }
  }
  return true;
}

Visualizing the Solved Sudoku Board

After the solve method successfully finds a solution, the printBoard method can be used to display the completed Sudoku grid to the console.

private void printBoard() {
  for (int row = BOARD_START_INDEX; row < BOARD_SIZE; row++) {
    for (int column = BOARD_START_INDEX; column < BOARD_SIZE; column++) {
      System.out.print(board[row][column] + " ");
    }
    System.out.println();
  }
}

This Java code provides a robust foundation for solving Sudoku puzzles using a recursive backtracking algorithm, demonstrating effective constraint checking and problem-solving techniques.