chiark / gitweb /
Patch from Rogier Goossens to speed up the Pattern solver.
authorSimon Tatham <anakin@pobox.com>
Fri, 12 Apr 2013 16:28:55 +0000 (16:28 +0000)
committerSimon Tatham <anakin@pobox.com>
Fri, 12 Apr 2013 16:28:55 +0000 (16:28 +0000)
commit383c15794a517a4e6dc0b7364edac1f7056cee82
tree757bcadc02d842af712ae28397826363c0ef1bc0
parentc94afe9cd6ff0ad719798d7fd6fb842a336f66ed
Patch from Rogier Goossens to speed up the Pattern solver.

do_recurse() now prunes early whenever it encounters a branch of the
search tree inconsistent with existing grid data (rather than the
previous naive approach of proceeding to enumerate all possibilities
anyway and then ruling them out one by one); do_recurse also tries to
split the row up into independent sections where possible; finally the
main solver loop (all three copies of which have now been factored out
into a new solve_puzzle function), instead of simply looping round and
round over all the rows and columns, heuristically looks at the ones
most changed since the last time deduction was attempted on them, on
the basis that that will probably yield the most information the
fastest.

[originally from svn r9828]
LICENCE
pattern.c
puzzles.but