| Hafting
| Joined: 19 Dec 2006 | Posts: 12 | : | Location: Trondheim | Items |
|
Posted: Fri Mar 09, 2007 1:12 pm Post subject: Another multicoloring trick |
|
|
I don't know if anyone else have discovered this before, I just found out and programmed this:
When doing a multicoloring, there will sometimes be cases when all the remaining candidates in some house (or a square) is colored. In this case, we know that exactly one of these many colors must be true, and all the others must be false. We don't know which one, of course.
Such a fact can be used in many ways - I started with these:
1. Register all such cases as they get discovered. I.e. a table of colorsets where exactly one must be true. If one such set is a subset of another, then the one true color must be in the smaller set. So the rest of the colors in the bigger set was proved false. This solved 3 more on the top50000 for me.
2. Check each candidate in the sudoku. If one of them can see all the colors in one such set (where one must be true) then we can remove that candidate. This solved further 41 extra of the top50000.
Not exactly a big breakthrough, but it helps, and it didn't slow my program all that much. There may be more too - perhaps more colors can be proven true or false by looking carefully at the colorsets. |
|