need help finding my own solving algorithm on this forum

shoop

I've been looking through the stickies and maybe I'm not looking carefully enough but I was wondering what my sudoku solving algorithm is called - I'm sure it must be well known since it is so simple. Yet it is completely general: it covers all reasoning that can be done without considering multiple houses at once.

It seems extremely related to the concept of "hidden subsets", but it may be slightly more general? It encompasses most simple solving techniques I think: all kinds of cross-hatching and locked candidates. It cannot handle patterns that require chains to be detected, such as x-wing. I'm not sure about strategies such as colouring or patterns, which I don't understand yet. I'm sure it can't handle those either.

1. For each cell, store which digits are still possible (the 'candidates' or 'pencil marks'). Cells for which the digit is given have one candidate, all other cells initially have nine.

2. Repeatedly make deductions within each house until none can be made in any house:

2a. Make a binary table that offsets the nine candidates against the nine cells in the house. (My implementation uses boolean logic and an array of nine ints to do this.) Each entry in the table is set to 'false' if that digit is not allowed in that cell, and 'true' otherwise.

2b. Now look if there are equal rows. If you can find N equal rows in which N elements are true, then this means that those N digits must go into those N places. Therefore those digits cannot occur in any other places. Thus, the corresponding bits can be cleared in all other rows.

2c. The same rule works in the other direction: if you can find N equal columns in which N elements are true, then this means that those N digits have nowhere else to go than into those places, so no other digits can go into those places. Ergo, the corresponding bits are cleared in all other columns.

Steps 2b and 2c are each others mirror image, but for bitvectors rows are easier to handle than columns. I nevertheless implemented only 2b; 2c is obtained by transposing the matrix, applying 2b and transposing again.

So to repeat my question, what is this trick called, if anything?
Thanks.

Ruud · Site Admin

You have implemented a limited search for naked and hidden subsets. If you perform an OR operation in the process, you'll find all subsets.

Here is a link to the topic that describes the method: http://www.setbb.com/sudoku/viewtopic.php?t=231&mforum=sudoku

cheers,
Ruud
_________________
Meet me at sudocue.net

shoop · Posted: Thu Aug 17, 2006 8:06 pm Post subject: