Solve the chessbits puzzle using with help from Peter Norvig's Sudoku solver
In [99]:
num_bits = 8
num_elements = 128
bit_mappings = defaultdict(list)
for i in range(num_elements):
bit_mappings[i].append(i)
for bit_index in range(num_bits - 1):
mask = 1 << bit_index
mask2 = num_elements - 1
bit_mappings[i].append((i ^ mask) & mask2)
assert all(len(bit_mappings[i]) == 8 for i in bit_mappings)
In [107]:
# New Version
from collections import defaultdict
# Update the units, rows, peers, digits
digits = ''.join(range(64)) # '12345678'
rows = 'ABCDEFGHIJKLMNOP'
cols = digits
squares = cross(rows, cols)
symmetric_map = dict(zip(squares, squares[::-1]))
units = {}
units = defaultdict(list)
for i, s in enumerate(squares):
for mapped_bit in bit_mappings[i]:
new_unit = [squares[remapped_bit] for remapped_bit in bit_mappings[mapped_bit]]
units[s].append(new_unit)
# get the squares for this unit
peers = {s: set(sum(units[s],[]))-set([s])
for s in squares}
In [122]:
digits = ''.join(str(x) for x in range(64)) # '12345678'
rows = ''.join(str(x) for x in range(64)) # '12345678'
print(digits)
print(rows)
In [111]:
def test():
assert len(squares) == 128
#assert all(len(peers[s]) == 15 for s in squares)
print("All tests pass")
test()
In [112]:
# code for parsing
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) == num_elements
return dict(zip(squares, chars))
In [116]:
# Code for constraint propagation
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):
# Find the symmetric square and eliminate those values as well
# return values
symmetric_square = symmetric_map[s]
if all(eliminate(values, symmetric_square, 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
In [117]:
# Code for displaying
def display(values):
"Display these values as a 2-D grid."
width = 1+max(len(values[s]) for s in squares)
line = '-'* width*8
print(line)
for r in rows:
print(''.join(values[r+c].center(width) for c in cols))
print(line)
print()
grid1 = "12030400050000000600000000000000070000000000000000000000000000800800000000000000000000000000007000000000000000600000005000403021"
display(parse_grid(grid1))
It looks like just constraint propagation is not enough, sadly. We will have to continue searching.
In [118]:
def solve(grid): return search(parse_grid(grid))
def search(values):
"Using depth-first search and propagation, try all possible values."
if not values:
return False ## Failed earlier
if all(len(values[s]) == 1 for s in squares):
return values ## Solved!
# display(values)
# print("press enter")
# _ = input()
## 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
result = solve(grid1)
if(result):
display(result)
else:
print("no solution found")
In [119]:
[result[s] for s in squares]
Out[119]: