Post

# Sudoku Solver

## 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.
1. static void Main(string[] args)
2. {
3.     var sudoku = new char[,]
4.     {
5.         { '5''3''.''.''7''.''.''.''.' },
6.         { '6''.''.''1''9''5''.''.''.' },
7.         { '.''9''8''.''.''.''.''6''.' },
8.         { '8''.''.''.''6''.''.''.''3' },
9.         { '4''.''.''8''.''3''.''.''1' },
10.         { '7''.''.''.''2''.''.''.''6' },
11.         { '.''6''.''.''.''.''2''8''.' },
12.         { '.''.''.''4''1''9''.''.''5' },
13.         { '.''.''.''.''8''.''.''7''9' }
14.     };
15.     solveSudoku(sudoku);
16. }
17. public static void solveSudoku(char[,] board)
18. {
19.     if (board == null || board.Length == 0)
20.         return;
21.     solve(board);
22. }
23. private static bool solve(char[,] board)
24. {
25.     for (int i = 0; i < board.GetLength(0); i++)
26.     {
27.         for (int j = 0; j < board.GetLength(1); j++)
28.         {
29.             if (board[i, j] == '.')
30.             {
31.                 for (char c = '1'; c <= '9'; c++)
32.                 {
33.                     if (isValid(board, i, j, c))
34.                     {
35.                         board[i, j] = c;
36.
37.                         if (solve(board))
38.                             return true;
39.                         else
40.                             board[i, j] = '.';
41.                     }
42.                 }
43.                 return false;
44.             }
45.         }
46.     }
47.     return true;
48. }
49. private static bool isValid(char[,] board, int row, int col, char c)
50. {
51.     for (int i = 0; i < 9; i++)
52.     {
53.         //check row
54.         if (board[i, col] != '.' && board[i, col] == c)
55.             return false;
56.         //check column
57.         if (board[row, i] != '.' && board[row, i] == c)
58.             return false;
59.         //check 3*3 block
60.         if (board[3 * (row / 3) + i / 3, 3 * (col / 3) + i % 3] != '.' && board[3 * (row / 3) + i / 3, 3 * (col / 3) + i % 3] == c)
61.         return false;
62.     }
63.     return true;
64. }