87 lines
3.1 KiB
Python
87 lines
3.1 KiB
Python
# Sudoku Solver
|
|
# Recursive backtracking algorithm
|
|
# Usage: python3 sudoku.py [puzzle.txt]
|
|
|
|
import sys
|
|
|
|
grid0 = [[0,0,8,0,0,0,0,1,6], # Data type for sudoku puzzles:
|
|
[5,0,0,0,9,2,0,0,8], # a list of 9 lists, each of 9 digits.
|
|
[0,0,0,1,0,0,0,0,0],
|
|
[9,0,0,3,0,0,8,2,0], # grid0 is a global variable used by readFile()
|
|
[0,2,0,0,0,0,0,7,0],
|
|
[0,8,4,0,0,6,0,0,5], # This sudoku is solved when there is no
|
|
[0,0,0,0,0,3,0,0,0], # filename argument on the command line.
|
|
[4,0,0,9,6,0,0,0,2],
|
|
[1,6,0,0,0,0,7,0,0]]
|
|
|
|
def readFile():
|
|
'''Parses a textfile containing a sudoku puzzle;
|
|
returns this puzzle as 'grid', a list of 9 lists of 9 digits.
|
|
Returns grid0 if no filename is given on the command line.
|
|
'''
|
|
if len(sys.argv) == 1: # No command line argument
|
|
return grid0
|
|
else:
|
|
name = sys.argv[1] # A filename or path/filename of a sudoku textfile
|
|
file = open(name)
|
|
grid = []
|
|
while True:
|
|
txt = file.readline()
|
|
if txt == "": break
|
|
row = []
|
|
for ch in txt: # In the sudoku textfile:
|
|
if ch == "#": break # a '#' can be used for comments,
|
|
if ch == ".": row.append(0) # '.' or '0' stand for empty cells
|
|
if ch == "_": row.append(0) # '_' or '-'
|
|
if ch == "-": row.append(0) # could also be used for this.
|
|
if ch.isdigit(): row.append(int(ch))
|
|
if row != []: # all lines without digits or empty cell characters give []
|
|
if len(row) != 9:
|
|
print("Sudoku file configuration error: not 9 columns");
|
|
file.close; exit() # Halt the program
|
|
grid.append(row)
|
|
file.close()
|
|
if len(grid) != 9:
|
|
print("Sudoku file configuration error: not 9 rows"); exit()
|
|
else:
|
|
return grid
|
|
|
|
def printGrid (grid):
|
|
for i in range(0, 9):
|
|
if i > 0 and i % 3 == 0:
|
|
print("------+-------+------", end="")
|
|
print()
|
|
for j in range(0, 9):
|
|
if j > 0 and j % 3 == 0: print("| ", end="")
|
|
n = grid[i][j]
|
|
c = "." if n == 0 else str(n)
|
|
print(c, end=" ")
|
|
print()
|
|
|
|
def valid (row, col, n):
|
|
res = True
|
|
for i in range(0, 9):
|
|
for j in range(0, 9):
|
|
if ( i == row or j == col or
|
|
i // 3 == row // 3 and j // 3 == col // 3 ): # square
|
|
if grid[i][j] == n: res = False
|
|
return res
|
|
|
|
def solve():
|
|
for row in range(0, 9):
|
|
for col in range(0, 9):
|
|
if grid[row][col] == 0:
|
|
for n in (range(1, 10)):
|
|
if valid(row, col, n):
|
|
grid[row][col] = n
|
|
solve() # recursive call
|
|
grid[row][col] = 0 # backtracking step
|
|
return
|
|
printGrid(grid) # The solved sudoku
|
|
input("\nPress enter to check for more solutions\n")
|
|
|
|
grid = readFile() # valid() and solve() use this global variable
|
|
printGrid(grid) # The unsolved sudoku
|
|
print()
|
|
solve()
|