Flying memes

Following from my previous post I’ve explored with an algorithm to create Sudokus by iterating from an empty grid by adding valid numbers to random cells and then invoking the solving function twice, once navigating the solution space from 1 to 9 and the other in reverse. If both solving functions return the same, valid, grid then that’s the solution.

from pprint import pprint
from math import floor
from copy import deepcopy
from itertools import chain 
from random import shuffle

def solve(src_grid, range_dir):
  grid = deepcopy(src_grid)
  original_grid = deepcopy(src_grid)

  p = 0
  cycle = 0
  dir = 1

  while(p < 81 and p >= 0 and cycle < 1000000):
    cycle = cycle + 1
    x = floor(p / 9)
    y = p % 9
    if original_grid[x][y] != 0:
      p = p + dir
      continue
    candidates = list(filter(getFilter(range_dir, grid[x][y]), getCandidates(grid, x, y)))
    if range_dir == -1:
      candidates.reverse()
    prev_val = grid[x][y]
    if len(candidates) > 0:
      grid[x][y] = candidates[0]
    if grid[x][y] == prev_val:
      grid[x][y] = 0
      dir = -1
    else:
      dir = 1
    p = p + dir
  return grid

def getCandidates(grid, x, y):
  candidates = []
  col = [grid[r][y] for r in range(9)]
  sqr_x = floor(x / 3) * 3
  sqr_y = floor(y / 3) * 3
  sqr = [grid[sqr_x + floor(i/3)][sqr_y + (i % 3)] for i in range(9)]
  for t in range(1, 10):
    if t not in grid[x] and t not in col and t not in sqr:
      candidates.append(t)
  return candidates

def getFilter(range_dir, element):
  if range_dir == 1:
    return lambda n: n > element
  else:
    target = element if element > 0 else 10
    return lambda n: n < target

def fetchFromFile(path):
  grid = []
  content = None

  with open(path, 'r') as file:
      content = file.read().replace("\n", " ").split(" ")

  for row in range(9):
    grid.append([])
    for col in range(9):
      grid[row].append(int(content[row*9+col]))
  
  return grid

# to create
grid = []
for row in range(9):
  grid.append([])
  for col in range(9):
    grid[row].append(0)

cycle = 0
same = False
slots = [[x,y] for x in range(0,9) for y in range(0,9)]
shuffle(slots)
digits = 0

while (same is False and cycle < 100):
  cycle = cycle + 1
  x,y = slots.pop(1)
  candidaes = getCandidates(grid, x, y)
  shuffle(candidaes)
  grid[x][y] = candidaes[0]
  grid_f = list(chain.from_iterable(grid))
  solve_d = list(chain.from_iterable(solve(grid, 1)))
  solve_r = list(chain.from_iterable(solve(grid, -1)))
  same = solve_d == solve_r
  unsolvable = solve_d == grid_f or 0 in solve_d
  if unsolvable:
    same = False
    grid[x][y] = 0
    slots.append([x, y])
  else:
    digits = digits + 1

if same:
  pprint(grid)
else:
  pprint("No solutions found")

Running the above returns a valid Sudoku puzzle to be solved:

[[0, 6, 0, 0, 0, 8, 0, 3, 4],
 [8, 5, 0, 0, 0, 0, 7, 9, 0],
 [4, 7, 0, 0, 0, 0, 8, 1, 2],
 [0, 0, 0, 7, 0, 0, 4, 0, 0],
 [7, 0, 5, 0, 8, 0, 9, 0, 0],
 [0, 0, 0, 5, 1, 0, 2, 0, 0],
 [2, 0, 7, 0, 0, 0, 1, 0, 5],
 [0, 3, 0, 0, 2, 7, 0, 0, 9],
 [6, 0, 1, 0, 9, 0, 0, 2, 0]]