chiark / gitweb /
I am COMPLETELY GORMLESS. The Solo grid generator, when eliminating
authorSimon Tatham <anakin@pobox.com>
Thu, 4 Aug 2005 11:16:10 +0000 (11:16 +0000)
committerSimon Tatham <anakin@pobox.com>
Thu, 4 Aug 2005 11:16:10 +0000 (11:16 +0000)
commite55838bc9b0d173ca539d0cfe714495b5c12b9dd
tree66f953c592e91281755c8dc507e10a1b3f44ed6b
parent414330d9ad00e3b788d48b1d928e46ad7698c508
I am COMPLETELY GORMLESS. The Solo grid generator, when eliminating
clues from a filled grid, was using the algorithm

 - loop over the whole grid looking for a clue (or symmetry group of
   clues) which can be safely removed
 - remove it
 - loop over the whole grid again, and so on.

This was due to my vague feeling that removing one clue might affect
whether another can be removed. Of course this can happen - two
clues can be alternative ways of deducing the same vital fact so
that removing one makes the other necessary - but what _can't_
happen is for removing one clue to make another _become_ removable,
since you can only do that by _adding_ information. In other words,
after testing a clue and determining that it can't be removed, you
never need to test it again. Thus, a much simpler algorithm is

 - loop over the possible clues (or symmetry groups) _once_, in a
   random order
 - for each clue (group), if it is removable, remove it.

This still guarantees to leave the grid in a state where no further
clues can be removed, but it greatly cuts down puzzle generation
time and also simplifies the code. I am a fool for not having
spotted this in three and a half months!

[originally from svn r6160]
solo.c