The New Sudoku Players' Forum

[Thumbs]

Thumbs, I don't think your two steps are enough. Consider yesterdays puzzle (No 94)

Code: Select all

8..7.....
.....4.2.
...2..17.
..6.2..9.
1..4.5..6
.2..9.3..
.31..2...
.4.3.....
.....8..3


I think repeating the two steps leaves it looking like:

Code: Select all

8.27...3.
.....4.2.
...2..17.
.8612..9.
1..4.5286
.2.8963.1
.31..2...
.483....2
2....8..3


but what's the next move?

I'd go for a 7 in the centre cell, but I don't think your logic would find it. (Or have I missed something obvious?)

Thank you, Simes, you are totally correct. I will adjust the old thinking cap and look for a refinement. This could become very addictive!

[Guest]

Having finally solved yesterdays truelly fiendish puzzle, I realise that the test I'd been putting off needs to be implemented as it is the only one that would have solved it. There is a column with two cells where the possibilities are "3678" and "1679" and 6 & 7 appear nowhere else, these cells therefore can only be 6 or 7, which then frees out that column.

[milobird]

Hi,

I'm new to this, but am seriously thinking of trying to code a sudoku solver for the Mac.

Thanks to everyone on this thread for their ideas, particularly howshaw and IJ who, as far as I can tell, seem to have covered most of the fundamental logic between them (but not all -- see points 4 and 5 below).

I think these are the basic techniques, starting with a full grid of "possibles" for each cell as described by IJ:

1) If a cell contains a number, remove that number from the possibles list of other cells in that row, column and box.

2) Scan each row/column/box and if n cells with the same set of n possibles are found, remove those numbers from the possibles list of the other cells in that row/column/box.

3) Scan each row/column/box and if n cells are the only ones to contain a certain grouping of n possibles, remove all other possibles from those cells. (This is a more general case of scanning for a unique possible.)

4) Scan each box and if a number x is only possible in one row/column, remove that number from the possibles list of the other cells in that row/column.

5) Scan each row/column and if a number x is only possible in one box, remove that number from the possibles list of the other cells in that box.

These techniques are all concerned with reducing the number of possibles for the cells in the puzzle. Of course, although I haven't bothered to mention it, when a cell only has one possible it can be filled in. I also haven't tackled the problem of when to apply and re-apply each of these techniques.

Please let me know if you think I have missed any pieces of logic out, or if you know of a sudoku puzzle that is solvable by logic not covered here.

Thanks,
Milo

[Thumbs]

Thumbs, I don't think your two steps are enough. Consider yesterdays puzzle (No 94)

Code: Select all

8..7.....
.....4.2.
...2..17.
..6.2..9.
1..4.5..6
.2..9.3..
.31..2...
.4.3.....
.....8..3


I think repeating the two steps leaves it looking like:

Code: Select all

8.27...3.
.....4.2.
...2..17.
.8612..9.
1..4.5286
.2.8963.1
.31..2...
.483....2
2....8..3


but what's the next move?

I'd go for a 7 in the centre cell, but I don't think your logic would find it. (Or have I missed something obvious?)

I have added twins elimination by row and column.

I did not bother with 3 triplets or 4 quads.

I also added elimination in the row or column within the 3x3 block based on 2-3 occurrences of the same digit, extrapolating to the rest of the row or column respectively. That's where the digit does not occur elsewhere in the block, of course.

The example you quote now solves via this additional logic.

[Guest]

Milobird, good stuff - how about the next logical steps

Tests 4 & 5 are the same - If you think of boxes, rows and columns as "Units", then both tests can be re-written as "If all possibilities for a digit in one unit (A), also all occur in another unit (B) then that digit can be eliminated from any cells in unit B that don't intersect with unit A"

Also, Tests 1 and 2 are just special cases of test 3 - Test 1 is test 2 where n=1, and test 3 is test 2 expanded to ignore other "noise" in the cells.

This leaves just two neat tests.

Can that be right?!?

[milobird]

Yes, test four and five are definitely the same! I realised this today when I was thinking of how I could implement them both without needing two separate (but almost identical) methods.

You are also correct that test one is a special case of test two! I hadn't considered this. But I think from programmers point of view it would be more efficient to test for this special case first. (Whereas scanning for a unique possible is less trivial.)

I think test three and four are different, though in a weird, confusing and rather beautiful way they are totally symmetrical, almost opposite. Do you know what I mean?

I missed out something very important from tests three and four. Both should not only include cells that contain the set of n possibles, but also cells that contain a subset of this set.

This is vital! (1,2,3), (1,2,3) and (1,2) is just as useful as (1,2,3), (1,2,3) (1,2,3).

This is difficult to code, but after thinking all day I think I've found a very elegant method... in my head at least...

I don't believe that this logic is definitive (there may be other valid logical tests), but it may well be sufficient to solve all logically solvable sudoku puzzles. (A bold assertion).

[Guest]

I think test three and four are different

Definitely! I was saying that 1,2 and 3 are the same and that 4 & 5 are the same, not that 3 & 4 are the same...

(1,2,3), (1,2,3) and (1,2) is just as useful as (1,2,3), (1,2,3) (1,2,3).

I feel so dumb now - I've stared at groups like this in puzzles and never once clicked what it could be telling me! Thanks - I'm off to revisit a "Very Hard" Pappocom that's had me stumped....

[Guest]

Hang on - this isn't right is it?

(1,2,3),(1,2,3),(1,2) doesn't tell you more than your tests 4 & 5 for single digits

Or maybe I don't understand after all!

Are you saying this tells you something about the other cells within that unit (row,block or column), or about the contents of a different unit if these cells are the intersection between the two units?

If you mean the former then I think you're wrong - without the 3rd 3, you don't know anything useful about how to place those digits. Do you?!?

If the latter, then this is no different to doing your test 4(&5) for digits 1,2 & 3 - so doesn't need special coding anyway.

I think I'm confused - not an uncommon state for me :o)

So, it's back to that puzzle then...

[simes]

Doesn't (1,2,3),(1,2,3),(1,2) let you eliminate 1, 2 and 3 from the possible numbers of other cells within the group?

[Guest]

Yes, of course. I was being dumb after all!

[milobird]

Oops, I meant to say that I don't think tests two and three are the same. They're virtually identical, but completely opposite. One looks at the possibles in a cell and attempts to infer information about the possibles in other cells, while the other test looks at which cells contain a particular possible and attempts to infer information about the other possibles in those cells.

One test is cell from the point of view of the cells, the other from the point of view of the possibles. What's interesting is that both these views can be represented in the same way, which I think must be at the heart of what makes sudoku such an aesthetically pleasing puzzle.

Including subsets in the test is very important. As another example of how this works, say you have the following box:
(1, 2, 3, 5, 6, 7, 8, 9)
(5, 6, 7, 8, 9)
(1, 2, 3, 4, 5, 6)
(5, 6)
(5, 7, 8)
(1, 2, 7, 8, 9)
(8, 9)
(5, 6, 7, 9)
(1, 2, 3, 4, 7)

You could then reduce this box to:
(1, 2, 3)
(5, 6, 7, 8, 9)
(1, 2, 3, 4)
(5, 6)
(5, 7, 8)
(1, 2)
(8, 9)
(5, 6, 7, 9)
(1, 2, 3, 4)

[Guest]

OK - that makes sense about 2 and 3, I've re-read them and it's spot on. "Virtually identical, but opposite" - I like it!

Could you talk me through how you get from the first state to the second - I don't get it.

[Guest]

Sorry Milobird, I'm having a bad day! There's no need to explain :o)

[milobird]

Call me Milo.

Next question: How to generate puzzles?

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

[Guest]

Righto Milo. Before I answer that question, I'm going to go back to the five tests I'm afraid! I've being thinking about this again, and would suggest that on the face of it 2 and 3 are different, and are both valid ways to reduce possibilities. However, in reality, they always produce the same result, and are synonymous... consider four remaining cells in a block where the first three were your example, and the last, the worst case scenario.

(123), (123), (12), (1234)

Now, test 1/2 would say 4 only appears in cell 4, so it must be 4

Test 3 would say 1,2 & 3 must be exclusively in cells 1,2 & 3, so cell 4 must be a 4

Likewise, imagine 5 cells...

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

Test 2 leaves cells 4 & 5 as (45), so does test 3.

I can't think of a situation where if one test could be applied the other could not, and I'm pretty sure they would always have the same result.

Maybe I wasn't going mad after all?!? Mind you, I haven't being thinking in a straight line since I found this web site, so I just don't know any more...

Anyway, that was quite long, so maybe I'll leave your puzzle making question until we get this one bottomed out :o)