# Solving Every Sudoku Puzzle in Python Source Code

Wed Jan 01 2020 19:00:00 GMT+0000 (UTC)

Saved by @faustj4r #python #puzzles

```import re
import random
import os

# GLOBAL VARIABLES
grid_size = 81

def isFull (grid):
return grid.count('.') == 0

# can be used more purposefully
def getTrialCelli(grid):
for i in range(grid_size):
if grid[i] == '.':
print 'trial cell', i
return i

def isLegal(trialVal, trialCelli, grid):

cols = 0
for eachSq in range(9):
trialSq = [ x+cols for x in range(3) ] + [ x+9+cols for x in range(3) ] + [ x+18+cols for x in range(3) ]
cols +=3
if cols in [9, 36]:
cols +=18
if trialCelli in trialSq:
for i in trialSq:
if grid[i] != '.':
if trialVal == int(grid[i]):
print 'SQU',
return False

for eachRow in range(9):
trialRow = [ x+(9*eachRow) for x in range (9) ]
if trialCelli in trialRow:
for i in trialRow:
if grid[i] != '.':
if trialVal == int(grid[i]):
print 'ROW',
return False

for eachCol in range(9):
trialCol = [ (9*x)+eachCol for x in range (9) ]
if trialCelli in trialCol:
for i in trialCol:
if grid[i] != '.':
if trialVal == int(grid[i]):
print 'COL',
return False
print 'is legal', 'cell',trialCelli, 'set to ', trialVal
return True

def setCell(trialVal, trialCelli, grid):
grid[trialCelli] = trialVal
return grid

def clearCell( trialCelli, grid ):
grid[trialCelli] = '.'
print 'clear cell', trialCelli
return grid

def hasSolution (grid):
if isFull(grid):
print '\nSOLVED'
return True
else:
trialCelli = getTrialCelli(grid)
trialVal = 1
solution_found = False
while ( solution_found != True) and (trialVal < 10):
print 'trial valu',trialVal,
if isLegal(trialVal, trialCelli, grid):
grid = setCell(trialVal, trialCelli, grid)
if hasSolution (grid) == True:
solution_found = True
return True
else:
clearCell( trialCelli, grid )
print '++'
trialVal += 1
return solution_found

def main ():
#sampleGrid = ['2', '1', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '3', '1', '.', '.', '.', '.', '9', '4', '.', '.', '.', '.', '7', '8', '2', '5', '.', '.', '4', '.', '.', '.', '.', '.', '.', '6', '.', '.', '.', '.', '.', '1', '.', '.', '.', '.', '8', '2', '.', '.', '.', '7', '.', '.', '9', '.', '.', '.', '.', '.', '.', '.', '.', '3', '1', '.', '4', '.', '.', '.', '.', '.', '.', '.', '3', '8', '.']
#sampleGrid = ['.', '.', '3', '.', '2', '.', '6', '.', '.', '9', '.', '.', '3', '.', '5', '.', '.', '1', '.', '.', '1', '8', '.', '6', '4', '.', '.', '.', '.', '8', '1', '.', '2', '9', '.', '.', '7', '.', '.', '.', '.', '.', '.', '.', '8', '.', '.', '6', '7', '.', '8', '2', '.', '.', '.', '.', '2', '6', '.', '9', '5', '.', '.', '8', '.', '.', '2', '.', '3', '.', '.', '9', '.', '.', '5', '.', '1', '.', '3', '.', '.']
sampleGrid = ['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '4', '6', '2', '9', '5', '1', '8', '1', '9', '6', '3', '5', '8', '2', '7', '4', '4', '7', '3', '8', '9', '2', '6', '5', '1', '6', '8', '.', '.', '3', '1', '.', '4', '.', '.', '.', '.', '.', '.', '.', '3', '8', '.']
printGrid(sampleGrid, 0)
if hasSolution (sampleGrid):
printGrid(sampleGrid, 0)
else: print 'NO SOLUTION'

if __name__ == "__main__":
main()

i = 0
for val in grid:
if int(val) < 10:
print '0'+str(val),
else:
print val,
else:
print val,
i +=1
if i in [ (x*9)+3 for x in range(81)] +[ (x*9)+6 for x in range(81)] +[ (x*9)+9 for x in range(81)] :
print '|',
if i in [ 27, 54, 81]:
print '\n---------+----------+----------+'
elif i in [ (x*9) for x in range(81)]:
print '\n'
else:
if i in [ 27, 54, 81]:
print '\n------+-------+-------+'
elif i in [ (x*9) for x in range(81)]:
print '\n'
```
content_copyCOPY

Takes a partially filled in grid, inserts the min value in a cell (could be a random cell, in this case the first free cell). If the min value is not legal it will increment until the max value is reached (number 9), checking each time if the incremented value is legal in that cell (ie does not clash with any already entered cells in square, col or row). If it is legal, it will call itself (the hasSolution function) thus using this slightly more filled in grid to find a new cell and check which value is legal in this next cell. If no values are legal in the next cell, it will clear the previous grid entry and try incrementing the value. isLegal = does not conflict with any other numbers in the same row, column or square

http://code.activestate.com/recipes/578140-super-simple-sudoku-solver-in-python-source-code/