Chessbits Solver

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)


0123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263
0123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263

In [111]:
def test():
    assert len(squares) == 128
    #assert all(len(peers[s]) == 15 for s in squares)
    print("All tests pass")

test()


All tests pass

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))


------------------------------------------------
  1     2   45678   3   35678   4   25678 15678 
34678   5   24678 14678 23678 13678 12345 12678 
34578   6   24578 14578 23578 13578 12346 12578 
23478 13478 12356 12478 12456 12378 13456 23456 
34568   7   24568 14568 23568 13568 12347 12568 
23468 13468 12357 12468 12457 12368 13457 23457 
23458 13458 12367 12458 12467 12358 13467 23467 
12567 12348 13567 23567 14567 24567   8   34567 
34567   8   24567 14567 23567 13567 12348 12567 
23467 13467 12358 12467 12458 12367 13458 23458 
23457 13457 12368 12457 12468 12357 13468 23468 
12568 12347 13568 23568 14568 24568   7   34568 
23456 13456 12378 12456 12478 12356 13478 23478 
12578 12346 13578 23578 14578 24578   6   34578 
12678 12345 13678 23678 14678 24678   5   34678 
15678 25678   4   35678   3   45678   2     1   
------------------------------------------------

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")


----------------
1 2 4 3 8 4 6 5 
3 5 7 6 2 7 1 8 
5 6 8 7 7 1 3 2 
4 8 2 1 6 3 5 4 
6 7 2 8 5 3 7 1 
8 1 5 4 4 6 3 2 
3 4 1 5 2 8 4 6 
7 2 6 3 1 5 8 7 
7 8 5 1 3 6 2 7 
6 4 8 2 5 1 4 3 
2 3 6 4 4 5 1 8 
1 7 3 5 8 2 7 6 
4 5 3 6 1 2 8 4 
2 3 1 7 7 8 6 5 
8 1 7 2 6 7 5 3 
5 6 4 8 3 4 2 1 
----------------


In [119]:
[result[s] for s in squares]


Out[119]:
['1',
 '2',
 '4',
 '3',
 '8',
 '4',
 '6',
 '5',
 '3',
 '5',
 '7',
 '6',
 '2',
 '7',
 '1',
 '8',
 '5',
 '6',
 '8',
 '7',
 '7',
 '1',
 '3',
 '2',
 '4',
 '8',
 '2',
 '1',
 '6',
 '3',
 '5',
 '4',
 '6',
 '7',
 '2',
 '8',
 '5',
 '3',
 '7',
 '1',
 '8',
 '1',
 '5',
 '4',
 '4',
 '6',
 '3',
 '2',
 '3',
 '4',
 '1',
 '5',
 '2',
 '8',
 '4',
 '6',
 '7',
 '2',
 '6',
 '3',
 '1',
 '5',
 '8',
 '7',
 '7',
 '8',
 '5',
 '1',
 '3',
 '6',
 '2',
 '7',
 '6',
 '4',
 '8',
 '2',
 '5',
 '1',
 '4',
 '3',
 '2',
 '3',
 '6',
 '4',
 '4',
 '5',
 '1',
 '8',
 '1',
 '7',
 '3',
 '5',
 '8',
 '2',
 '7',
 '6',
 '4',
 '5',
 '3',
 '6',
 '1',
 '2',
 '8',
 '4',
 '2',
 '3',
 '1',
 '7',
 '7',
 '8',
 '6',
 '5',
 '8',
 '1',
 '7',
 '2',
 '6',
 '7',
 '5',
 '3',
 '5',
 '6',
 '4',
 '8',
 '3',
 '4',
 '2',
 '1']