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)