untamed

"Where the mind is without fear and the head is held high; Where knowledge is free; Where the world has not been broken up into fragments by narrow domestic walls; Where words come from the depth of truth; Where tireless striving stretches its arms toward perfection; Where the clear stream of reason has not lost its way into the dreary desert sand of dead habit; Into that heaven of freedom it should be our intent. ( my adaption from Rabindranath Tagores famous lines)

Tuesday, July 12, 2005

Sudoku - Solving techniques

SUDOKUSolving techniques
Fundamentally there exist 2 logical methods of solution:
First: In elimination, progress is made by successively eliminating candidate numbers from one or more cells to leave just one choice. After each answer has been achieved, another scan may be performed - usually checking to see the effect of the latest number. There are a number of elimination tactics. One of the most common is "unmatched candidate deletion". Cells with identical sets of candidate numbers are said to be matched if the quantity of candidate numbers in each is equal to the number of cells containing them. For example, cells are said to be matched within a particular row, column, or region if two cells contain the same pair of candidate numbers (p,q) and no others, or if three cells contain the same triple of candidate numbers (p,q,r) and no others. These are essentially coincident contingencies. These numbers (p,q,r) appearing as candidates elsewhere in the same row, column, or region in unmatched cells can be deleted.
Second: In the what-if approach, a cell with only two candidate numbers is selected and a guess is made. The steps above are repeated unless a duplication is found, in which case the alternative candidate is the solution. In logical terms this is known as reductio ad absurdum : For each candidate for a cell, the question is posed: will entering a particular number prevent completion of the other placements of that number? If the answer if yes, then that candidate can be eliminated. The what-if approach requires a pencil and eraser. This approach may be frowned on by logical purists as too much Trial and Error but it can arrive at solutions fairly rapidly.

Ideally one needs to find a combination of techniques which avoids some of the drawbacks of the above elements. The counting of regions, rows, and columns can feel boring. Writing candidate numbers into empty cells can be time-consuming. The what-if approach can be confusing unless you are well organised. The SOLUTION is to find a technique which minimises counting, marking up, and rubbing out.
To get this drudgery out of the way try this link http://www.angusj.com/sudoku/ which is “Simple Sudoku” and it does the “markings” for you. In this site also see the "a step by step guide for solving Sudoku" on the very first page. It is excellent.

For persons not familiar with reductio ad absurdum, it is a mode of argumentation that that seeks to establish a contention by deriving an absurdity from its denial, thus arguing that a thesis must be accepted because its rejection would be untenable. It is a style of reasoning that has been employed throughout the history of mathematics and philosophy from classical antiquity onwards. Say, I have a Su Doku puzzle partially filled in and I see there are two squares within a box, row or column where some symbol could go. If I show that putting it in one box leads to a chain of logical deductions from which a contradiction follows, then the alternative must be correct. Many mathematical theorems can be proven using proof by use of reductio ad absurdum, for example the fact that the square root of 2 is not the ratio of two integers.( My observation: Even though the proof of the irrationality of the square root of two using this method is accepted by mathematicians ,I still believe it is not the strictest proof ; it is indirect proof.)

1 Comments:

  • At 12:14 PM, Anonymous Anonymous said…

    Great post on sudoku tips and techniques! I humbly ask that you try my new sudoku puzzles that you can get via a daily email or RSS feed. Thanks!

     

Post a Comment

<< Home