Sudoku
in [Math]
|
Prev: How many Primes?
Next: divisor problem
From: Hauke Reddmann on 17 Aug 2005 05:43 In sci.math Stephen J. Herschkorn <sjherschko(a)netscape.net> wrote: > Sometimes, I get myself to a point where all I can do is guess and see > if this leads to a contradiction. For this, I just copy the current > worksheet and put a border around the cell where I make the guess. Well, I can't really draw hypotheses from having done about just 10 Sudokus (it's a VERY fresh fad here in Germany too :-) of various difficulty but I never needed more than 2nd degree of logic (A can be filled with X but then I foul up at B) to solve, and in most cases straightforward "A can only filled with X/X can only go to A"), recursively applied, sufficed. Feel free to email me a superhard Sudoku to prove me wrong :-) -- Hauke Reddmann <:-EX8 fc3a501(a)uni-hamburg.de His-Ala-Sec-Lys-Glu Arg-Glu-Asp-Asp-Met-Ala-Asn-Asn
From: on 17 Aug 2005 06:35 In article <ddv0re$1q5$2(a)rzsun03.rrz.uni-hamburg.de>, Hauke Reddmann <fc3a501(a)uni-hamburg.de> writes: >In sci.math Stephen J. Herschkorn <sjherschko(a)netscape.net> wrote: > >> Sometimes, I get myself to a point where all I can do is guess and see >> if this leads to a contradiction. For this, I just copy the current >> worksheet and put a border around the cell where I make the guess. > >Well, I can't really draw hypotheses from having done about >just 10 Sudokus (it's a VERY fresh fad here in Germany too :-) >of various difficulty but I never needed more than 2nd >degree of logic (A can be filled with X but then I foul up >at B) to solve, and in most cases straightforward "A can >only filled with X/X can only go to A"), recursively >applied, sufficed. > >Feel free to email me a superhard Sudoku to prove me wrong :-) To save me time, I wrote a simple program that fills in all straightforward deductions of the kind: 1) The only number that can go in this square is 3. 2) The only place where the 5 in row 7 can go is here. I found that this completely solves almost all puzzles rated easy or medium. It sometimes fails to solve difficult problems. For these, I have found one application of one of the following types of reasoning will complete it. 3) The 3 in row 5 must go in column 1 or 3. In either case, this forces the 3 in row 6 to go in column 5. 4) The 3 and the 7 in row 5 must go in columns 1 and 3. Hence no other number can go in either of these places, which then enables you to place another number somewhere else. Derek Holt. `
From: john_ramsden on 17 Aug 2005 06:54 m...(a)mimosa.csv.warwick.ac.uk () wrote: > > > Feel free to email me a superhard Sudoku to prove me wrong :-) > > To save me time, I wrote a simple program that fills in all > straightforward deductions of the kind: > > 1) The only number that can go in this square is 3. > > 2) The only place where the 5 in row 7 can go is here. > > [...] Although it may sound almost heretical, I must admit these Sudoko puzzles leave me completely cold; they seem almost as daft and pointless as those alphametic puzzles such as CAT + DOG = SCRAP. (That's not meant to imply I find either type easy, quite the reverse.) 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.
From: John R Jones on 17 Aug 2005 09:01 Stephen J. Herschkorn wrote: > In sci.math, Ioannis wrote: > > >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. > > > >... Yes Excel is a clear choice for this. I added a "help" function which works out what values each cell can be and what cells must be. The algorithms used: a value is forced if there is a singleton in the "can be" matrix, or if it is the only position left for that digit in a row, column or squarelet. This is all done by worksheet formulae. I then wrote a macro to copy the musts to the puzzle cells, re-apply the algorithms and iterate until there are no more musts. The idea was that I would then only have to guess some values and backtrack manually. However, I have yet to find a puzzle that isnt automatically filled in by the blessed thing :-(. Any really tough ones out there? JJ
From: mensanator@aol.compost on 17 Aug 2005 12:54
John R Jones wrote: > Stephen J. Herschkorn wrote: > > In sci.math, Ioannis wrote: > > > > >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. > > > > > >... > > Yes Excel is a clear choice for this. > I added a "help" function which works out what values each cell can be > and what cells must be. > The algorithms used: a value is forced if there is a singleton in the > "can be" matrix, > or if it is the only position left for that digit in a row, column or > squarelet. > This is all done by worksheet formulae. > I then wrote a macro to copy the musts to the puzzle cells, re-apply > the algorithms > and iterate until there are no more musts. > The idea was that I would then only have to guess some values and > backtrack manually. > However, I have yet to find a puzzle that isnt automatically filled in > by the blessed thing :-(. > Any really tough ones out there? The Chicago Sun-Times just started running them a week ago: <http://www.suntimes.com/sudoku> They rate them as Monday: very easy Tuesday: very easy Wednesday: easy Thursday: easy Friday: medium Saturday: hard On the very easy puzzles, I can follow a trail of singletons from start to finish, they are so easy my spreadsheet isn't needed. Saturday's wasn't so simple. The singletons dried up after a few passes and I was left with doubles, leaving me no choice but to guess and follow to the end or backtrack when the guess led to a contradiction. I was stumped before I had a decent backtracking mechanism in place. > JJ |