Sudoku Sledgehammer
A recent article in American Scientist that talkes about Sudoku mentions that the distinction between logic and backtracking is a distinction that doesn't seem to exist. And yet, there definitely seems to be some intangible distinction that the puzzle constructors use there.

I've been thinking about this for a while, and I believe I have my finger on this distinction. It goes like this:

There is a very powerful heuristic that is actually a generalization of many of the standard heuristic. I'll call it the Sledgehammer (just to be cute).

Statement: If a Sudoku puzzle can be solved by repeated applications of the Sledgehammer, then it is considered a puzzle that is "solvable by logic". If it cannot, then it is a puzzle that "requires backtracking".

Perhaps by now I've gotten you curious as to what the Sledgehammer is. It's actually rather difficult to explain, but I'll try:

The first step is to look at a Sudoku puzzle in a slightly different way, in terms of what I call Placements and Rules.

If you're familiar with Knuth's Dancing Links, you might recognize this form of reasoning, as it's often used to recast puzzles to be solved by his algorithm, although Dancing Links is a trial-and-error algorithm, while the Sledgehammer is not.

A Placement is, in short, a specific number going in a specific cell. For example, "The number 5 goes in row 2, column 7" is a Placement, as is "The number 3 goes in row 9, column 8."

A standard Sudoku puzzle has 729 Placements -- 81 cells, each of which has 9 Placements. When one tries to solve a Sudoku puzzle, one is trying to select 81 out of those 729 Placements that satisfy certain Rules.

What is a Rule? My definition here might not be exactly what you expect, but here it is: A Rule is a set of Placements such that only one of those Placements can be in the solution. For a standard Sudoku puzzle, all Rules have exactly 9 Placements, and there are
324 Rules total.

For example, here are the 9 Placements in one of the Rules:
"The number 6 goes in row 2, column 1."
"The number 6 goes in row 2, column 2."
"The number 6 goes in row 2, column 3."
"The number 6 goes in row 2, column 4."
"The number 6 goes in row 2, column 5."
"The number 6 goes in row 2, column 6."
"The number 6 goes in row 2, column 7."
"The number 6 goes in row 2, column 8."
"The number 6 goes in row 2, column 9."
A more common way of stating this Rule might be:
"There is exactly one 6 in row 2."

Here's another Rule, with its 9 Placements:
"The number 1 goes in row 5, column 8."
"The number 2 goes in row 5, column 8."
"The number 3 goes in row 5, column 8."
"The number 4 goes in row 5, column 8."
"The number 5 goes in row 5, column 8."
"The number 6 goes in row 5, column 8."
"The number 7 goes in row 5, column 8."
"The number 8 goes in row 5, column 8."
"The number 9 goes in row 5, column 8."
A more common way of stating this Rule might be:
"Only one number can be placed in row 5, column 8."

By now it should be clear why there are 324 Rules -- there are 81 "Row" Rules, 81 "Column" Rules, 81 "Region" Rules, and 81 "Cell" Rules. Sometimes Rules are disjoint (they have
no Placements in common).

All Sudoku puzzles effectively start with the same 729 Placements and 324 Rules -- the only distinction is the "givens", which is some of the Placements that are earmarked to already be in the solution.

The power of restating a Sudoku puzzle in terms of Placements and Rules is that it completely abstracts away the concepts of "row" or "column" or even "digit". I could give you 729 different cookies, and give you 324 different groupings of 9 cookies each, and ask you to find me 81 cookies such that exactly one of each grouping is selected -- and you could be solving a Sudoku puzzle without even realizing it!

The process of "solving" a Sudoku puzzle can be thought of this way: you have 729 Placements. We keep on discarding Placements until we only have 81 Placements left. At that point, the puzzle is solved. How do we represent "givens"? A simple way is to just
discard the other eight Placements in the same "Cell" Rule (although, if we want, we could discard the eight Placements in the same "Row" Rule -- as you'll see later, the Sledgehammer doesn't care). Or, going with my cookie analogy, you have 729 cookies, and you keep on eating cookies, making sure that you keep at least one cookie from each "Rule", until you have 81 cookies left.

Okay, now I think I've finally laid the groundwork for explaining the Sledgehammer. Here goes.

Sledgehammer:
For every value of N from 1 to 9:
For every set of N disjoint Rules (call them the Premises):
For every set of N Rules (call them the Conclusions):
If all the (undiscarded) Placements in the Premises are all
contained in the Conclusion, then:
discard all the other Placements in the Conclusions; and
discard all the Placements that appear in the Conclusions more
than once.

That's it!

Okay, maybe you want to hear that in plain English. Let me use the cookie example, and N = 2. We've eaten enough cookies such that these are four of our Rules:

Rule W: Gingersnap, Butterscotch
Rule X: Chocolate, Snickerdoodle, Oatmeal
Rule Y: Gingersnap, Oatmeal, Chocolate, Macaroon
Rule Z: Butterscotch, Chocolate, Peanut, Snickerdoodle

Remember that each Rule has to end up with exactly one cookie.

Okay, look at Rule W and Rule X. Those are disjoint, so let's call them the Premises. Now, look at Rule Y and Rule Z, and call those the Conclusions.

There are five cookies in the Premises (Gingersnap, Butterscotch, Chocolate, Snickerdoodle, Oatmeal), and all five of those are in the Conclusions. So, the Sledgehammer is satisfied, and it tells us to eat all the other cookies in the Conclusions, which would be Peanut and Macaroon. It also tells us to each anything that appears in the Conclusions more than once, which would be Chocolate.

This results in:
Rule W: Gingersnap, Butterscotch
Rule X: Snickerdoodle, Oatmeal
Rule Y: Gingersnap, Oatmeal
Rule Z: Butterscotch, Snickerdoodle

Now, why does this logic make sense? Well, Chocolate can't stay, because if we keep it, we'd have to get rid of Gingersnap (Rule Y) and Butterscotch (Rule Z), but then Rule W is empty. And of our five cookies in the premises, two of them have to stay, and so that accounts for two in Rules Y and Z, so we can't keep any of the other cookies in Y and Z.

So, from a logic standpoint, the Sledgehammer really makes a lot of sense, but it's bit hard to visualize -- perhaps because it is taking a lot of individual deductions and rolling it up into a giant ball.

The wonderful thing about the Sledgehammer is that almost all common Sudoku heuristics are really special cases of the Sledgehammer.

For example, here's a heuristic:
"Suppose we have eliminated 9 from columns 4-9 of row 1. Then we know that the 9 in the upper-left region is in row 1, so we can eliminate it from rows 2-3, columns 1-3."

This is the Sledgehammer with
Premise = "9 in row 1" Rule
Conclusion = "9 in upper-left region" Rule.

Even a fancy heuristic, such as the X-Wing, is simply the Sledgehammer with two "row" Rules as Premises and two "column" Rules as Conclusions.

One on-again, off-again project that I've been playing with is: if most heuristics are a special case of the Sledgehammer, then surely we can take each individual instance of the Sledgehammer and give a numerical measurement that means "how likely is a human going to see this instance?" Using that, it should be theoretically possible to write a program that will solve a Sudoku like a tireless human would, and possibly even give a good estimate for the true difficulty of a puzzle.

There are some advanced heuristics that are not part of the Sledgehammer; these include Hamada's Logic and Coloring. The real question to me is: is there an even more generalized rule that covers those heuristics as well?