Quand j'ai rencontré mon père à la maison après un long moment, j'ai utilisé une application pour smartphone pour résoudre le Sudoku. Nous le ferons avec Google Colaboratory.
Si vous recherchez sur Google avec "sudoku", il semble y avoir un site comme celui-ci, donc mon objectif est de résoudre le problème ici. En regardant "Difficulté", il semble qu'il y ait les 4 niveaux suivants.
J'essaierai de résoudre une question chacun.
Par exemple, si le problème suivant ...
Je vais l'exprimer comme une liste bidimensionnelle comme suit. À propos, ce problème est un exemple de difficulté facile.
sudoku.ipynb
# easy
list_sudoku = [
[0, 4, 8, 0, 9, 0, 0, 5, 0],
[0, 0, 0, 7, 4, 5, 2, 1, 0],
[0, 7, 5, 0, 0, 2, 4, 0, 0],
[0, 0, 0, 0, 7, 0, 0, 0, 2],
[7, 0, 6, 4, 0, 9, 0, 0, 0],
[9, 0, 2, 0, 6, 0, 3, 0, 0],
[0, 0, 0, 6, 1, 0, 8, 2, 7],
[0, 1, 3, 0, 5, 0, 6, 4, 9],
[0, 0, 7, 9, 8, 0, 0, 0, 1]]
Par exemple, dans la cellule supérieure gauche du problème ci-dessus, il est décidé que les nombres déjà dans la verticale, l'horizontale et le bloc ne seront pas inclus, de sorte que les candidats peuvent être réduits à [1,2,3,6]. Voilà pourquoi. Créez une fonction qui peut faire cela.
Commençons par dresser une liste des candidats 1 à 9 en tant que variables.
sudoku.ipynb
list_possible = [i for i in range(1, 10)]
Créons maintenant une fonction. Tout d'abord, vertical.
sudoku.ipynb
def narrow_ver(x, list_possible, list_sudoku):
"""
Affiner les candidats dans le sens vertical
"""
list_ver = [list_sudoku[i][x] for i in range(9) if type(list_sudoku[i][x]) is int]
return set(list_possible) - set(list_ver)
Puis sur le côté.
sudoku.ipynb
def narrow_hor(y, list_possible, list_sudoku):
"""
Affinez les candidats dans le sens horizontal
"""
list_hor = [list_sudoku[y][i] for i in range(9) if type(list_sudoku[y][i]) is int]
return set(list_possible) - set(list_hor)
Et dans le bloc.
sudoku.ipynb
def narrow_blo(x, y, list_possible, list_sudoku):
"""
Affinez les candidats dans le bloc
"""
index_x = (x // 3) * 3
index_y = (y // 3) * 3
list_blo = [list_sudoku[i][j] for i in range(index_y, index_y+3) for j in range(index_x, index_x+3) if type(list_sudoku[i][j]) is int]
return set(list_possible) - set(list_blo)
Créez une fonction qui appelle verticalement, horizontalement et à l'intérieur d'un bloc ...
sudoku.ipynb
def narrow(x, y, list_possible, list_sudoku):
"""
Affinez les candidats pour la cellule cible
"""
list_possible = narrow_ver(x, list_possible, list_sudoku)
list_possible = narrow_hor(y, list_possible, list_sudoku)
list_possible = narrow_blo(x, y, list_possible, list_sudoku)
return sorted(list(list_possible))
Créez une fonction qui exécute ↑ pour toutes les cellules. Cependant, les cellules pour lesquelles le nombre a déjà été décidé sont terminées.
sudoku.ipynb
def apply_narrow(list_sudoku):
"""
Étroit pour toutes les cellules()Courir
"""
for y in range(9):
for x in range(9):
if list_sudoku[y][x] != 0 and type(list_sudoku[y][x]) is int:
continue
elif list_sudoku[y][x] == 0:
list_sudoku[y][x] = narrow(x, y, list_possible, list_sudoku)
else:
list_sudoku[y][x] = narrow(x, y, list_sudoku[y][x], list_sudoku)
if len(list_sudoku[y][x]) == 1:
list_sudoku[y][x] = list_sudoku[y][x][0]
return list_sudoku
Peut-être que c'est tout ce que vous devez résoudre? Essayons!
Copiez-le dans temp_sudoku, comparez-le avec celui après avoir exécuté apply_narrow (), et s'il n'y a pas de changement, il se terminera.
sudoku.ipynb
import copy
list_possible = [i for i in range(1, 10)]
count = 0
temp_sudoku = []
while(True):
temp_sudoku = copy.deepcopy(list_sudoku)
count += 1
list_sudoku = apply_narrow(list_sudoku)
if temp_sudoku == list_sudoku:
break
print(count)
list_sudoku
↓ Résultat de sortie
6
[[2, 4, 8, 1, 9, 6, 7, 5, 3],
[3, 6, 9, 7, 4, 5, 2, 1, 8],
[1, 7, 5, 8, 3, 2, 4, 9, 6],
[4, 5, 1, 3, 7, 8, 9, 6, 2],
[7, 3, 6, 4, 2, 9, 1, 8, 5],
[9, 8, 2, 5, 6, 1, 3, 7, 4],
[5, 9, 4, 6, 1, 3, 8, 2, 7],
[8, 1, 3, 2, 5, 7, 6, 4, 9],
[6, 2, 7, 9, 8, 4, 5, 3, 1]]
Vous l'avez résolu! Je l'ai fait!
Que diriez-vous moyen?
sudoku.ipynb
# medium
list_sudoku = [
[9, 0, 0, 8, 1, 0, 0, 0, 0],
[0, 0, 5, 0, 0, 4, 7, 0, 6],
[0, 0, 0, 2, 0, 5, 8, 0, 1],
[0, 9, 0, 7, 4, 0, 5, 0, 0],
[0, 0, 0, 0, 0, 3, 0, 7, 0],
[7, 4, 0, 0, 0, 0, 0, 0, 0],
[3, 0, 0, 9, 5, 0, 6, 0, 0],
[0, 0, 6, 4, 0, 0, 0, 1, 3],
[1, 7, 0, 0, 0, 0, 0, 0, 4]]
↓ Résultat
6
[[9, [3, 6], [2, 3, 7], 8, 1, [6, 7], [3, 4], [3, 4], 5],
[8, 1, 5, 3, 9, 4, 7, 2, 6],
[[4, 6], [3, 6], [3, 7], 2, [6, 7], 5, 8, [3, 4, 9], 1],
[[2, 6], 9, [1, 2, 3, 8], 7, 4, [2, 6], 5, [3, 6], [2, 8]],
[[2, 6], [5, 6], [1, 2, 8], [1, 5], [2, 6, 8], 3, [1, 4], 7, [2, 8, 9]],
[7,
4,
[1, 2, 3, 8],
[1, 5],
[2, 6, 8],
[2, 6, 9],
[1, 3],
[3, 6, 9],
[2, 8, 9]],
[3, 2, 4, 9, 5, 1, 6, 8, 7],
[5, 8, 6, 4, [2, 7], [2, 7], 9, 1, 3],
[1, 7, 9, 6, 3, 8, 2, 5, 4]]
N'est-ce pas bon? Les 2e, 7e et 9e lignes sont toutes résolues et les lignes sont plutôt bonnes. Apparemment, cela seul ne suffit pas pour restreindre les candidats.
Si ce résultat est représenté dans un tableau, il ressemble à ce qui suit. Le déficit est un candidat.
Eh bien, il est tellement rempli que cela ressemble à un répit, mais comment le résoudre? Si vous essayez de le résoudre vous-même ... Par exemple, s'il est "46" dans la 1ère colonne et la 3ème ligne, il n'y a aucune autre cellule dans le bloc qui a "4" comme candidat, donc la réponse est décidée comme "4".
Après avoir réduit les candidats de cellule, comparez-les avec les candidats de cellule à la verticale, à l'horizontale et au bloc. À la suite de la comparaison, s'il y a un candidat qui n'est pas dans d'autres cellules, créez une fonction qui y répond.
Il utilise itertools, alors importons-le.
sudoku.ipynb
import itertools
D'abord à partir de la cellule verticale.
sudoku.ipynb
def generate_possible_ver(x, y, list_sudoku):
"""
Collecter les cellules candidates dans le sens vertical
"""
list_ver = [list_sudoku[i][x] for i in range(9) if type(list_sudoku[i][x]) is list and i!=y]
return set(itertools.chain.from_iterable(list_ver))
Puis sur le côté.
sudoku.ipynb
def generate_possible_hor(x, y, list_sudoku):
"""
Recueillir des candidats pour les cellules horizontales
"""
list_hor = [list_sudoku[y][i] for i in range(9) if type(list_sudoku[y][i]) is list and i!=x]
return set(itertools.chain.from_iterable(list_hor))
Et dans le bloc.
sudoku.ipynb
def generate_possible_blo(x, y, list_sudoku):
"""
Collectez les cellules candidates dans le bloc
"""
index_x = (x // 3) * 3
index_y = (y // 3) * 3
list_blo = [list_sudoku[i][j] for i in range(index_y, index_y+3) for j in range(index_x, index_x+3) if type(list_sudoku[i][j]) is list and (i!=y or j!=x)]
return set(itertools.chain.from_iterable(list_blo))
Créez une fonction qui compare les candidats et les affecte à la cellule s'il n'y a qu'un seul candidat.
sudoku.ipynb
def find_only_one(x, y, list_possible, list_sudoku):
"""
Comparez avec les cellules candidates verticales, horizontales et en bloc,
S'il y a un candidat qui n'est pas dans d'autres cellules, répondez-y
"""
diff_ver = set(list_possible) - generate_possible_ver(x, y, list_sudoku)
if len(diff_ver) == 1:
return list(diff_ver)[0]
diff_hor = set(list_possible) - generate_possible_hor(x, y, list_sudoku)
if len(diff_hor) == 1:
return list(diff_hor)[0]
diff_blo = set(list_possible) - generate_possible_blo(x, y, list_sudoku)
if len(diff_blo) == 1:
return list(diff_blo)[0]
return list_possible
Créez une fonction qui exécute ↑ pour toutes les cellules. Bien sûr, celui qui a déjà la réponse est passé.
sudoku.ipynb
def try_solve(list_sudoku):
"""
Pour les cellules pour lesquelles la réponse n'a pas encore été déterminée
narrow()Et trouve_only_one()Courir
"""
for y in range(9):
for x in range(9):
if list_sudoku[y][x] != 0 and type(list_sudoku[y][x]) is int:
continue
else:
list_sudoku[y][x] = narrow(x, y, list_sudoku[y][x], list_sudoku)
list_sudoku[y][x] = find_only_one(x, y, list_sudoku[y][x], list_sudoku)
if type(list_sudoku[y][x]) is list and len(list_sudoku[y][x]) == 1:
list_sudoku[y][x] = list_sudoku[y][x][0]
return list_sudoku
Essayons-le maintenant!
Cette fois également, s'il n'y a pas de changement par rapport à temp_sudoku, cela prendra fin.
sudoku.ipynb
import copy
list_possible = [i for i in range(1, 10)]
count = 0
temp_sudoku = []
while(True):
temp_sudoku = copy.deepcopy(list_sudoku)
count += 1
list_sudoku = try_solve(apply_narrow(list_sudoku))
if temp_sudoku == list_sudoku:
break
print(count)
list_sudoku
↓ Résultat de sortie
4
[[9, 6, 2, 8, 1, 7, 3, 4, 5],
[8, 1, 5, 3, 9, 4, 7, 2, 6],
[4, 3, 7, 2, 6, 5, 8, 9, 1],
[2, 9, 1, 7, 4, 6, 5, 3, 8],
[6, 5, 8, 1, 2, 3, 4, 7, 9],
[7, 4, 3, 5, 8, 9, 1, 6, 2],
[3, 2, 4, 9, 5, 1, 6, 8, 7],
[5, 8, 6, 4, 7, 2, 9, 1, 3],
[1, 7, 9, 6, 3, 8, 2, 5, 4]]
Ça m'a l'air bien. Allons dur avec cette condition.
sudoku.ipynb
# hard
list_sudoku = [
[1, 3, 0, 6, 0, 0, 0, 8, 0],
[0, 4, 6, 0, 3, 0, 0, 0, 0],
[0, 2, 0, 5, 0, 0, 0, 0, 0],
[0, 0, 0, 2, 0, 0, 1, 0, 6],
[0, 9, 0, 0, 5, 7, 0, 0, 0],
[8, 0, 0, 0, 0, 0, 0, 4, 5],
[0, 0, 0, 0, 0, 0, 3, 7, 0],
[0, 0, 0, 0, 6, 3, 4, 0, 0],
[0, 0, 0, 0, 0, 0, 5, 0, 1]]
↓ Résultat
4
[[1, 3, 5, 6, 7, 2, 9, 8, 4],
[9, 4, 6, 8, 3, 1, 2, 5, 7],
[7, 2, 8, 5, 4, 9, 6, 1, 3],
[3, 5, 7, 2, 8, 4, 1, 9, 6],
[6, 9, 4, 1, 5, 7, 8, 3, 2],
[8, 1, 2, 3, 9, 6, 7, 4, 5],
[2, 6, 9, 4, 1, 5, 3, 7, 8],
[5, 8, 1, 7, 6, 3, 4, 2, 9],
[4, 7, 3, 9, 2, 8, 5, 6, 1]]
Vous avez terminé! Peut-être que tous les Allemands de ce monde peuvent être résolus avec cette logique? Essayons aussi Expert!
sudoku.ipynb
# expert
list_sudoku = [
[4, 0, 0, 0, 8, 0, 1, 0, 0],
[0, 0, 0, 2, 0, 9, 0, 0, 0],
[0, 0, 0, 7, 3, 0, 0, 0, 0],
[0, 2, 0, 0, 0, 1, 0, 0, 9],
[0, 0, 5, 0, 0, 0, 0, 7, 0],
[0, 9, 0, 0, 0, 0, 0, 5, 0],
[0, 1, 0, 5, 0, 0, 4, 0, 0],
[6, 0, 0, 3, 0, 0, 0, 0, 0],
[0, 0, 4, 0, 0, 7, 6, 0, 3]]
↓ Résultat
3
[[4, [3, 7], [2, 3, 7, 9], 6, 8, 5, 1, [2, 3, 9], [2, 7]],
[[3, 5, 7, 8],
[3, 5, 6, 7, 8],
[3, 6, 7, 8],
2,
1,
9,
[3, 5, 7, 8],
[3, 4, 6, 8],
[4, 5, 6, 7, 8]],
[[1, 2, 5, 8, 9],
[5, 6, 8],
[1, 2, 6, 8, 9],
7,
3,
4,
[2, 5, 8, 9],
[2, 6, 8, 9],
[2, 5, 6, 8]],
[[3, 7, 8], 2, [3, 6, 7, 8], [4, 8], 5, 1, [3, 8], [3, 4, 6, 8], 9],
[[1, 3, 8], 4, 5, 9, [2, 6], [2, 3, 6, 8], [2, 3, 8], 7, [1, 2, 6, 8]],
[[1, 3, 8],
9,
[1, 3, 6, 8],
[4, 8],
7,
[2, 3, 6, 8],
[2, 3, 8],
5,
[1, 2, 4, 6, 8]],
[[2, 3, 7, 8, 9],
1,
[2, 3, 7, 8, 9],
5,
[2, 6, 9],
[2, 6, 8],
4,
[2, 8, 9],
[2, 7, 8]],
[6, [5, 7, 8], [2, 7, 8, 9], 3, 4, [2, 8], [2, 5, 7, 8, 9], 1, [2, 5, 7, 8]],
[[2, 5, 8, 9], [5, 8], 4, 1, [2, 9], 7, 6, [2, 8, 9], 3]]
Oui. Ça n'a pas marché du tout. Est-ce que c'est comme ça dans une table?
Comme prévu, c'est un niveau Expert. Je ne peux pas du tout résoudre ça. Pour aggraver les choses, je n'ai pas l'impression de pouvoir le résoudre moi-même. Que faire maintenant?
Je ne peux pas m'en empêcher, alors je vais tous les essayer dans l'ordre. Il semble que cela puisse être fait de manière récursive.
Tout d'abord, la fonction de vérification des doublons. Vous pouvez le résoudre par round robin, mais vous n'êtes pas obligé d'essayer des nombres dont vous savez déjà qu'ils ne correspondent pas.
sudoku.ipynb
def dup_check(x, y, possible, list_sudoku):
"""
Dans les cellules verticales, horizontales et en bloc
Vérifiez s'il existe déjà des valeurs en double
"""
for pos in range(9):
if list_sudoku[y][pos] == possible or list_sudoku[pos][x] == possible:
return False
index_x = (x // 3) * 3
index_y = (y // 3) * 3
for pos_y in range(index_y, index_y+3):
for pos_x in range(index_x, index_x+3):
if list_sudoku[pos_y][pos_x] == possible:
return False
return True
Et une fonction à résoudre par rond-point. Il y a une boucle infinie s'il y a un problème insoluble, nous avons donc fixé une limite de temps (60 secondes). Le nombre de secondes est approprié.
sudoku.ipynb
def brute_force(list_sudoku, list_ans, x=0, y=0):
"""
Essayez de résoudre par rond-point
Si cela prend plus de 60 secondes, il est jugé qu'il ne peut pas être résolu
"""
if type(list_sudoku[y][x]) is list:
time_process = time.time()
if (time_process - time_start) >= 60:
return False
for possible in list_sudoku[y][x]:
if dup_check(x, y, possible, list_ans):
list_ans[y][x] = possible
if x <= 7:
next_x = x + 1
next_y = y
elif y <= 7:
next_x = 0
next_y = y + 1
else:
return True
if not brute_force(list_sudoku, list_ans, next_x, next_y):
continue
else:
return True
list_ans[y][x] = []
return False
else:
list_ans[y][x] = list_sudoku[y][x]
if x <= 7:
next_x = x + 1
next_y = y
elif y <= 7:
next_x = 0
next_y = y + 1
else:
return True
return brute_force(list_sudoku, list_ans, next_x, next_y)
Que diriez-vous?
sudoku.ipynb
import copy
import time
time_start = time.time()
temp_sudoku = copy.deepcopy(list_sudoku)
list_ans = [[[] for i in range(9)] for j in range(9)]
result = brute_force(temp_sudoku, list_ans)
print(result)
list_ans
↓ Résultat de sortie
True
[[4, 7, 9, 6, 8, 5, 1, 3, 2],
[5, 3, 8, 2, 1, 9, 7, 6, 4],
[1, 6, 2, 7, 3, 4, 5, 9, 8],
[7, 2, 6, 8, 5, 1, 3, 4, 9],
[3, 4, 5, 9, 2, 6, 8, 7, 1],
[8, 9, 1, 4, 7, 3, 2, 5, 6],
[9, 1, 3, 5, 6, 8, 4, 2, 7],
[6, 8, 7, 3, 4, 2, 9, 1, 5],
[2, 5, 4, 1, 9, 7, 6, 8, 3]]
Résolu! Je l'ai fait!
Je voulais le résoudre avec une logique autre que le round robin, mais je ne pouvais pas le résoudre normalement, donc je ne pouvais pas l'implémenter. Si vous recherchez "Comment résoudre quelques Allemands", vous trouverez diverses choses, mais vous ne pouvez pas le résoudre en vous référant à l'une d'elles. .. Je veux faire quelque chose à ce sujet si possible.
Pour le round robin, reportez-vous à ce qui suit. ・ Résoudre les mathématiques avec Python
J'ai allumé l'écran pour pouvoir l'essayer. SUDOKU SOLVER
Recommended Posts