| 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667 |
- from graphviz import Digraph
- from chess_state import ChessState
- proof = Digraph(format='svg', node_attr={'shape': 'record'}, comment='Proof that chess domino is not possible')
- def state_id(index):
- return f'state{index}'
- class Solver:
- def __init__(self, board_size=8):
- self.board_size = board_size
- self.steps = 1
- self.starting_state = ChessState(board_size=board_size)
- self.states = [self.starting_state]
- def solvable(self, state):
- current_id = len(self.states) - 1
- x, y = state.next_move()
- if x is None:
- return True # end of board
- for direction in ['right', 'down']:
- if state.possible(x, y, direction):
- next_state = state.put(x, y, direction)
- self.steps += 1
- found_symmetry = -1
- # look for symmetry
- for i, b in enumerate(self.states):
- if next_state.symmetric_to(b):
- print(f'found symmetry between states {current_id} and {i}')
- found_symmetry = i
- break
- # symmetry found
- if found_symmetry != -1:
- proof.edge(state_id(current_id),
- state_id(found_symmetry),
- label=f'put next brick facing {direction} at {(x,y)}')
- continue
- # pace next brick
- self.states.append(next_state)
- next_id = len(self.states) - 1
- proof.edge(state_id(current_id),
- state_id(next_id),
- label=f'put next brick facing {direction} at {(x,y)}')
- proof.node(name=state_id(next_id), label=next_state.board_label())
- # try to solve the remaining board
- if self.solvable(next_state):
- return True
- return False
- if __name__ == '__main__':
- s = Solver()
- proof.node(name=state_id(0), label=s.starting_state.board_label())
- result = s.solvable(s.starting_state)
- print('solvable:', result)
- print('steps:', s.steps)
- print('states:', len(s.states))
- # proof.render(f'img/proof.gv', view=False)
|
