Developing a constraint formula to identify naked sets
During the development of the sudoku solver it occurred to me that there had to be a better way to look for naked sets than to try a pair, then a triplet etc. I reasoned that there must be a way of expressing that mathematically, whereby all manner of sets pairs , triplets etc could all be identified by means of a single formula. I also hypothesised that ‘hidden sets’ were in fact just a subset of more complex naked sets.. for example a hidden pair might be identified by a related naked quad. I haven’t yet proved this but I have not yet found a hidden set that was not identifiable as a more complex naked set. I would appreciate any input that helps to prove or disprove this theory. Because of this I did not implement a hidden set module in the solver, rather relying on the naked set formula to find them. Another realization that was helpful is that dealing with the list of items in which a particular possibility appears is actually more useful than trying to deal with with list of possibilities that appear in an item, and is key to developing the following formulas.
My approach was to develop an excel formula for identifying all sets. Here is an example of a quad. The sheet and formulas can be downloaded here. The first column contains the possibilities in a region (column, row or box), and the output of the formula is the identification of a naked sets in the last column. I have broken the formula down into a series of columns to better explain the process. This is telling me that items 1,2,3 and 9 together make a group who share the naked quad 1357. This means that 1357 can be eliminated from all items other than 1,2,3 and 9. Of course item 6 is a naked set of only the possibility 8, meaning that 8 could be removed from any other item containing an 8.
Here are the formulas sort: This removes duplicates and sorts the possibilities that have been entered in the first column.=bitAnd(A4) who: This shows which items contain each possibility, 1 through 9.=afsep(“”,IF(bitAnd(B4,C4:C12)<>””,B4:B12,””)) related: This shows which possibilities are related to each other, by identifying which possibilities are shared by a particular item.=afsep(“”,IF(bitAnd(D4,D4:D12)<> “”, B4:B12,””)) Items in set: This shows where possibilities are a subset of all related items.=afsep(“”,IF(bitAnd(C4:C12,E4)=C4:C12,B4:B12,””)) = Naked sets: Finally this identifies which are actually naked sets- where the related items have the same number of members as there are member in the set.IF(LEN(E4)=LEN(F4),E4,””)
You can download sudbittwiddle.xlsm, the test sheet from the download page. You can read more about Bit Twiddling or take a look at the Sudoku Generator and Solver