37 Sudoku Solver
37 Sudoku Solver
Sudoku Solver 
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
1
2
3
Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
The ‘.’ character indicates empty cells.
Example 1:
1
2
3
4
5
6
7
**Input:** board = [["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"]]
**Output:** [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
**Explanation:** The input board is shown above and the only valid solution is shown below:
Constraints:
1
2
3
4
board.length == 9
board[i].length == 9
board[i][j] is a digit or '.'.
It is **guaranteed** that the input board has only one solution.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
public class Solution {
public void SolveSudoku(char[][] board) {
Calc(board);
}
public bool Calc(char[][] board)
{
for(int i = 0 ; i < 9 ; i ++)
{
for(int j = 0 ; j < 9 ; j ++)
{
if(board[i][j] == '.')
{
var ls = findValidList(board , i , j);
if(ls.Count > 0)
{
foreach(var item in ls)
{
board[i][j] = item.ToString()[0];
if(Calc(board))
{
return true ;
}
}
board[i][j] = '.';
return false;
//findValidList(board , i , j)
}
else
{
return false;
}
}
}
}
return true;
}
public List<int> findValidList(char[][] board , int i , int j)
{
int[] arr = new int[9];
for(int k = 0 ; k < 9 ; k ++)
{
if(board[k][j] != '.')
{
arr[Int32.Parse(board[k][j].ToString()) - 1] = 1;
}
if(board[i][k] != '.')
{
//Console.WriteLine(Int32.Parse(board[i][k].ToString()) - 1);
arr[Int32.Parse(board[i][k].ToString()) - 1] = 1;
}
}
int k1 = 3*(i / 3) + 2;
int l = 3*(j / 3) + 2;
for (int c = 3 * (i / 3); c <= k1; c++)
{
for (int x = 3 * (j / 3); x <= l; x++)
{
if (board[c][x] != '.')
{
arr[Int32.Parse(board[c][x].ToString()) - 1] = 1;
}
}
}
List<int> ls = new List<int>();
for(int k = 0 ; k < 9 ; k ++)
{
if(arr[k] == 0)
{
ls.Add(k + 1);
}
}
return ls;
}
}
This post is licensed under CC BY 4.0 by the author.