search

fiveham / Sudoku_Solver

Solve sudoku puzzles by representing the puzzle as a bipartite graph of truth-claims about cells' values and rule-statements that have exactly one true neighbor and removing edges as information is added
MIT License
0 stars 0 forks source link

Xor-chain pairs (in ColorChain) are tested by brute force #4

Closed fiveham closed 8 years ago

fiveham commented 8 years ago

Currently, given n xor-chains, tests between chains for bridge interactions take O(n^2) time. Bridges between xor-chains can be found in O(n) time by first creating a Map from Claims of a chain to the chain, iterating over a collection of the chains, and for each chain, bridging Facts are detected, and those bridging Facts that contain Claims that map to another chain constitute the analysable link between two chains.

fiveham commented 8 years ago

Implementing the XY-Chain technique as a subtechnique of ColorChain (since both involve analysis of size-2 Facts vis-a-vis those Facts' two states) has allowed bridge analysis to be subsumed under XY-Chain analysis and to be removed from the program.