The New Sudoku Players' Forum

[milobird]

For your example:

(123), (123), (12), (12345), (12345)

Test two and test three can both be used interchangeably to eliminate (123) in the last two cells. But consider the following:

(12), (12), (12357), (12467), (346), (457), (3567), (12345689), (13689)

I must admit it took me a while to come up with that example! For a while there I thought you were right ...

Milo

[Guest]

Crikey - looking at that I think I need a computer program to sort it out for me. Any ideas?

No, but seriously folks, I had been thinking about this too, and decided that when test 2 works so does test 3. But if test 3 works, test 2 doesn't necessarilly work.

To me that means that that 2 is a special case of 3, so you only need 3. Which is what I said first off, but let you convince me I was wrong about!

[milobird]

Well, my point was not that you can solve the whole row, but that you need method two to reduce it to:
(12), (12), (357), (467), (346), (457), (3567), (345689), (3689)

And then method three to reduce it to:
(12), (12), (357), (467), (346), (457), (3567), (89), (89)

And that neither of these methods on their own would get you this far.

But, I think I'm wrong.

Take a look at this:
http://www.sudokusolver.co.uk/solvemethods.html

I think most of his logic is covered by ours, though in very different language. Even his method D is covered by our method 2, but he raises the very interesting example of four cells each containing a subset of four numbers, but only containing three each. Up til now I had assumed that at least one of the cells would have to contain the complete grouping, even if the others only contained a subset, so now I'm back to square one as far as thinking of a programmable algorythm for this!

It also allows my example to be solvable only using method 2:

(12), (12), (357), (467), (346), (457), (3567), (345689), (3689)

Cells 3-7 only contain the numbers (34567), so therefore no other cells can contain them:

(12), (12), (357), (467), (346), (457), (3567), (89), (89)

So perhaps method 2 and 3 are synonymous after all. Can you give me an example where method 3 works but method 2 doesn't?

Milo

[Guest]

Ah - I thought that was what you meant by subsets, I didn't realise you where assuming the need for one complete set. I'd been thinking along the lines of a minimal case like three cells with one digit each - say 1, 2 & 3, is a set of three cells with three possibilities. If you can code it to allow even for this possibility, I think it will cover everything. Realising this doesn't make it any easier to do though! I'm trying to work on a sensible way to reduce the combinations that need testing, but haven't got that far yet, though it's not as big a number as you might expect. The number of combinations starts reducing again after 4 digits (there are the same number of 5 digit combinations as 4 digits, and the same number of 6 digit combinations as 3, etc.)

By the way, I decided that they are synonymous, not special/general cases too. I had a thought about using place maps (i.e. digit 1 can go in cells 1,5 & 6, etc. to build up a picture of where each digit can go). This was on the basis that the way the tests are worded, this is the best way to do test 3. However, I soon realised that you just end up with exactly the same problem to solve (i.e. an array of possibilities that need whittling); you haven't gained any information at all, just represented it differently. Does that make sense?

[Guest]

Aha! Synonymous isn't quite right - they are, but for opposite Ns - that is test 2 where N=1 is the same as test 3 where N=9 and vice versa. So, in fact you could only to test the combinations of 1,2,3 & 4, but you perform two tests - one on the placement maps, and one on the possibilities for the cells.

So you test for 1 cell containing 1 possibility
then all 2 cell combinations for 2 possibilities
etc.

At the same time test for 1 digit appearing in one place only
then all two digit combinations appearing in two places
etc.

When you get to N=4, you've tested every possibility.

Obviously the same algorithm can be used to generate the combinations for both tests, as the are both just a pick list of 9 values, so the tests can be carried out in a single loop.

I like that!

[milobird]

Good idea ... but don't forget n=5! One of the tests has to cover that!

But aren't there an enormous number of possiblities to search for higher values of n? I still think there must be a better way.

You're right that the tests are synonymous, or more accurately complementary, as you describe. They are two sides of approaching the same problem. Analysing the cells and analysing the possibles do actually give different information, its just that solving one in isolation is exactly as difficult as solving the other. But perhaps there's a way to combine the information...

My head hurts.

[milobird]

No, hang on ...

n=5 is unnecessary, isn't it.

n=1 for one test is equivalent to n=8 for the other.
n=2, n=7
n=3, n=6
n=4, n=5

So you only need to test up to n=4 for each.

[Guest]

That's it - sorry about the curve ball when I said N=1 and N=9 are synonymous - should have been 8.

[Guest]

Well, I've gone through and worked out number of combinations for up to 4 digits from 9. I think it's 381 -

9 for 1
36 for 2
210 for 3
126 for 4 (Surprising, but think this is right).

That's not that bad - I thought it would be worse, but it has the feeling of brute force about.

However, I think you can be a bit more elegant and reduce the number you need to test like this:

Take the case of N=3

Find all the possible digits for cells with 3 or less possibilities, this is likely to be less than nine, it could be 6 for instance. You then only need to test the combinations of 3 from 6, which is a lot less than 3 from 9. If any of those combinations is unique to 3 cells, you have a hit.

For the other test, you find all the cells for digits that are possible in 3 or less cells.

I think in a real puzzle, you will find that this is generally only a couple of dozen tests per unit. What do you think?

[Guest]

Milobird says:

Code: Select all

It also allows my example to be solvable only using method 2:
(12), (12), (357), (467), (346), (457), (3567), (345689), (3689)
Cells 3-7 only contain the numbers (34567), so therefore no other cells can contain them:
(12), (12), (357), (467), (346), (457), (3567), (89), (89)

Am I right in thinking that the number of cells (in this case 5, comprising cells 3-7) must be >= the number of numbers (in this case 5, comprising 34567) for method 2 to apply? Is this the only condition?

Anthony Jordan

[milobird]

Anthony-
The number of cells must = the number of possibles.
It is impossible for it to be larger.
That is the only condition!

IJ-
I think you've cracked it. Thanks! I think the best thing to do is to check for n=1, then n=2 if you can't solve the puzzle without it, etc. In practice only the very hardest puzzles will require you to use n=4. Doing it this way also lets you grade the puzzle by difficulty.

Something that worries me is that this guy...
http://www.sudokusolver.co.uk/solvemethods.html
...seems to have the same logic, but he still had to add a guessing feature. Perhaps this logic isn't definitive after all.

[milobird]

So, here is the revised list of techniques:

1) Scan each row/column/box, and if a certain possible only exists in coincidence with another row/column/box, remove it from the other cells in that other row/column/box.

2) Scan each row/column/box, and if n cells with the same set or subset of n possibles are found, and no other possibles, remove those numbers from the possibles list of the other cells in that row/column/box.
From n=1 ("single possible") to n=4.

3) Scan each row/column/box, and if n cells are the only cells to contain the same set or subset of n possibles, along with other possibles, remove those other possibles.
From n=1 ("unique possible") to n=4.

[Pappocom]

Hello, Milo and IJ. A while ago, Milo asked:

Next question: How to generate puzzles?

Or am I not allowed to ask that here... ;-)

As you suspected, Milo, that subject may be testing your host's hospitality and tolerance just a little too far, don't you think?

As the title says, these are Sudoku Players forums. They are not meant to be forums for programmers. I allowed this forum (Sudoku solvers) because some players apparently get assistance from Solvers.

For a while now, this thread has been a conversation between the two of you. You can continue your conversation, of course, but perhaps it would be a good idea to do so off-forum? I don't mean any disrespect and I hope you take none.

With thanks. Wayne.

[milobird]

No problem. I didn't mean any disrespect either.

[simes]

But I'm interested in this thread too. Just because others haven't posted, doesn't mean they don't want to read it.