# Naive java recursion approach

• ``````public class Solution {

/**
* Assumptions:
* numbers are between 1 and 9
* there is a solution
* board is always 9 X 9 fields
*
* approach
* dfs of solution space
* backtracking if a change results in an invalid board
*/
public void solveSudoku(char[][] board) {
if ( isSolution(board) ) { return; }
for ( int r = 0; r < 9; r++ ) {
for ( int c = 0; c < 9; c++ ) {
if ( isEmpty(board, r, c) ) {
for ( int i = 1; i <= 9; i++ ) {
board[r][c] = Character.forDigit(i, 10);
if ( isValidRow(board, r) && isValidCol(board, c) && isValidBlock(board, r, c) ) {
solveSudoku(board);
if ( isSolution(board) ) { return; }
}
}
board[r][c] = '.';
return;
}
}
}
}

private static boolean isEmpty(char[][] board, int r, int c) {
return board[r][c] == '.';
}

static boolean isSolution(char[][] board) {
for ( int r = 0; r < 9; r++ )
if ( !isCompleteRow(board, r) || !isValidRow(board, r) ) return false;
for ( int c = 0; c < 9; c++ )
if ( !isValidCol(board, c) ) return false;
for ( int i = 0; i < 9; i = i + 3 )
for ( int j = 0; j < 9; j = j + 3 )
if ( !isValidBlock(board, i, j) ) return false;
return true;
}

private static boolean isCompleteRow(char[][] board, int r) {
for ( int c = 0; c < 9; c++ ) {
if ( board[r][c] == '.' ) { return false; }
}
return true;
}

private static boolean isValidBlock(char[][] board, int i, int j) {
i = i / 3;
j = j / 3;
BitSet nums = new BitSet();
for ( int r = i * 3, n = r + 3; r < n ; r++ )
for ( int c = j * 3, m = c + 3; c < m ; c++ ) {
if ( !isEmpty(board, r, c) ) {
if ( nums.get(board[r][c] - '0') ) return false;
nums.set(board[r][c] - '0');
}
}
return true;
}

static boolean isValidRow(char[][] board, int r) {
BitSet nums = new BitSet();
for ( int c = 0; c < 9; c++ ) {
if ( !isEmpty(board, r, c) ) {
if ( nums.get(board[r][c] - '0') ) return false;
nums.set(board[r][c] - '0');
}
}
return true;
}

static boolean isValidCol(char[][] board, int c) {
BitSet nums = new BitSet();
for ( int r = 0; r < 9; r++ ) {
if ( !isEmpty(board, r, c) ) {
if ( nums.get(board[r][c] - '0') ) return false;
nums.set(board[r][c] - '0');
}
}
return true;
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.