Sudoku: step-by-step solution of a harder puzzleSolving a Harder Sudoku PuzzleWhat you see and what you getThis is a step by step solution of a random Sudoku "devilish" puzzle, intended to demonstrate additional methods of solution. It is a follow-up to a web page analyzing a simpler puzzle--simpler, though not too easy, either. If you have not done so, it might be a good idea to start there.As before, follow the steps listed below provide an idea of how the solution is derived. There may exist other approaches--but here are the methods I used, and they worked. The array used is pictured above; it is suggested you bring it up on the screen (in larger format) by clicking here, print it and then use a pencil to fill in the empty squares, in the order of the steps outlined below (you may add in the corner of each cell filled its number in the sequence of steps, to help retracing your route). As before, some intermediate stages of the solution will be shown, with added numbers marked with *. (the lines below are repeated from the earlier puzzle)
A Sudoku puzzle contains 9 rows of 9 numbers, each containing (1, 2, 3 ... 9) in a different order, and the same holds for the columns. In addition, however, each Sudoku array can be divided into 9 smaller 3-by-3 squares, each of which which also must contain all the numbers (1,2,3....9). In fact many such arrays exist. The challenge of the puzzle is--given just some of the numbers of a specific array, fill in the missing ones, using only logical deduction based on the above requirements. The puzzle consists of a square array of 81 cells, which can be divided into 9 columns, (counted from the left), each containing 9 cells. In each column, cells are numbered from the bottom. Or else, it can be divided into 9 rows (counted from the bottom), each containing 9 cells. In each row, cells are numbered from the left. A notation like 6 (3,2) will mean the number "6" in cell 2 of column 3 Extra division lines (or darker ones) divide the array into 9 boxes, each with 3 rows of 3 cells each. To define the positions of boxes, it is easiest to classify them by stacks and tiers: Three boxes in a vertical columns will be called a stack (distinguishing left, right or middle stacks) Three boxes in a horizontal row will be called a tier (distinguishing bottom, top or middle tiers) The requirement of the puzzle:
No number may be repeated, none can be left out. Added Comment on Unresolved PairsAdditional notes on solving the puzzle can be found with the preceding puzzle. The hints there include "solution rule 2" or SR2:
If that variety includes all numbers except for one, that remaining number is the only choice remaining. Here this rule is not sufficient, and we may need use cells where, on applying this method, all numbers but two are eliminated. By itself, this information is not particularly useful--knowing, for instance, that the only numbers which can appear in that cell would be 2 or 7. However, if we test another cell in the same box and also find that the number in it must be either 2 or 7, then we have an unresolved pair. These two cells must contain 7 and 2: we do not know in which order--and it may take a while before we do--but in filling other cells in the same box, we may safely assume that the number needed is not either 7 or 2. Instead of "box" we may equally write "row" or "column". In particular, if all cells except for two in a row or column are filled, the two cells left are also an unresolved pair. That is no help in filling other cells in that row or column--they are already full!--but if these two cells also belong to the same box, the information may help fill other cells there.
Numbers entered as part of the solution will be introduced in the order in which they are derived, numbered in parentheses. Copy the puzzle here, print it and enter numbers as they are derived. Unresolved pairs may be written in tiny numerals--and if you use a pencil, you can erase ambiguous entries when they can be replaced by final ones. The first 13 cells are relatively easy--but can't be skipped, they will be needed later. [1] 2 (8,3)
Now choices become limited. Using SR2--in filling an empty call, excluding all numbers of the same row, column or box--may leave one not with one choice but two. In the middle box of the top tier (6, 9) can be 1 or 3 (6, 8) can be 1 or 3 , too.
(4, 9) can be 6 or 8 only (4, 8) can be 6 or 8 only, too, by a similar argument.
[14] 5 (5, 8)
[15] 6 (5, 2)
The top box and the bottom box in the middle stack each have two empty cells, in the same row. Taking into account cells with known contents (including unresolved pairs in the top box), these cells must contain either 2 or 4. Two of the cells on top and bottom share the same column, and therefore their numbers must differ. They too, are an unresolved pair. (Each also forms a separate UP with the empty cell to its right, but that is not used right now). In the drawing above, UPs are denoted by two numbers sharing the same cell Even if the order of 2 and 4 in the above pair is not known, the remaining two cells in the 4th column must contain 3 and 9. There is already a 3 at (7, 5), so [17] 9 (4, 5) ---------------------------- [18] 3 (3, 8)
[20] 1 (6, 8) [21] 9 (9, 4)
[22] 3 (2, 4)
[23] 2 (2, 5)
Also, the middle box of the first stack has only one place open for the "6":
I saw no way of deducing that, except tracing the consequences of each choice, and see which one leads to a dead end. (Computer programs to solve Sudokus use this approach, but a machine can trace choices much faster than a human). It worked, but needed too many steps before a contradiction was reached, allowing one of the choices to be ruled out. You can follow that sequence by clicking here: the lesson seems to be: try to avoid such trials of choices unless absolutely unavoidable, and search all avenues before resorting to them! Later I realized, a better choice existed, solving the cell (9,5): [26] 8 (9, 5)
[27] 1 (9, 7)
[28] 6 (9, 8)
[30] 8 (8, 9)
[32] 8 (4, 8)
[33] 1 (1, 9) [34] 9 (2, 9)
[36] 6 (2, 7)
[38] 9 (1, 6)
------------------------------ [40] 5 (2, 6)
[43] 4 (3, 6) [44] 7 (3, 4)
The remaining cells are rather easy to fill [45] 8 (5, 6) [46] 1 (7, 6)
[47] 4 (7, 4)
[49] 1 (5, 4) [50] 6 (6, 4)
Now the time has come to deal with the ambiguous cells with can be filled by either "2" or "4". There has to be a "4" in column 6, but of the remaining free cells, one is disqualified by having a "4" right next to it. Therefore [51] 4 (6, 2)
[55] 7 (6, 5) ---------------------------- Further ExplorationAn article "The Science behind Sudoku" by Jean-Paul Delahaye appeared in Scientific American, June 2006, p. 80-87.(Also cited in the preceding web page.) |