Sudoku
in [Math]
|
Prev: How many Primes?
Next: divisor problem
From: Paul Nutteing on 24 Aug 2005 17:41 "Simon Tatham" <anakin(a)pobox.com> wrote in message news:Ozk*JtZWq(a)news.chiark.greenend.org.uk... > > Simon Tatham wrote: > >> (I'm not being seriously secretive: I will describe the technique if > >> asked. I just thought I'd leave it out of this posting, simply > >> because it seems a bit silly to post a puzzle _and_ its solution!) > > Puppet_Sock <puppet_sock(a)hotmail.com> wrote: > > Well, I got quite far with it, but eventually broke down and > > had to guess. Only had about 10 spots left by the time I needed > > to guess though. > > > > So, yes please. > > I'm not sure how you got down to only 10 empty squares and _then_ > needed to guess; when I tried it, I got to the following position > before running out of ordinary things to do and having to resort to > something interesting. (And my automated solver agrees that there's > nothing ordinary left to do in this position.) > > 6 3 | 5 b | a 8 7 > 1 7 | 2 | 3 > 5 | 3 | 1 > ------+-------+------ > 3 7 | 5 d | c 6 8 > 1 6 | | 4 > 2 5 | 6 | 3 9 > ------+-------+------ > 7 8 1 | 2 | 4 9 5 > 4 3 6 | 9 7 5 | 8 1 2 > 5 9 2 | 4 | 3 7 6 > > 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 > (although we don't know which yet), and that means d (which is in > line with both b and c) cannot be a 1. Therefore it's a 9, and the > rest of the solution follows easily. > -- > Simon Tatham "I'm going to pull his head off. Ear by ear." > <anakin(a)pobox.com> - a games teacher I had exactly the same completed grid before arbitrarily selecting on row 4 column 3 the guess of 4 rather than 9 leading to a solution but selecting 9 led to a paradox. But is there only one solution ? Incidentally in OE5 selecting properties of the message may give the text in equal width font. What they aren't telling you about DNA profiles and what Special Branch don't want you to know. http://www.nutteing2.50megs.com/dnapr.htm or nutteingd in a search engine Valid email nutteing(a)fastmail.....fm (remove 4 of the 5 dots) Ignore any other apparent em address used to post this message - it is defunct due to spam.
From: Mark Thornquist on 24 Aug 2005 17:43 Simon Tatham wrote: >>Simon Tatham wrote: >> >>>(I'm not being seriously secretive: I will describe the technique if >>>asked. I just thought I'd leave it out of this posting, simply >>>because it seems a bit silly to post a puzzle _and_ its solution!) > > > Puppet_Sock <puppet_sock(a)hotmail.com> wrote: > >>Well, I got quite far with it, but eventually broke down and >>had to guess. Only had about 10 spots left by the time I needed >>to guess though. >> >>So, yes please. > > > I'm not sure how you got down to only 10 empty squares and _then_ > needed to guess; when I tried it, I got to the following position > before running out of ordinary things to do and having to resort to > something interesting. (And my automated solver agrees that there's > nothing ordinary left to do in this position.) > > 6 3 | 5 b | a 8 7 > 1 7 | 2 | 3 > 5 | 3 | 1 > ------+-------+------ > 3 7 | 5 d | c 6 8 > 1 6 | | 4 > 2 5 | 6 | 3 9 > ------+-------+------ > 7 8 1 | 2 | 4 9 5 > 4 3 6 | 9 7 5 | 8 1 2 > 5 9 2 | 4 | 3 7 6 > > 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 > (although we don't know which yet), and that means d (which is in > line with both b and c) cannot be a 1. Therefore it's a 9, and the > rest of the solution follows easily. Rats, you beat me to it. That's the same way I solved it. I mentally call that set of four cells a "broken box". -- Mark Thornquist
From: r.e.s. on 24 Aug 2005 21:14 "Simon Tatham" <anakin(a)pobox.com> wrote ... > 6 3 | 5 b | a 8 7 > 1 7 | 2 | 3 > 5 | 3 | 1 > ------+-------+------ > 3 7 | 5 d | c 6 8 > 1 6 | | 4 > 2 5 | 6 | 3 9 > ------+-------+------ > 7 8 1 | 2 | 4 9 5 > 4 3 6 | 9 7 5 | 8 1 2 > 5 9 2 | 4 | 3 7 6 > > 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 > (although we don't know which yet), and that means d (which is in > line with both b and c) cannot be a 1. Therefore it's a 9, and the > rest of the solution follows easily. Isn't this just an example of a so-called "forcing chain"? (e.g. see http://www.simes.clara.co.uk/programs/sudokutechnique7.htm) If I am not mistaken, yours is a case of the following forcing- chain pattern (my ab, bc, ..., are the candidate numbers in a cell, where a,b,c,... are distinct): (1) ab ca b ca ab bc ==> a bc Two more such chains are ... (2) ab da b da ab bc cd ==> a bc cd and (3) ab ea b ea ab bc cd de ==> a bc cd de In each case, starting with, say, the pair of candidates in the upper right cell, each candidate leads to the conclusion that the upper left cell must be 'b' and the lower left cell is 'a'. (More might be implied, depending on the box boundaries.) It seems to me that these examples support the idea that when people say a sudoku "requires guessing" (backtracking), what it amounts to is that the patterns (forcing chains, etc.) necessary to solve it are simply not among those they recognise. If they find a guess that leads to a contradiction, this can lead to a "new" pattern that can be added to their repertoire, if their memory is good enough. (The pattern of many chains is far too complicated to be considered "memorable".) E.g., pattern (2) emerged from a "guess" needed to solve the 8/21 LA Times sudoku. --r.e.s.
From: Patrick Hamlyn on 24 Aug 2005 21:21 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. OK not a *whole* lot easier... -- Patrick Hamlyn posting from Perth, Western Australia Windsurfing capital of the Southern Hemisphere Moderator: polyforms group (polyforms-subscribe(a)egroups.com)
From: Ed Murphy on 25 Aug 2005 02:00
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 * "only 3 values" is overly specific; if d could be 1 or 7, then d = 1 could be ruled out by the same method |