编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。
一个数独。
答案被标成红色。
Note:
- 给定的数独序列只包含数字 1-9 和字符 '.' 。
- 你可以假设给定的数独只有唯一解。
- 给定数独永远是 9x9 形式的。
代码
class Solution:
def solveSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
self.sove(board)
def sove(self,board):
caice = self.findnone(board)
if caice == (10,10):
return True
else:
pg = self.pinggu(board,caice[0],caice[1])
if len(pg) == 0:
return False
else:
for i in pg:
board[caice[0]][caice[1]] = str(i)
if self.isok(board) == True:
return True
else:
if self.sove(board) == True:
return True
else:
board[caice[0]][caice[1]] = "."
def isok(self,nowb):
for i in range(0,len(nowb)):
for j in range(0,len(nowb[i])):
if nowb[i][j] == ".":
return False
return True
def findnone(self,nowb):
for i in range(0,len(nowb)):
for j in range(0,len(nowb[i])):
# print(nowb[i][j])
if nowb[i][j] == ".":
return (i,j)
return (10,10)
def pinggu(self,nowb,ii,jj):
buf = {}
for i in range(0,9):
buf[nowb[ii][i]] = 1
buf[nowb[i][jj]] = 1
for c in [0,3,6]:
# print(c)
for k in [0,3,6]:
if ((ii == c or (ii == (c+1)) or (ii == (c + 2)) ) and ( jj == k or (jj == (k+1)) or (jj == (k+2)))):
for i in range(c,3+c):
for j in range(k,3+k):
# print((i,j))
buf[nowb[i][j]] = 1
res = []
for i in range(1,10):
if str(i) in buf:
pass
else:
res.append(i)
return res
