Sudoku
in [Math]
|
Prev: How many Primes?
Next: divisor problem
From: Hauke Reddmann on 20 Aug 2005 12:15 In sci.math Timothy Little <tim-usenet(a)little-possums.net> wrote: > What's the real difference between "this square could be 3 or 5, let's > see what follows if it's 3" versus "this square could be 3 or 5, let's > see what follows in both cases at once"? Lets change the example a bit. I have two free cells in a line in a 3x3 block and don't know whether 3 goes left and 5 right or vice versa. But I already know from that in this line won't be either a 3 or 5 elsewhere, and can deduct further from there. So I don't have to fill in an error-prone 3 or 5 but let this undecided until I'm there again. No rubber required :-) -- Hauke Reddmann <:-EX8 fc3a501(a)uni-hamburg.de His-Ala-Sec-Lys-Glu Arg-Glu-Asp-Asp-Met-Ala-Asn-Asn
From: mensanator@aol.compost on 20 Aug 2005 12:53 Hauke Reddmann wrote: > In sci.math Timothy Little <tim-usenet(a)little-possums.net> wrote: > > > What's the real difference between "this square could be 3 or 5, let's > > see what follows if it's 3" versus "this square could be 3 or 5, let's > > see what follows in both cases at once"? > > Lets change the example a bit. I have two free cells in a line in > a 3x3 block and don't know whether 3 goes left and 5 right > or vice versa. But I already know from that in this line won't > be either a 3 or 5 elsewhere, and can deduct further from there. But what if ALL the blank cells have similar pairing symmetry? Now, it may be that on a "proper" Sudoku, this never happens and that is what I'm trying to figure out. And looking ahead a couple moves is the same as backtracking, isn't it? If you have to look ahead to resolve a pair, then there is no logic that forces the choice AT THAT STEP. > So I don't have to fill in an error-prone 3 or 5 but let this undecided > until I'm there again. No rubber required :-) I've needed it. But I'm new at this and have only done a dozen, so it could very well be that I merely missed the logical step that would have taken me past the point where I got stuck. But I got stuck using my Excel analyzer which is why I'm belaboring this issue. If my analyzer isn't making the logical step obvious, then my analyzer algorithm needs improvement. Now if it turns out that the "hard" puzzles are hard BECAUSE there are points where you have to guess or look ahead, then my analyzer is fine as it is. > -- > Hauke Reddmann <:-EX8 fc3a501(a)uni-hamburg.de > His-Ala-Sec-Lys-Glu Arg-Glu-Asp-Asp-Met-Ala-Asn-Asn
From: Gary on 20 Aug 2005 14:07 I think this is how to put sudoku into the framework of a "covering" problem: Given a matrix of 0's and 1's, we want to find some rows that together have exactly one 1 in each column. In other words, their sum is the vector of all 1's. Here is how to construct the matrix for sudoku: The rows are indexed by pairs (d,(x,y)), where d is a digit and (x,y) are the coordinates of a cell. The columns are in four groups, each group having 81 columns. The first group have labels (d,x), where d is a digit and x labels a row of the puzzle. The second group have labels (d,y), where d is a digit and y labels a column of the puzzle. The third group have labels (d,b), where d is a digit and b labels a box of the puzzle. The fourth group have labels (x,y). where (x,y) are the coordinates of a cell. In row (d,(x,y)) we place a 1 in the columns labelled (d,x), (d,y), (d,b) where b is the box containing the cell (x,y), and (x,y). Each row has four 1's. This gives a 729x324 matrix, which I think deserves the name The Sudoku Matrix. (Of course we can do this for n^2 x n^2 sudoku.) Here's the point: A valid completed sudoku grid corresponds to a set of 81 rows which "cover" in the sense that they collectively have exactly one 1 in each column. A puzzle may be described by a set of rows which extends uniquely to a set of 81 rows which cover. Solving the puzzle is finding the rest of the rows. One way to efficiently search for a solution in covering problems is by a backtracking method of Knuth which he calls "dancing links." Solving the puzzle via the matrix puts deductions like "only two numbers can go in this cell" and "this number can only go in these two cells" on the same footing, and makes any distinction between them artificial. On the other matter, maybe another message as this is already too long. Gary McGuire
From: George on 22 Aug 2005 02:35 > > So what happens when ALL the blank squares end up > with multiple > numbers in the corners? Don't you have to guess at > that point? > Or are they saying that should never happen on a > proper Sudoku, > that there must be some logic I'm overlooking that > tells me which > number to pick? > There might be a logical technique that works. There is furious discussion in the sudoku community over whether outright guessing is required for some puzzles. Some argue yes, but some argue that there is always some logical technique that works, and go to great lengths to find such techniques. When confronted with a puzzle that no existing techniques can solve, they come up with a new "technique" which solves that puzzle. Applying these rather complicated techniques is slower in practice than trial-and-error, for humans anyway. It may turn out that for 9x9 sudoku, there is some array of "techniques" that solves all puzzles, but this will be because 9x9 is too small. I'm sure that for n^2 x n^2 sudoku guessing is required. It is NP-complete after all. Of course, all puzzles in newspapers can be solved by the basic techniques. Some puzzle-setters guarantee this in the small print. I assume they have a solver program that tries only the basic tricks, and they check that each puzzle can be solved by this solver before printing it. Gary McGuire
From: SudokuJohn on 23 Aug 2005 09:44
> My uncle is possessed with Sudoku. He spends hours marking and erasing but he > finally solves it. > > He is a civil engineer and also has a Microsoft certificate for Excel usage, or something > like that. > > I suggested he ported the game to Excel, using a template, so he doesn't have to > scratch and erase all the time. > I note your uncle is a civil engineer. When I was a mathematics undergraduate one of my lecturers told me a story to indicate the difference between mathematicians and engineers. A mathematics undergraduate and a group of engineering undergraduates were each given an assignment to do over a weekend. The assignment was to produce detailed step-by-step instructions on how to make a cup of tea given an empty kettle, a teapot, a cup and saucer, a spoon, a packet of tea bags, a bowl of sugar and a bottle of milk. The students were told that no assumptions should be made about the prior knowledge of the intended user of the instructions, and that not even the most minor of steps should be omitted. The set of instructions should be sufficient to enable a visitor from Mars to successfully make a cup of tea. The assignments were reviewed the following week. There were a few minor differences such as adding the milk to the tea or the tea to the milk, but in general all the students produced remarkably similar sets of extremely detailed if long-winded instructions describing how to make a cup of tea starting with an empty kettle. The same group of students were given another assignment for the following weekend. The new assignment was to produce detailed step-by-step instructions on how to make a cup of tea given a kettle filled with water, a teapot, a cup and saucer, a spoon, a packet of tea bags, a bowl of sugar and a bottle of milk. The students were again told that no assumptions should be made about the prior knowledge of the intended user of the instructions, and that not even the most minor of steps should be omitted. As before, the set of instructions should be sufficient to enable a visitor from Mars to successfully make a cup of tea. This time there was a major difference between the instruction produced by the mathematician and those produced by the engineers. The engineers produced sets of instructions almost as long as those produced for the previous week's assignment, but this time describing how to make a cup of tea starting with a kettle of water. The mathematician had taken a different approach. He had submitted the same set of instructions he'd produced for the previous week's assignment with a short introduction which read "Empty the water from the kettle and then perform the following instructions.". The moral of this story is not to make extra work for yourself by re-inventing the wheel. In this Sudoku context, why should your uncle bother to write his own software when SudokuPC is available at little cost from www.sudokupc.co.uk? Download the free trial version and see what I mean. Your uncle will have to scratch and erase no more! |