数独解決プログラムを実装するための Python コード例

最近、私は自分のキャリアのため、関連するプログラムの解決策をオンラインで探しました。

皆さんの Python の学習に役立つことを願っています。 Linux システムに付属の Sudoku ゲームを開いていくつかプレイしてみました。残念ながら、私は数独の初心者で、これまで数独をプレイしたことがなく、混乱する前に数歩も踏み出すことができませんでした。

そこで、コンピューターの強力な計算能力を使って、数独を激しく解くことを計画しました。これは非常に楽しかったです。

以下は、数独プログラムを作成する際の私のアイデアと経験の一部を記録します。

1. 数独ゲームの基本的な解決策

プログラミングは一般的に方法論です。プログラムが何であっても、問題解決プロセスは、コンピューターが実装できるいくつかの単純な方法に分割する必要があります。ことわざにあるように、シンプルさは偉大さにつながります。 0と1しか理解できないコンピュータでは、さらにステップを細分化し、段階的に問題を解決する必要があります。

まず、数独を解くための基本的な概念について考えてみましょう。

数独には横9マス、縦9マスの計81マスがあり、9マスの9マスに分かれています。ルールは簡単です。各グリッドの数字は、水平方向と垂直方向の行および 9 マスのグリッドに同じ数字がないことを確認する必要があります。

したがって、私たちの一般的なアイデアは、1 から始めて、最初の空白から数字を埋めてみるということです。1 が繰り返しなしで縦横 9 個の正方形の要件を満たさない場合は、2 を埋め、というように、数値が入力されます。一時的にルールを満たす数値を入力し、このセルを中断して次のスペースに移動し、プロセスを繰り返します。

特定のスペースに到達し、すでに無数の選択肢があることがわかった場合は、前のセルの 1 つが間違って入力されたことを意味します。その後、前のセルに戻り、前のセルの中断から 9 を試し続けます。間違って埋められたグリッドに到達します。

このようにして、重要な手順を整理できます:

•次のスペースを見つける
•順番にセルに1から9までの数字を埋めていきます
•埋められた数字がルールに従っているかどうかを再帰的に判断します

II. プログラム

は、フィンランドの数学者 Inkara が 3 か月かけて設計した世界で最も難しい Sudoku を使用して、最初に Sudoku をテストしました。以下のように、

は 0 で空間を表し、入れ子になったリストとして数独を表すため、各グリッドの行と列の数は、リスト内の対応する各数値のインデックスと正確になります。

プログラムは次のとおりです:

 #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()

注目に値するのは、使用される再帰的判断により、間違った分岐を選択した場合に、前のレベルに巧妙に戻ることができるということです。具体的な実装は、for ループを使用して、記録ブレーク ポイントに到達するまで 1 から 9 までの数字を連続的に入力することです。次の層の戻り値によってバックトラックするかどうかを決定します。

プログラムの出力は次のとおりです:

[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

プログラムには多くの操作がありますが、それでも非常に高速であることがわかります。

以上が数独解決プログラムを実装するための Python コード例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。