请教Leetcode 上的 Sudoku solver# JobHunting - 待字闺中
T*s
1 楼
用python 实现，可是不知道问题出在哪里，结果显示output 和 input 一模一样。
请教大家。
谢谢。
~~~~~~~~~~~~~~~~~
class Solution:
# @param board, a 9x9 2D array
# Solve the Sudoku by modifying the input board in-place.
# Do not return any value.
class _State:
def __init__(self, board, row, col, rowsum, colsum, blocksum):
# board --- the board at the current state
# whichRow and whichCol --- row and col indices that need to
work
on (unfilled)
# rowStat, colStat and blockStat are 1D or 2D arrays that record
presence of elements
self.board = board
self.row, self.col = row, col
self.rowsum, self.colsum, self.blocksum = rowsum, colsum,
blocksum
def solveSudoku(self, board):
D1 = {str(i): (2 ** (i - 1)) for i in range(1, 10)}
D2 = {(2 ** (i - 1)): str(i) for i in range(1, 10)}
nb = [[D1.get(e, 0) for e in line] for line in board] # new board
in
2 ** k
rs = [sum(line) for line in nb] # rowsum
cs = [sum([line[j] for line in nb]) for j in range(9)] # colsum
bs = [[0] * 3] * 3 # blocksum
for i in range(3):
for j in range(3):
for m in range(3):
for n in range(3):
bs[i][j] += nb[m + 3 * i][n + 3 * j]
stack = [self._State(nb, 0, 0, rs, cs, bs)]
while len(stack) > 0:
state = stack.pop()
state.row, state.col = 0, 0
while state.row < 9 and state.col < 9 and
state.board[state.row][state.col] != 0:
state.col += 1
if state.col == 9:
state.row += 1
state.col = 0
if state.row == 9: break
for v in D1.values():
if v & state.rowsum[state.row] != 0: continue
if v & state.colsum[state.col] != 0: continue
if v & state.blocksum[state.row // 3][state.col // 3] != 0:
continue
nnb = state.board
nnb[state.row][state.col] = v
nrs = state.rowsum
nrs[state.row] += v
ncs = state.colsum
ncs[state.col] += v
nbs = state.blocksum
nbs[state.row // 3][state.col // 3] += v
stack.append(self._State(nnb, 0, 0, nrs, ncs, nbs))
board = ["".join([str(D2.get(num,"")) for num in line]) for line in
state.board]
return None
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
请教大家。
谢谢。
~~~~~~~~~~~~~~~~~
class Solution:
# @param board, a 9x9 2D array
# Solve the Sudoku by modifying the input board in-place.
# Do not return any value.
class _State:
def __init__(self, board, row, col, rowsum, colsum, blocksum):
# board --- the board at the current state
# whichRow and whichCol --- row and col indices that need to
work
on (unfilled)
# rowStat, colStat and blockStat are 1D or 2D arrays that record
presence of elements
self.board = board
self.row, self.col = row, col
self.rowsum, self.colsum, self.blocksum = rowsum, colsum,
blocksum
def solveSudoku(self, board):
D1 = {str(i): (2 ** (i - 1)) for i in range(1, 10)}
D2 = {(2 ** (i - 1)): str(i) for i in range(1, 10)}
nb = [[D1.get(e, 0) for e in line] for line in board] # new board
in
2 ** k
rs = [sum(line) for line in nb] # rowsum
cs = [sum([line[j] for line in nb]) for j in range(9)] # colsum
bs = [[0] * 3] * 3 # blocksum
for i in range(3):
for j in range(3):
for m in range(3):
for n in range(3):
bs[i][j] += nb[m + 3 * i][n + 3 * j]
stack = [self._State(nb, 0, 0, rs, cs, bs)]
while len(stack) > 0:
state = stack.pop()
state.row, state.col = 0, 0
while state.row < 9 and state.col < 9 and
state.board[state.row][state.col] != 0:
state.col += 1
if state.col == 9:
state.row += 1
state.col = 0
if state.row == 9: break
for v in D1.values():
if v & state.rowsum[state.row] != 0: continue
if v & state.colsum[state.col] != 0: continue
if v & state.blocksum[state.row // 3][state.col // 3] != 0:
continue
nnb = state.board
nnb[state.row][state.col] = v
nrs = state.rowsum
nrs[state.row] += v
ncs = state.colsum
ncs[state.col] += v
nbs = state.blocksum
nbs[state.row // 3][state.col // 3] += v
stack.append(self._State(nnb, 0, 0, nrs, ncs, nbs))
board = ["".join([str(D2.get(num,"")) for num in line]) for line in
state.board]
return None
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
