Site Map

         

Sudoku: step-by-step solution of a harder puzzle


Solving a Harder Sudoku Puzzle

What you see and what you get

    This 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)

        Sudoku comes from Japan (it originated in the US in 1979, but became popular in Japan after 1984--see article in "Scientific American" cited at the bottom) and is based on what mathematicians call "Latin Squares"--square arrays of numbers in which every number appears exactly once in any row and in any column (different letters, colors or symbols may be used in place of the numbers).

        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:
      Every column, row and box must contain all the nine numbers 1,2,3 ... 9.
      No number may be repeated, none can be left out.

Added Comment on Unresolved Pairs

Additional notes on solving the puzzle can be found with the preceding puzzle. The hints there include "solution rule 2" or SR2:
    The same number cannot appear twice in any row, column or box. Therefore, we look for cells whose row, column and box contain between them a wide variety of numbers.
        If that variety includes all numbers except for one, that remaining number is the only choice remaining.
In the puzzle used earlier as an example, the upper right corner cell was a good candidate for this approach. Its row contained (8, 5, 1, 4, 3), its column (9, 4, 2, 6, 8) and its box (in addition to the cells mentioned above), (8, 7). Thus all numbers but "9" were accounted for, showingt hat "9" belonged in the cell: any other number in that cell would have forced a duplication.

    Here this rule is not sufficient, and we may need use cell 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.
        In principle, it is possible to need to identify unresolved groups of more than two cells. In the case below, two unresolved pairs together help fill another cell in the same box, so that we are really using a group of 4 unresolved cells, arranged in two pairs. Larger unresolved groups make the puzzle more difficult. With a pair, once one of the cells is filled, the other one is also solved, but with larger groups that is no longer true.

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)
    Only one choice (OOC) exists here
[2]     3 (9,3)
    Only one choice (OOC) exists.
[3]     3 (1,2)
    OOC here too. Couldn't have got here without the preceding step!
[4]     8 (2,1)
    OOC here too
[5]     9 (5,3)
    OOC here too (in the rows)
[6]     6 (3,1)
    OOC here too. We are trying to fill the bottom left box.
[7]     8 (6, 3)
    OC for an 8 in the 3rd row
[8]     8 (7, 2)
    OC for an 8 in that row. We are on our way to filling the bottom right box.
[9]     4 (8,1)
    OOC a 4 in that box.
[10]     7 (9,1)
    Last cell left in the box
[11]     5 (6,1)
    OOC
[12]     7 (7,7)
    OOC
[13]     1 (4,1)
    OOC... but here the easy choices have run out.
--------------------------------
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.
    Therefore, the numbers (1, 3) in that box are an "unresolved pair"--they occupy those cells, but in an unknown order.
Similarly, in the same box, since (1,3) are already in one of the above cells

(4, 9) can be 6 or 8 only
(4, 8) can be 6 or 8 only, too, by a similar argument.
    Therefore, (6, 8) in that box are another unresolved pair (UP).


[14]     5 (5, 8)
    With (1,3,6, 8) excluded by unresolved pairs in the box, and (2, 4, 7, 9) disqualified by sharing the same row or column, this is the only choice.

[15]     6 (5, 2)
    By the above argument, column 4 has a "6" (even though we don't know in which of two cells it is). Therefore "6" must occupy this cell--each adjacent column already includes that number.

        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
[16]     3 (4, 6),    and
[17]     9 (4, 5)
----------------------------
[18]     3 (3, 8)
    Next, using SR2 gives [18]. Filling this cell resolves the order of one unresolved pair:
[19]     3 (6, 9)
[20]     1 (6, 8)


    [21]     9 (9, 4)
        The "9" in [17] leaves no other choice.

    [22]     3 (2, 4)
        No other place in this box allows a "3"

    [23]     2 (2, 5)
        There must exist a "2" in this box and column.
    Also, the middle box of the first stack has only one place open for the "6":
    [24]     6 (1, 5)
    from which
    [25]     6 (8, 4) [26A]     5 (1, 3)
[27A]     4 (3, 3)
    have been added in skinny numerals, and so have all the other choices deduced from them, whose numbering will be distinguished by the letter "A".

        Having placed the "4", we can now complete column 3, and because of the "5" in (4,4), only one choice remains:
[28A]     5 (3, 6)
[29A]     7 (3, 4)
    The middle box of the first stack has only one place open for the "4":
[30A]     4 (1, 6)
    leaving only one cell open for the "9"
[31A]     9 (2, 6)

    We proceed to the top left box. Somewhere in it must be a "5" and a "6", but these can only be in the middle column--in the two flanking columns, those numbers are already in place, lower down in the puzzle. However, before trying to place them, it helps to examine the right hand top box, which has 4 empty cells--two on the right edge of the puzzle and two on the top edge--and the missing numbers which go there are (1, 5, 6, 8).

        Of these, "5" cannot be on the right edge of the puzzle, because the column along that edge already has a "5" at (9,2). Therefore "5" must go into one of the cells along the top edge, either (7,9) or (8,9). Therefore, no matter which of the two it is, another "5" cannot go into the top row of the left hand top box. This decides our choice in placing the next two numbers: the "6" must go on top, the "5" below it.
[33A]     5 (2, 7)
[34A]     6 (2, 9)
    (The two remaining cells of the box are easily filled--9 obviously goes into the corner of the puzzle--but are not relevant here).

        The placing of the "6" in the top row resolves the ambiguity of the unresolved pair in (4,9) and (4,8), either of which could hold either a "6" or an "8." Because of [34a], that choice is decided as
[35A]     8 (4, 9)
[36A]     6 (4, 8)
    It follows that neither 8 nor 6 could go in the top cells of the right-hand top box (anyway, at most one of them could do so, since it was earlier determined that "5" must also be placed there). That forces them into the right side of the box, into cells (9,7) and (9,8).

        And here comes the crunch. Only one free cell remains on the right-hand edge of the puzzle, cell (9,5), and the only number missing in that column is "1." However, that row--row 5--already has a "1" in it, in cell (3,5)!

Therefore, the assumed placement does not work and we are left with:

[26]     4 (1, 3)
[27]     5 (3, 3)


Two more unresolved pairs must now be added in the middle box of the first stack:
    The two blank cells in column 3 ((3,4),(3, 6)) must hold 7 and 4.
   Then, the first two cells in row 6, ((1,6),(2, 6)) must hold 9 and 5.

    In the 3 boxes of the middle tier, therefore, the first box has 5 in the top row. The second box already has a 5 (in the bottom), so the third box must have 5 in the middle row. Only one choice:
[28]     5 (8, 5)
    This leaves only one choice for a "5" in the top right box:
[29]     5 (7, 9)
                The remaining cells are relatively easy:

[30]     1 (9, 7)
    Of the two remaining open cells on the right edge, one must contain a "6". One already has that number in its row, leaving OOC:

[31]     6 (9, 8)
            And completing the box:
[32]     8 (8, 9)
    The last step resolves an ambiguity

[33]     8 (4, 8]
[34]     6 (4, 9)
    Next, the top row can be completed:
[35]     1 (1,9)
    Only one choice for the last cell:
[36]     9 (2, 9)
    This now resolves an ambiguity on the start of row 6:
[37]     9 (1, 6)
[38]     5 (2, 6)

[39]     6 (2, 7)     Last empty cell in column 2.
[40]     5 (1, 7)     Last empty cell in column 1.
---------------------------------
[41]     8 (9, 5)     Last empty cell in column 9.
[42]     8 (5, 6)     Last "8" to be placed.
[43]     7 (8, 6)     SR2--all others ruled out.
[44]     4 (3, 6)     Ambiguity removed by step [43].
[45]     7 (3, 4)     Other side of the ambiguity.
[46]     7 (6, 5)

    crossing of the only row and and only column that lack a "7".

[47]     4 (5, 5)
    Last empty cell in row 5. Filling it now helps resolve the several ambiguous pairs of "2" and "4"
----------------------------
[48]     2 (5, 7)     One ambiguous pair
[49]     4 (4, 7)    




[50]     2 (4,2)     Another ambiguous pair
[51]     6 (2, 7)    
[52]     2 (6,4)

        Last numbers in their columns
[53]     4 (7,4)    
[54]     1 (5,4)    
[55]     1 (7,4)    
----------------------------

Further Exploration

    An 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.)