Solving sudoku puzzles

Here is how I approach sudoku, almost all of it learned ‘on the job’.

[Ideally, I would include in this post nice pictures of the grid, or pieces of it, but I’m not prepared to invest that much effort in html hacking/research. So we will have to settle for verbal descriptions.]

I have my own notion of how to label the 81 squares: the obvious a1–i9 scheme borrowed from chess doesn’t appeal to me because the digits 1–9 are already needed to represent the items being placed. Instead I name the columns A–I, left to right, and the rows R–Z, top to bottom. So squares have names like CS, HX, and so on.

As I mentioned before, I transcribe newspaper or online puzzles onto my own grids (on decent paper that can take fountain pen ink without bleeding), about 7cm square.

The notations I make (aside from filling in digits whose position can be determined) are almost always assertions of the form ‘digit k must be placed in one of the squares of set Σ’. For example, if I can determine that there must be a 7 in one of the two squares {AR, AS}, I write a small ‘7’ on the horizontal line that separates those squares. This same fact can be written in a linearized form, for discussion purposes, as 7AR|7AS, or more compactly as 7ARS (‘distributing’ the ‘A’ over the ‘R’ and the ‘S’ in the obvious way).

I have conventions for notating facts involving more widely separated squares; the details are unimportant. I see what I can accomplish by considering pairs of squares, and then work up to triples and so on as needed. Note, though, that I very seldom resort to exhaustive listings of the digits a single square might contain: assertions like 7AR|9AR.

Using these methods, the most difficult placements to see are those where, for a given square, all digits but one have been ruled out; but it usually suffices to glance occasionally at the rows or columns that have only a few squares not labeled in any way, note the digits that are prima facie candidates for those squares, and see what eliminations can be made in the light of the other sudoku constraints.

Early on in teaching myself sudoku I worked out the important type of reasoning whereby (to use the linearized version of my notation) the facts 3EFX and 7EFX combine to form the much more useful fact (37)(EFX). I refer to this as a ‘locked pair’, although I don’t think this is the standard nomenclature. There are two digits to be placed in two squares, and they ‘lock out’ other digits that might otherwise have been placeable in those squares. So if the facts 3EFX and 8EXY are already known, discovering the fact 7EFX locks the squares EX and FX, and we can place the digit 8 in square EY.

These methods suffice for the vast majority of puzzles. I’ve read about the technique known as ‘X-Wing’, which involves squares that themselves form a rectangle, such as AR, FR, AV, FV. If we determine the ‘horizontal’ facts 3AFR and 3AFV, we can also conclude the ‘vertical’ facts 3ARV and 3FRV. But I almost never find myself using this kind of reasoning.

On the other hand, a form of reasoning that I use often but have never seen discussed (it’s not easy to search for) involves what I call solvability arguments. Here we rely on the fact—or meta-fact—that published sudoku puzzles are guaranteed to have a unique solution.

Here’s how it works in the simplest form: suppose we have the facts (45)(GHT) and 4GHZ. We can conclude that ¬5GZ and ¬5HZ, because otherwise the four squares involved would be undecidable: we might have 4 in GT and HZ and 5 in HT and GZ, or the other way around. Looking at this from the point of view of a sudoku constructor, if four squares forming a rectangle contain only two digits among them, one of those squares must be included among the données or the puzzle will be unsolvable.

In another common setup, suppose again that we have (45)(GHT) and that 1, 4, and 5 need to be distributed among squares GX, GZ, and HZ. These latter squares form a triangle. The two linear placements (45)(GXZ) and (45)(GHZ) are both impossible: the first would make GT unfillable, while the second is ruled out as in the previous paragraph. So only the diagonal placement (45){GX,HZ} is possible, and we can place 1 in the remaining square of the triangle, GZ.

Sometimes solvability arguments can turn into long daisy chains: if we have, for example, (35)(AUV), (86)(DUV), (13)(EUV), and (16)(GUV), we can see that *(58)(HUV) would cause a problem, by joining up the ends of the chain 5–3–1–6–8 and making all ten squares unsolvable.

This entry was posted in Uncategorized. Bookmark the permalink.

One Response to Solving sudoku puzzles

  1. Pingback: Turing tests | dysangelist

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s