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]])
Show your support

Clapping shows how much you appreciated Tomáš Bouda’s story.