Flying memes

Just a small practice exercise that solves Sudoku by iterating over valid values for each cell and backtracking on errors. I like how compact the solution is, although probably not very performant.

from pprint import pprint
from math import floor
from copy import deepcopy

grid = []
content = None

with open('startgrid.txt', '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]))

original_grid = deepcopy(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
  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(max(1, grid[x][y]), 11):
    if t not in grid[x] and t not in col and t not in sqr:
      grid[x][y] = t
      break
  if grid[x][y] == 0 or grid[x][y] == 10:
    grid[x][y] = 0
    dir = -1
  else:
    dir = 1
  p = p + dir

pprint([cycle, grid])

The input file, containing the puzzle to be solved, looks like this:

0 0 0 0 7 0 2 0 0
0 0 3 0 9 0 1 0 0
1 5 0 0 0 0 0 3 0
0 0 0 5 0 0 0 0 0
3 7 0 0 2 0 0 9 5
0 0 0 0 0 9 0 0 0
0 4 0 0 0 0 0 2 8
0 0 6 0 8 0 4 0 0
0 0 2 0 3 0 0 0 0

And the script outputs the solution alongside the number of iterations required:

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