<jupyter_start><jupyter_text>Alguns testes para as funçoes<jupyter_code>### Solver Functions ###
# <NAME>

def num_moves(sudoku):
    'returns the maximum number of moves to do on the current sudoku / Counting the zeroes(empty squares)'
    moves = 0
    for line in sudoku:
        moves += list(line).count(0)
    return moves
null_sudoku  = [[0,0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0,0]]

null_sol =     [[1,2,3,4,5,6,7,8,9],
                [4,5,6,7,8,9,1,2,3],
                [7,8,9,1,2,3,4,5,6],
                [2,3,1,6,7,4,8,9,5],
                [8,7,5,9,1,2,3,6,4],
                [6,9,4,5,3,8,2,1,7],
                [3,1,7,2,6,5,9,4,8],
                [5,4,2,8,9,7,6,3,1],
                [9,6,8,3,4,1,5,7,2]]
assert(num_moves(null_sudoku) == 81)
assert(num_moves(null_sol)    == 0)
def all_moves():
    'generates a list with all the possible moves of every square of the board' 

    ans = [[1,2,3,4,5,6,7,8,9] for _ in range(81)]
    return ans

def available_moves(sudoku):
    'returns the available guess_list of every square'

    guess_list = all_moves()
 
    for i in range(9):
        for j in range(9):
            if (not (sudoku[i][j])) == False:
                numago = sudoku[i][j]
                guess_list[(9*i + j)] = []
                
                for k in range(9):
                    if numago in guess_list[9*i +k]:
                        guess_list[(9*i + k)].remove(numago)  #remove da linha
                    if numago in guess_list[(9*k + j)]:
                        guess_list[(9*k + j)].remove(numago)  #remove da coluna
                        
                a,b = (i//3)*3,(j//3)*3
                
                for m in range(a,a+3):
                    for n in range(b,b+3):
                        if numago in guess_list[9*m+n]:
                            guess_list[(9*m+n)].remove(numago)
    return guess_list
%timeit all_moves()
assert(len(all_moves()) == 81)
assert(len(sum(available_moves(null_sol),[])) == 0)
def next_move(guess_list):
    'returns a list with the next moves, and its indexes (q,r)'
    
    if sum(map(sum,guess_list)) == 0: # no more available guesses >.<
        return [],None,None
    minmoves = 10
    idxmin = None
    for (i,move) in enumerate(guess_list):
        l = len(move)
        if 0 < l and l < minmoves:
            idxmin = i
            minmoves = l
            if l == 1:
                break
    q,r = divmod(idxmin,9)
    return guess_list[idxmin],q,r


def next_branch(branch,move,q,r):

    'returns the next branch to try (left to right)'
    if move == 0:
        #print(move,q,r,'wut')
        return -1 # error code
    j = branch.count([q,r])
    if j >= len(move):
        return 0
    return [move[j]]  # starts from the *left* of the list

def refresh_guess_list(move,q,r,guess_list):
    'given a move on the [q][r] square, refreshes the guess_list'
    new_guess_list        = guess_list
    new_guess_list[9*q+r] = []
    k = 9*q
    l = 9*(q//3)*3 + (r//3)*3
    mmm = move[0]
    for i in range(9):
        if mmm in new_guess_list[r+9*i]:
            new_guess_list[r+9*i].remove(mmm)  # remove da coluna
        if mmm in new_guess_list[k+i]:
            new_guess_list[k+i].remove(mmm)   # remove da linha

    for m in range(3):
        for n in range(3):
            if mmm in new_guess_list[l + m+9*n ]:
                new_guess_list[l + m+9*n ].remove(mmm)

    return new_guess_list

def copy_GL(guess_list):
    return [l[:] for l in guess_list]

def check_line(n,guess_list):
    'returns the n_th line in the guess_list (n from 0 to 8)'
    nth_line = guess_list[n*9:9*(n+1)]
    idxs = range(9*n,9*(n+1))
    return nth_line,idxs

def check_col(n,guess_list):
    'returns the n_th column in the guess_list (n from 0 to 8)'
    col_idxs = [(l*9)+n for l in range(9)]
    nth_column  = [guess_list[i] for i in col_idxs]
    
    return nth_column,col_idxs

def check_box(n,guess_list):
    'returns the n_th box in the guess_list (n from 0 to 8)'
    #code gore  basically math to get the right indexes from the boxes
    if n < 3:
        nth_box = guess_list[n*3:(n+1)*3] + guess_list[n*3 + 9:(n+1)*3 + 9] + guess_list[n*3 + 18:(n+1)*3 + 18]
        idxs = [n*3,3*n+1,3*n+2,n*3 + 9,n*3 + 10,n*3 + 11,n*3 + 18,n*3 + 19,n*3 + 20]
    elif n < 6:
        nth_box = guess_list[27+(n%3)*3:27+(n%3+1)*3] + guess_list[36+(n%3)*3:36+(n%3+1)*3] + guess_list[45+(n%3)*3:45+(n%3+1)*3]
        idxs = [27+(n%3)*3,28+(n%3)*3,29+(n%3)*3,36+(n%3)*3,37+(n%3)*3,38+(n%3)*3,45+(n%3)*3,46+(n%3)*3,47+(n%3)*3]
    elif n >= 6:
        nth_box = guess_list[54+(n%3)*3:54+(n%3+1)*3] + guess_list[63+(n%3)*3:63+(n%3+1)*3] + guess_list[72+(n%3)*3:72+(n%3+1)*3]
        idxs = [54+(n%3)*3,55+(n%3)*3,56+(n%3)*3,63+(n%3)*3,64+(n%3)*3,65+(n%3)*3,72+(n%3)*3,73+(n%3)*3,74+(n%3)*3]
    return nth_box,idxs

def check_singles(guess_list):
    singles = []
    for i in range(9):
        i_box,box_idxs = check_box(i,guess_list)
        i_line,line_idxs = check_line(i,guess_list)
        i_col,col_idxs = check_col(i,guess_list)
        for j in range(1,10):
            if sum(i_box,[]).count(j) == 1:
                for a,square in enumerate(i_box):
                    if j in square:
                        if [[j,box_idxs[a]]] not in singles:
                            singles += [[j,box_idxs[a]]]
            if sum(i_line,[]).count(j) == 1:
                for a,square in enumerate(i_line):
                    if j in square:
                        if [[j,line_idxs[a]]] not in singles:
                            singles += [[j,line_idxs[a]]]

            if sum(i_col,[]).count(j) == 1:
                for a,square in enumerate(i_col):
                    if j in square:
                        if [[j,col_idxs[a]]] not in singles:
                            singles += [[j,col_idxs[a]]]
    return singles
### Solver ###
# <NAME>

import numpy as np
#from solver_funcs import *

def sudoku_starter(board):
    'adapting to the guess_list variable'
    backups         = [] #sudokus backup
    branch          = [] # branch of the guessing tree 
    sudoku_board    = np.empty((9,9), dtype = int) # empty sudoku 9x9 board 
    sudoku_board[:] = board[:]  #here we copy the board list
    moves           = num_moves(sudoku_board)  # counts the number of zeroes
    guess_list      = available_moves(sudoku_board) #list with all the possible moves
    singles         = check_singles(guess_list)
    for single in singles:
        q,r = divmod(single[1],9)
        if sudoku_board[q][r] == 0:
            move               = [single[0]]
            sudoku_board[q][r] = move[0]
            moves             -= 1
            guess_list         = refresh_guess_list(move,q,r,guess_list)
    move,q,r        = next_move(guess_list) # next right move
    while moves: # while there are moves to be made we make'em
        l = len(move)
        if l > 1:
            return sudoku_solver(sudoku_board,moves,guess_list,branch,backups)
        if l == 1:
            sudoku_board[q][r] =  move[0]
            moves             -=  1
            guess_list         =  refresh_guess_list(move,q,r,guess_list)
            move,q,r           =  next_move(guess_list)
    return sudoku_board

def sudoku_solver(sudoku_board,moves,guess_list,branch,backups):
    'solves the sudoku by trying to guess from the list with least possible guesses'
    while moves > 0:
        move,q,r          = next_move(guess_list)
        if not move:
            backups       = backups[:-1]
            branch        = branch[:-1]
            sudoku_board  = backups[-1][0]
            guess_list    = backups[-1][1]
            moves         = num_moves(sudoku_board)
        elif move == 1:
            sudoku_board[q][r] = move[0]
            guess_list         = refresh_guess_list(move,q,r,guess_list)
            moves             -= 1
        else:
            guess            = next_branch(branch,move,q,r)
            if not guess:
                k = (branch.index([q,r]))
                sudoku_board = backups[k-1][0]
                guess_list   = backups[k-1][1]
                backups      = backups[:k]
                branch       = branch[:k]
                moves        = num_moves(sudoku_board)
            else:
                backups.append([sudoku_board.copy(),copy_GL(guess_list)])
                sudoku_board[q][r] = guess[0]
                moves             -= 1
                branch            += [[q,r]]
                guess_list         = refresh_guess_list(guess,q,r,guess_list)
    return sudoku_board
sudoku_starter(null_sudoku)
import cProfile
cProfile.run("sudoku_starter(null_sudoku)", sort='tottime')
def next_branch(branch,move,q,r):
    # invertendo a ordem dos galhos
    'returns the next branch to try (right to left)'
    if move == 0:
        #print(move,q,r,'wut')
        return -1 # error code
    j = branch.count([q,r])
    if j >= len(move):
        return 0
    return [move[-j-1]]  # starts from the *right* of the list
sudoku_starter(null_sudoku)
import cProfile
cProfile.run("sudoku_starter(null_sudoku)", sort='tottime')
normal_sudoku  =      [[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]]

normal_sol =          [[8,1,2,7,5,3,6,4,9],
                       [9,4,3,6,8,2,1,7,5],
                       [6,7,5,4,9,1,2,8,3],
                       [1,5,4,2,3,7,8,9,6],
                       [3,6,9,8,4,5,7,2,1],
                       [2,8,7,1,6,9,5,3,4],
                       [5,2,1,9,7,4,3,6,8],
                       [4,3,8,5,2,6,9,1,7],
                       [7,9,6,3,1,8,4,5,2]]
%time sudoku_starter(normal_sudoku)
ans = [[8, 1, 2, 7, 5, 3, 6, 4, 9],
       [9, 4, 3, 6, 8, 2, 1, 7, 5],
       [6, 7, 5, 4, 9, 1, 2, 8, 3],
       [1, 5, 4, 2, 3, 7, 8, 9, 6],
       [3, 6, 9, 8, 4, 5, 7, 2, 1],
       [2, 8, 7, 1, 6, 9, 5, 3, 4],
       [5, 2, 1, 9, 7, 4, 3, 6, 8],
       [4, 3, 8, 5, 2, 6, 9, 1, 7],
       [7, 9, 6, 3, 1, 8, 4, 5, 2]]
def next_branch(branch,move,q,r):
    # voltando para a ordem normal
    'returns the next branch to try (left to right)'
    if move == 0:
        #print(move,q,r,'wut')
        return -1 # error code
    j = branch.count([q,r])
    if j >= len(move):
        return 0
    return [move[j]]  # starts from the *left* of the list
%time sudoku_starter(normal_sudoku)
ans2 = [[8, 1, 2, 7, 5, 3, 6, 4, 9],
       [9, 4, 3, 6, 8, 2, 1, 7, 5],
       [6, 7, 5, 4, 9, 1, 2, 8, 3],
       [1, 5, 4, 2, 3, 7, 8, 9, 6],
       [3, 6, 9, 8, 4, 5, 7, 2, 1],
       [2, 8, 7, 1, 6, 9, 5, 3, 4],
       [5, 2, 1, 9, 7, 4, 3, 6, 8],
       [4, 3, 8, 5, 2, 6, 9, 1, 7],
       [7, 9, 6, 3, 1, 8, 4, 5, 2]]
assert(ans == ans2)<jupyter_output><empty_output>