The Official Sudoku Thread.

I tried it once and found it just difficult enough to realy challenge me, but not so difficult that I abandoned all hope. Pretty perfect, really. I'm a little wary of getting in any deeper, though, as I'm not sure I need more obsessions.

(for reference)

I hate you, you've ruined my life.

Love,
Austin

We binned our crossword for a Sudoku in our latest corporate magazine. It had two possible solutions, so it was kind of crap.

Isn't "the nation" all doing kakuro now? I might have mispelt that. It's the "NUMBER ONE PUZZLE IN JAPAN", apparently.

I mourn the retreat of cryptics for these things :(

am preferring kakuro to sudoku at the moment, less mindless faffing.

The Daily Telegraph now has jigsaw sudoku, where the major boxes aren't square. And our Wednesday paper has one, always ultra-easy with one full 9-square filled in (in a lighter typeface, like you won't really notice it or something).

uh? 8)

there's always (at least) one place on the grid where you KNOW the answer, there's only one possible value it can be given the state of the other squares. when you guess it's because the square you're guessing doesn't have a single logical value. which means, in effect, you're filling in the wrong square - look somewhere else. (this continually having to find the exact square is what bores me)

i would like to do another 4x4x4 one but that means buy the independant on a saturday. am also thinking about a kakuro solver thing.

Yes, this happens a lot in the medium and hard categorized puzzles.

It's also true you should never have to guess where a number goes - you should either know from direct evidence (numbers in all the surrounding boxes preclude any other possibility) or by interpolation (which I was going to write out an example of but it made no sense in writing whatsoever).

Because I haven't done them that much (I used to do them in Games years ago, and have done a few since the rage started, but I haven't gotten into them so much) but that has happened to me often. And while that is using logic (and I assume it's what Jaq means by "interpolation"), that is also using guessing -- you have to guess that it is 2, follow the consequences, and realize that it can't be 2.

And I can't think of a form of sudoku guessing that doesn't amount to that (although some guesses would be more productive than others).

So, because I'm a hopeless technoid, I charted the solve sequence for yesterday's Guardian competition puzzle:
http://www.theilliterate.com/archives/illiterati/sudoku.jpg

Solving this Sudoku:

1) Find all the section direct evidence locations.
a. 3 goes in B7
b. 5 goes in F5
2) Check Column 6 for direct evidence locations.
a. 9 goes in H6
3) Check Column 6 for interpolated locations.
a. Neither 2 nor 4 can go into G6, therefore 6 goes in G6.
4) Check row F for interpolated locations.
a. None definite.
5) Focusing on the section that contains G7:
a. The numbers 1, 6 and 9 will go in the bottom row of this section
b. Therefore, 4 goes in H7
6) Focusing on the section that contains G1:
a. 5 will go in the second row, either in H1 or H3
b. Therefore, in the section that contains G7, 5 goes in G8
c. Therefore, in the section that contains G7, 7 goes in H8
7) Check column 7 for direct evidence locations.
a. 7 goes in E7
b. by direct evidence, 7 goes in B9
8) Focusing on the section containing G4:
a. 2 and 8 must go in H5 and J5
b. therefore, 3 and 7 go in the upper row
c. therefore 7 goes in G5 and 3 goes in G4
d. by direct evidence, 4 goes in G2
e. by direct evidence, 4 goes in A1
f. by direct evidence, 7 goes in C2
9) Focusing on the section containing D4:
a. 4 will go the middle row
b. therefore, in the section containing D7, 4 goes in the bottom row
c. therefore, 4 goes in F9
10) By direct evidence, 1 goes in D2 (I missed this in the first step)
11) By direct evidence, 1 goes in E9
12) By direct evidence, 5 goes in A9
13) Focusing on the section containing D7:
a. 9 goes in the upper row
b. therefore, in the section containing D1, 9 goes in the middle row
c. therefore, 9 goes in E3
14) Focusing on Row C:
a. 5 goes in C4 by direct evidence
b. 5 goes in B3 by direct evidence
c. 5 goes in H1 by direct evidence
d. 3 goes in F2
e. 3 goes in J3
f. 7 goes in J1
15) Focusing on the section containing D1:
a. 8 goes in F1
16) Focusing on the section containing D4:
a. 2 will be in the center column of the section containing G4
b. therefore 2 will be in the center row of the section containing D4
c. therefore 2 goes in D1
d. therefore 6 goes in E1
e. therefore 6 goes in D5
f. therefore 6 goes in F8
g. therefore 6 goes in A7
h. therefore 6 goes in J9
i. therefore 6 goes in B4
17) Completing Columns 4 and 7:
a. 1 goes in J7
b. 2 goes in E4
18) checking for direct evidence locations:
a. 9 goes in J8
b. 3 goes in D8
c. 9 goes in D9
d. 3 goes in E5
e. 4 goes in E6
f. 4 goes in C5
19) checking Row C for direct evidence locations:
a. 1 goes in C8
b. 2 goes in A8
c. 2 goes in C6
20) checking Row B for direct evidence locations:
a. 2 goes in B2
b. 9 goes in B5
c. 1 goes in A5
21) checking Row A:
a. 9 goes in A2
b. 8 goes in A3
22) completing rows H and J:
a. 8 goes in J2
b. 2 goes in H3
c. 2 goes in J5
d. 8 goes in H5

so the criteria of "no guessing" is therefore "there exists a series of soduku states from initial to complete, each with one additional number filled in such that between any two states the number filled in is the only possible one in that position."

i also noticed what might be a simple mental technique in jaq's solutions where he starts off looking not for what it can't be but what it "must" be -- i.e. this region requires a 5 somewhere, but it cannot be in place a, b, c, d, etc. and therefore *must* be in the only remaining place. but this can also be reworded to be thought of as "boxes y and z cannot contain any numbers but 5 and 6" to keep the succinct criteria above clear.

i may just be stating the obvious in all this, but i only dick around with these puzzles on rare occasion, so it took me a bit to think this through.

so i figure you could create seperate binary vectors for each of the possible states of each box -- one with limits from the region, one with limits from horizontal line, one from vertical line, and then you could multiply them through (straight product). then you take a cross product (with a little manipulation?) of all state matrices in a region, row, or column and in theory in at least one of these cross products (of which there would be 27 total) there would be one column (row?) with only one 1 and the rest zeroes, and that would tell you a correct location and value.

or something like that. one it was all math i'm also sure there would be all sorts of ways to optimize it and propigate the change thru the 27 resultant vectors so they didn't have to be recalced each time.

this:
http://home.clara.net/koogy/SoDorky3.html?000703000100008040306000908004807500050000080007901200901000802060100003000405
(click hint)
shows 8 different squares where you KNOW the value for the initial position. but this is done using brute force and would be tedious for a human to do this (that said, i tend to do sudoku the same way the code does, going through all squares and listing alternatives and maybe that's why i find them too repetative...)

"1) Find all the section direct evidence locations.
a. 3 goes in B7
b. 5 goes in F5
2) Check Column 6 for direct evidence locations.
a. 9 goes in H6"

see, that's all very well but WHY did you choose column 6 in step 2? experience? trial and error? that's the tricky bit.

> so i figure you could create seperate binary vectors

i got this far 8)

I don't know that a strict math approach can be used as a solver for sudoku, because the numbers are simply symbols. The puzzle can be done in an identical manner using the letters A-I or any other set of 9 symbols. Probability and constraints might turn up a more elegant solution - you start with 9 ones, and have 81 possible locations. As soon as you place one of them, you have only 63 possible locations for the remaining 8. Place another and you have only 47 locations left, then 31 left after placing 6, etc.

The solvers written by (for?) the current Sudoku game developers run through the actual logic algorithms, in order to rank the puzzle as easy, medium, hard, diabolical. The solver written by Andrew (http://nf.wh3rd.net/sudoku/) is just brute force from his admission.

It has the most complete sequence, mainly. Focusing on a section that has a full row or column yields good results generally. A section that is mostly empty between two that have a similar set of numbers in place is also a good plan.

Something Casuistry commented on in the sudoku c/d thread referenced upthread - the solving gets to the point where it is always the same. I think that's why I like these for work. The Kakuro puzzles are taking more concentration and effort, since they involve actual math as well as logic, so I'm not able to work at them the same way.

Sudoku story: We were at the eye doctor's office a few weeks ago, picking up contacts. The doctor was sitting behind the reception desk, off to the side, with a pile of files and whatnot, looking very studious, while the receptionist helped us. I figured the doc was working on insurance forms or something, but no - he had a sudoku slipped into a file folder :)

i disagree. you soon learn by rote the maximums and minimums for a given sequence size (3, 6, 10, 15 or 17, 24, 30, 35...) (and anything 1 more or 1 less that these) so it's just pattern recognition until the very end (i find).

(btw, you can transpose rows or cols 1-3, 4-6, or 7-9 without changing the nature of the puzzle, which means that there are actually at least an order of magnitude less soduku than you would think -- not to mention that you can swap all 2s and 9s or whatever too)

(also -- 4 is the minimum # of initial numbers for a 4x4 soduku, what's the minimum for yr. standard 9x9 and is there a formula that tells you for arbitrary sizes?)

it turns out that the minimum # problem is unsolved! (and also that the general case sudoko solution is, unsurprisingly, np-complete!)

the page also cites knuth's dancing links algorithm and graph coloring, which shows that my speculations above were sorta on the right track.

i don't think you need a brute force solver though. certainly the early versions that filled in values it was sure about would finish most of the guardian easy and medium puzzles without resorting to brute force. there is, however, one last technique that i haven't coded (because it is tricky) (and thanks to mr o'farrell for firming this up for me over on ile):

if, in any 3x3 square, all the possible positions for a given value are in the same vertical or horizontal line then you can eliminate that possibility from other squares in the same line in the 9x9 grid (one of them must be A so nothing else can be).

also, if you have two empty squares in a line and each can have only the same two values then nothing else on that line can take those values AND nothing else in the 3x3 can take those values. (same for 3 empty squares with the same three possible values and (maybe) if the possible values are A or B, B or C and A or C)

(um, why am i so against brute force solvers when writing code to model the way a human would do these things is so much less efficient?)

koogs, as I work more of these, I agree the solving is becoming much more rote.

For me, having access to a solver has given me a sanity check along the lines of "is this damnable thing truly solvable?" But what I really want is a tool that would give me just one number, and illustrate the logic of determination - more of a trainer than a solver I guess. Actually, with the fever pitch of Sudoku at the moment, programming a trainer/simulator might be worthwhile. Far beyond my skills though.

I'm not getting this easy/medium/hard bit. Is it just the case that you start off with more ambiguities in a 'hard' puzzle, then you work out three numbers and it's an 'easy' one?

I'm sure what I'm going to say has been said better and more clearly many times before.

Because I'm a sloppy thinker, I canmake mistakes on the easiest of Sudokus, such as repeating a digit in a row, column or box without noticing until much later. So, I thought I'd write a program based on very simple principles and see how well it coped with published puzzles ranging from 'very easy' to 'fiendish'.

All the program does (without bothering with the coding details) is to see what digits can be used in any cell by eliminating anything already present in the row/col/box to which the cell belongs. If a cell has only one free value, assign it. It is also common for each cell to have several possible values, but for only one cell in any given row/col/box to have a particular digit in its set of possible values, so assign it.

If any cells have to be given digits by these simple rules, go through the whole process again from the augmented solution.

For most puzzles, including some 'very hard' and 'fiendish' ones, the solution appears in a flash. However, this algorithm can stall. What I then do is show the current solution and the possible digits for each unassigned cell. I then make a guess for a cell with only two possible values and attempt to resolve. The manual interventions could easily be automated, but I don't mind spending a minute on the most difficult puzzles.

When I wrote the program, I suspected it would sometimes stall, as indeed it does.

In the last couple of days, I've been thinking about a Kakoru algorithm. This seems like a much more challenging problem, but perhaps I'm missing something.

interesting question -- what is the minimum possible starters for a "well defined" solution REGARDLESS of the "guessing" criteria, and is it different?

A B C D E F G H I
+-------+-------+-------+
1| . . . | . . . | 2 . . |
2| . . 3 | 4 5 . | . 1 . |
3| 1 2 . | . . 6 | . . 9 |
+-------+-------+-------+
4| . . . | . . 7 | . . 8 |
5| . 5 . | . 8 . | . 7 . |
6| 6 . . | 9 . . | . . . |
+-------+-------+-------+
7| 7 . . | 1 . . | . 5 6 |
8| . 8 . | . 2 3 | 4 . . |
9| . . 9 | . . . | . . . |
+-------+-------+-------+

   A B C   D E F   G H I
 +-------+-------+-------+
1| . . . | . . . | 2 . . |
2| . . 3 | 4 5 . | . 1 . |
3| 1 2 . | . . 6 | . . 9 |
 +-------+-------+-------+
4| . . . | . . 7 | . . 8 |
5| . 5 . | . 8 . | . 7 . |
6| 6 . . | 9 . . | . . . |
 +-------+-------+-------+
7| 7 . . | 1 . . | . 5 6 |
8| . 8 . | . 2 3 | 4 . . |
9| . . 9 | . . . | . . . |
 +-------+-------+-------+

i do not understand alan's comment.

i do not understand alan's comment.

Me, either.

Presumably everything will fall into place now.

I really liked the suduko interface in Brain Age on the DS, but I got tired of crazy laughing guy and having to draw pictures all the time. So I picked up Suduko Gridmaster for the DS this weekend and am liking it. 400-some puzzles at varying levels, timed challenge puzzles, and this box/row/column highlighting scheme that's nice. Also, once you've placed 9 of the same number, it grays out as a selection.

Chintzy, annoying music though. But you can turn the volume so low it is off on the DS.