我试图用python中的open CV包来解决数独难题。因此,当我试图调用主函数中的solve_sudoku()
函数时,会得到一个错误:
AttributeError: 'bool' object has no attribute 'keys'
这是主要代码:
ans = solve_sudoku(strsudo)
这是解数独代码
import time
import random
def cross(A, B):
"Cross product of elements in A and elements in B."
return [a+b for a in A for b in B]
digits = '123456789'
rows = 'ABCDEFGHI'
cols = digits
squares = cross(rows, cols)
unitlist = ([cross(rows, c) for c in cols] +
[cross(r, cols) for r in rows] +
[cross(rs, cs) for rs in ('ABC', 'DEF', 'GHI')
for cs in ('123', '456', '789')])
units = dict((s, [u for u in unitlist if s in u]) for s in squares)
# print(units)
peers = dict((s, set(sum(units[s], []))-set([s])) for s in squares)
def parse_grid(grid):
"""Convert grid to a dict of possible values, {square: digits}, or
return False if a contradiction is detected."""
# To start, every square can be any digit;
# then assign values from the grid.
values = dict((s, digits) for s in squares)
for s, d in grid_values(grid).items():
if d in digits and not assign(values, s, d):
return False
# (Fail if we can't assign d to square s.)
return values
def grid_values(grid):
"Convert grid into a dict of {square: char} with '0' or '.' for empties."
chars = [c for c in grid if c in digits or c in '0.']
assert len(chars) == 81
return dict(zip(squares, chars))
def assign(values, s, d):
"""Eliminate all the other values (except d) from values[s] and propagate.
Return values, except return False if a contradiction is detected."""
other_values = values[s].replace(d, '')
if all(eliminate(values, s, d2) for d2 in other_values):
return values
else:
return False
def eliminate(values, s, d):
"""Eliminate d from values[s]; propagate when values or places <= 2.
Return values, except return False if a contradiction is detected."""
if d not in values[s]:
return values
# Already eliminated
values[s] = values[s].replace(d, '')
# (1) If a square s is reduced to one value d2,
# then eliminate d2 from the peers.
if len(values[s]) == 0:
return False
# Contradiction: removed last value
elif len(values[s]) == 1:
d2 = values[s]
if not all(eliminate(values, s2, d2) for s2 in peers[s]):
return False
# (2) If a unit u is reduced to only one place for a value d,
# then put it there.
for u in units[s]:
dplaces = [s for s in u if d in values[s]]
if len(dplaces) == 0:
return False
# Contradiction: no place for this value
elif len(dplaces) == 1:
# d can only be in one place in unit; assign it there
if not assign(values, dplaces[0], d):
return False
return values
def display(values):
"Display these values as a 2-D grid."
width = 1+max(len(values[s]) for s in squares)
line = '+'.join(['-'*(width*3)]*3)
for r in rows:
print (''.join(values[r+c].center(width)+('|' if c in '36' else '')
for c in cols))
if r in 'CF':
print(line)
print
def solve(grid): return search(parse_grid(grid))
def search(values):
"Using depth-first search and propagation, try all possible values."
if values is False:
return False
# Failed earlier
if all(len(values[s]) == 1 for s in squares):
return values
# Solved!
# Chose the unfilled square s with the fewest possibilities
n, s = min((len(values[s]), s) for s in squares if len(values[s]) > 1)
return some(search(assign(values.copy(), s, d))
for d in values[s])
def some(seq):
"Return some element of seq that is true."
for e in seq:
if e:
return e
return False
def solve_all(grids, name='', showif=0.0):
"""Attempt to solve a sequence of grids. Report results.
When showif is a number of seconds, display puzzles that take longer.
When showif is None, don't display any puzzles."""
def time_solve(grid):
start = time.clock()
values = solve(grid)
t = time.clock()-start
# Display puzzles that take long enough
if showif is not None and t > showif:
display(grid_values(grid))
if values:
display(values)
print ('(%.2f seconds)\n' % t)
return (t, solved(values))
times, results = zip(*[time_solve(grid) for grid in grids])
N = len(grids)
if N > 1:
print("Solved % d of % d % s puzzles(avg % .2f secs(% d Hz), max % .2f secs)."
% (sum(results), N, name, sum(times)/N, N/sum(times), max(times)))
def solved(values):
"A puzzle is solved if each unit is a permutation of the digits 1 to 9."
def unitsolved(unit): return set(values[s] for s in unit) == set(digits)
return values is not False and all(unitsolved(unit) for unit in unitlist)
def from_file(filename, sep='\n'):
"Parse a file into a list of strings, separated by sep."
# return file(filename).read().strip().split(sep)
pass
def random_puzzle(N=17):
"""Make a random puzzle by making N assignments. Restart on contradictions.
Note the resulting puzzle is not guaranteed to be solvable, but empirically
about 99.8% of them are solvable."""
values = dict((s, digits) for s in squares)
for s in random.sample(squares, N):
if not assign(values, s, random.choice(values[s])):
return random_puzzle(N)
# Give up and make a new puzzle
return ''.join(values[s] if len(values[s]) == 1 else '.' for s in squares)
def shuffled(seq):
"Return a randomly shuffled copy of the input sequence."
seq = list(seq)
random.shuffle(seq)
return seq
grid1 = '003020600900305001001806400008102900700000008006708200002609500800203009005010300'
grid2 = '4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......'
hard1 = '.....6....59.....82....8....45........3........6..3.54...325..6..................'
grid3 = '79......3.......6.8.1..4..2..5......3..1......4...62.92...3...6.3.6.5421.........'
extreme ='.26....1.75......2..86.1.9......3....9.4.8.2....1......1.5.92..6......57.3....98.'
# result = solved(grid_values(extreme))
def solve_sudoku(s):
k = solve(s)
keys = k.keys()
keys.sort()
ans = ''.join(k[i] for i in keys)
return ans
错误:
File "C:\....", line 112, in <module>
ans = solve_sudoku(strsudo)
File "C:.....", line 182, in solve_sudoku
keys = k.keys()
AttributeError: 'bool' object has no attribute 'keys'
我怀疑
parse_grid
正在返回False
,这导致False
从solve
传递到search
。所以search
返回False
,但是solve_sudoku
无法检查它。只需检查从solve
到solve_sudoku
的False
返回值。之所以发生这种情况,是因为
parse_grid
认为它检测到了一个矛盾,即初始状态的不一致。检查grid
参数以查找数据中的错误。相关问题 更多 >
编程相关推荐