Skip to content

Instantly share code, notes, and snippets.

@jesusgoku

jesusgoku/sudoku_solve.py

Created August 7, 2020 15:43
Show Gist options
  • Save jesusgoku/092b479ba441af5345abf88b0c0c1b19 to your computer and use it in GitHub Desktop.
Save jesusgoku/092b479ba441af5345abf88b0c0c1b19 to your computer and use it in GitHub Desktop.
Download ZIP
Sudoku solve algorithm show in Computerphile: https://www.youtube.com/watch?v=G_UYXzGuqvM
Raw
sudoku_solve.py
grid = [ [4, 0, 0, 0, 0, 5, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 9, 8],
[3, 0, 0, 0, 8, 2, 4, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 8, 0],
[9, 0, 3, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 3, 0, 6, 7, 0],
[0, 5, 0, 0, 0, 9, 0, 0, 0],
[0, 0, 0, 2, 0, 0, 9, 0, 7],
[6, 4, 0, 3, 0, 0, 0, 0, 0], ]
def possible(x, y, n):
for i in range(0, 9):
if grid[i][x] == n and i != y:
return False
for i in range(0, 9):
if grid[y][i] == n and i != x:
return False
x0 = (x // 3) * 3
y0 = (y // 3) * 3
for X in range(x0, x0 + 3):
for Y in range(y0, y0 + 3):
if grid[Y][X] == n:
return False
return True
def Print(matrix):
for i in range(9):
print(matrix[i])
def solve():
global grid
for y in range(9):
for x in range(9):
if grid[y][x] == 0:
for n in range(1, 10):
if possible(x, y, n):
grid[y][x] = n
solve()
grid[y][x] = 0
return
Print(grid)
input("")
solve()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment