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 :•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
#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()[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
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!
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
