"""
  how to run this:

             1: import thisfile as s
  optionally 2: s.grid = whatever initial puzzle you want to solve
     either 3a: s.print_grid() to see the unsolved puzzle rendered with unicode text
         or 3b: s.paint_grid() to see it drawn with tkinter graphics
             4: s.solve()
             5: s.print_grid() or s.paint_grid() again to see the solution
"""



import random
import tkinter as tk
import tkinter.font as tkf

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 badgrid():
  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():
  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 = "")

win = None
fon = None

def paint_grid():
  global win, fon
  size = 20
  cellsize = 2 * size
  edge = cellsize // 2
  whole = cellsize * 10
  if not win:
    win = tk.Tk()
  if not fon:
    fon = tkf.Font(family = "times new roman", size = size, weight = "bold")
  can = tk.Canvas(win, width = whole, height = whole, background = "white")
  can.pack()
  for (r, c) in ((0, 0), (0, 6), (3, 3), (6, 0), (6, 6)):
    can.create_rectangle(edge + r * cellsize,       edge + c * cellsize,
                         edge + (r + 3) * cellsize, edge + (c + 3) * cellsize,
                         fill = "#E0E0E0")
  for r in range(0, 10, 1):
    if r % 3 != 0:
      can.create_line(edge,             edge + r * cellsize, 
                      whole - edge + 2, edge + r * cellsize,
                      width = 2, fill = "#C0C0C0")
  for c in range(0, 10, 1):
    if c % 3 != 0:
      can.create_line(edge + c * cellsize, edge,
                      edge + c * cellsize, whole - edge,
                      width = 2, fill = "#C0C0C0")
  for r in range(0, 10, 3):
    can.create_line(edge - 1,         edge + r * cellsize, 
                    whole - edge + 2, edge + r * cellsize, 
                    width = 3, fill = "black")
  for c in range(0, 10, 3):
    can.create_line(edge + c * cellsize, edge, 
                    edge + c * cellsize, whole - edge, 
                    width = 3, fill = "black")
  for r in range(0, 9):
    for c in range(0, 9):
      if grid[r][c] != 0:
        can.create_text(edge + cellsize // 2 + cellsize * c, edge + cellsize // 2 + cellsize * r,
                        text = str(grid[r][c]), anchor = "center", fill = "black", font = fon)

def ok(row, col, number):
  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(row, col):
  if col == 9:
    col = 0
    row += 1
    if row == 9:
      return True
  if grid[row][col] != 0:
    return solve_from(row, col + 1)
  for number in range(1, 10):
    if ok(row, col, number):
      grid[row][col] = number
      if solve_from(row, col + 1):
        return True
      grid[row][col] = 0
  return False

def solve():
  return solve_from(0, 0)