스도쿠 해결 프로그램을 구현하기 위한 Python 코드 예제

최근에는 아이들과 함께 스도쿠를 배우려고 합니다. 관련 프로그램에 대한 솔루션을 온라인에서 검색해 보았는데, 모든 분들이 Python을 배우는데 도움이 되기를 바랍니다.

우연히 Linux 시스템에 포함된 프로그램을 발견했습니다. 저는 스도쿠 게임을 열고 몇 가지 게임을 했습니다. 불행하게도 저는 스도쿠 초보자입니다. 저는 스도쿠를 한 번도 해본 적이 없고, 몇 걸음도 떼지 못한 채 난장판에 빠졌습니다.

그래서 컴퓨터의 강력한 컴퓨팅 파워를 이용해 격렬하게 스도쿠를 풀려고 했는데 꽤 재미있더군요.

다음은 스도쿠 프로그램 작성에 대한 나의 아이디어와 경험을 기록합니다.

1. 스도쿠 게임의 기본 솔루션

프로그래밍은 일반적으로 방법론입니다. 프로그램이 무엇이든 문제 해결 과정은 컴퓨터가 구현할 수 있는 몇 가지 간단한 방법으로 나누어져야 합니다. 속담처럼 단순함이 위대함을 가져온다. 0과 1만 이해할 수 있는 컴퓨터의 경우에는 단계를 세분화하여 문제를 단계별로 풀어나가는 것이 더욱 필요합니다.

먼저 스도쿠 풀이의 기본 개념을 생각해 봅시다.

스도쿠는 가로 9개, 세로 9개 총 81개의 격자로 구성되어 있으며 9개의 정사각형 격자로 나뉩니다. 규칙은 간단합니다. 각 그리드의 숫자는 가로 및 세로 행과 9각형 그리드에 동일한 숫자가 없도록 해야 합니다.

그래서 우리의 일반적인 아이디어는 첫 번째 공백부터 시작하여 1부터 시작하여 숫자를 채우는 것입니다. 1이 반복 없이 9개의 가로 및 세로 정사각형 요구 사항을 충족하지 않으면 2를 채우고 등등 비유하자면 일시적으로 규칙에 맞는 숫자가 채워질 때까지 셀이 중단되고 다음 공간으로 이동하면서 과정이 반복됩니다.

특정 공간에 도달했는데 셀 수 없이 많은 옵션이 있는 것을 발견하면 이전 사각형이 잘못 채워졌음을 의미합니다. 그런 다음 이전 사각형으로 돌아가서 이전 사각형이 중단된 후부터 까지 9번을 계속 시도합니다. 이 지점으로 돌아갑니다. 잘못된 상자로 이동합니다.

이런 방법으로 중요한 단계를 정리할 수 있습니다.

•다음 공백 찾기
•셀에 1부터 9까지의 숫자를 차례로 입력하세요
•입력한 숫자가 규칙에 맞는지 재귀적으로 판단

2. 프로그램

먼저, 스도쿠 테스트는 핀란드의 수학자 잉카라가 고안한 프로그램을 사용합니다. 3개월 세상에서 가장 어려운 스도쿠입니다. 다음과 같이

은 공백을 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!