# 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]])`