Sudoku
in [Math]
|
Prev: How many Primes?
Next: divisor problem
From: Ed Murphy on 25 Aug 2005 23:46 On Thu, 25 Aug 2005 15:49:15 +0000, Patrick Hamlyn wrote: > Ed Murphy <emurphy42(a)socal.rr.com> wrote: > >>On Thu, 25 Aug 2005 01:21:01 +0000, Patrick Hamlyn wrote: >> >>> Simon Tatham <anakin(a)pobox.com> wrote: >>> >>>>I've marked four squares a, b, c and d in the above diagram. Their >>>>possible values are: >>>> >>>> - a could be 2 or 9 >>>> - b could be 1 or 9 >>>> - c could be 1 or 2 >>>> - d could be 1 or 9. >>>> >>>>The important points are that each of b and c is in line with a; each >>>>can contain one of the possible numbers in a; and each can also contain >>>>a 1. Therefore, if neither of b and c were 1 then between them they'd >>>>contain a 2 and a 9, and there would be no remaining number to put in >>>>a; hence at least one of b and c must be a 1 >>> >>> It might be easier to just note that if you have ab cd >>> fillable with only 3 values, then one value must be repeated on a >>> diagonal, the only possibility being 1 on a and d. >> >>This is wrong in multiple ways: >> >>* a cannot be 1 (given) >> >>* d cannot be 1 (deduced) >> >>* the point is not that one value must be repeated on some diagonal, >> but rather that one value must appear on a specific diagonal, and thus >> be absent from the other >> >> > The point *is* that a value must be repeated, since there are three > possible values covering four points. It is furthermore true that the > repeated values must be on a diagonal, since orthogonal points may not > have the same value. > > The fact that I inadvertently rearranged the labelling of a,b,c,d from the > original is minor, irrelevant and easily seen beyond with the smallest > *positive* effort. I strongly disagree with "easily" and "positive". I honestly believe you're underestimating the difficulty because you have the benefit of knowing your own original intent. I did *try* to figure out what you meant, but I evaluated the first two points only to the extent that they would lead to the third - it didn't occur to me to consider them in isolation. Now that you've explicitly presented them with isolation, we have the following: * Four cells, three values -> at least one value must appear in two cells (pigeonhole principle) * These two cells cannot be orthogonal, so they must be diagonal (specific relative geometry of the four cells in question) * Possibilities are (a=d=9, b=1, c=1) (a=d=9, b=1, c=2) (b=c=1, a=2, d=9) (b=c=1, a=9, d=9) though the first and last of these are actually identical. > And I wasn't solving the general case, I was pointing out a simpler > application of logic which could be used on this one. I don't have to > solve the general case just because *you* think it's the only way to do > it. Actually, you were simply solving a different general case (four cells, three values) than the OP's general case (b-c must contain N -> d != N).
From: on 26 Aug 2005 03:56 In article <Pine.LNX.4.60-041.0508251604020.5351(a)unix43.andrew.cmu.edu>, "Arthur J. O'Dwyer" <ajo(a)nospam.andrew.cmu.edu> writes: > >On Thu, 25 Aug 2005, Simon Tatham wrote: >[...] >> Hmm. I suppose it could be seen that way, although that's not how I >> saw it. I saw it as a special case of a rather different pattern, >> which I currently describe as `mutual neighbour analysis'. Rather >> than being a chain of arbitrary length, this pattern involves >> finding two non-adjacent squares and a bunch of their mutual >> neighbours, and observing that placing a particular number in one of >> the end squares forces all the neighbours to take values which cause >> a contradiction in the other end square. >[...] >> If the 45 square has a 4 in it, [...] a problem. Hence, the 45 square >> can't be a 4, so must be a 5. > > Tell me again how this is distinct from "backtracking"? Basically, >your method is > > 1. Fill in a value for cell X. > 2. Fill in a value for cells Y, Z,... dependent on X. > 3. If at any point you find a contradiction, return to step 1. > >That looks a lot like backtracking to me! > Perhaps it is backtracking. I am starting to think that whether you backtrack or not is not the essential difference between the two approaches to solving Sudoku under discussion. But I still convinced that there is a genuine difference. Let me call them the logical method and the guessing method. With the logical method, you may backtrack either on paper or in your head, but your aim is to show that all possibilities lead to a common conclusion, namely that a certain number definitely goes in a certain square. You are not trying to find a contradiction. With the guessing method, your aim is to either complete the puzzle or to obtain a contradiction. A significant difference between the two approaches is that with the logical method, on completing the puzzle, (assuming you have made no mistakes) you have proved that the solution is unique. With the guessing method, it happens frequently that you solve the puzzle but without knowing for certain that the solution is unique. Derek Holt.
From: Simon Tatham on 26 Aug 2005 04:14 Arthur J. O'Dwyer <ajo(a)nospam.andrew.cmu.edu> wrote: > Tell me again how this is distinct from "backtracking"? Backtracking is what you do when you have no knowledge of what's a good thing to try next. You pick an arbitrary unfilled square, and you make a _guess_; you don't know if the guess is right or not, and you don't know how long it's going to take you to find out. You continue solving, being prepared at any time to encounter a contradiction and conclude your initial guess was wrong. Sometimes it turns out to have been right, and you fill in a successful solution, and then you have to decide whether you're content to have found _a_ solution or whether your conscience is going to force you to go back and try the other branch to see if it was the only possible one. A pattern like the one I posted _could_ be done by backtracking, if you happened to be so phenomenally lucky as to pick square d to guess, and to pick a 1 to put in there, then your backtracking approach might find out extremely quickly that that couldn't be right. The point of it, though, is that by _searching_ for this specific pattern (or others like it) in the grid, you avoid all the uncertainty: by the time you make your `guess' of 1 in square d, you already _know_ it's going to be proved wrong rather than proved right, and you know it's going to be a very short chain of reasoning that demonstrates this. That, to my mind, should be more than enough to be going on with. -- Simon Tatham "Thieves respect property; they only wish the property to <anakin(a)pobox.com> be their own, that they may more properly respect it."
From: bill.daly on 26 Aug 2005 13:13 mensanator(a)aol.compost wrote: > Ok, set up your grid at R1C1:R9C9 > > 4 5 > 9 8 7 > 8 6 > 9 6 4 5 3 > 1 2 5 8 3 7 6 > 4 6 3 1 9 2 7 8 5 > 2 3 5 > 2 7 4 > 1 9 7 > ... > BTW, this does not necessarily solve the puzzle (I'm still stuck on > this example). On easy puzzles, I can usually just follow the forced > moves from start to end. On hard ones, I sometimes have to backtrack > because the discrepency may occur after a dozen moves. Let me try a different layout, which I'm hoping Google doesn't screw up: |4 |5 |9 8| 7 86| | ---+---+--- 9 |645| 3 125|837|6 463|192|785 ---+---+--- |2 |35 2 |7 4| 1| 9| 7 I can spot several moves in the above grid. I usually work as far as I can go with one simple procedure, which is to look at just one digit at a time. Each digit must ultimately appear nine times in the grid, and it is often possible to identify new occurrences, given only the ones already known and the fact that several of the other cells are occupied. For example in the above, look at the digit 8. There are four of the nine eights already present, at R2C6, R3C2, R5C4 and R6C8. Now, look at the top-right box, i.e. R1C7:R3C9. This box must contain an 8, but it cannot be in R2, R3 or C8 because these already contain an 8, and it cannot be in R1C7 because there is already a digit there, thus it must be in R1C9. Similar reasoning shows that the 3 in the bottom-middle box (R7C4:R9C6) must be in R9C4, which in turn implies that the 3 in the bottom-left box (R7C1:R7C3) must be in R8C2. I haven't followed this any further, but it may help you on your way. I usually just cycle through the digits, looking for inferences like these, until I either solve the puzzle or reach a configuration where this procedure is no help. (Cleaning up at the end generally involves some additional simple logic, typically negative.) This works for me at least 80% of the time. Here are a couple of other procedures I have used from time to time, though they're not as helpful as it might appear at first glance. [I find it helpful to have a term which describes sets of three cells in the same row/column and same box. I think of them as "triads". In each grid, there are 27 row triads and 27 column triads. If the boxes are numbered 1-9 in the natural way, then we can say that R1 consists of the three row triads R1B1, R1B2 and R1B3, meaning R1C1:R1C3, R1C4:R1C6 and R1C7:R1C9. Similarly for the other rows. For columns, we can say that C1 consists of the three column triads C1B1, C1B4 and C1B7, meaning R1C1:R3C1, R4C1:R6C1 and R7C1:R9C1. Similarly for the other columns.] Now consider the nine row triads in a layer of rows, e.g. R1, R2 and R3, which is the same as B1, B2 and B3. There are just four essentially different ways that three each of the nine digits can be placed in this layer. I'll use the letters abcdefghi to represent some permutation of the nine digits. The digits in each triad should be considered unordered. abc|def|ghi| ghi|abc|def| def|ghi|abc| or, abg|cdi|efh| efi|abh|cdg| cdh|efg|abi| or, ade|bhi|cfg| chi|afg|bde| bfg|cde|ahi| or, abc|ghi|def| ghi|def|abc| def|abc|ghi| When you have enough information about a layer, this can allow you to draw inferences which would otherwise be hard to come to. For example, in any 2*2 minor of the above, each digit must appear at least once, and three of the digits must appear twice. Also, as soon as you know the digits in any two triads not in the same row or box, you can infer the contents of all the other triads. Another possible inference is based on the assumption that the puzzle has a unique solution (not always the case, in my experience). Certain configurations can arise only when there is more than one solution, thus it is possible to infer that these configurations cannot arise in a valid puzzle. For example, if one row triad consists of abc, then no other row triad over the same columns can consist of the same three digits abc, since an alternative solution would be created if these two triads were swapped. Let me just add one other remark: excessive use of the term "NP-complete" has been associated with paralysis of the brain.
From: Marc Olschok on 27 Aug 2005 16:16
In sci.math john_ramsden(a)sagitta-ps.com wrote: >[...] > But, changing the topic temporarily, I did used to enjoy > the Rubik's cube, and I wonder if anyone has yet found a > workable and neat way to represent all the patterns and > operations in a group theoretic form or something similar. There is e.g. Singmaster, David: Notes on Rubik's magic cube (5th ed.) Enslow Publishers, Hillside, N.J., 1981. Marc |