Résoudre les mathématiques avec Python (incomplet)
Récemment, je suis accro à la résolution de l'Allemagne suprême dans un jeu pour smartphone. Lors de la résolution avec du papier et un stylo, trouvez les carrés qui peuvent contenir des valeurs numériques et appliquez-leur les valeurs numériques. Lors de la résolution avec un appareil tel qu'un smartphone, une fois que toutes les valeurs numériques sont attribuées à tous les carrés, recherchez les carrés qui ne contiennent probablement pas la même valeur numérique à partir des carrés déterminés et supprimez les valeurs numériques. Il est plus rapide de penser par «soustraction».
Je le résolve toujours avec cette méthode, mais j'ai écrit un programme et essayé de voir si cette méthode pouvait résoudre un problème de manière algorithmique (?) À chaque fois. À partir de la conclusion, il y avait des problèmes qui n'ont pas pu être résolus, donc si vous voulez construire un programme qui peut être résolu sans faute, nous vous recommandons d'envisager une méthode round-robin dans laquelle les substitutions sont effectuées dans l'ordre à partir d'une extrémité. (Voir ci-dessous)
Comment résoudre (image)
Tout d'abord, s'il y avait un tel problème
(1) Remplacez une fois tous les nombres pour toutes les cellules pour lesquelles les nombres n'ont pas été déterminés.
(2) Faites attention à chacun des éléments déterminés et effacez les valeurs numériques verticalement, horizontalement et depuis le carré 3x3 où les valeurs numériques existent.
(Ce chiffre est après avoir fonctionné sur "1" au milieu à gauche. Répétez ceci pour toutes les valeurs déterminées.)
③ Cette fois, faites attention à la verticale, à l'horizontale et à 3x3, et entrez la valeur qui ne peut être entrée que dans cet élément comme valeur de décision.
(Dans le cas de cette figure, il n'y a qu'un seul "1" en haut à gauche 3x3, donc "1" est déterminé ici.)
④ Répétez ces opérations.
Implémentez-le par programme.
code
sudoku_solver.py
import numpy as np
import copy
xx = [1, 2, 3, 4, 5, 6, 7, 8, 9]
x1 = [1]
x2 = [2]
x3 = [3]
x4 = [4]
x5 = [5]
x6 = [6]
x7 = [7]
x8 = [8]
x9 = [9]
lists = [
[copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(x4), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(xx)],
[copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(x5), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(xx)],
[copy.deepcopy(xx), copy.deepcopy(x3), copy.deepcopy(x6), copy.deepcopy(x8), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(x7), copy.deepcopy(x2)],
[copy.deepcopy(xx), copy.deepcopy(x8), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(x6), copy.deepcopy(x5), copy.deepcopy(xx), copy.deepcopy(xx)],
[copy.deepcopy(x1), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(x5), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(x9), copy.deepcopy(xx)],
[copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(x2), copy.deepcopy(xx), copy.deepcopy(x7)],
[copy.deepcopy(xx), copy.deepcopy(x1), copy.deepcopy(xx), copy.deepcopy(x2), copy.deepcopy(xx), copy.deepcopy(x8), copy.deepcopy(x4), copy.deepcopy(x3), copy.deepcopy(x6)],
[copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(x8), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(x4), copy.deepcopy(x7), copy.deepcopy(xx), copy.deepcopy(x9)],
[copy.deepcopy(xx), copy.deepcopy(x6), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(x1), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(x5)],
]
cells = np.array(lists)
flags = np.zeros((9, 9))
grid = [(0, 3), (3, 6), (6, 9)]
while np.any(flags==0):
for i, ii in enumerate(cells):
for j, jj in enumerate(ii):
if len(jj) == 1 and flags[i, j] == False:
num = jj[0]
flags[i, j] = True
#Recherchez verticalement, horizontalement et direction, et supprimez le même numéro
for kk in cells[i]:
if num in kk and len(kk) != 1:
kk.remove(num)
for kk in cells[:, j]:
if num in kk and len(kk) != 1:
kk.remove(num)
#Supprimer le même numéro en 3x3
if i < 3:
l = 0
elif i >= 3 and i < 6:
l = 3
elif i >= 6 and i < 9:
l = 6
if j < 3:
d = 0
elif j >= 3 and j < 6:
d = 3
elif j >= 6 and j < 9:
d = 6
for ll in cells[l:l+3, d:d+3]:
for mm in ll:
if num in mm and len(mm) != 1:
mm.remove(num)
for ii in range(1, 10):
#Recherchez verticalement, horizontalement et direction, et décidez si un seul nombre est entré
for jj in range(0, 9):
counter1 = 0
counter2 = 0
marker1 = 0
marker2 = 0
for kk in range(0, 9):
if ii in cells[jj, kk]:
counter1 += 1
marker1 = kk
if ii in cells[kk, jj]:
counter2 += 1
marker2 = kk
if counter1 == 1:
cells[jj, marker1].clear()
cells[jj, marker1].append(ii)
if counter2 == 1:
cells[marker2, jj].clear()
cells[marker2, jj].append(ii)
#Rechercher dans 3x3 et décider si un seul numéro est entré
for jj in grid:
for kk in grid:
counter3 = 0
marker3 = 0
marker4 = 0
for mm, ll in enumerate(cells[jj[0]:jj[1], kk[0]:kk[1]]):
for oo, nn in enumerate(ll):
if ii in nn:
counter3 += 1
marker3 = mm
marker4 = oo
if counter3 == 1:
cells[jj[0]+marker3, kk[0]+marker4].clear()
cells[jj[0]+marker3, kk[0]+marker4].append(ii)
#Création d'un tableau pour l'impression
num_list = []
for ii in cells:
_num_list = []
for jj in ii:
if len(jj) == 1:
_num_list.append(jj[0])
else:
_num_list.append(0)
num_list.append(_num_list)
print("---------------------------")
for ii in num_list:
print(ii)
print("---------------------------")
L'un de mes objectifs était de m'entraîner à utiliser numpy, donc je l'utilise pour le moment. Pour un tableau tridimensionnel qui a une liste contenant 1 à 9 en 9x9, si la valeur numérique de la cellule a été déterminée (si la longueur du tableau tridimensionnel est 1) et exécuter l'opération de ② Le problème est résolu en gérant avec un tableau bidimensionnel 9x9 qui gère s'il a été complété ou non avec True-False.
Résultat d'exécution
Voici le résultat de l'exécution.
---------------------------
[2, 7, 1, 6, 4, 3, 9, 5, 8]
[8, 9, 5, 1, 7, 2, 3, 6, 4]
[4, 3, 6, 8, 9, 5, 1, 7, 2]
[7, 8, 3, 9, 2, 6, 5, 4, 1]
[1, 4, 2, 5, 8, 7, 6, 9, 3]
[6, 5, 9, 4, 3, 1, 2, 8, 7]
[9, 1, 7, 2, 5, 8, 4, 3, 6]
[5, 2, 8, 3, 6, 4, 7, 1, 9]
[3, 6, 4, 7, 1, 9, 8, 2, 5]
---------------------------
finalement
Il semble qu'il y ait des problèmes qui ne peuvent être résolus avec cette seule logique, et tout en essayant de résoudre de tels problèmes continue de tourner. J'ai découvert en enquêtant cette fois, mais il semble qu'il existe différentes solutions dans Sugoku, et il semble que quelque chose ne soit pas suffisant avec cette solution (je ne sais pas ce que c'est.) Cette fois, le but n'était pas de résoudre tous les problèmes en Allemagne, alors je l'ai juste vérifié pour le moment. Si vous voulez terminer la suite, je pense que ce qui suit sera utile. Pour le moment, je pense que ce sera terminé plus rapidement que le tournoi à la ronde.
Comment résoudre Nampure / Advanced
Je veux juste résoudre n'importe quel problème! Comme mentionné au début, il est recommandé d'utiliser la méthode round-robin suivante.
Résoudre les mathématiques avec Python
De plus, cette fois, je ne l'ai résolu que normalement, mais cela seul n'est pas intéressant, j'ai donc essayé de reconnaître le problème à partir des images et des photos et de le résoudre. La prochaine fois, j'écrirai sur ce domaine.
Recommended Posts