import numpy as np

limit = 10000
backtracks = 0
generate_pair_flag = False


def makeRandomSudoku(number_of_randoms):
    # generates a random board with no constraints
    # board has number_of_randoms filled in values with all other values as zero
    grid_list = [0] * 81
    locations = np.random.choice(81, number_of_randoms, replace=False)
    for location in locations:
        grid_list[location] = int(np.random.randint(1, high=10))

    i = 0
    grid = []
    while i < len(grid_list):
        grid.append(grid_list[i:i + 9])
        i += 9
    return grid


def findNextCellToFill(grid):
    # Takes a 9 by 9 grid and looks row by column for the first zero.
    # Returns either x, y coordinates of first '0' or -1, -1
    for x in range(0, 9):
        for y in range(0, 9):
            if grid[x][y] == 0:
                return x, y
    return -1, -1


def isValid(grid, i, j, e):
    # takes a 9 by 9 grid; i,j coordinates; and a number 'e' then looks row-wise, column-wise, and sector-wise for duplicates of the number 'e''
    # returns True if passes row/column/sector checks.
    # returns False otherwise
    rowOk = all([e != grid[i][x] for x in range(9)])
    if rowOk:
        columnOk = all([e != grid[x][j] for x in range(9)])
        if columnOk:
            # find the top left x, y coordinate of section containing the i,j cell
            secTopX, secTopY = 3*(i//3), 3*(j//3)
            for x in range(secTopX, secTopX+3):
                for y in range(secTopY, secTopY+3):
                    if grid[x][y] == e:
                        return False
            return True
    return False


# In[7]:



def solveSudoku(grid, i=0, j=0):
    # fills in missing squares of Sudoku puzzle using rules with a brute-force guess/check
    # takes a grid and starts looking in the top left corner i,j = 0,0
    global limit
    global backtracks
    if backtracks < limit:
        i, j = findNextCellToFill(grid)
        if i == -1:
            # we solved it or there's nothing left to solve
            return True

        for e in range (1, 10):
            # try different values in i, j location
            if isValid(grid, i, j, e):
                grid[i][j] = e
                if solveSudoku(grid, i, j):
                    return True

                # undo current cell for backtracking
                if backtracks < limit:
                    backtracks += 1
                    grid[i][j] = 0
        else:
            # loop fell through without filling a number
            return False



    else:
        return False
        


def printSudoku(grid):
    numrow = 0
    for row in grid:
        if numrow % 3 == 0 and numrow != 0:
            print(' ')
        print(row[0:3], ' ', row[3:6], ' ', row[6:9])
        numrow += 1
    return

def generate_pair():
    global backtracks
    backtracks = 0
    # generates an unsolved and solved grid
    solved = makeRandomSudoku(10)
    unsolved = solved.copy()
    if solveSudoku(solved):
        return unsolved, solved
    else:
        backtracks = 0
        return generate_pair()


# asdf = makeRandomSudoku(5)
# printSudoku(asdf)
# asdf1 = asdf[:][:]
# print("\n")
# solveSudoku(asdf1)
# printSudoku(asdf1)
# print("\n")
# printSudoku(asdf)


asdf1, asdf2 = generate_pair()
print(asdf1)
print(asdf2)