Résolution de Nampre avec Python (partie 2)

Calendrier de l'Avent IPFactory 2019 Jour 14

Je suis pycys de IP Factory et ISC 1ère année. C'est la deuxième partie de Résoudre Nampre avec Python.

Le programme ci-dessous ne peut pas résoudre les problèmes qui nécessitent un placement temporaire dans le processus de résolution. Soyez prudent lorsque vous vous y référez.

J'ai écrit le code

J'ai finalement pu le faire. La plupart des problèmes devraient être résolus en moins d'une seconde. J'ai écrit l'algorithme tel quel pour le faire à temps, donc ce n'est pas facile à lire. Je l'écrirai soigneusement plus tard. J'ai ajouté un algorithme, donc j'écrirai un article plus tard, y compris une explication.

nampre.py

import time, copy as cp

#Trame 3 × 3 n Jugement de confirmation&Processus d'exclusion
def cubic_frame_judgment():
    flag = False
    for i in range(3):
        for j in range(3):
            indices = [() for n in range(9)]
            for sub_i in range(i*3, i*3+3):
                for sub_j in range(j*3, j*3+3):
                    for num in unconfirmed_numbers[sub_i][sub_j]:
                        indices[num-1] = (sub_i, sub_j) if not indices[num-1] else (9,9)
            for index in indices:
                if index != (9,9) and index not in subscripts:
                    flag = True
                    nampre[index[0]][index[1]] = indices.index(index)+1
                    column_excluder(index[0], index[1], indices.index(index)+1)
                    row_excluder(index[0], index[1], indices.index(index)+1)
                    cubic_frame_excluder(index[0], index[1], indices.index(index)+1)
                    subscripts.add((index[0], index[1]))
    return flag

#Colonne n Jugement de confirmation&Processus d'exclusion
def column_judgment():
    flag = False
    for j in range(9):
        indices = [() for n in range(9)]
        for i in range(9):
            for num in unconfirmed_numbers[i][j]:
                indices[num-1] = (i, j) if not indices[num-1] else (9,9)
        for index in indices:
            if index != (9,9) and index not in subscripts:
                flag = True
                nampre[index[0]][index[1]] = indices.index(index)+1
                column_excluder(index[0], index[1], indices.index(index)+1)
                row_excluder(index[0], index[1], indices.index(index)+1)
                cubic_frame_excluder(index[0], index[1], indices.index(index)+1)
                subscripts.add((index[0], index[1]))
    return flag

#Rangée n Jugement de confirmation&Processus d'exclusion
def row_judgment():
    flag = False
    for i in range(9):
        indices = [() for n in range(9)]
        for j in range(9):
            for num in unconfirmed_numbers[i][j]:
                indices[num-1] = (i, j) if not indices[num-1] else (9,9)
        for index in indices:
            if index != (9,9) and index not in subscripts:
                flag = True
                nampre[index[0]][index[1]] = indices.index(index)+1
                column_excluder(index[0], index[1], indices.index(index)+1)
                row_excluder(index[0], index[1], indices.index(index)+1)
                cubic_frame_excluder(index[0], index[1], indices.index(index)+1)
                subscripts.add((index[0], index[1]))
    return flag

#Rechercher une cellule qui n'a qu'un seul numéro&Processus d'exclusion
def only_one_judgment():
    flag = False
    for i in range(9):
        for j in range(9):
            if len(unconfirmed_numbers[i][j]) == 1 and (i,j) not in subscripts:
                flag = True
                num = unconfirmed_numbers[i][j][0]
                nampre[i][j] = num
                column_excluder(i, j, num)
                row_excluder(i, j, num)
                cubic_frame_excluder(i, j, num)
                subscripts.add((i,j))
    return flag

#Traitement des exceptions 1
def cubic_tumor_excluder():
    flag = False
    #Vérification du cadre 3x3
    for i in range(3):
        for j in range(3):
            overlapping_numbers = [[] for i in range(9)]
            for sub_i in range(i*3, i*3+3):
                for sub_j in range(j*3, j*3+3):
                    for num in unconfirmed_numbers[sub_i][sub_j]:
                        overlapping_numbers[num-1].append((sub_i, sub_j))
            for index_box in overlapping_numbers:
                if overlapping_numbers.count(index_box) == len(index_box) >= 2:
                    nums = [index+1 for index, indices in enumerate(overlapping_numbers) if indices == index_box]
                    for index in index_box:
                        if unconfirmed_numbers[index[0]][index[1]] != nums:
                            flag = True
                            unconfirmed_numbers[index[0]][index[1]] = cp.deepcopy(nums)
    #Vérification des lignes
    for i in range(9):
        overlapping_numbers = [[] for i in range(9)]
        for j in range(9):
            for num in unconfirmed_numbers[i][j]:
                overlapping_numbers[num-1].append((i, j))
        for index_box in overlapping_numbers:
            if overlapping_numbers.count(index_box) == len(index_box) >= 2:
                nums = [index+1 for index, indices in enumerate(overlapping_numbers) if indices == index_box]
                for index in index_box:
                    if unconfirmed_numbers[index[0]][index[1]] != nums:
                        flag = True
                        unconfirmed_numbers[index[0]][index[1]] = cp.deepcopy(nums)
    #Vérification de la colonne
    for j in range(9):
        overlapping_numbers = [[] for i in range(9)]
        for i in range(9):
            for num in unconfirmed_numbers[i][j]:
                overlapping_numbers[num-1].append((i, j))
        for index_box in overlapping_numbers:
            if overlapping_numbers.count(index_box) == len(index_box) >= 2:
                nums = [index+1 for index, indices in enumerate(overlapping_numbers) if indices == index_box]
                for index in index_box:
                    if unconfirmed_numbers[index[0]][index[1]] != nums:
                        flag = True
                        unconfirmed_numbers[index[0]][index[1]] = cp.deepcopy(nums)
    return flag

#Version inversée de l'exception 1
def remainder_excluder():
    flag = False
    #Cadre 3x3
    for i in range(3):
        for j in range(3):
            cubic_frame_nums = []
            for sub_i in range(i*3, i*3+3):
                for sub_j in range(j*3, j*3+3):
                    cubic_frame_nums.append(cp.deepcopy(unconfirmed_numbers[sub_i][sub_j]))
            for nums in cubic_frame_nums:
                if len(nums) == cubic_frame_nums.count(nums) > 1:
                    for sub_i in range(i*3, i*3+3):
                        for sub_j in range(j*3, j*3+3):
                            if unconfirmed_numbers[sub_i][sub_j] != nums:
                                for num in nums:
                                    if num in unconfirmed_numbers[sub_i][sub_j]:
                                        unconfirmed_numbers[sub_i][sub_j].remove(num)
                                        flag = True
    #côté
    for i in range(9):
        row_line_nums = []
        for j in range(9):
            row_line_nums.append(cp.deepcopy(unconfirmed_numbers[i][j]))
        for nums in row_line_nums:
            if len(nums) == row_line_nums.count(nums) > 1:
                for j in range(9):
                    if unconfirmed_numbers[i][j] != nums:
                        for num in nums:
                            if num in unconfirmed_numbers[i][j]:
                                unconfirmed_numbers[i][j].remove(num)
                                flag = True
    #Verticale
    for j in range(9):
        column_line_nums = []
        for i in range(9):
            column_line_nums.append(cp.deepcopy(unconfirmed_numbers[i][j]))
        for nums in column_line_nums:
            if len(nums) == column_line_nums.count(nums) > 1:
                for i in range(9):
                    if unconfirmed_numbers[i][j] != nums:
                        for num in nums:
                            if num in unconfirmed_numbers[i][j]:
                                unconfirmed_numbers[i][j].remove(num)
                                flag = True
    return flag

#Traitement des exceptions 2
def line_confirm():
    flag = False
    for i in range(3):
        for j in range(3):
            #Traitement horizontal
            row_lines = []
            for sub_i in range(i*3, i*3+3):
                row_line = []
                for sub_j in range(j*3, j*3+3):
                    for num in unconfirmed_numbers[sub_i][sub_j]:
                        row_line.append(num)
                row_lines.append(list(set(row_line)))
            exclusive_union = row_lines[0] + row_lines[1] + row_lines[2]
            exclusive_union = [num for num in exclusive_union if not exclusive_union.count(num) >= 2]
            if exclusive_union:
                for number in exclusive_union:
                    for row in row_lines:
                        if number in row:
                            row_i = i*3+row_lines.index(row)
                            for sub_j in range(0, j*3):
                                if number in unconfirmed_numbers[row_i][sub_j] and len(unconfirmed_numbers[row_i][sub_j]) > 1:
                                    flag = True
                                    unconfirmed_numbers[row_i][sub_j].remove(number)
                            for sub_j in range(j*3+3, 9):
                                if number in unconfirmed_numbers[row_i][sub_j] and len(unconfirmed_numbers[row_i][sub_j]) > 1:
                                    flag = True
                                    unconfirmed_numbers[row_i][sub_j].remove(number)
            #Traitement vertical
            column_lines = []
            for sub_j in range(j*3, j*3+3):
                column_line = []
                for sub_i in range(i*3, i*3+3):
                    for num in unconfirmed_numbers[sub_i][sub_j]:
                        column_line.append(num)
                column_lines.append(list(set(column_line)))
            exclusive_union = column_lines[0] + column_lines[1] + column_lines[2]
            exclusive_union = [num for num in exclusive_union if not exclusive_union.count(num) >= 2]
            if exclusive_union:
                for number in exclusive_union:
                    for column in column_lines:
                        if number in column:
                            column_j = j*3+column_lines.index(column)
                            for sub_i in range(0, i*3):
                                if number in unconfirmed_numbers[sub_i][column_j] and len(unconfirmed_numbers[sub_i][column_j]) > 1:
                                    flag = True
                                    unconfirmed_numbers[sub_i][column_j].remove(number)
                            for sub_i in range(i*3+3, 9):
                                if number in unconfirmed_numbers[sub_i][column_j] and len(unconfirmed_numbers[sub_i][column_j]) > 1:
                                    flag = True
                                    unconfirmed_numbers[sub_i][column_j].remove(number)
    return flag

#Tableau 3D Lire le même numéro de la même colonne
def column_excluder(i, j, n):
    flag = False
    for sub_i in range(9):
        if n in unconfirmed_numbers[sub_i][j]:
            unconfirmed_numbers[sub_i][j].remove(n)
            flag = True
    unconfirmed_numbers[i][j] = [n]

#Jouez le même numéro de la même ligne dans un tableau en trois dimensions
def row_excluder(i, j, n):
    flag = False
    for sub_j in range(9):
        if n in unconfirmed_numbers[i][sub_j]:
            unconfirmed_numbers[i][sub_j].remove(n)
            flag = True
    unconfirmed_numbers[i][j] = [n]
    
#Tableau 3D Lire le même numéro à partir de la même image
def cubic_frame_excluder(i, j, n):
    flag = False
    for sub_i in range(i//3*3, i//3*3+3):
        for sub_j in range(j//3*3, j//3*3+3):
            if n in unconfirmed_numbers[sub_i][sub_j]:
                flag = True
                unconfirmed_numbers[sub_i][sub_j].remove(n)
    unconfirmed_numbers[i][j] = [n]

#Pour la sortie
def nampre_print():
    print("____________________________________")
    for index, nums in enumerate(nampre):
        if index == 8:
            print("|", end="")
            [print(" "+str(n)+" |",end="") for i, n in enumerate(nums)]
            print("\n ￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣")
        elif (index+1)%3 == 0:
            print("|", end="")
            [print(" "+str(n)+" |",end="") for i, n in enumerate(nums)]
            print("\n|===|===|===|===|===|===|===|===|===|")
        else:
            print("|", end="")
            [print(" "+str(n)+" |",end="") for i, n in enumerate(nums)]
            print("\n|---|---|---|---|---|---|---|---|---|")


#Mesurer le temps
start = time.time()

#Entrée et formatage dans un tableau 2D
nums = [int(i) for i in input().split()]
nampre = [[] for i in range(9)]
for index, i in enumerate(nums):
    nampre[index//9].append(i)

#Génération de tableaux 3D pour référence numérique non confirmée
unconfirmed_numbers = [[[n for n in range(1,10)] for j in range(9)] for i in range(9)]

#Indicateur de continuation du traitement
flag = False

#Numéro confirmé indice
subscripts = set()

#Raser la matrice 3D
for i in range(9):
    for j in range(9):
        if nampre[i][j] != 0 and (i,j) not in subscripts:
            flag = True
            num = nampre[i][j]
            column_excluder(i, j, num)
            row_excluder(i, j, num)
            cubic_frame_excluder(i, j, num)
            subscripts.add((i,j))

nampre_print()
while flag:
    flag = cubic_frame_judgment() or row_judgment() or column_judgment() or only_one_judgment() or cubic_tumor_excluder() or remainder_excluder() or line_confirm()
nampre_print()
print(str(time.time()-start)+"[sec]")