Exemple de code Python pour implémenter le programme de résolution de Sudoku

Récemment, j'emmène mes enfants apprendre le Sudoku. En raison de ma carrière, j'ai recherché en ligne des solutions à des programmes connexes. Je les partage avec vous ici. J'espère que cela sera utile à tout le monde pour apprendre le python.

<.>J'ai accidentellement découvert un programme fourni avec le système Linux. J'ai ouvert le jeu Sudoku et joué à quelques jeux. Malheureusement, je suis novice en Sudoku, je n'ai jamais joué au Sudoku auparavant et je ne pouvais même pas faire quelques pas avant de me retrouver dans le pétrin.

J'ai donc prévu d'utiliser la puissante puissance de calcul de l'ordinateur pour résoudre violemment le Sudoku, ce qui était assez amusant.

Ce qui suit enregistrera certaines de mes idées et expériences dans l'écriture de programmes de Sudoku.

1. Solution de base au jeu de Sudoku

La programmation en général est une méthodologie. Quel que soit le programme, le processus de résolution de problèmes doit être décomposé en plusieurs méthodes simples que l’ordinateur peut mettre en œuvre. Comme le dit le proverbe, la simplicité mène à la grandeur. Pour un ordinateur qui ne peut comprendre que 0 et 1, il est encore plus nécessaire de subdiviser les étapes et de résoudre le problème étape par étape.

Tout d’abord, réfléchissons aux concepts de base de la résolution du Sudoku.

Le Sudoku compte un total de 81 grilles, neuf horizontalement et neuf verticalement, et est divisé en 9 grilles de neuf carrés. Les règles sont simples : les nombres dans chaque grille doivent garantir qu'il n'y a pas de nombres identiques dans les rangées horizontales et verticales et dans la grille de neuf carrés.

Notre idée générale est donc d'essayer de remplir le nombre à partir du premier blanc, en commençant par 1. Si 1 ne satisfait pas à l'exigence de neuf carrés horizontaux et verticaux sans répétition, alors remplissez 2, et ainsi on Par analogie, jusqu'à ce qu'un nombre qui répond temporairement aux règles soit rempli, la cellule est interrompue et le processus est répété en passant à l'espace suivant.

Si vous atteignez un certain espace et constatez qu'il existe d'innombrables options, cela signifie que l'espace précédent a été mal rempli, puis revenez à l'espace précédent et continuez à essayer 9 depuis l'espace précédent jusqu'à ce que vous reveniez à ce point. Allez dans la mauvaise case.

De cette façon, nous pouvons trier les étapes importantes :

•Trouver l'espace suivant

•Remplir à tour de rôle les chiffres de 1 à 9 dans la cellule
•Juger de manière récursive si le nombre renseigné est conforme aux règles

2. Programme

Premièrement, le test Sudoku utilise un programme conçu par le mathématicien finlandais Inkara qui a passé 3 mois. Le Sudoku le plus difficile jamais créé au monde. Comme suit

représente l'espace avec 0, et représente le Sudoku comme une liste imbriquée, de sorte que le nombre de lignes et de colonnes de chaque grille soit exactement le nombre correspondant de chaque grille dans la liste. L'index du numéro.

Le programme est le suivant :

 #coding=utf-8
 import datetime
 class solution(object):
   def __init__(self,board):
     self.b = board
     self.t = 0
 
   def check(self,x,y,value):#检查每行每列及每宫是否有相同项
     for row_item in self.b[x]:
       if row_item == value:
         return False
     for row_all in self.b:
       if row_all[y] == value:
         return False
     row,col=x/3*3,y/3*3
     row3col3=self.b[row][col:col+3]+self.b[row+1][col:col+3]+self.b[row+2][col:col+3]
     for row3col3_item in row3col3:
       if row3col3_item == value:
         return False
     return True
 
   def get_next(self,x,y):#得到下一个未填项
     for next_soulu in range(y+1,9):
       if self.b[x][next_soulu] == 0:
         return x,next_soulu
     for row_n in range(x+1,9):
       for col_n in range(0,9):
         if self.b[row_n][col_n] == 0:
           return row_n,col_n
     return -1,-1 #若无下一个未填项，返回-1
 
   def try_it(self,x,y):#主循环
     if self.b[x][y] == 0:
       for i in range(1,10):#从1到9尝试
         self.t+=1
         if self.check(x,y,i):#符合 行列宫均无条件 的
           self.b[x][y]=i #将符合条件的填入0格
           next_x,next_y=self.get_next(x,y)#得到下一个0格
           if next_x == -1: #如果无下一个0格
             return True #返回True
           else:    #如果有下一个0格，递归判断下一个0格直到填满数独
             end=self.try_it(next_x,next_y)
             if not end:  #在递归过程中存在不符合条件的，即 使try_it函数返回None的项
               self.b[x][y] = 0  #回朔到上一层继续
             else:
               return True
 
   def start(self):
     begin = datetime.datetime.now()
     if self.b[0][0] == 0:
       self.try_it(0,0)
     else:
       x,y=self.get_next(0,0)
       self.try_it(x,y)
     for i in self.b:
       print i
     end = datetime.datetime.now()
     print '\ncost time:', end - begin
     print 'times:',self.t
     return
 
 
 s=solution([[8,0,0,0,0,0,0,0,0],
     [0,0,3,6,0,0,0,0,0],
     [0,7,0,0,9,0,2,0,0],
     [0,5,0,0,0,7,0,0,0],
     [0,0,0,8,4,5,7,0,0],
     [0,0,0,1,0,0,0,3,0],
     [0,0,1,0,0,0,0,6,8],
     [0,0,8,5,0,0,0,1,0],
     [0,9,0,0,0,0,4,0,0]])
 73 s.start()

Il est à noter que le jugement récursif utilisé peut astucieusement revenir au niveau précédent en prenant la mauvaise branche. L'implémentation spécifique consiste à utiliser une boucle for pour remplir en continu les nombres de 1 à 9 tout en atteignant le point d'interruption de l'enregistrement. Déterminez s’il faut revenir en arrière en fonction de la valeur de retour de la couche suivante.

Le résultat du programme est le suivant :

[8, 1, 2, 7, 5, 3, 6, 4, 9]
[9, 4, 3, 6, 8, 2, 1, 7, 5]
[6, 7, 5, 4, 9, 1, 2, 8, 3]
[1, 5, 4, 2, 3, 7, 8, 9, 6]
[3, 6, 9, 8, 4, 5, 7, 2, 1]
[2, 8, 7, 1, 6, 9, 5, 3, 4]
[5, 2, 1, 9, 7, 4, 3, 6, 8]
[4, 3, 8, 5, 2, 6, 9, 1, 7]
[7, 9, 6, 3, 1, 8, 4, 5, 2]

cost time: 0:00:00.060687
times: 45360

Vous pouvez voir que même si le programme comporte de nombreuses opérations, il est toujours très rapide.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!