Je veux résoudre SUDOKU

introduction

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.

Quels sont les défis?

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.

la mise en oeuvre

problème

Par exemple, si le problème suivant ... easy.jpg

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]]

Fonction pour restreindre les candidats

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!

Essayez de résoudre Facile

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. meduim_in_process.jpg

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".

Une fonction qui trouve la réponse en la comparant avec d'autres candidats de cellule

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!

Essayez de résoudre Medium

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.

Essayez de résoudre dur

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?

expert_in_process.jpg

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?

Une fonction à résoudre par round robin

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)

Essayez de résoudre Expert

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!

finalement

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.

référence

Pour le round robin, reportez-vous à ce qui suit. ・ Résoudre les mathématiques avec Python

Au fait

J'ai allumé l'écran pour pouvoir l'essayer. SUDOKU SOLVER

Recommended Posts

Je veux résoudre SUDOKU
J'ai essayé de laisser optuna résoudre le nombre
Je veux résoudre APG4b avec Python (chapitre 2)
Je veux comprendre à peu près systemd
Je veux gratter des images et les former
Je veux faire ○○ avec les Pandas
Je veux copier l'annotation de yolo
Je veux déboguer avec Python
Vous voulez résoudre un problème de classification simple?
Je veux détecter des objets avec OpenCV
Je veux imprimer dans la notation d'inclusion
Je veux les gratter tous ensemble.
Je veux résoudre APG4b avec Python (seulement 4.01 et 4.04 au chapitre 4)
Je veux savoir comment fonctionne LINUX!
Je veux écrire un blog avec Jupyter Notebook
Je veux utiliser jar de python
Je voulais résoudre ABC160 avec Python
Je veux créer un environnement Python
Je veux utiliser Linux sur mac
Je veux installer Python avec PythonAnywhere
Je veux analyser les journaux avec Python
Je veux jouer avec aws avec python
Je souhaite utiliser la console IPython Qt
Je voulais résoudre ABC159 avec Python
Je veux afficher la barre de progression
Je veux faire un programme d'automatisation!
J'ai essayé de résoudre TSP avec QAOA
Je veux intégrer Matplotlib dans PySimpleGUI
Je voulais résoudre ABC172 avec Python
Je veux gérer la rime part2
Je souhaite développer des applications Android sur Android
Je veux que CAPTCHA dise des mots HIWAI
Je veux gérer la rime part5
Je veux gérer la rime part4
Je veux faire de matplotlib un thème sombre
Je souhaite me connecter à PostgreSQL à partir de plusieurs langues
Je veux faire le test de Dunnett en Python
Je veux pouvoir penser à la récurrence
Je veux corriger Datetime.now dans le test de Django
Je veux INSÉRER un DataFrame dans MSSQL
Je voulais résoudre NOMURA Contest 2020 avec Python
Je veux mémoriser, y compris les arguments de mots clés de Python
Je veux créer une fenêtre avec Python
Quoi qu'il en soit, je veux vérifier facilement les données JSON
[Python] Je veux gérer 7DaysToDie depuis Discord! 1/3
Je veux moquer datetime.datetime.now () même avec pytest!
Je veux frapper 100 sciences des données avec Colaboratory
Je veux faire un jeu avec Python
Je veux visualiser les fichiers csv en utilisant Vega-Lite!
Je veux être OREMO avec setParam!
Je ne veux pas passer un test de codage
Je souhaite stocker les informations de la base de données dans la liste
Je veux fusionner des dictionnaires imbriqués en Python
Je veux faire des crises de ma tête
Je veux gérer systemd par fuseau horaire! !!
Je souhaite utiliser le répertoire temporaire avec Python2
Je veux obtenir les données de League of Legends ③
Je veux obtenir les données de League of Legends ②