def generate_board():
    base = 3
    side = base * base
    def pattern(r,c): return (base * (r % base) + r // base + c) % (side)

    from random import sample
    def shuffle(s): return sample(s,len(s))

    rBase = range(base)
    rows  = [g * base + r for g in shuffle(rBase) for r in shuffle(rBase)]
    cols  = [g * base + c for g in shuffle(rBase) for c in shuffle(rBase)]
    nums  = shuffle(range(1,base * base + 1))
    #nums = range(1,base*base+1)
    board = [ [nums[pattern(r,c)] for c in cols] for r in rows ]

    squares = side * side
    empties = squares * 3 // 4
    for p in sample(range(squares), empties):
        board[p // side][p % side] = 0

    return board

def print_board(b):
    boardstr = ""
    for i in range(9):
        if i == 3 or i == 6:
            boardstr += "---------------------\n"
        for j in range(9):
            boardstr += str(b[i][j]) + " "
            if j == 8:
                boardstr += "\n"
            if j == 2 or j == 5:
                boardstr += "| "
    print(boardstr)

def is_valid_number(b, num, x, y):
    for i in range(9):
        if b[i][y] == num:
            return False
    for j in range(9):
        if b[x][j] == num:
            return False
    for i in range(3):
        for j in range(3):
            if b[(x // 3) * 3 + i][(y // 3) * 3 + j] == num:
                return False
    return True

def next_valid_position(b):
    for i in range(9):
        for j in range(9):
            if b[i][j] == 0:
                return (i, j)
    return True

def solve_board(b):
    if next_valid_position(b) != True:
        x, y = next_valid_position(b)

        for i in range(1, 10):
            if is_valid_number(b, i, x, y):
                board[x][y] = i
                solve_board(board)
        board[x][y] = 0
    else:
        print("Board solved!\n")
        print_board(board)
        return

print("Generating Board...\n")
board = generate_board()
print_board(board)
solve_board(board)