solver.py

# 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')