import time
from random import shuffle, sample

size = 9
block_size = 3
wanted = set([x for x in range(1, size + 1)])


def create_board():
    """ Create a board using the following method:
        1. create a row (0-9) and shuffle it
        2. Copy and shift the row to the left
        3. cycle through all shifts, appending each new row.
        4. return valid sudoku board.
    """
    shifts = [0, 3, 3, 1, 3, 3, 1, 3, 3]
    row = [x for x in range(1, size + 1)]
    shuffle(row)
    board = []
    for step in shifts:
        row = rotate(row, step)
        board.append(row)
    return board


def rotate(l, n):
    """ Return a list that was rotated by N steps. Positive N rotates left. """
    n = n % len(l)
    return l[n:] + l[:n]

def depopulate(board):
    """Remove a percentage values from a boardto make the Sudoku puzzle."""
    for x, y in get_index_samples(percent=0.6):
        board[x][y] = 0


def get_index_samples(percent):
    """ Get some percentage of X, Y positions in the board"""
    indexes = [(x, y) for x in range(size) for y in range(size)]
    samples = sample(indexes, k=int(percent * (size * size)))
    return samples

def blocks(board):
    """ Yields each block (3x3 grid) from the board for validation. """
    # iterate in 3x3 blocks starting @ 0,3,6 in the x & y
    for x, y in ((x, y)
                 for y in range(0, size, block_size)
                 for x in range(0, size, block_size)):
        yield [board[by][bx]
               for by in range(y, y + block_size)
               for bx in range(x, x + block_size)]


def is_solved(board):
    """ Returns True if board is a valid Sudoku solution. """
    # check rows have 1-9
    for row in board:
        if wanted != set(row):
            return False
    # zip subarrays to make columns and check also
    for col in zip(*board):
        if wanted != set(col):
            return False
    # check the 3x3 blocks to ensure they are also good.
    for block in blocks(board):
        if wanted != set(block):
            return False
    # its a valid solution!
    return True


def get_positions(board):
    """ Return a list of tuples of open positions on a board. """
    open_positions = []
    for x in range(len(board)):
        for y in range(len(board[x])):
            if board[x][y] == 0:
                open_positions.append((x, y))
    return open_positions


def get_row_set(board, position):
    """ Return a unique set of all used values in a row"""
    x, y = position
    return set([num for num in board[x] if num != 0])


def get_col_set(board, position):
    """ Return a unique set of all used values in a column"""
    x, y = position
    return set([row[y] for row in board if row[y] != 0])


def get_block_set(board, position):
    """ Return a unique set of all used values in a 3x3 block"""
    x, y = position
    block_x, block_y = (int(x / block_size), int(y / block_size))
    start_x = block_size * block_x
    start_y = block_size * block_y
    block = [board[x][y]
             for y in range(start_y, start_y + block_size)
             for x in range(start_x, start_x + block_size)
             if board[x][y] != 0]
    return set(block)


def choices(board, position):
    """ Combine the sets of used values at a position
     and return unused numbers as a list. """
    available = set([x for x in range(1, size + 1)])
    row_set = get_row_set(board, position)
    col_set = get_col_set(board, position)
    block_set = get_block_set(board, position)
    return list(available.difference(row_set.union(col_set).union(block_set)))


def solve(board):
    """ Recursive Sudoku solve with backtracking. """
    positions = get_positions(board)
    if len(positions) is 0:
        return True  # base case, solved all positions
    for position in positions:
        # get possibilities for position
        available_choices = choices(board, position)
        for choice in available_choices:
            # set board[x,y] == choice
            x, y = position
            board[x][y] = choice
            if solve(board):
                return True
            # backtrack: unset position
            board[x][y] = 0
        return False  # tried all choices, none fit


if __name__ == '__main__':
    # rank 11 sudoku puzzle.
    # board = [
    #     [8, 0, 0, 0, 0, 0, 0, 0, 0],
    #     [0, 0, 3, 6, 0, 0, 0, 0, 0],
    #     [0, 7, 0, 0, 9, 0, 2, 0, 0],
    #     [0, 5, 0, 0, 0, 7, 0, 0, 0],
    #     [0, 0, 0, 0, 4, 5, 7, 0, 0],
    #     [0, 0, 0, 1, 0, 0, 0, 3, 0],
    #     [0, 0, 1, 0, 0, 0, 0, 6, 8],
    #     [0, 0, 8, 5, 0, 0, 0, 1, 0],
    #     [0, 9, 0, 0, 0, 0, 4, 0, 0]
    # ]
    board = create_board()
    print("Board is: ")
    for row in board:
        print(row)
    depopulate(board)
    print("Puzzle is: ")
    for row in board:
        print(row)
    print("Solving..")
    solve(board)
    print("Solved: {}".format(is_solved(board)))
    print("Time: {}".format(time.process_time()))
    for row in board:
        print(row)