[PYTHON] 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.

• Easy
• Medium
• Hard
• Expert

J'essaierai de résoudre une question chacun.

la mise en oeuvre

problème

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

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.

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?

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