Sudoku Solver

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.

This is another backtracking problem. The key point is, when r > 8 (the whole thing is filled), the function returns a true, which will terminate the whole recursion. Very Important! Another thing is that if you searched a pre-filled location, directly return the result of the next position, do not continue the procedure.

public class Solution {
    public void solveSudoku(char[][] board) {
        if (solvable (board, 0, 0))
            return;
    }
    
    public boolean solvable (char[][] board, int r, int c) {
        if (r > 8) //filled eveything
            return true;
        int nextR = (c == 8)? r+1 : r;
        int nextC = (c == 8)? 0 : c+1;
        if (board[r][c] == '.') {
            for (int i = 1; i <= 9; i++) {// try 1 ~ 9
                board[r][c] = (char)(i + (int)'0');
                if (isValid(board, r, c))
                    if (solvable(board, nextR, nextC))
                        return true;
            }
            board[r][c] = '.';
            return false;
        } 
        return solvable(board, nextR, nextC);
    }
    
    public boolean isValid(char[][] board, int r, int c) {
        for (int i = 0; i < 9; i++) {
            if (board[r][i] == board[r][c]) {
                if (i != c)
                    return false;
            }
            if (board[i][c] == board[r][c]) {
                if (i != r)
                    return false;
            }
        }
        //get the starting point of the 3x3 square
        int row = (r/3)*3;
        int col = (c/3)*3;
        for (int i = row; i < row + 3; i++) {
            for (int j = col; j < col + 3; j++) {
                if (board[i][j] == board[r][c])
                    if (i != r || j != c)
                        return false;
            }
        }
        return true;
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s