# Sudoko Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy **all of the following rules**:

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.

```
class Solution:
# @param board, a 9x9 2D array
# Solve the Sudoku by modifying the input board in-place.
# Do not return any value.
def solveSudoku(self, board):
self.board = board
self.solve()
def findUnassigned(self):
for row in range(9):
for col in range(9):
if self.board[row][col] == ".":
return row, col
return -1, -1
def solve(self):
row, col = self.findUnassigned()
#no unassigned position is found, puzzle solved
if row == -1 and col == -1:
return True
for num in ["1","2","3","4","5","6","7","8","9"]:
if self.isSafe(row, col, num):
self.board[row][col] = num
if self.solve():
return True
self.board[row][col] = "."
return False
def isSafe(self, row, col, ch):
boxrow = row - row%3
boxcol = col - col%3
if self.checkrow(row,ch) and self.checkcol(col,ch) and self.checksquare(boxrow, boxcol, ch):
return True
return False
def checkrow(self, row, ch):
for col in range(9):
if self.board[row][col] == ch:
return False
return True
def checkcol(self, col, ch):
for row in range(9):
if self.board[row][col] == ch:
return False
return True
def checksquare(self, row, col, ch):
for r in range(row, row+3):
for c in range(col, col+3):
if self.board[r][c] == ch:
return False
return True
```

## Related Problems

Given a string **S** and an integer **K**, return *the length of the longest substring of* **S** *that contains at most* **K** **distinct*** characters*.

Given an integer array nums, you need to find one **continuous subarray** such that if you only sort this subarray in non-decreasing order, then the whole array will be sorted in non-decreasing order.

Return *the shortest such subarray and output its length*.

You are given two integer arrays nums1 and nums2, sorted in **non-decreasing order**, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

**Merge** nums1 and nums2 into a single array sorted in **non-decreasing order**.

The final sorted array should not be returned by the function, but instead be *stored inside the array *nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Given a string s, *find the first non-repeating character in it and return its index*. If it does not exist, return -1