Skip to content

Instantly share code, notes, and snippets.

@siddhantmedar
Created July 22, 2022 02:09
Show Gist options
  • Save siddhantmedar/cfda98e85a286808d1ded5bd8d90ece8 to your computer and use it in GitHub Desktop.
Save siddhantmedar/cfda98e85a286808d1ded5bd8d90ece8 to your computer and use it in GitHub Desktop.
Python code for sudoku solver [Backtracking Problem]
def isSafe(i, j, num, n):
for k in range(n):
if board[i][k] == num or board[k][j] == num:
return False
sx, sy = (i // 3) * 3, (j // 3) * 3
for x in range(sx, sx + 3):
for y in range(sy, sy + 3):
if board[x][y] == num:
return False
return True
def sudokuSolver(i, j, n):
if i == n:
for r in range(n):
for c in range(n):
print(board[r][c], end=" ")
print()
return
if j == n:
return sudokuSolver(i + 1, 0, n)
if board[i][j] != 0:
return sudokuSolver(i, j + 1, n)
for num in range(1, n + 1):
if isSafe(i, j, num, n):
board[i][j] = num
if sudokuSolver(i, j + 1, n):
return True
board[i][j] = 0
return False
board = [[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]]
sudokuSolver(0, 0, len(board))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment