Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
- Each of the digits
1-9must occur exactly once in each row. - Each of the digits
1-9must occur exactly once in each column. - Each of the digits
1-9must occur exactly once in each of the 93x3sub-boxes of the grid.
The '.' character indicates empty cells.
Example 1:
Input: board = [[“5″,”3″,”.”,”.”,”7″,”.”,”.”,”.”,”.”],[“6″,”.”,”.”,”1″,”9″,”5″,”.”,”.”,”.”],[“.”,”9″,”8″,”.”,”.”,”.”,”.”,”6″,”.”],[“8″,”.”,”.”,”.”,”6″,”.”,”.”,”.”,”3″],[“4″,”.”,”.”,”8″,”.”,”3″,”.”,”.”,”1″],[“7″,”.”,”.”,”.”,”2″,”.”,”.”,”.”,”6″],[“.”,”6″,”.”,”.”,”.”,”.”,”2″,”8″,”.”],[“.”,”.”,”.”,”4″,”1″,”9″,”.”,”.”,”5″],[“.”,”.”,”.”,”.”,”8″,”.”,”.”,”7″,”9″]]
Output: [[“5″,”3″,”4″,”6″,”7″,”8″,”9″,”1″,”2”],[“6″,”7″,”2″,”1″,”9″,”5″,”3″,”4″,”8”],[“1″,”9″,”8″,”3″,”4″,”2″,”5″,”6″,”7”],[“8″,”5″,”9″,”7″,”6″,”1″,”4″,”2″,”3”],[“4″,”2″,”6″,”8″,”5″,”3″,”7″,”9″,”1”],[“7″,”1″,”3″,”9″,”2″,”4″,”8″,”5″,”6”],[“9″,”6″,”1″,”5″,”3″,”7″,”2″,”8″,”4”],[“2″,”8″,”7″,”4″,”1″,”9″,”6″,”3″,”5”],[“3″,”4″,”5″,”2″,”8″,”6″,”1″,”7″,”9”]]
Explanation: The input board is shown above and the only valid solution is shown below:
Constraints:
board.length == 9board[i].length == 9board[i][j]is a digit or'.'.- It is guaranteed that the input board has only one solution.
Java Solution
public class SudokuSolver {
public void solveSudoku(char[][] board) {
if (board == null || board.length != 9 || board[0].length != 9) {
return;
}
solve(board);
}
private boolean solve(char[][] board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') {
for (char num = '1'; num <= '9'; num++) {
if (isValid(board, i, j, num)) {
board[i][j] = num;
if (solve(board)) {
return true;
}
board[i][j] = '.'; // undo the choice if it doesn't lead to a solution
}
}
return false; // no valid choice found
}
}
}
return true; // board is filled completely
}
private boolean isValid(char[][] board, int row, int col, char num) {
// Check if 'num' is not already present in the current row, column, and 3x3 subgrid
for (int i = 0; i < 9; i++) {
if (board[row][i] == num || board[i][col] == num || board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == num) {
return false;
}
}
return true;
}
public static void printBoard(char[][] board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.print(board[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
SudokuSolver solver = new SudokuSolver();
char[][] board = {
{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
{'6', '.', '.', '1', '9', '5', '.', '.', '.'},
{'.', '9', '8', '.', '.', '.', '.', '6', '.'},
{'8', '.', '.', '.', '6', '.', '.', '.', '3'},
{'4', '.', '.', '8', '.', '3', '.', '.', '1'},
{'7', '.', '.', '.', '2', '.', '.', '.', '6'},
{'.', '6', '.', '.', '.', '.', '2', '8', '.'},
{'.', '.', '.', '4', '1', '9', '.', '.', '5'},
{'.', '.', '.', '.', '8', '.', '.', '7', '9'}
};
System.out.println("Original Sudoku Board:");
printBoard(board);
solver.solveSudoku(board);
System.out.println("\nSolved Sudoku Board:");
printBoard(board);
}
}
This program defines a SudokuSolver class with the solveSudoku method to solve the Sudoku puzzle. The isValid method checks if a number can be placed in a specific position on the board. The solve method uses backtracking to fill the board with valid numbers. The main method demonstrates how to use the program with the provided example.
Python Solution
Here’s the Python solution to solve the Sudoku problem using backtracking:
class SudokuSolver:
def solveSudoku(self, board):
if not board or len(board) != 9 or len(board[0]) != 9:
return
self.solve(board)
def solve(self, board):
for i in range(9):
for j in range(9):
if board[i][j] == '.':
for num in map(str, range(1, 10)):
if self.isValid(board, i, j, num):
board[i][j] = num
if self.solve(board):
return True
board[i][j] = '.' # undo the choice if it doesn't lead to a solution
return False # no valid choice found
return True # board is filled completely
def isValid(self, board, row, col, num):
# Check if 'num' is not already present in the current row, column, and 3x3 subgrid
for i in range(9):
if board[row][i] == num or board[i][col] == num or board[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == num:
return False
return True
def printBoard(board):
for i in range(9):
print(" ".join(board[i]))
if __name__ == "__main__":
solver = SudokuSolver()
board = [
['5', '3', '.', '.', '7', '.', '.', '.', '.'],
['6', '.', '.', '1', '9', '5', '.', '.', '.'],
['.', '9', '8', '.', '.', '.', '.', '6', '.'],
['8', '.', '.', '.', '6', '.', '.', '.', '3'],
['4', '.', '.', '8', '.', '3', '.', '.', '1'],
['7', '.', '.', '.', '2', '.', '.', '.', '6'],
['.', '6', '.', '.', '.', '.', '2', '8', '.'],
['.', '.', '.', '4', '1', '9', '.', '.', '5'],
['.', '.', '.', '.', '8', '.', '.', '7', '9']
]
print("Original Sudoku Board:")
printBoard(board)
solver.solveSudoku(board)
print("\nSolved Sudoku Board:")
printBoard(board)
This Python code mirrors the Java solution. The SudokuSolver class has the solveSudoku method to solve the Sudoku puzzle, and the isValid method checks if a number can be placed in a specific position on the board. The solve method uses backtracking to fill the board with valid numbers. The printBoard function helps print the Sudoku board. The if __name__ == "__main__": block demonstrates how to use the program with the provided example.