I wrote a Sudoku solving algorithm in the background in Python.

It solves a 2D array like this (zero means "empty field"):

```
(
(7, 0, 0, 0, 0, 9, 0, 0, 3),
(0, 9, 0, 1, 0, 0, 8, 0, 0),
(0, 1, 0, 0, 0, 7, 0, 0, 0),
(0, 3, 0, 4, 0, 0, 0, 8, 0),
(6, 0, 0, 0, 8, 0, 0, 0, 1),
(0, 7, 0, 0, 0, 2, 0, 3, 0),
(0, 0, 0, 5, 0, 0, 0, 1, 0),
(0, 0, 4, 0, 0, 3, 0, 9, 0),
(5, 0, 0, 7, 0, 0, 0, 0, 2),
)
```

like that:

```
(
(7, 5, 8, 2, 4, 9, 1, 6, 3),
(4, 9, 3, 1, 5, 6, 8, 2, 7),
(2, 1, 6, 8, 3, 7, 4, 5, 9),
(9, 3, 5, 4, 7, 1, 2, 8, 6),
(6, 4, 2, 3, 8, 5, 9, 7, 1),
(8, 7, 1, 9, 6, 2, 5, 3, 4),
(3, 2, 7, 5, 9, 4, 6, 1, 8),
(1, 8, 4, 6, 2, 3, 7, 9, 5),
(5, 6, 9, 7, 1, 8, 3, 4, 2)
)
```

But for the "difficult" Sudokus (where there are many zeros at the beginning), it's quite slow. It takes about 9 seconds for the algorithm to solve the Sudoku above. It's way better than what I started doing (90 seconds), but still slow.

I think the "deep copy" can be improved / replaced (as it is executed 103,073 times in the example below), but my basic approaches have been slower.

I've heard about C / C ++ solutions of 0.01 second, but I do not know if these are backtracking algorithms of a mathematical solution …

This is my entire algorithm with 2 examples of Sudokus:

```
from copy import deepcopy
def is_sol_row(mat,row,val):
m = len(mat)
for i in range(m):
if mat(row)(i) == val:
return False
return True
def is_sol_col(mat,col,val):
m = len(mat)
for i in range(m):
if mat(i)(col) == val:
return False
return True
def is_sol_block(mat,row,col,val):
rainbow = (0,0,0,3,3,3,6,6,6)
i = rainbow(row)
j = rainbow(col)
elements = {
mat(i + 0)(j + 0), mat(i + 1)(j + 0), mat(i + 2)(j + 0),
mat(i + 0)(j + 1), mat(i + 1)(j + 1), mat(i + 2)(j + 1),
mat(i + 0)(j + 2), mat(i + 1)(j + 2), mat(i + 2)(j + 2),
}
if val in elements:
return False
return True
def is_sol(mat,row,col,val):
return is_sol_row(mat,row,val) and is_sol_col(mat,col,val) and is_sol_block(mat,row,col,val)
def findAllZeroIndizes(mat):
m = len(mat)
indizes = ()
for i in range(m):
for j in range(m):
if mat(i)(j) == 0:
indizes.append((i,j))
return indizes
def sudoku(mat):
q = ((mat,0))
zeroIndizes = findAllZeroIndizes(mat)
while q:
t,numSolvedIndizes = q.pop()
if numSolvedIndizes == len(zeroIndizes):
return t
else:
i,j = zeroIndizes(numSolvedIndizes)
for k in range(1,10):
if is_sol(t,i,j,k):
newt = deepcopy(t)
newt(i)(j) = k
q.append((newt,numSolvedIndizes+1))
return False
mat = (
(7, 0, 0, 0, 0, 9, 0, 0, 3),
(0, 9, 0, 1, 0, 0, 8, 0, 0),
(0, 1, 0, 0, 0, 7, 0, 0, 0),
(0, 3, 0, 4, 0, 0, 0, 8, 0),
(6, 0, 0, 0, 8, 0, 0, 0, 1),
(0, 7, 0, 0, 0, 2, 0, 3, 0),
(0, 0, 0, 5, 0, 0, 0, 1, 0),
(0, 0, 4, 0, 0, 3, 0, 9, 0),
(5, 0, 0, 7, 0, 0, 0, 0, 2),
)
# mat = (
# (3, 0, 6, 5, 0, 8, 4, 0, 0),
# (5, 2, 0, 0, 0, 0, 0, 0, 0),
# (0, 8, 7, 0, 0, 0, 0, 3, 1),
# (0, 0, 3, 0, 1, 0, 0, 8, 0),
# (9, 0, 0, 8, 6, 3, 0, 0, 5),
# (0, 5, 0, 0, 9, 0, 6, 0, 0),
# (1, 3, 0, 0, 0, 0, 2, 5, 0),
# (0, 0, 0, 0, 0, 0, 0, 7, 4),
# (0, 0, 5, 2, 0, 6, 3, 0, 0)
# )
print(sudoku(mat))
```