'''
This program solves sudoku.
The board is a list of lists. An empty cell is represented by zero.
The algoritm is a recursive backtracking, that tries to feel the cell with minimum
 number of available values.
'''

'''
Returns True iff it is legal to put x in board[r][c].
The function assumes that cell (r,c) is empty (board[r][c] == 0)
'''
def islegal(board, r, c, x):
    for i in range(len(board)): #This loop checks that no cell in the row r and col. c contains x 
        if board[r][i] == x or board[i][c] == x:
            return False
    '''
    Your code here.
    The code should check whether x is not assigned
     to any of the cells in the sub-board that contains cell (r,c) 
    '''
    return True

'''
Returns the number of values that can be assigned to board[r][c]
The function assumes that cell (r,c) is empty (board[r][c] == 0)
'''
def countlegal(board, r, c):
    count = 0
    '''
    Your code here.
    The code should run over all possible assignments
     to board[r][c] and counts (into the variable count)
     the number of legal assignments
    '''
    return count

'''
Returns the row and col. of the cell with minimum legal assignments
If all cells has a value, returns [-1,-1]
'''
def findmin(board):
    m = len(board) + 1 #The number of assignments to the cell with minimum possible assignments. Init. to a large number
    coor = [-1,-1]#The coordinates of the cell with minimum possible assignments.
    for r in range(len(board)): #Scanning all cells
        for c in range(len(board)):
            if board[r][c] == 0:#Is the cell empty?
                x = countlegal(board, r, c)
                '''
                Your code here.
                Update m and coor (if needed).
                '''
    return coor

'''
Prints the board
'''
def printboard(board):
    '''
    Your code here.
    This function prints the board.
    '''
    print()

'''
Solves the sudoku riddle using recursive backtracking.
If there is a solution to the given board, it returns True,
 and board contains the solution.
Otherwise it returns False, and board is unchanged 
'''
def solve(board):
    [r,c]  =findmin(board)#Finds the next cell to assign value to.
    if r == -1:#If all cells were assigned a value, the riddle is solved. 
        return True
    for i in range(1,len(board)+1):#i scans through all possible assignments
        if islegal(board, r, c, i):#If the assignment is legal:
            board[r][c] = i          #  Make the assignment.
            if solve(board):       #  Try to solve the new board
                return True
            board[r][c] = 0          #  Erase the assigment if it did not lead to a solution
    return False