# Day 23: Sudoku

Back on the day, I was fresh undergraduate at my first lecture of Linear algebra. The lecturer came in the class and told us, “This puzzle was a gift from my former student. It’s similar to Rubik’s cube but way more complex and I’m not able to solve it. Whoever of you solves it has granted A in the class.”

My classmate found a sequence of moves that led to permutation of three positions and wrote a program that first found solution in 6000 moves and then in 3000 moves. 3 weeks later he got A for granted.

Do you have a story about puzzle, too? Feel free to share with me.

https://github.com/coells/100days

#### algorithm

def sudoku(matrix, n=0):

if n >= 81:

return matrix

if matrix.A1[n]:

return sudoku(matrix, n + 1)

i, j, k, l = n // 9, n % 9, n // 27 * 3, (n % 9) // 3 * 3

# get viable values

x = set(range(1, 10)) - (

set(matrix[i].A1) |

set(matrix.T[j].A1) |

set(matrix[k:k + 3, l:l + 3].A1)

)

# backtracking

for value in x:

matrix[i, j] = value

if sudoku(matrix, n + 1) is not None:

return matrix

else:

matrix[i, j] = 0

#### hard sudoku

sudoku(np.matrix("""

8 0 0 1 0 9 0 7 0;

0 9 0 0 0 0 8 0 0;

5 0 3 0 4 0 0 0 0;

0 0 0 0 0 0 7 9 0;

0 0 7 2 6 5 3 0 0;

0 3 8 0 0 0 0 0 0;

0 0 0 0 9 0 4 0 1;

0 0 6 0 0 0 0 2 0;

0 5 0 4 0 2 0 0 3

"""))

matrix([[8, 2, 4, 1, 3, 9, 5, 7, 6],

[6, 9, 1, 5, 2, 7, 8, 3, 4],

[5, 7, 3, 6, 4, 8, 2, 1, 9],

[4, 6, 5, 3, 8, 1, 7, 9, 2],

[9, 1, 7, 2, 6, 5, 3, 4, 8],

[2, 3, 8, 9, 7, 4, 1, 6, 5],

[3, 8, 2, 7, 9, 6, 4, 5, 1],

[1, 4, 6, 8, 5, 3, 9, 2, 7],

[7, 5, 9, 4, 1, 2, 6, 8, 3]])