import random
import itertools
from copy import deepcopy

def make_board(m = 3):
 numbers = list(range(1, m**2 + 1))
 board = None

 while board is None:
 board = attempt_board(m, numbers)
 return board

def attempt_board(m, numbers):
 n = m**2
 board = [[None for _ in range(n)] for _ in range(n)]
 for i, j in itertools.product(range(n), repeat = 2):
 i0, j0 = i - i % m, j - j % m
 random.shuffle(numbers)
 for x in numbers:
  if(x not in board[i]) and all(row[j] != x for row in board) and all(x not in row[j0:j0+m] for row in board[i0:i]):
  board[i][j] = x
  break
 else:
  return None
 return board

def print_board(board, m = 3):
 numbers = list(range(1, m**2 + 1))
 omit = 5
 challange = deepcopy(board)
 for i, j in itertools.product(range(omit), range(m ** 2)):
 x = random.choice(numbers) - 1
 challange[x][j] = None
 spacer = "++---+---+---++---+---+---++---+---+---++"
 print (spacer.replace('-', '='))
 for i, line in enumerate(challange):
 print("|| {0} | {1} | {2} || {3} | {4} | {5} || {6} | {7} | {8} ||".format(*(cell or ' ' for cell in line)))
 if(i + 1) % 3 == 0:
  print(spacer.replace('-', '='))
 else:
  print(spacer)
 return challange

def print_answer(board):
 spacer = "++---+---+---++---+---+---++---+---+---++"
 print(spacer.replace('-','='))
 for i, line in enumerate(board):
 print("|| {0} | {1} | {2} || {3} | {4} | {5} || {6} | {7} | {8} ||".format(*(cell or ' ' for cell in line)))
 if(i + 1) % 3 == 0:
  print(spacer.replace('-','='))
 else:
  print(spacer)

def is_full(challange, m = 3):
 for i, j in itertools.product(range(m**2), repeat = 2):
 if challange[i][j] is None:
  return False
 return True

def cal_candidate(challange, x, y, m = 3):
 candidate = range(1, m ** 2 + 1)
 for i in range(m ** 2):
 if challange[x][i] in candidate:
  candidate.remove(challange[x][i])
 if challange[i][y] in candidate:
  candidate.remove(challange[i][y])
 for i, j in itertools.product(range(m), repeat = 2):
 x0, y0 = x - x % m, y - y % m
 if challange[x0 + i][y0 + j] in candidate:
  candidate.remove(challange[x0 + i][y0 + j])
 return candidate

def least_candidate(challange, m = 3):
 least, x, y = m ** 2, -1, -1
 for i, j in itertools.product(range(m ** 2), repeat = 2):
 if not challange[i][j]:
  num = len(cal_candidate(challange, i, j))
  if num < least:
  least = num
  x, y = i, j
 return x, y

def solving_soduku(challange, m = 3):
 if is_full(challange):
 return challange
 x, y = least_candidate(challange)
 id = x * (m ** 2) + y
 result = try_candidate(challange, id)
 return result

def try_candidate(challange, id, m = 3):
 if is_full(challange):
 return challange
 x = id / (m ** 2)
 y = id % (m ** 2)
 while challange[x][y]:
 id = (id + 1) % m ** 4
 x = id / (m ** 2)
 y = id % (m ** 2)
 candidate = cal_candidate(challange, x, y)
 if len(candidate) == 0:
 return False
 for i in range(len(candidate)):
 challange[x][y] = candidate[i]
 result_r = try_candidate(challange, (id + 1) % m ** 4)
 if not result_r:
  pass
 else:
  return challange
 challange[x][y] = None
 return False


#Board = make_board()
#print Board
#challange = print_board(Board)
#print_answer(Board)

#result = solving_soduku(challange) 
#print_answer(result) 


testing = [[8, None, None, None, None, None, None, None, None],
   [None, None, 3, 6, None, None, None, None, None],
   [None, 7, None, None, 9, None, 2, None, None],
   [None,5 , None, None, None, 7, None, None, None ],
   [None, None, None, None, 4, 6, 7, None, None],
   [None, None, None, 1, None, None, None, 3, None],
   [None, None, 1, None, None, None, None, 6, 8],
   [None, None, 8, 5, None, None, None, 1, None],
   [None, 9, None, None, None, None, 4, None, None]]
result = solving_soduku(testing)
print_answer(result)