Sudoku multiples algorithm

[Default User]

I'm working on a Sudoku solver (everybody else is doing it, I just want
to be popular). If you aren't familiar with the game, be warned that
I'm assuming some familiarity. Also, I know there are web forums
dealing specifically with this topic, but I don't like web forums that
much and I don't want to go around joining stuff.

Right now I'm looking at eliminating possibles by identifying multiples
of some cardinality in a block, row, or column. For ease of display,
I'll use columns.

Let's assume a cardinality of three (triples). Some are easy to
identify, like:

149
14
49

Here, all you have to do is find one tuple that has a number of
elements that matches the cardinality you're looking for, then check
all other possibles that have the same number of elements or fewer to
see if those possibles are a subset of the first.

The tricky one is something like:

19
14
49

That still forms a 149 triple, but how to identify it? A real brute
force method is to form every possible n-tuple for the available
possibles, but that's not elegant and would be rather wasteful.

Any ideas? I googled a bit and didn't find a good answer to my
question, but if someone has a web site that discusses this question,
that would be helpful.



Brian

[[jongware]]

Post by Default User
I'm working on a Sudoku solver (everybody else is doing it, I just want
to be popular). If you aren't familiar with the game, be warned that
I'm assuming some familiarity. Also, I know there are web forums
dealing specifically with this topic, but I don't like web forums that
much and I don't want to go around joining stuff.
Right now I'm looking at eliminating possibles by identifying multiples
of some cardinality in a block, row, or column. For ease of display,
I'll use columns.
Let's assume a cardinality of three (triples). Some are easy to
149
14
49
Here, all you have to do is find one tuple that has a number of
elements that matches the cardinality you're looking for, then check
all other possibles that have the same number of elements or fewer to
see if those possibles are a subset of the first.
19
14
49
That still forms a 149 triple, but how to identify it? A real brute
force method is to form every possible n-tuple for the available
possibles, but that's not elegant and would be rather wasteful.
Any ideas? I googled a bit and didn't find a good answer to my
question, but if someone has a web site that discusses this question,
that would be helpful.

Bit masks can be useful here. For every cell, create a bit mask with the
bits set for the possibilities in that cell. OR them together and count the
bits -- if it is 3 you have a triple somewhere.
You need some additional checking for "special" cases such as
1
23
123
which *will* report a triple if you check too soon. A hidden triple like
A:1234
B:12
C:235
needs to be ANDed first in each combination, resulting in 3 new numbers
(A&B=12, A&C=23, B&C=2) which only hold bits which are also in one of the
*other* cells. The 'visible' triple is actually a special case of this.

[Jongware]

[Default User]

Post by [jongware]

Post by Default User
I'm working on a Sudoku solver (everybody else is doing it, I just
want to be popular). If you aren't familiar with the game, be
warned that I'm assuming some familiarity. Also, I know there are
web forums dealing specifically with this topic, but I don't like
web forums that much and I don't want to go around joining stuff.
Right now I'm looking at eliminating possibles by identifying
multiples of some cardinality in a block, row, or column. For ease
of display, I'll use columns.
Let's assume a cardinality of three (triples). Some are easy to
149
14
49
Here, all you have to do is find one tuple that has a number of
elements that matches the cardinality you're looking for, then check
all other possibles that have the same number of elements or fewer
to see if those possibles are a subset of the first.
19
14
49
That still forms a 149 triple, but how to identify it? A real brute
force method is to form every possible n-tuple for the available
possibles, but that's not elegant and would be rather wasteful.
Any ideas? I googled a bit and didn't find a good answer to my
question, but if someone has a web site that discusses this
question, that would be helpful.

Bit masks can be useful here. For every cell, create a bit mask with
the bits set for the possibilities in that cell. OR them together and
count the bits -- if it is 3 you have a triple somewhere.

That sounds good. I'm working in C, so bit-fiddling's is easy.

Post by [jongware]
You need some additional checking for "special" cases such as
1
23
123
which will report a triple if you check too soon.

I think I have adequate checks for singles in place, but I'll review it.

A hidden triple like

Post by [jongware]
A:1234
B:12
C:235
needs to be ANDed first in each combination, resulting in 3 new
numbers (A&B=12, A&C=23, B&C=2) which only hold bits which are also
in one of the *other* cells. The 'visible' triple is actually a
special case of this.

That's good, that can take care of an extra check I wasn't even going
to deal with yet.

Thanks.



Brian

[Default User]

Post by [jongware]

Post by Default User
I'm working on a Sudoku solver
Right now I'm looking at eliminating possibles by identifying
multiples of some cardinality in a block, row, or column.

Bit masks can be useful here. For every cell, create a bit mask with
the bits set for the possibilities in that cell. OR them together and
count the bits -- if it is 3 you have a triple somewhere.

I guess I'm not following this.

Here's an example of cells in a column and their possibles:

cell 1: 123
cell 2: 12
cell 3: 2345
cell 4: 369
cell 5: 123
cell 6: 56
cell 7: 258
cell 8: 3456
cell 9: 789

Clearly this has a 123 triple in it. Using the LSB to indicate "1" and
so on, the cell mask bit patterns would be:

cell 1: 123: 000000111
cell 2: 12: 000000011
cell 3: 2345: 000011110
cell 4: 369: 100100100
cell 5: 123: 000000111
cell 6: 56: 000110000
cell 7: 258: 010010010
cell 8: 3456: 000111100
cell 9: 789: 111000000


ORing all those together is going to give you 111111111, for a bit
count of 9. What am I missing?



Brian

[[Jongware]]

Post by Default User

Post by [jongware]

Post by Default User
I'm working on a Sudoku solver
Right now I'm looking at eliminating possibles by identifying
multiples of some cardinality in a block, row, or column.

Bit masks can be useful here. For every cell, create a bit mask with
the bits set for the possibilities in that cell. OR them together and
count the bits -- if it is 3 you have a triple somewhere.

I guess I'm not following this.
cell 1: 123
cell 2: 12
cell 3: 2345
cell 4: 369
cell 5: 123
cell 6: 56
cell 7: 258
cell 8: 3456
cell 9: 789
Clearly this has a 123 triple in it. Using the LSB to indicate "1" and
cell 1: 123: 000000111
cell 2: 12: 000000011
cell 3: 2345: 000011110
cell 4: 369: 100100100
cell 5: 123: 000000111
cell 6: 56: 000110000
cell 7: 258: 010010010
cell 8: 3456: 000111100
cell 9: 789: 111000000
ORing all those together is going to give you 111111111, for a bit
count of 9. What am I missing?

The obvious.
Suppose you have a solved sudoku. Cell values are [123456789], so each cell
has one (1) bit set on each position. Just ORing all of them together yields
'111111111', which *is* correct. The 'obvious' part comes from the fact that
in every single row or column *at least* every digit (thus bit) appears
once.

[Jongware]

[Default User]

Post by [Jongware]

Post by Default User

Post by [jongware]
Bit masks can be useful here. For every cell, create a bit mask
with the bits set for the possibilities in that cell. OR them
together and count the bits -- if it is 3 you have a triple

Clearly this has a 123 triple in it. Using the LSB to indicate "1"
cell 1: 123: 000000111
cell 2: 12: 000000011
cell 3: 2345: 000011110
cell 4: 369: 100100100
cell 5: 123: 000000111
cell 6: 56: 000110000
cell 7: 258: 010010010
cell 8: 3456: 000111100
cell 9: 789: 111000000
ORing all those together is going to give you 111111111, for a bit
count of 9. What am I missing?

The obvious.
Suppose you have a solved sudoku. Cell values are [123456789], so
each cell has one (1) bit set on each position. Just ORing all of
them together yields '111111111', which is correct. The 'obvious'
part comes from the fact that in every single row or column *at
least* every digit (thus bit) appears once.

Originally you said to set a bit for every possibility in a cell. So a
solved one would have no bits set in any cell, every bit mask would be
000000000. What should the bit masks for the example I gave have looked
like?



Brian

[Arthur J. O'Dwyer]

Post by Default User

Post by [Jongware]

Post by Default User

Post by [jongware]
Bit masks can be useful here. For every cell, create a bit mask
with the bits set for the possibilities in that cell. OR them
together and count the bits -- if it is 3 you have a triple

Clearly this has a 123 triple in it. Using the LSB to indicate "1"
cell 1: 123: 000000111
cell 2: 12: 000000011
cell 3: 2345: 000011110
cell 4: 369: 100100100
cell 5: 123: 000000111
cell 6: 56: 000110000
cell 7: 258: 010010010
cell 8: 3456: 000111100
cell 9: 789: 111000000
ORing all those together is going to give you 111111111, for a bit
count of 9. What am I missing?

The obvious.
Suppose you have a solved sudoku. Cell values are [123456789], so
each cell has one (1) bit set on each position. Just ORing all of
them together yields '111111111', which is correct. The 'obvious'
part comes from the fact that in every single row or column *at
least* every digit (thus bit) appears once.

Originally you said to set a bit for every possibility in a cell. So a
solved one would have no bits set in any cell, every bit mask would be
000000000. What should the bit masks for the example I gave have looked
like?

No; in a solved sudoku, there is exactly /one/ possibility in each cell,
so ORing them all together gives 111111111 as Jongware stated.
If you ever OR everything together and get something with zeros in it,
then you've made a mistake and need to backtrack. However, I don't see
how this is such a useful insight, or how it has any relationship to
finding "triples" (which I still don't know what they are), so maybe it's
not Jongware's point.

Personally, as a programmer who considers sudoku "rote computation,"
I see no reason to bother with triples or X-wings or Death Stars or
whatever other shortcuts humans have come up with. Just put all the
possibilities in a matrix and brute-force it. It takes less than a
second, works all the time, and scales in the obvious way to bigger
or funny-shaped grids.

-Arthur

[Richard Heathfield]

Post by Arthur J. O'Dwyer
Personally, as a programmer who considers sudoku "rote computation,"
I see no reason to bother with triples or X-wings or Death Stars or
whatever other shortcuts humans have come up with. Just put all the
possibilities in a matrix and brute-force it. It takes less than a
second, works all the time, and scales in the obvious way to bigger
or funny-shaped grids.

One of the rules of Sudoku is that the solution must be unique. In a really
tough Sudoku, you may decide to guess at the contents of a particular cell.
If that leads to a situation such as this:

+-------+-------+-------+
| 1 2 . | 4 5 . | 7 8 . |
| 4 5 . | 7 8 . | 1 2 . |
| 7 8 . | 1 2 . | 4 5 . |
+-------+-------+-------+
| 2 3 1 | 5 6 4 | 8 9 7 |
| 5 6 4 | 8 9 7 | 2 3 1 |
| 8 9 7 | 2 3 1 | 5 6 4 |
+-------+-------+-------+
| 3 1 2 | 6 4 5 | 9 7 8 |
| 6 4 5 | 9 7 8 | 3 1 2 |
| 9 7 8 | 3 1 2 | 6 4 5 |
+-------+-------+-------+

then there is no way to tell where the 3s, 6s, and 9s go, in the top three
rows; that is, there is no unique solution, and so you know your original
guess was wrong.

If you brute-force it and find more than one solution, all but one of them
is invalid. To find out which, you simply have to do the analysis.

So brute force is not actually a valid way to solve this problem. At best,
it will give you a set of possibilities. What you /can/ do, then, is to
find out which numbers are in the same place in all of those final grids.

This might sound like a reasonable strategy, but there's another problem. If
you take a typical Sudoku, with perhaps 27 of the cells filled for you,
then there are 54 cells left to fill. If we assume (and it's a big
assumption, but it simplifies the mathematics) that you're given three 1s,
three 2s, three 3s, etc, then you have to work through 9! * 6! combinations
in your brute force - a total of 261,273,600 combinations. Each has to be
checked for validity. Assuming you can generate a candidate solution and
check it for validity in 1 millisecond (which is probably a bit
optimistic), you're looking at around 3 days of computation - with no
guarantee of a winning grid at the end of it.

Sudoku solver programs that take three days not to come up with a winner are
sometimes considered sub-optimal.

[Willem]

Richard wrote:
) One of the rules of Sudoku is that the solution must be unique. In a really
) tough Sudoku, you may decide to guess at the contents of a particular cell.
) If that leads to a situation such as this:
)
) +-------+-------+-------+
)| 1 2 . | 4 5 . | 7 8 . |
)| 4 5 . | 7 8 . | 1 2 . |
)| 7 8 . | 1 2 . | 4 5 . |
) +-------+-------+-------+
)| 2 3 1 | 5 6 4 | 8 9 7 |
)| 5 6 4 | 8 9 7 | 2 3 1 |
)| 8 9 7 | 2 3 1 | 5 6 4 |
) +-------+-------+-------+
)| 3 1 2 | 6 4 5 | 9 7 8 |
)| 6 4 5 | 9 7 8 | 3 1 2 |
)| 9 7 8 | 3 1 2 | 6 4 5 |
) +-------+-------+-------+
)
) then there is no way to tell where the 3s, 6s, and 9s go, in the top three
) rows; that is, there is no unique solution, and so you know your original
) guess was wrong.

False. Instead, you know that the sudoku is malformed, because it does not
have a unique solution.

) If you brute-force it and find more than one solution, all but one of them
) is invalid. To find out which, you simply have to do the analysis.

This is complete nonsense. If brute force finds more than one solution,
then the assumption that the solution is unique, is simply false.


SaSW, Willem

[Richard Heathfield]

Post by Willem
) One of the rules of Sudoku is that the solution must be unique. In a
really ) tough Sudoku, you may decide to guess [and then you discover
that, as a consequence of your guess,] there is no unique solution, and
so you know your original ) guess was wrong.
False. Instead, you know that the sudoku is malformed, because it does
not have a unique solution.

On the contrary, you've shown that the particular guess you made would not
lead to a unique solution, and thus would lead to a malformed sudoku, and
therefore cannot be a correct guess.

I am here relying, by the way, on What A Bloke Down The Pub Told Me - I
think it was in rec.puzzles, actually, but I don't recall exactly - i.e.
that it is legitimate to deduce that a guess is incorrect if that guess
leads inexorably to a non-unique solution.

Perhaps a sudoku aficionado will chip in with their two penn'orth.

[Willem]

Richard wrote:
) Willem said:
)
)> Richard wrote:
)> ) One of the rules of Sudoku is that the solution must be unique. In a
)> really ) tough Sudoku, you may decide to guess [and then you discover
)> that, as a consequence of your guess,] there is no unique solution, and
)> so you know your original ) guess was wrong.
)>
)> False. Instead, you know that the sudoku is malformed, because it does
)> not have a unique solution.
)
) On the contrary, you've shown that the particular guess you made would not
) lead to a unique solution, and thus would lead to a malformed sudoku, and
) therefore cannot be a correct guess.
)
) I am here relying, by the way, on What A Bloke Down The Pub Told Me - I
) think it was in rec.puzzles, actually, but I don't recall exactly - i.e.
) that it is legitimate to deduce that a guess is incorrect if that guess
) leads inexorably to a non-unique solution.

That is true, *assuming* the sudoku is well-formed. That is, if you *know*
the sudoku only has one unique solution, and your guess leads to a pattern
that can never lead to a unique solution, then you can stop right there,
instead of going on and finding out that your guess will lead to a
contradiction. It *has* to lead to a contradiction, because otherwise
the sudoku would have multiple solutions.

If you don't trust the sudoku maker enough, you can still use the pattern
to find a good candidate for a guess that will lead to a contradiction.

In any case, a solution for a sudoku is nothing more than a completely
filled-in grid that obeys the three basic rules of sudoku (rows, columns
and blocks), of course with all the original puzzle numbers in their place.


SaSW, Willem

[Arthur J. O'Dwyer]

Post by Richard Heathfield

Post by Willem
) One of the rules of Sudoku is that the solution must be unique. In a
really ) tough Sudoku, you may decide to guess [and then you discover
that, as a consequence of your guess,] there is no unique solution, and
so you know your original ) guess was wrong.
False. Instead, you know that the sudoku is malformed, because it does
not have a unique solution.

On the contrary, you've shown that the particular guess you made would not
lead to a unique solution, and thus would lead to a malformed sudoku, and
therefore cannot be a correct guess.

You got all that right except for the "On the contrary" at the
beginning. You're right that

Post by Richard Heathfield
the particular guess you made would not
lead to a unique solution, and thus would lead to a malformed sudoku,
and therefore cannot be a correct guess;

however, it does /not/ therefore follow that any other guess must
necessarily be correct! A well-formed sudoku has exactly one solution,
no more, no less. If there's any two ways --- using guessing or otherwise
--- to fill in the grid differently, then the sudoku is malformed.

It might be interesting, in the vein of
<Pine.LNX.4.60-***@unix50.andrew.cmu.edu>
to try to construct a "pseudo-sudoku" where the solution depended on
being able to rule out "bad" guesses that otherwise would lead to
multiple solutions; but I can't for the life of me see how! What
would you fill in as the first box, and how would that /not/ count as
a "guess" leading to multiple possible solutions, assuming there were
several solutions with that value for that box?

-Arthur

[Default User]

Post by Default User

Post by [Jongware]
Suppose you have a solved sudoku. Cell values are [123456789], so
each cell has one (1) bit set on each position. Just ORing all of
them together yields '111111111', which is correct. The 'obvious'
part comes from the fact that in every single row or column *at
least* every digit (thus bit) appears once.

Originally you said to set a bit for every possibility in a cell.
So a solved one would have no bits set in any cell, every bit mask
would be 000000000. What should the bit masks for the example I
gave have looked like?

No; in a solved sudoku, there is exactly one possibility in each
cell, so ORing them all together gives 111111111 as Jongware stated.

We weren't, I thought, discussing ORing the entire puzzle. When I say
"possibles", that means a value that hasn't been ruled out, but hasn't
been determined to be the only one. So there are no possibles if the
cell has been uniquely determined.

If you ever OR everything together and get something with zeros in
it, then you've made a mistake and need to backtrack.

There's no backtracking, because I don't use guessing. This is not a
method that looks for contradictions.

However, I
don't see how this is such a useful insight, or how it has any
relationship to finding "triples" (which I still don't know what they
are), so maybe it's not Jongware's point.

If in a row, column, or block you can get three cells that can have
only possible values contained in a set of three numbers, then one of
those will have one of the three, guaranteed, as those are their only
choices. Likewise, no other cell in the same row, column, or block can
have any of those three values, so you can strike all three off the
possible list for every other cell.

Personally, as a programmer who considers sudoku "rote computation,"
I see no reason to bother with triples or X-wings or Death Stars or
whatever other shortcuts humans have come up with. Just put all the
possibilities in a matrix and brute-force it. It takes less than a
second, works all the time, and scales in the obvious way to bigger
or funny-shaped grids.

I don't solve the puzzles that way, so neither will my program. You may
consider it an unreasonable restriction, but I'm obviously doing the
exercise for my reasons, not anyone else's. If all I wanted was a
solver, I could download one. This, like the puzzles themselves, is a
mental and programming exercise. I'm refreshing my C after using C++ a
lot over the past years, and an interesting problem is always helpful
to me.


Brian

[[jongware]]

Post by Default User

Post by Default User

Post by [Jongware]
Suppose you have a solved sudoku. Cell values are [123456789], so
each cell has one (1) bit set on each position. Just ORing all of
them together yields '111111111', which is correct. The 'obvious'
part comes from the fact that in every single row or column *at
least* every digit (thus bit) appears once.

Originally you said to set a bit for every possibility in a cell.
So a solved one would have no bits set in any cell, every bit mask
would be 000000000. What should the bit masks for the example I
gave have looked like?

No; in a solved sudoku, there is exactly one possibility in each
cell, so ORing them all together gives 111111111 as Jongware stated.

We weren't, I thought, discussing ORing the entire puzzle. When I say
"possibles", that means a value that hasn't been ruled out, but hasn't
been determined to be the only one. So there are no possibles if the
cell has been uniquely determined.

If you ever OR everything together and get something with zeros in
it, then you've made a mistake and need to backtrack.

There's no backtracking, because I don't use guessing. This is not a
method that looks for contradictions.

However, I
don't see how this is such a useful insight, or how it has any
relationship to finding "triples" (which I still don't know what they
are), so maybe it's not Jongware's point.

A triple is any combination of three cells with only three numbers allowed
in them. While you don't know which of the numbers should be in each of
those cells, these numbers can be scratched from the *rest* of the row,
column or block.
A visible triple consists of 3 cells with 3 unique numbers, a hidden triple
may have other numbers in those cells as well -- you can scratch the extra
numbers from the triplet and make it a visible one. { 123 }, {124}, {123} is
a hidden triplet where you can scratch the '4'.

Back to topic. Why include bits for cells you *know* do not contain the
numbers you're checking?
Your example is: { 123 }, { 12 }, { 2345 }, { 369 }, { 123 }, { 56 }, {
258 }, { 3456 }, { 789 }
You're checking for a { 123 } triplet. ANDing { 123 } (bitwise!) with these
cells and discarding empty ones leaves you with
{ 123 }, { 12 }, { 2345 }, { 369 }, { 123 }, { 258 }, { 3456 }
There are 3 exact matches agains the { 123 } bitmask -- the required number
for a triplet! This leaves you with
{ 123 }, { 12 }, { 123 }
.. and you can scratch 1,2,3 in the other cells: { 45 }, { 69 }, { 56 }, {
58 }, { 456 }, { 789 }
..which happens to contain another triplet { 456 }, which leaves you with
{ 9 }, { 8 }, { 7 } -- three singles!
How do you know which set of numbers to check for a triplet? Iterating over
all cells containing 3 numbers and testing them against the rest for an
exact match will find the common case. The hidden sets and the
{ab},{bc},{ca} triplet are just a bit more difficult (hint: iterate a few
times over the entire set).
It still is a good trick, though. The same goes for quads and hidden quads,
but you'll need even more iterations.

[Jongware]

[Default User]

Post by [jongware]
How do you know which set of numbers to check for a triplet?
Iterating over all cells containing 3 numbers and testing them
against the rest for an exact match will find the common case.

Correct, and that's what the program currently does. That's easy to do
for any cardinality.

Post by [jongware]
The
hidden sets and the {ab},{bc},{ca} triplet are just a bit more
difficult (hint: iterate a few times over the entire set).

I guess I'm not seeing this, still. Without some brute force method
like forming possible triples and checking, I haven't come up with
anything. I've tried to think about how I recognize the pattern when I
am solving one, but some of that is obviously an ingrained recognition
without any specific steps. That is, I see 12 13 23 and know it's a 123
triple immediately. That's difficult to program.

With some of the higher cardinality ones, like a quad maybe, I'll
sometimes do a process like:

1. Here's a 123, let's see what else.

2. Hmm, no triple anywhere, but there's a 234, so let's think about
1234.

3. Ah, a 24, we're still rolling.

4. 13, that fits. We got one.





Brian

[[jongware]]

...

Post by Default User

Post by [jongware]
The
hidden sets and the {ab},{bc},{ca} triplet are just a bit more
difficult (hint: iterate a few times over the entire set).

I guess I'm not seeing this, still. Without some brute force method
like forming possible triples and checking, I haven't come up with
anything. I've tried to think about how I recognize the pattern when I
am solving one, but some of that is obviously an ingrained recognition
without any specific steps. That is, I see 12 13 23 and know it's a 123
triple immediately. That's difficult to program.
With some of the higher cardinality ones, like a quad maybe, I'll
1. Here's a 123, let's see what else.
2. Hmm, no triple anywhere, but there's a 234, so let's think about
1234.
3. Ah, a 24, we're still rolling.
4. 13, that fits. We got one.

The general case is something like 'for every n-let (be it 2, 3, 4) there
should be exactly n cells with *only* these numbers.
That can be found by, yes, brute force :-D but at least you don't have to
compare *every* cell against every other one.
I'd have to check my own s*d*k* code to see how I solved this particular
problem.
[I gave up working on that when I tried to introduce swordfishes ... and
when I found a s*d*k* generator whose grids even angusj couldn't solve!]

[Jongware]

[Willem]

[jongware] wrote:
) The general case is something like 'for every n-let (be it 2, 3, 4) there
) should be exactly n cells with *only* these numbers.
) That can be found by, yes, brute force :-D but at least you don't have to
) compare *every* cell against every other one.

Wouldn't it be easier to just iterate over the cells, instead of
iterating over the possibilities ? It goes a little bit like this:


findnlet(setofnumbers, setofcells, rightmostcell) :
iterate with currentcell from rightmostcell+1 to SUDOKUSIZE
newset is merge setofnumbers with contents of currentcell
if size of newset < SUDOKUSIZE/2
if size of newset <= size of setofcells
telluser newset found, namely setofcells
otherwise
findnlet(newset, add currentcell to setofcells, currentcell)

Which you call with:
findnlet(emptyset, emptyset, 0)

And where each cell contains the current possibilities.


Of course this is not an actual programming language, but you get the idea.


SaSW, Willem

[Barry]

Post by Willem
) The general case is something like 'for every n-let (be it 2, 3, 4) there
) should be exactly n cells with *only* these numbers.
) That can be found by, yes, brute force :-D but at least you don't have to
) compare *every* cell against every other one.
Wouldn't it be easier to just iterate over the cells, instead of
iterate with currentcell from rightmostcell+1 to SUDOKUSIZE
newset is merge setofnumbers with contents of currentcell
if size of newset < SUDOKUSIZE/2
if size of newset <= size of setofcells
telluser newset found, namely setofcells
otherwise
findnlet(newset, add currentcell to setofcells, currentcell)
findnlet(emptyset, emptyset, 0)
And where each cell contains the current possibilities.
Of course this is not an actual programming language, but you get the idea.
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

If I interpret your pseudo-code correctly this was approximately the
approach I used although
I computed the n-tuples for several values of n and put them in a "hash
table" up front,
and did the set comparison stuff iteratively (i.e. I kept my own stack).

barry

[Default User]

Post by Willem
) The general case is something like 'for every n-let (be it 2, 3, 4)
there ) should be exactly n cells with only these numbers.
) That can be found by, yes, brute force :-D but at least you don't
have to ) compare every cell against every other one.
Wouldn't it be easier to just iterate over the cells, instead of
iterate with currentcell from rightmostcell+1 to SUDOKUSIZE
newset is merge setofnumbers with contents of currentcell
if size of newset < SUDOKUSIZE/2
if size of newset <= size of setofcells
telluser newset found, namely setofcells
otherwise
findnlet(newset, add currentcell to setofcells, currentcell)
findnlet(emptyset, emptyset, 0)
And where each cell contains the current possibilities.

I've played with this some but can't get it to work, and I'm not sure I
understand how it's supposed to work. Could you give a thumbnail
description of what it's supposed to be doing?

I have an implementation in C that I think captures the pseudocode, but
it's not giving the correct results. Before I post that code, if you'd
explain what the algorithm was supposed to do I may be able to figure
out where I went wrong from there.




Brian

[Willem]

Default wrote:
) Willem wrote:
)> findnlet(setofnumbers, setofcells, rightmostcell) :
)> iterate with currentcell from rightmostcell+1 to SUDOKUSIZE
)> newset is merge setofnumbers with contents of currentcell
)> if size of newset < SUDOKUSIZE/2
)> if size of newset <= size of setofcells
)> telluser newset found, namely setofcells
)> otherwise
)> findnlet(newset, add currentcell to setofcells, currentcell)
)>
)> Which you call with:
)> findnlet(emptyset, emptyset, 0)
)
) I've played with this some but can't get it to work, and I'm not sure I
) understand how it's supposed to work. Could you give a thumbnail
) description of what it's supposed to be doing?
)
) I have an implementation in C that I think captures the pseudocode, but
) it's not giving the correct results. Before I post that code, if you'd
) explain what the algorithm was supposed to do I may be able to figure
) out where I went wrong from there.

What it's supposed to do is iterate over all possible combinations
of cells in a row, and tell the user whenever a combination of cells
contains a set of possibilities that is no larger than the number
of cells. In that case, you have a n-let.

Because you're only interested in n-lets where n is smaller than half
the size of the sudoku, you cut off the search whenever the current
set of possibilities gets larger than that.

Caveat: I just threw it together as an idea on the spot.


SaSW, Willem