#!/usr/bin/python
# -*- coding: iso-8859-15 -*-

import sys
import math
from random import randint, shuffle

if (len(sys.argv) != 3):
  print('Usage: generate.py block-size difficulty')
  print('block-size: [2x2|3x2|3x3]')
  print('difficulty: [easy|medium|hard]')
  exit()

blocksize, difficulty = sys.argv[1], sys.argv[2]

if not blocksize in ['2x2', '3x2', '3x3']:
  print('wrong size given')
  exit()

splitted_blocksize = blocksize.split('x')
size_horizontal = int(splitted_blocksize[0])
size_vertical = int(splitted_blocksize[1])

boardSize = size_horizontal * size_vertical

if not difficulty in ['easy', 'medium', 'hard']:
  print('wrong difficulty given')
  exit()

############################################################################

# medium -> 5 (default) ; easy -> 1 ; hard -> 5
difficultyLevel = 5;
if difficulty == 'easy':
   difficultyLevel = 1
if difficulty == 'hard':
   difficultyLevel = 10

# draw grid (array style)
def drawGrid(grid):
  gridVerticalSize = len(grid)
  gridHorizontalSize = len(grid[0])
  horizontalLineLength = ((size_horizontal + 1) * size_vertical) + 1

  for row in range(gridHorizontalSize):
    if ((row % size_vertical) == 0):
      sys.stdout.write(('═' * horizontalLineLength) + '\n')
    for col in range(gridVerticalSize):
      if ((col % size_horizontal) == 0):
        sys.stdout.write('║')
      if grid[row][col] != 0:
        sys.stdout.write(str(grid[row][col]))
      else:
        sys.stdout.write(' ')
    sys.stdout.write('║\n')
  sys.stdout.write(('═' * horizontalLineLength) + '\n')
  sys.stdout.write('\n')

# draw grid (inline style)
def drawGridInline(grid):
  for row in range(len(grid)):
    for col in range(len(grid[row])):
      sys.stdout.write(str(grid[row][col]))
  sys.stdout.write('\n')

#initialise empty grid
def generateEmptyGrid(boardSize):
  emptyGrid = []
  for row in range(boardSize):
    emptyGrid.append([])
    for col in range(boardSize):
      emptyGrid[row].append(0)
  return emptyGrid

#A check if the grid is full
def checkFullyCompletedGrid(grid):
  for row in range(len(grid)):
    for col in range(len(grid[row])):
      if grid[row][col] == 0:
        return False
  return True

# (deep) copy of grid
def copyGrid(grid):
  copiedGrid = []
  for row in range(len(grid)):
     copiedGrid.append([])
     for col in range(len(grid[row])):
        copiedGrid[row].append(grid[row][col])
  return copiedGrid

#A backtracking/recursive function to check all possible combinations of numbers until a solution is found
def solveGrid(grid):
  gridSize = len(grid)
  cellsCount = len(grid) * len(grid[0])
  numberList = [(value + 1) for value in range(gridSize)]

  global solutionsCount

  #Find next empty cell
  for i in range(0, cellsCount):
    row = i // gridSize
    col = i % gridSize
    if grid[row][col] == 0:
      shuffle(numberList)
      for value in numberList:
        #Check that this value has not already be used on this row
        if not(value in grid[row]):
          #Check that this value has not already be used on this column
          foundInColumn = False
          for r in range(0, gridSize):
            if (value == grid[r][col]):
              foundInColumn = True

          if not foundInColumn:
            # Get sub-square
            blockColFrom = size_horizontal * int(col / size_horizontal)
            blockRowFrom = size_vertical * int(row / size_vertical)
            square = [grid[i][blockColFrom:blockColFrom + size_horizontal] for i in range(blockRowFrom, blockRowFrom + size_vertical)]

            #Check that this value has not already be used on this sub square
            if not any(value in squareLine for squareLine in square):
              grid[row][col] = value
              if checkFullyCompletedGrid(grid):
                solutionsCount += 1
                break
              else:
                if solveGrid(grid):
                  return True
      break
  grid[row][col] = 0

#A backtracking/recursive function to check all possible combinations of numbers until a solution is found
def fillGrid(grid):
  boardSize = len(grid)
  cellsCount = len(grid) * len(grid[0])
  numberList = [(value + 1) for value in range(boardSize)]

  global solutionsCount

  #Find next empty cell
  for i in range(0, cellsCount):
    row = i // boardSize
    col = i % boardSize
    if grid[row][col] == 0:
      shuffle(numberList)
      for value in numberList:
        #Check that this value has not already be used on this row
        if not(value in grid[row]):
          #Check that this value has not already be used on this column
          foundInColumn = False
          for r in range(0, boardSize):
            if (value == grid[r][col]):
              foundInColumn = True

          if not foundInColumn:
            # Get sub-square
            blockColFrom = size_horizontal * int(col / size_horizontal)
            blockRowFrom = size_vertical * int(row / size_vertical)
            square = [grid[i][blockColFrom:blockColFrom + size_horizontal] for i in range(blockRowFrom, blockRowFrom + size_vertical)]

            #Check that this value has not already be used on this sub square
            if not any(value in squareLine for squareLine in square):
              grid[row][col] = value
              if checkFullyCompletedGrid(grid):
                return True
              else:
                if fillGrid(grid):
                  return True
      break
  grid[row][col] = 0

solutionsCount = 1
def computeResolvableGrid(grid, wantedAttempts):
  global solutionsCount

  # A higher number of attempts will end up removing more numbers from the grid
  # Potentially resulting in more difficiult grids to solve!

  # Start Removing Numbers one by one
  attempts = wantedAttempts
  while attempts > 0:
    # Select a random cell that is not already empty
    row = randint(0, boardSize - 1)
    col = randint(0, boardSize - 1)
    while grid[row][col] == 0:
      row = randint(0, boardSize - 1)
      col = randint(0, boardSize - 1)

    # Remove value in this random cell
    savedCellValue = grid[row][col]
    grid[row][col] = 0

    solutionsCount = 0
    solveGrid(copyGrid(grid))

    # Non unique solution => restore this cell value
    if solutionsCount != 1:
      grid[row][col] = savedCellValue
      attempts -= 1

grid = generateEmptyGrid(boardSize)

sys.stdout.write('Solved grid:\n')
fillGrid(grid)
drawGrid(grid)

computeResolvableGrid(grid, difficultyLevel)

sys.stdout.write('Generated grid:\n')
drawGrid(grid)

sys.stdout.write('Inline grid:\n')
drawGridInline(grid)