Sudoku
in [Math]
|
Prev: How many Primes?
Next: divisor problem
From: Stephen J. Herschkorn on 26 Sep 2005 00:04 jgnovak(a)superlink.net wrote: >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? > > I just find a spreadsheet an easier way of erasing numbers I have eliminated. With a clean sheet, I can see what cannot or must go where easier. I never use the computational or logical capabilities of the computer to solve the puzzle. -- Stephen J. Herschkorn sjherschko(a)netscape.net Math Tutor on the Internet and in Central New Jersey and Manhattan
From: mensanator@aol.compost on 26 Sep 2005 00:03 jgnovak(a)superlink.net wrote: > Am I missing something!!!!! I solve these puzzles in the paper the old > fashioned way, with a pencil. Good for you. > Do I have to do them on Excel? No. You don't have to use a pencil either. You could use a pen. But mistakes are easier to correct if you use a pencil. > I have > no problem doing the easy and medium, (within ten to twenty minutes), Because easy and medium problems are solvable using only simple logical implications. > but I still have not been able to do a hard. Is there a way to do it > without using the computer? Sure. Learn the hard logical implications and how to recognize them. But you ought to be able to solve the hard puzzles with guessing and backtracking (where a pencil comes in handy). They say guessing/backtracking is never required, but it does work when you can't see the logical implication.
From: Jon Haugsand on 26 Sep 2005 02:06 * mensanator(a)aol.com > They say guessing/backtracking is never > required, but it does work when you can't see the logical > implication. Is there a definition of when "logical implication" ends and "guessing/backtracking" starts? If you say "4 cannot be put in (3,5) because then you need 5,7 or 9 in (3,8), but that leads to ..........[deleted a looooong part of the sentence] ..... so that column 3 doesn't get a 1." I assume all guessing/backtracking can be reduced to such sentences. On the other hand, a *real* beginner can say "I guess a 1 in (2,2). Let us see. Oh there is a 1 in (3,3). It won't work. So, let us go back and remove the guessing." Some people's guessing and backtracking is other people's logical implication, I would think. Or isn't it? -- Jon Haugsand Dept. of Informatics, Univ. of Oslo, Norway, mailto:jonhaug(a)ifi.uio.no http://www.ifi.uio.no/~jonhaug/, Phone: +47 22 85 24 92
From: mensanator@aol.compost on 26 Sep 2005 03:12
Jon Haugsand wrote: > * mensanator(a)aol.com > > They say guessing/backtracking is never > > required, but it does work when you can't see the logical > > implication. > > Is there a definition of when "logical implication" ends and > "guessing/backtracking" starts? If you say "4 cannot be put in (3,5) > because then you need 5,7 or 9 in (3,8), but that leads to > .........[deleted a looooong part of the sentence] ..... so that > column 3 doesn't get a 1." I assume all guessing/backtracking can be > reduced to such sentences. That's my understanding. Hard means how long and complicated the sentence is. > On the other hand, a *real* beginner can > say "I guess a 1 in (2,2). Let us see. Oh there is a 1 in (3,3). > It won't work. So, let us go back and remove the guessing." > > Some people's guessing and backtracking is other people's logical > implication, I would think. Or isn't it? I don't think so. Guessing means you are choosing from more than one number. Logical implication means there is only one possible choice. For instance, my sudoku.xls spreadsheet doesn't solve the puzzles, it just indicates what numbers are possible for each cell. When my sheet shows --------1 in a cell, it means 1 is the only choice for that cell. That's a very simple logical implication. Other times, I'll see -------21 --------21 .......... <-- indicates cell filled ------321 .......... .......... .......... .......... .......... so although at this point it would appear that cell (1,2) can contain either 1, 2 or 3. But it must be 3 by the more complicated logical implication that a 3x3 region must contain a 3. Even though the cell is showing three numbers there is only one choice. You get stuck when you have -------21 --------21 .......... .......... .......... .......... .......... .......... .......... and no simple rule to decide which cell gets 2 and which gets 1. At this point you can guess and if you are wrong (assuming the puzzle has a unique solution) eventually my sheet will show you a cell containing ---------- which means the cell is empty and there is no number that can be placed in it. The guess must have been wrong so you bactrack and switch the original guess to the other number. It is my understanding that at the point I made the guess, there is a logical rule (x-wing, coloring, etc.) that would have pointed to the right number if only I had been savvy enough to see it. > > -- > Jon Haugsand > Dept. of Informatics, Univ. of Oslo, Norway, mailto:jonhaug(a)ifi.uio.no > http://www.ifi.uio.no/~jonhaug/, Phone: +47 22 85 24 92 |