Sudoku Solver

In this blog, you will learn about Solution for the LeetCode Problem #37.

Introduction

 

You are given a 9 X 9 sudoku which is assumed to have only one unique solution. Each cell may contain any one of the characters from '1' to '9' and if it's an empty cell then it will have the  '.' character. Solve the given Sudoku puzzle by filling in the empty cells. A sudoku solution must satisfy all of the following rules:

1. Each of the digits from  1-9 must occur exactly once in each row.
2. Each of the digits from 1-9 must occur exactly once in each column.
3. Each of the the digits from  1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

Given below is the sample input & its corresponsding output and here is the leetcode question.

 

 

 

Solution

 

This problem can be best solved by a dynamic programming approach by using a recursive method to check for the valid sudoku board. Any other approach would make it a bit complex. So in this solution, we will keep adding each character from '1' to '9' and check whether it's valid for the baord or not. It's that simple, and given below is the C# pseudo code for the algorithm.

static void Main(string[] args)
{
    var sudoku = new char[,]
    {
        { '5', '3', '.', '.', '7', '.', '.', '.', '.' },
        { '6', '.', '.', '1', '9', '5', '.', '.', '.' },
        { '.', '9', '8', '.', '.', '.', '.', '6', '.' },
        { '8', '.', '.', '.', '6', '.', '.', '.', '3' },
        { '4', '.', '.', '8', '.', '3', '.', '.', '1' },
        { '7', '.', '.', '.', '2', '.', '.', '.', '6' },
        { '.', '6', '.', '.', '.', '.', '2', '8', '.' },
        { '.', '.', '.', '4', '1', '9', '.', '.', '5' },
        { '.', '.', '.', '.', '8', '.', '.', '7', '9' }
    };
    solveSudoku(sudoku);
}
public static void solveSudoku(char[,] board)
{
    if (board == null || board.Length == 0)
        return;
    solve(board);
}
private static bool solve(char[,] board)
{
    for (int i = 0; i < board.GetLength(0); i++)
    {
        for (int j = 0; j < board.GetLength(1); j++)
        {
            if (board[i, j] == '.')
            {
                for (char c = '1'; c <= '9'; c++)
                {
                    if (isValid(board, i, j, c))
                    {
                        board[i, j] = c;

                        if (solve(board))
                            return true;
                        else
                            board[i, j] = '.';
                    }
                }
                return false;
            }
        }
    }
    return true;
}
private static bool isValid(char[,] board, int row, int col, char c)
{
    for (int i = 0; i < 9; i++)
    {
        //check row
        if (board[i, col] != '.' && board[i, col] == c)
            return false;
        //check column
        if (board[row, i] != '.' && board[row, i] == c)
            return false;
        //check 3*3 block
        if (board[3 * (row / 3) + i / 3, 3 * (col / 3) + i % 3] != '.' && board[3 * (row / 3) + i / 3, 3 * (col / 3) + i % 3] == c)
        return false;
    }
    return true;
}