Tuesday, February 11, 2014

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.

Solution:
DFS transformation. 

public class Solution {
    public void solveSudoku(char[][] board) {
        helper(board);
    }
    public boolean helper(char[][] board){
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if(board[i][j] == '.'){
                    for(int k = 1; k <= 9; k++){
                        board[i][j] = (char)(k + '0');
                        if(isValid(board, i, j) && helper(board)) 
                            return true;
                        board[i][j] = '.';
                    }    
                    return false;
                }
            }
        }
        return true;
    }
    public boolean isValid(char[][] board, int row, int col){
        char c = board[row][col];
        for(int i = 0; i < 9; i++){  // check rows
            if(i == row) continue;
            if(board[i][col] == c) return false;
        }
        for(int j = 0; j < 9; j++){ // check cols
            if(j == col) continue;
            if(board[row][j] == c) return false;
        }
        int a = row/3*3;
        int b = col/3*3;
        for(int i = 0; i < 3; i++){ // check cubic
            for(int j = 0; j < 3; j++){
                if(a+i==row && b+j==col) continue;
                if(board[a+i][b+j] == c) return false;
            }
        }
        return true;
    }
}

No comments:

Post a Comment