import random

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

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

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

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

grid = grid1

def bad_grid():
  choices = [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
  g = [ ]
  for r in range(0, 9):
    g.append([ 0 ] * 9)
    for c in range(0, 9):
      g[r][c] = random.choice(choices)
  return g

def print_grid():
  global grid
  toppart = "\u2501\u252f\u2501\u252f\u2501"
  bigmidpart = "\u2501\u253f\u2501\u253f\u2501"
  midpart = "\u2500\u253c\u2500\u253c\u2500"
  botpart = "\u2501\u2537\u2501\u2537\u2501"
  print("\u250f", toppart, "\u2533", toppart, "\u2533", toppart, "\u2513", sep = "")
  for r in range(0, 9):
    print("\u2503", end = "")
    for c in range(0, 9):
      s = grid[r][c]
      if s == 0:
        s = " "
      print(s, end = "")
      if c % 3 == 2:
        print("\u2503", end = "")
      else:
        print("\u2502", end = "")
    print()
    if r == 2 or r == 5:
      print("\u2523", bigmidpart, "\u254b", bigmidpart, "\u254b", bigmidpart, "\u252b", sep = "")
    elif r < 8:
      print("\u2520", midpart, "\u2542", midpart, "\u2542", midpart, "\u2528", sep = "")
  print("\u2517", botpart, "\u253b", botpart, "\u253b", botpart, "\u251b", sep = "")

def ok(row, col, number):
  global grid
  for c in range(0, 9):
    if grid[row][c] == number:
      return False
  for r in range(0, 9):
    if grid[r][col] == number:
      return False
  baserow = row // 3 * 3
  basecol = col // 3 * 3
  for r in range(0, 3):
    for c in range(0, 3):
      if grid[baserow + r][basecol + c] == number:
        return False
  return True

  def solve_from():                 |  def solve():
    global grid                     |    global grid
    r = 0                           |    r = 0
    c = 0                           |    c = 0
    n = 1                           |    n = 1
    s = []                          |    s = []
    while r < 9:                    |    while r < 9:
      if c > 8:                     |      if c > 8:
        c = 0                       |        c = 0
        r += 1                      |        r += 1
 +                                  +        n = 1                     +
        continue                    |        continue
      if grid[r][c] != 0:           |      if grid[r][c] == 0:
        c += 1                      |        c += 1
 +                                  +        n = 1                     +
        continue                    |        continue
      if n > 9:                     |      if n > 9:
        if len(s) == 0:             |        if len(s) == 0:
          return False              |          return False
        (r, c, n) = s.pop()         |        (r, c, n) = s.pop()
        grid[r][c] = 0              |        grid[r][c] = 0
        n += 1                      |        n += 1
        continue                    |        continue
      if not ok(r, c, n):           |      if not ok(r, c, n):
        n += 1                      |        n += 1
      else:                         |      else:
        s.append((r, c, n))         |        s.append((r, c, n))
        grid[r][c] = n              |        grid[r][c] = n
        c += 1                      |        c += 1
 +                                  +        n = 1                     +
    return True                     |    return True