chiark / gitweb /
Enhance Filling's solver to handle large ghost regions.
authorSimon Tatham <anakin@pobox.com>
Tue, 20 Oct 2015 19:33:53 +0000 (20:33 +0100)
committerSimon Tatham <anakin@pobox.com>
Tue, 20 Oct 2015 19:33:53 +0000 (20:33 +0100)
commit90af15b43ed57a6835091bb1c98227052590b3ea
tree68f4595352c69cc840cb74d30106def87658dcc9
parent3c0b01114ccf6aaead7aede33b4eaa26d325454b
Enhance Filling's solver to handle large ghost regions.

The previous solver could cope with inferring a '1' in an empty
square, but had no deductions that would enable it to infer the
existence of a '4'-sized region in 5x3:52d5b1a5b3. The new solver can
handle that, and I've made a companion change to the clue-stripping
code so that it aims to erase whole regions where possible so as to
actually present this situation to the player.

Current testing suggests that at the smallest preset a nontrivial
ghost region comes up in about 1/3 of games, and at the largest, more
like 1/2 of games. I may yet decide to introduce a difficulty level at
which it's skewed to happen more often still and one at which it
doesn't happen at all; but for the moment, this at least gets the
basic functionality into the code.
filling.c