# Non brute-force Sudoku

The mypuzzle.org site (Difficulty = Hard, Date = 2016-07-12) has the following Sudoku puzzle. I filled in a three easy cells (in square brackets) but then got stuck. Aside from brute force, is there a 'nice' continuation to this particular Sudoku?

It would be reasonable to assume that this is a valid Sudoku, so strategies like unique rectangles may be used.

The next step is to fill in the squares with all valid possibilities. E.g. the digits in each blank spot in the top row (call them A3 and A4) are 1 or 8, and as @Marius commented, G2 is either 1 or 5 (we get this from having 1, 2, 5 as the remaining candidates in the bottom-left 3x3 square; row G already has G7=2, so G2 can only be 1 or 5).

This puzzle seems insufficiently constrained, and even the built-in solver from the "To Solver" button gave up. However, the difficulty level isn't the highest and presumably these puzzles are produced and verified algorithmically - hence this post.

 3[4]_ | _ 7 2 | 5 9 6
_ _[9]| 4 _ _ | _ _ 2
_ _ 7 | _ _ _ | 3 _ 4
-----------------------
_ _ _ | _ _ _ | _ 4 _
_ _ _ | _ _ _ | _ _ _
_ 9 _ | _ _ _ | _ _ _
-----------------------
8 _ 4 | _ _ _ | 2 _ _
9 _ _ | _ _ 7 |[4]_ _
7 3 6 | 2 4 _ | _ _ 9

• I don't think that this helps much but G2 can be either 1 or 5. – Marius Jul 18 '16 at 12:35
• @Marius True. I'll edit to outline the approach I took. – Lawrence Jul 18 '16 at 12:38
• Another likely unhelpful find, I7 can be either 1 or 8 (1,5,8 for the row, 5 in the 7th column). – Poolsharker Jul 18 '16 at 15:45
• My little mobile app allows for a puzzle to be entered. When I entered these numbers it says that the 'puzzle was not fully entered' which suggests that it might be under-defined. – rhsquared Jul 18 '16 at 16:05

Unfortunately as others have noted their algorithm is not producing "proper" sudokus (proper means "has a unique solution")

Using brute force we can find $80,485$ solutions (I enumerated all using my home brewed brute force solver which utilises a dancing links implementation of Algorithm X).

Since it is not proper, one cannot really employ a couple of solving strategies that rely on the sudoku being proper (such as "unique rectangles" and "bi-value universal grave"), as these can give one solution where there are many, but even if we do use these strategies we still do not find a single solution.

We can employ some of the advanced strategies:
"almost locked sets";
"death blossom";
"cell forcing chains"; and
"Bowman's bingo"
to reduce the possible values for cells to:

+----------------------------+----------------------------+----------------------------+
|       3        4       18  |      18        7        2  |       5        9        6  |
|     156     1568        9  |       4    13568    13568  |     178      178        2  |
|    1256    12568        7  |   15689    15689    15689  |       3       18        4  |
+----------------------------+----------------------------+----------------------------+
|    1256    25678    12358  | 1356789  1235689   135689  |   16789        4    13578  |
|   12456    25678    12358  | 1356789  1235689  1345689  |   16789   123578    13578  |
|   12456        9    12358  |  135678   123568   134568  |    1678   123578    13578  |
+----------------------------+----------------------------+----------------------------+
|       8       15        4  |   13569    13569    13569  |       2    13567      137  |
|       9      125      125  |   13568    13568        7  |       4    13568     1358  |
|       7        3        6  |       2        4      158  |      18      158        9  |
+----------------------------+----------------------------+----------------------------+


Which is, in fact, the same sets of possible values my solver ends up with.

You can see the strategies above in action without working through them by hand by inputting the puzzle into the solver at suokuwiki.org

As a bonus here is one of the minimal additions of ($3$) clues to make the given puzzle as solved so far proper:

+---------+---------+---------+
| 3  4  · | ·  7  2 | 5  9  6 |
| 1  ·  9 | 4  ·  · | ·  ·  2 | < the 1 in this row
| ·  ·  7 | ·  ·  · | 3  ·  4 |
+---------+---------+---------+
| ·  ·  · | ·  ·  · | ·  4  · |
| ·  ·  · | ·  8  · | ·  5  · | < the 8 and 5 in this row
| ·  9  · | ·  ·  · | ·  ·  · |
+---------+---------+---------+
| 8  ·  4 | ·  ·  · | 2  ·  · |
| 9  ·  · | ·  ·  7 | 4  ·  · |
| 7  3  6 | 2  4  · | ·  ·  9 |
+---------+---------+---------+


This is a relatively easy sudoku to solve.

• Thanks for interacting in chat earlier, and posting an answer here :) . I have a question: how did you determine that the sudoku wasn't proper? Was this the conclusion from finding multiple solutions even after applying the advanced strategies, or do you have an independent test? – Lawrence Jul 18 '16 at 23:23
• Personally, being lazy, I found it wasn't proper by asking my solver to generate solutions, as soon as it finds a second solution the puzzle is identified as not proper. To work it out by hand one would need to find two solutions that both work under the rules of sudoku. – Jonathan Allan Jul 18 '16 at 23:27
• You could notice something like the fact that (calling top row 0, left column 0) and a cell (row, column): (0,2),(0,3),(3,2),(3,3) can all be either 1 or 8, and even if the rest were completed this would still be true (like unique rectangles). – Jonathan Allan Jul 18 '16 at 23:36
• There is no known way (other than search) that will work for any given unverified puzzle. – Jonathan Allan Jul 18 '16 at 23:37
• Added a proper sudoku formed by adding clues to your partially solved one. Also note that there are proper sudoku that the strategy-based solver at sudokuwiki.org cannot solve (the solution count will work as it is brute-force), examples are produced on the site at Weekly Unsolvable. There are, however, logical strategies not implemented by the solver. I think I might post a question with some absolutely diabolical ones to see if people can use logical deduction to solve them. – Jonathan Allan Jul 19 '16 at 4:49

The website Sudoku Wiki has a good solver which shows which technique it is using for each step.

It goes through some of its "extreme solutions" (cell forcing chains, quad forcing chains) and then is unable to solve it.

The website also has a solution counter (using a brute force algorithm) which says there are over 500 possible solutions to the puzzle.

Here are two solutions, marked in red where they differ.

• If there are truly 2 solutions, then this is a bad puzzle. There should be only one. – Trenin Jul 18 '16 at 16:25
• Both solutions seem to be consistent with the given numbers. :/ – Deusovi Jul 18 '16 at 16:47
• Thanks for the edit. As I mentioned the website said there was at least 500 solutions, I just picked 2 at random to show. – gtwebb Jul 18 '16 at 16:52
• +1 Thank you for pointing to the solver. How do you get it to reveal the 'hidden singles'? When I clicked on "Take Step", it didn't enter the 3 singles at A2, B3 and G7. – Lawrence Jul 18 '16 at 23:12
• Found out how to get it to reveal the 'hidden singles': click "Take Step" multiple times. When it finds a successful strategy, it just notes that the strategy is available but waits for an additional click before implementing it, allowing the user to try to nut it out first, if so desired. – Lawrence Jul 18 '16 at 23:20