Screwing around on Neo4j to implement a graphing Minesweeper solver.

neo4j_minesweeper.py

##
# Define observations
observations = {
    'v': (1, 'ab'),
    'w': (2, 'abc'),
    'x': (2,  'bcd'),
    'y': (2,   'cde'
                 'f'
                 'g'),

    'z': (1,     'f'
                 'g')
}

##
# Connect to Neo4j
from py2neo import Graph
graph = Graph(auth=('minesweeper', 'minesweeper'))


##
# Setup Neo models
from py2neo.ogm import GraphObject, Property, RelatedFrom, RelatedTo


class Cell(GraphObject):
    __primarykey__ = 'label'

    label = Property()


class Observation(GraphObject):
    __primarykey__ = 'label'

    label = Property()

    scenarios = RelatedFrom('Scenario', 'SATISFIES')


class Scenario(GraphObject):
    __primarykey__ = '__id__'

    label = Property()
    num_cells = Property()

    cells = RelatedTo(Cell, 'INCLUDES')


class Truth(GraphObject):
    __primarykey__ = 'label'

    label = Property()

    cells = RelatedTo(Cell, 'IMPLIES')


##
# Reset graph state
graph.delete_all()


##
# Fill graph with observations
from itertools import combinations

truth = Truth()
truth.label = 'The True True'
graph.push(truth)


cell_labels = {cell for mines, cells in observations.values() for cell in cells}
all_cells = {}
for label in cell_labels:
    cell = Cell()
    cell.label = label
    graph.merge(cell)
    all_cells[label] = cell


for label, (mines, cells) in observations.items():
    observation = Observation()
    observation.label = label

    for combination in combinations(cells, mines):
        scenario = Scenario()
        scenario.label = ''.join(combination)
        scenario.num_cells = len(combination)


        for cell in combination:
            scenario.cells.add(all_cells[cell])

        # Because we don't use a primary key, merging is weird for Scenarios.
        # We manually push, so we don't find whole scenarios or rels missing
        graph.push(scenario)

        observation.scenarios.add(scenario)

    graph.merge(observation)


##
# Remove invalid scenarios

# This removes any scenarios completely containing two or more other scenarios.
graph.run('''

    MATCH 
        (super:Observation)<-[:SATISFIES]-(super_s:Scenario)-[:INCLUDES]->(c:Cell),
        (sub:Observation)<-[:SATISFIES]-(sub_s:Scenario)-[:INCLUDES]->(c)

    WHERE
        super_s.num_cells > sub_s.num_cells

    WITH DISTINCT
        super,
        super_s,
        sub

    MATCH
        (sub)<-[:SATISFIES]-(sub_p1:Scenario)-[:INCLUDES]->(c1:Cell),
        (sub)<-[:SATISFIES]-(sub_p2:Scenario)-[:INCLUDES]->(c2:Cell),
        (super_s)-[:INCLUDES]->(c1),
        (super_s)-[:INCLUDES]->(c2)
    
    WHERE
        sub_p1 <> sub_p2 AND
        c1 <> c2

    DETACH DELETE super_s

''')


##
# Mark cells that are definitely mines

# We know a mine is a cell if all of an Observation's Scenarios include it
graph.run('''

    MATCH
        (truth:Truth),
        (observation:Observation)<-[:SATISFIES]-(scenario:Scenario)-[:INCLUDES]->(cell:Cell)

    WHERE NOT (truth)-[:IMPLIES]->(cell)

    WITH DISTINCT
        truth,
        observation,
        COLLECT(scenario) AS scenarios,
        COLLECT(cell) AS all_cells

    UNWIND all_cells AS cell
    MATCH (cell)
    WHERE
        ALL(scenario IN scenarios WHERE (scenario)-[:INCLUDES]->(cell)) AND
        NOT (truth)-[:IMPLIES]->(cell)  // prevent dupes
    CREATE (truth)-[:IMPLIES]->(cell)

''')


##
# Prune any non-True-mine-containing siblings of True-mine-containing Scenarios

# If any of an Observation's Scenarios include a True mine, any Scenarios of
# that Observation *not* including that True mine are invalid. We delete.
graph.run('''

    MATCH
        (:Truth)-[:IMPLIES]->(cell:Cell),
        (observation:Observation)<-[:SATISFIES]-(:Scenario)-[:INCLUDES]->(cell)

    WITH DISTINCT
        cell,
        observation

    MATCH (scenario:Scenario)-[:SATISFIES]->(observation)
    WHERE NOT (scenario)-[:INCLUDES]->(cell)

    DETACH DELETE scenario

''')


##
# Remove True mines from Scenarios

# Any cell included in all scenarios of an observation can simply be presumed.
# Since we have already removed non-True-mine-containing scenarios of
# observations touching a True mine, we can safely remove True mines from any
# scenarios.
graph.run('''

    MATCH
        (:Truth)-[:IMPLIES]->(cell:Cell),
        (scenario:Scenario)-[rel:INCLUDES]->(cell)

    DELETE rel
    SET scenario.label = replace(scenario.label, cell.label, ''),
        scenario.num_cells = scenario.num_cells - 1

''')


##
# Dedupe scenarios

# The last stage leaves the graph in an intermediate step -- before removing
# True mines from Scenarios, each Scenario completely satisfied its Observation.
# Now, some Scenarios are mutually exclusive with each other, while others
# require another sibling Scenario to satisfy their Observation.

# This state is only possible because A Big, Bad Observation contains all the
# scenarios of an Underdog Observation. Our Underdog isn't trying to cheat the
# system: each of its Scenarios will completely satisfy the Underdog.

# So, here we remove any Underdogs' scenarios from Big, Bad Observations that
# are supersets of Underdog.
graph.run('''

    // This could prolly be optimized

    MATCH
        (underdog:Observation)<-[:SATISFIES]-(underdog_s:Scenario)-[:INCLUDES]->(cell:Cell),
        (big_bad:Observation)<-[:SATISFIES]-(big_bad_s:Scenario)-[:INCLUDES]->(cell)

    OPTIONAL MATCH
        (underdog_s) // WIP ****************************

    WHERE
        big_bad_s.num_cells = underdog_s.num_cells

    WITH DISTINCT
        big_bad,
        underdog

    MATCH
        (underdog)<-[:SATISFIES]-(underdog_s:Scenario)

    WITH
        big_bad,
        COLLECT(underdog_s) AS underdog_scenarios

    MATCH
        (big_bad)

    WHERE
        all(scenario IN underdog_scenarios
            WHERE )

''')