Created
June 1, 2021 04:02
-
-
Save Gosev/ce3defb6415b67ec03f48fa11fc158f0 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# sudoku solver using backtracking / recursion | |
import os | |
import sys | |
import glob | |
import json | |
import re | |
import math | |
import copy | |
def readFile(path): | |
f = open(path, "r") | |
grid = [] | |
for x in f: | |
itms = x.replace('\r\n', '').replace('\n', '').replace('space', '0').split(',') | |
grid.append(list(map(lambda x: int(x), itms))) | |
return grid | |
def getPossibilities(grid, i,j): | |
# find all the possibilities | |
if not grid[i][j] == 0: | |
return [grid[i][j]] | |
exists = [] | |
# find what items can be placed here | |
for k in range(0,9): | |
# what are the items with the same first index | |
lineval = grid[i][k] | |
if lineval not in exists and not lineval == 0: | |
exists.append(lineval) | |
# what are the items with the same second index | |
colval = grid[k][j] | |
if colval not in exists and not colval == 0: | |
exists.append(colval) | |
# what are the items in the same square | |
sq_col = math.floor(i/3) * 3 | |
sq_line = math.floor(j/3) * 3 | |
for k in range(0,3): | |
for k2 in range(0,3): | |
line = sq_line + k | |
col = sq_col + k2 | |
val = grid[col][line] | |
if val not in exists and not val== 0: | |
exists.append(val) | |
available = [] | |
for i in range(1,10): | |
if i not in exists: | |
available.append(i) | |
return available | |
def printGrid(in_grid): | |
for i in range(0,9): | |
print("[", ", ".join(map(lambda x: str(x), in_grid[i])), "],") | |
def simpleSolve(in_grid): | |
grid = copy.deepcopy(in_grid) | |
found = True | |
zeroCount = 1 | |
while found and zeroCount > 0: | |
zeroCount = 0 | |
found = False | |
for i in range(0,9): | |
for j in range(0,9): | |
if grid[i][j] == 0: | |
zeroCount = zeroCount + 1 | |
poss = getPossibilities(grid, i,j) | |
if (len(poss) == 0): | |
raise ValueError("Error at {},{} : 0 possibilities".format(i,j)) | |
if (len(poss) == 1): | |
found = True | |
grid[i][j] = poss[0] | |
return grid, zeroCount | |
def getLowestOptions(grid): | |
lowest = { | |
"i": -1, | |
"j": -1, | |
"poss": [1,2,3,4,5,6,7,8,9,10] | |
} | |
for i in range(0,9): | |
for j in range(0,9): | |
if grid[i][j] == 0: | |
poss = getPossibilities(grid, i,j) | |
if len(poss) < len(lowest["poss"]): | |
lowest = { | |
"i" : i, | |
"j" : j, | |
"poss": poss | |
} | |
return lowest | |
def solveGrid(in_grid, depth): | |
grid = copy.deepcopy(in_grid) | |
grid, zerocount = simpleSolve(grid) | |
solutions = [] | |
if zerocount == 0: | |
solutions = [grid] | |
return solutions | |
else: | |
options = getLowestOptions(grid) | |
for itm in options["poss"]: | |
leaf = copy.deepcopy(grid) | |
leaf[options["i"]][options["j"]] = itm | |
try: | |
solutions += solveGrid(leaf, depth + 1) | |
except ValueError: | |
# invalid option so ignore | |
pass | |
if (len(solutions) > 1): | |
raise Exception("Error : more than one possibiliy") | |
if depth == 0: | |
if len(solutions) == 0: | |
raise Exception("No solution found") | |
# printGrid(node["solutions"][0]) | |
return solutions | |
def check_grids(folder = 'textdownloads', difficulty= 'easy', max_page = 900): | |
print('in check nb') | |
folderlength = len(folder) | |
itm = './{}/sudoku_{}_*.txt'.format(folder, difficulty) | |
base = './{}/sudoku_{}_'.format(folder, difficulty) | |
files = glob.glob(itm) | |
count = 0 | |
subcount = -1 | |
book = [] | |
solvedNb = 0 | |
unsolved = 0 | |
filenb = 0 | |
for file in files: | |
filenb = filenb + 1 | |
nb = file[len(base): -4] | |
grid = readFile(file) | |
# puzz, zero = simpleSolve(grid, nb == "242081") | |
ret = solveGrid(grid, 0) | |
if (len(ret) == 1): | |
solvedNb = solvedNb + 1 | |
else: | |
unsolved = unsolved + 1 | |
print(len(ret), "solutions found") | |
print(solvedNb, unsolved, (100*solvedNb)/(solvedNb+unsolved),"%", filenb) | |
check_grids() | |
grid = [ | |
[ 1, 0, 0, 0, 0, 0, 0, 0, 6 ], | |
[ 0, 2, 0, 0, 0, 0, 0, 5, 0 ], | |
[ 0, 0, 3, 0, 0, 0, 4, 0, 0 ], | |
[ 0, 0, 0, 0, 7, 0, 0, 0, 0 ], | |
[ 9, 8, 7, 0, 5, 0, 3, 2, 1 ], | |
[ 0, 0, 0, 0, 9, 0, 0, 0, 0 ], | |
[ 0, 0, 4, 0, 3, 0, 7, 0, 0 ], | |
[ 0, 5, 0, 0, 2, 0, 0, 8, 0 ], | |
[ 6, 0, 0, 0, 1, 0, 0, 0, 9 ]] | |
# printGrid(grid) | |
ret = solveGrid(grid, 0) | |
#print (len(ret["solutions"]), 'solutions found') |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment