chiark / gitweb /
Bridges solver enhancement. In the stage 3 solver, we were considering
authorSimon Tatham <anakin@pobox.com>
Thu, 31 May 2012 18:10:11 +0000 (18:10 +0000)
committerSimon Tatham <anakin@pobox.com>
Thu, 31 May 2012 18:10:11 +0000 (18:10 +0000)
commit9d2f61dcfa61136c48809345ab484c65d82a4a43
treef074c85b9d9b3e8f2c7dc22f649a757f31303de2
parent00f74d4c7dceef7e21d9895c7a41c7abc777f0ee
Bridges solver enhancement. In the stage 3 solver, we were considering
the possibility that an island might form an isolated subgraph by
connecting to one of its neighbours (and, if so, reducing the maximum
bridge count in that direction so that some bridge would have to go
elsewhere), but we were not also considering the possibility that it
might form an isolated subgraph by connecting to _more_ than one of
its neighbours. For instance, if you have a 3 adjacent to a 1, a 2 and
something else, then at least one bridge must go to the something-else.

Previously insoluble test case:
10x10m2:a2b4a5a2a2a1ga2d3b33a3a4c2aa3e1a22b2a4b4aa3b1a2b33a1e3aa2a1a2c23a3a3a4a2a

[originally from svn r9543]
bridges.c