37 Sudoku Solver

Problem

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution. A sudoku puzzle...... and its solution numbers marked in red.

Solutions

public class Solution {
    public void solveSudoku(char[][] board) {
        solve(board, 0, 0);
    }
    private boolean solve(char[][] board, int i, int j){
        if (i == board.length - 1 && j == board[0].length){
            return true;
        }
        if (j == board[0].length){
            i = i + 1;
            j = 0;
        }
        if (board[i][j] == '.'){
            for (int k = 1; k <= 9; k ++ ){
                board[i][j] = (char)((int)'0' + k);
                if (valid(board, i, j) == true){
                    boolean tmp = solve(board, i, j+1);
                    if (tmp == true){
                        return true;
                    }
                }
            }//for k
            board[i][j] = '.';
        }// i j
        else{
            return solve(board, i, j+1);
        }

        return false;
    }
    private boolean valid(char[][] board, int x, int y){
        int check = 0;
        for (int j = 0; j < board[0].length; j ++){
            int val = board[x][j] - '0';
            if (board[x][j] == '.'){
                continue;
            }
            if ((check & (1<<(val-1))) == 1<<(val-1)){
                return false;
            }
            else{
                check = check | 1<<(val-1);
            }
        }
        check = 0;
        for (int i = 0; i < board.length; i ++){
            int val = board[i][y] - '0';
            if (board[i][y] == '.'){
                continue;
            }
            if ((check & (1<<(val-1))) == 1<<(val-1)){
                return false;
            }
            else{
                check = check | 1<<(val-1);
            }
        }
        int ib = x/3;
        int jb = y/3;
        check = 0;
        for (int i = ib*3; i < (ib+1)*3; i ++){
            for (int j = jb*3; j < (jb+1)*3; j++){
                int val = board[i][j] - '0';
                if (board[i][j] == '.'){
                    continue;
                }
                if ((check & (1<<(val-1))) == 1<<(val-1)){
                    return false;
                }
                else{
                    check = check | 1<<(val-1);
                }
            }
        }


        return true;
    }
}