Saturday, June 14, 2014

LeetCode: 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

public class Solution {
    public void solveSudoku(char[][] board) {
       solveSudoku(board, 0,  0);
    }
    
    public boolean solveSudoku(char[][] board, int row, int col)
    {
        if (row == 9)
            return true;
        int nextRow = col == 8 ? row+1 : row;
        int nextCol = col == 8 ? 0 : col+1;
        if (board[row][col] !='.')
            return solveSudoku(board, nextRow, nextCol);
        for (char c='1'; c<='9'; c++)
        {
            if (canPut(board, c, row, col))
            {
                board[row][col] = c;
                if (solveSudoku(board, nextRow, nextCol))
                    return true;
                board[row][col] = '.';
            }
        }
        return false;
    }
    
    public boolean canPut(char[][] board, char c, int row, int col)
    {
        for(int i=0; i<9; i++)
        {
            if(board[row][i]==c)
                return false;
            if(board[i][col]==c)
                return false;
        }
        int startRowGroup = (row/3)*3;
        int startColGroup = (col/3)*3;
        for(int i=startRowGroup; i<startRowGroup+3; i++)
        {
            for(int j=startColGroup; j<startColGroup+3; j++)
                if(board[i][j]==c)
                    return false;
        }
        return true;
    }
    
}

No comments :

Post a Comment