최근에는 아이들과 함께 스도쿠를 배우려고 합니다. 관련 프로그램에 대한 솔루션을 온라인에서 검색해 보았는데, 모든 분들이 Python을 배우는데 도움이 되기를 바랍니다.
우연히 Linux 시스템에 포함된 프로그램을 발견했습니다. 저는 스도쿠 게임을 열고 몇 가지 게임을 했습니다. 불행하게도 저는 스도쿠 초보자입니다. 저는 스도쿠를 한 번도 해본 적이 없고, 몇 걸음도 떼지 못한 채 난장판에 빠졌습니다.
그래서 컴퓨터의 강력한 컴퓨팅 파워를 이용해 격렬하게 스도쿠를 풀려고 했는데 꽤 재미있더군요.
다음은 스도쿠 프로그램 작성에 대한 나의 아이디어와 경험을 기록합니다.
1. 스도쿠 게임의 기본 솔루션
일반적인 프로그래밍은 방법론입니다. 프로그램이 무엇이든 문제 해결 과정은 컴퓨터가 구현할 수 있는 몇 가지 간단한 방법으로 나누어져야 합니다. 속담처럼 단순함이 위대함을 가져온다. 0과 1만 이해할 수 있는 컴퓨터의 경우에는 단계를 세분화하여 문제를 단계별로 풀어나가는 것이 더욱 필요합니다.
먼저 스도쿠 풀이의 기본 개념을 생각해 봅시다.
스도쿠는 가로 9개, 세로 9개 총 81개의 격자로 구성되어 있으며 9개의 정사각형 격자로 나뉩니다. 규칙은 간단합니다. 각 그리드의 숫자는 가로 및 세로 행과 9각형 그리드에 동일한 숫자가 없도록 해야 합니다.
그래서 우리의 일반적인 아이디어는 1부터 시작하여 첫 번째 공백부터 숫자를 채우는 것입니다. 1이 반복 없이 9개의 가로 및 세로 정사각형 요구 사항을 충족하지 않으면 2를 채우는 것입니다. on 비유하자면, 일시적으로 규칙을 만족하는 숫자가 채워질 때까지 이 셀은 중단되고, 다음 공간으로 이동하면서 이 과정이 반복됩니다.
특정 공간에 도달했는데 셀 수 없이 많은 옵션이 있는 경우 이전 공간이 잘못 채워졌다는 의미이며, 이전 공간으로 돌아가서 돌아올 때까지 이전 공간에서 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!