Sudoku
in [Math]
|
Prev: How many Primes?
Next: divisor problem
From: edward on 29 Aug 2005 13:31 On 24 Aug 2005 21:07:40 +0100 (BST), 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. This has been previosly refered to as an "xy-wing" -- the shortest possible forcing chain. It is implemented as a solving tactic in "Simple Sudoku". (http://www.angusj.com/sudoku/) See: http://www.setbb.com/phpbb/viewtopic.php?t=63&mforum=sudoku and: http://sudoku.com/forums/viewtopic.php?t=992 What is strange to me is that this simplest version is often the only difference between someone rating a puzzle "easy" or "diabolical" or some such over the top hyperbole. In fact, some software (Pappocom) insist that this teensy little pattern makes the puzzle completely invalid.
From: r.e.s. on 29 Aug 2005 14:20 <edward(a)margaretcho.com> wrote ... > This has been previosly refered to as an "xy-wing" -- the shortest > possible forcing chain. The following is an even simpler forcing chain ... Exclusion of 'a' from 'xa' by "naked pairs": ab / | xa | \ | ab (Each line joins two cells in the same row, column, or box.) > What is strange to me is that this simplest version is often the only > difference between someone rating a puzzle "easy" or "diabolical" or > some such over the top hyperbole. In fact, some software (Pappocom) > insist that this teensy little pattern makes the puzzle completely > invalid. They're wrong to say such sudokus are "not solvable by logic alone". There is no basis for allowing the above "exclusion by naked pairs" as using "logic only", but not likewise "exclusion by an xy-wing": ab / \ xa bc \ / ac --r.e.s.
From: Ulysse Keller on 30 Aug 2005 20:07 On Mon, 29 Aug 2005 18:20:45 GMT, "r.e.s." <r.s(a)ZZmindspring.com> wrote: ><edward(a)margaretcho.com> wrote ... >> This has been previosly refered to as an "xy-wing" -- the shortest >> possible forcing chain. >The following is an even simpler forcing chain ... >Exclusion of 'a' from 'xa' by "naked pairs": > > ab > / | > xa | > \ | > ab > >(Each line joins two cells in the same row, column, or box.) > >> What is strange to me is that this simplest version is often the only >> difference between someone rating a puzzle "easy" or "diabolical" or >> some such over the top hyperbole. In fact, some software (Pappocom) >> insist that this teensy little pattern makes the puzzle completely >> invalid. >They're wrong to say such sudokus are "not solvable by logic alone". >There is no basis for allowing the above "exclusion by naked pairs" >as using "logic only", but not likewise "exclusion by an xy-wing": > > ab > / \ > xa bc > \ / > ac > >--r.e.s. > I agree ... partially ! OK, it is stupid to say that *any* sudoku is "not solvable by logic alone" - I consider that to solve means to find all solutions (which implies to prove / verify that the solution is unique if it is ...) and even "brute force" with a lot of backtracking might be called using logic as long as it is done correctly - using a computer to do it might be more critical (at least if it does not output its complete 'reasoning' so that it can be verified by the human operator ...) but let's forget this here ... On the other hand, I pretend that the triangle above is much simpler than the xy-wing. Doing about 15 sudokus contained in my daily newspaper (all I attacked I finished !) I sometimes used the following general principle, which indeed is a bit less trivial than the usual simple methods: When a line, a column or a box contains n cells (usually n=2 or 3 in practice) such that a subset S of the 9 ciphers is known such that S has n elements and each of the n cells must contain a cipher belonging to S (but one does not know which one), then the ciphers of S are "occupied" in the line / column / box, meaning that the other cells of the l. / c. / b. may *not* belong to S. May-be you think that your triangular forcing chain is more general than the case n=2 of my general principle (*) - but this would be an illusion, because if 3 cells are such that each pair made of 2 of the 3 is in a line, a column or a box, then there is a line, column or box containing all 3 ! (This is a fact completely independent of the contents of the cells ...) Proof: for 2 cells to be in a line, column or box is an equivalence relation, so that if two pairs out of the 3 given cells are in the same of the 3 relations, then all 3 cells are in a line, column or box. So let us suppose that none of the 3 relations applies to more than one pair out of the 3 cells (there are three such pairs). Because we have 3 relations, this implies that one pair must be in a box, one in a line and one in a column. Call the cells A,B,C and say that B,C are in a box; we can also suppose without loss of generality that A is in a line with B and in a column with C. Then A is in the intersection of the line containing B and the column containig C. But this intersection consists of only one cell, which belongs to the box containing B and C ! (BTW this means that the case we just considered is 'void' - by contradiction, but this is not essential to this proof ...) (*) which is still rather simple to use and to discover / understand, so that it might be added to the usual simple methods - whereas when I tried the sudoku of Simon Tatham, I was first stuck exactly in the configuration in which he introduced the variables a,b,c,d for the contents of four cells - and to continue would have needed some mini-backtracking (or proof by contradiction if one prefers) but in fact I looked at Simon's 'picture' with a to d and 'could not help' reading his argument so that I used it and indeed could finish the sudoku nearly instantly after that ... I also find that it is probably not so easily to just see an xy-wing in solving a sudoku !
From: r.e.s. on 30 Aug 2005 22:13 "Ulysse Keller" <ulysse(a)ulysseK.ch> wrote ... > When a line, a column or a box contains n cells (usually n=2 > or 3 in practice) such that a subset S of the 9 ciphers is known > such that S has n elements and each of the n cells must contain > a cipher belonging to S (but one does not know which one), > then the ciphers of S are "occupied" in the line / column / box, > meaning that the other cells of the l. / c. / b. may *not* belong > to S. The well-known methods of "hidden subsets" and "naked subsets" are among those explained at the website I mentioned. > May-be you think that your triangular forcing chain is more general > than the case n=2 of my general principle No, I don't think that. > I looked at Simon's 'picture' with a to d and 'could not > help' reading his argument so that I used it and indeed could finish > the sudoku nearly instantly after that ... I also find that it is > probably not so easily to just see an xy-wing in solving a sudoku ! The pattern Simon described (which is an xy-wing), can be difficult to recognise when it occurs, but it's certainly not the "blind trial & error" that some people find so objectionable. --r.e.s.
From: jgnovak on 25 Sep 2005 23:31
Am I missing something!!!!! I solve these puzzles in the paper the old fashioned way, with a pencil. Do I have to do them on Excel? I have no problem doing the easy and medium, (within ten to twenty minutes), but I still have not been able to do a hard. Is there a way to do it without using the computer? |