Notices
Results 1 to 6 of 6

Thread: Solving Sudoku

  1. #1 Solving Sudoku 
    Forum Bachelors Degree
    Join Date
    Apr 2009
    Posts
    416
    I was recently forced to spend some deal of time sitting down at the DMV. so, to occupy said deal of time, i brought along a Sudoku book. Being of academic inclination I believe most members of the forum know the basics of Sudoku, however for those who do not know:

    A sudoku problem is a 9x9 grid of squares - thus totaling 81 tiles - which when complete have the numbers 1-9 repeating exactly once in every row, column, and major box. a major box is one of nine boxes consisting of a smaller 3x3 grid inside of the 9x9 grid. A sudoku problem is only considered properly posed if it can be solved without any guessing, and if none of the hints - tiles already filled in - are redundant. This means that if the tile were erased, you could not use logical methods to derive the correct value for the tile using only the hints.

    the objective is of course to fill in all the tiles such that each row, column, and box has the numbers 1-9 exactly once each. This requirement of a solved sudoku problem leads to a number of logical devices that can be used to solve it. Here I wish to present a novel logical device which can be implemented by humans (as opposed to the many devices computers can use) to rapidly solve the puzzles.

    The device I present requires an initial input of time, however after this time input it greatly decreases the amount of time that must be spent to complete each next tile.

    one starts by examining the top-most, left-most square. If the square is a hint, proceed onto the next square, otherwise identify the values of all the hints and previously filled squares which share either a major box, row, or column with the square in question. mark the box with all the values that are not identified in this manner, these are the possibible values of the box.

    one then repeats this process for the next square to the right, and continues in this manner down the rows untill all the squares are either marked or are a hint.

    during this process the better part of the squares will have multiple possible values, however some squares invariably are identified as having only one possible value as a result only of the hints.

    begin with one of these known squares. upon filling in its value, you can eliminate that value as a possibility from the squares that share a row, column, or major box with it. This often reveals other known squares, and if it does not then there are other known squares for which to repeat this process and eliminate more possibilities. It is key that upon filling in a known square you immediately remove it as a possibility from that boxes which it affects, as if you do not you will end up with a lack of important information about the potential values of boxes.

    I have found that in all well posed sudoku puzzles, it is possible to rapidly complete the grid(within minutes for a well practiced person) once the initial possibility plotting is done.

    if anyone believes my method is faulty, a better method exists, i have not explained it sufficiently, or that improvements can be made i welcome your criticisms.


    physics: accurate, objective, boring
    chemistry: accurate if physics is accurate, slightly subjective, you can blow stuff up
    biology: accurate if chemistry is accurate, somewhat subjective, fascinating
    religion: accurate if people are always right, highly subjective, bewildering
    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Senior
    Join Date
    Sep 2006
    Posts
    399
    When I do a soduko I never write the little numbers in the corner unless there are only two such possible numbers. That way if another box in the row, column, or square shares the same pair, then you can exclude those numbers from the remaining boxes in that row, column, or square; I often find that very useful.

    I once saw a woman on an airplane doing the method you describe -- it looked tedious and no fun.


    Don't bother visiting my Earth Sciences forum, it died a death due to lack of love
    Reply With Quote  
     

  4. #3  
    Suspended
    Join Date
    Apr 2007
    Location
    Pennsylvania
    Posts
    8,795
    What you have outlined sounds like a fairly standard technique, which works well for the easier puzzles. Have you tried it on puzzles rated "hard" or "very hard"?

    I think with the harder puzzles you have to think a little bit deeper. As an example, you may know that a number fits into a particular row or column of a 3 by 3 box, but there are 2 or 3 possibilities. However you can use the information to eliminate the possibility of the same number appearing in that row or column of another 3 by 3 box.
    Reply With Quote  
     

  5. #4  
    Forum Bachelors Degree
    Join Date
    Apr 2009
    Posts
    416
    i have used this technique on a 16x16 grid, and it was still effective. the method you describe is one of a few different patterns that can be used to derive information that is not available looking only at the hints. however, even doing the 16 grid I did not need to use them, although they are useful.
    physics: accurate, objective, boring
    chemistry: accurate if physics is accurate, slightly subjective, you can blow stuff up
    biology: accurate if chemistry is accurate, somewhat subjective, fascinating
    religion: accurate if people are always right, highly subjective, bewildering
    Reply With Quote  
     

  6. #5  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    There's many established (and named) techniques: SadMan Software: Techniques for Solving Sudoku. All work for any sized grid.
    Reply With Quote  
     

  7. #6  
    Forum Professor arKane's Avatar
    Join Date
    Apr 2009
    Location
    Washington state
    Posts
    1,181
    Quote Originally Posted by MagiMaster View Post
    There's many established (and named) techniques: SadMan Software: Techniques for Solving Sudoku. All work for any sized grid.
    Nice link. Before I had a hard drive crash I had an impressive Sudoku game collection and one thing I noticed was that absolutely everyone that puts a Sudoku game together has their own flavor of generated games to the point where you could tell the difference from one game to the other. Yes I liked some better than others. I sometimes found myself liking only the games that didn't provide tips, because I didn't want to get used to depending on tips. You might say that you don't have to use the tips feature just because it's there. But the trouble is if it's there it will get used.
    Reply With Quote  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •