# You Complete Me

March 14, 2012 5:55 AM Subscribe

What is the minimal number of clues necessary to create a uniquely solvable Sudoku puzzle? It turns out to be 17, though it took fancy symmetry arguments and nearly a year of computer time to prove it. But no need to read the paper when you can watch the video.

Yes, yes. But I still can't beat the jetski level in Battletoads.

posted by Fizz at 6:10 AM on March 14, 2012 [1 favorite]

posted by Fizz at 6:10 AM on March 14, 2012 [1 favorite]

It's just you. Sudoku is a lot more challenging than Tic Tac Toe.

Also: eyebrows

posted by DU at 6:13 AM on March 14, 2012

Also: eyebrows

posted by DU at 6:13 AM on March 14, 2012

*Is it just me, or is being a "Sudoku fan" akin to being a "Tic Tac Toe fan"?*

So what kind of puzzles are we allowed to be a fan of, o wise one?

I'm not really a big Sudoku fan myself, but to compare it to Tic-Tac-Toe is like comparing catch to football.

posted by kmz at 6:14 AM on March 14, 2012 [4 favorites]

I have to admit I'm getting tired of exhaustive searches being trotted out as proofs.

Not that they're invalid mind you, it's just that they seem like cheating.

posted by Tell Me No Lies at 6:16 AM on March 14, 2012 [1 favorite]

Not that they're invalid mind you, it's just that they seem like cheating.

posted by Tell Me No Lies at 6:16 AM on March 14, 2012 [1 favorite]

So, Michael Spivak is into sudoku now?

posted by Dr Dracator at 6:17 AM on March 14, 2012

posted by Dr Dracator at 6:17 AM on March 14, 2012

*I'm not really a big Sudoku fan myself, but to compare it to Tic-Tac-Toe is like comparing catch to football.*

You've clearly not played 'Extreme Tic Tac Toe'!

posted by Fizz at 6:17 AM on March 14, 2012

*I have to admit I'm getting tired of exhaustive searches being trotted out as proofs.*

Not that they're invalid mind you, it's just that they seem like cheating.

Not that they're invalid mind you, it's just that they seem like cheating.

I hate to be so dismissive, but it does seem like mere trivia. Non-brute-force proofs feel like they advance our understanding, or at least reflect an understanding. Brute force proofs are both inscrutable and hard to generalize.

(The really cool result would have been if there was some way to determine the minimum number of clues for an (N^2) by (N^2) sudoku for any integer N. It's hard to see how the OP result could be used except to help verify that larger work.

By the way, does anyone know if there is a closed-form solution for the number of different (N^2) by (N^2) sudoku puzzles?)

posted by Jpfed at 6:28 AM on March 14, 2012

I've actually been wondering about this very fact for years. Glad to see it's been figured out. Like many, I'm sad the solution wasn't more... elegant.

posted by Wulfhere at 6:29 AM on March 14, 2012 [1 favorite]

posted by Wulfhere at 6:29 AM on March 14, 2012 [1 favorite]

Previously.

I wondered this and searched and whadyaknow! Mefi Strikes again!

+17

posted by marienbad at 6:32 AM on March 14, 2012

I wondered this and searched and whadyaknow! Mefi Strikes again!

+17

posted by marienbad at 6:32 AM on March 14, 2012

Sudoku always strikes me as the Farmville of logic puzzles.

posted by Aquaman at 6:54 AM on March 14, 2012 [2 favorites]

posted by Aquaman at 6:54 AM on March 14, 2012 [2 favorites]

*I hate to be so dismissive, but it does seem like mere trivia. Non-brute-force proofs feel like they advance our understanding, or at least reflect an understanding. Brute force proofs are both inscrutable and hard to generalize.*

Not necessarily. A lot of problem sets are translatable to each other, so if you can brute force a solution to one of them, you know that there are possible solutions to all of them.

posted by empath at 6:57 AM on March 14, 2012

*I have to admit I'm getting tired of exhaustive searches being trotted out as proofs.*

I think exhaustive searches are fine as proofs -- if you tested every X in your theorem that X is in the class of Y, then you have conclusively proven or disproven that theorem.

Inelegant? Maybe. Certain? Absolutely -- as long as your exhaustive test is correct, but I've seen plenty of non-exhaustive "proofs" fall by the wayside as well.

Note that the hard part of the Four Color Theorem proof was not the exhaustive search of the set of maps that was both unavoidable and reducible. The proof of the reducibility was simple, the test of set of maps, while it took a while, wasn't the big problem.

The big problem was the unavoidability proof, which took 400 pages and had to be checked by hand. Testing the set of 1936 maps (later reduced to 633) was simple compared to that.

And, occasionally, an exhaustive proof will lead to a non-exhaustive proof, simply by giving a hint -- or by simply proving that it is possible, thus encouraging further searches.

Finally: Just because a proof is non-exhaustive does not make it elegant. See Wiles' proof of Fermat's Last Theorem.

posted by eriko at 6:57 AM on March 14, 2012 [6 favorites]

The video is annoying me because he keep saying that 17 is the minimum for the Sudoko to be SOLVABLE when he means "have a unique solution". Even and empty grid is "solvable".

posted by mary8nne at 7:35 AM on March 14, 2012

posted by mary8nne at 7:35 AM on March 14, 2012

**mary8nne**:

*Even an empty grid is "solvable".*

Well, yes, but if you can just randomly sprinkle numbers around the grid, you're not SOLVING a Sudoku, you're CREATING one. 17 is the minimum possible number of required clues so that you're guaranteed not to be coming up with a Sudoku of your own creation. So his use of 'solving' is correct.

Does the paper hit on the maximum number of clues required? I just watched the video, and they don't talk about that.

posted by Malor at 8:29 AM on March 14, 2012

*Does the paper hit on the maximum number of clues required?*

I'm going with 80, but I haven't yet confirmed this using computers.

posted by wabashbdw at 8:43 AM on March 14, 2012 [4 favorites]

"Maximum number of clues, such that the puzzle has a unique solution, but removing

(The "any" is important, because if you instead specify "... removing one specific clue leaves a puzzle that does not have a unique solution," the answer is trivially 78 clues, as it's possible for a puzzle with only four blank squares, i.e., 77 clues, to have two possible solutions.)

posted by DevilsAdvocate at 8:56 AM on March 14, 2012 [3 favorites]

*any*one of the clues leaves a puzzle that does not have a unique solution" is an interesting question.(The "any" is important, because if you instead specify "... removing one specific clue leaves a puzzle that does not have a unique solution," the answer is trivially 78 clues, as it's possible for a puzzle with only four blank squares, i.e., 77 clues, to have two possible solutions.)

posted by DevilsAdvocate at 8:56 AM on March 14, 2012 [3 favorites]

> By the way, does anyone know if there is a closed-form solution for the number of different (N^2) by (N^2) sudoku puzzles?

Probably not, given that there isn't even one known for Latin squares.

posted by eruonna at 9:03 AM on March 14, 2012

Probably not, given that there isn't even one known for Latin squares.

posted by eruonna at 9:03 AM on March 14, 2012

*Is it just me, or is being a "Sudoku fan" akin to being a "Tic Tac Toe fan"?*

Is it just me, or is successfully placing your thread-shit as a FIRST comment akin to winning [simplistic game of choice]?

posted by aught at 9:11 AM on March 14, 2012 [3 favorites]

It's basically just a dull number puzzle, but the bouncy "Angry Sudoku" theme made it popular.

posted by dhartung at 9:12 AM on March 14, 2012

posted by dhartung at 9:12 AM on March 14, 2012

Sudoku puzzles are like crosswords for illiterates.

posted by monospace at 9:18 AM on March 14, 2012 [1 favorite]

posted by monospace at 9:18 AM on March 14, 2012 [1 favorite]

*(The "any" is important, because if you instead specify "... removing one specific clue leaves a puzzle that does not have a unique solution," the answer is trivially 78 clues, as it's possible for a puzzle with only four blank squares, i.e., 77 clues, to have two possible solutions.)*

No, reread my original question: what's the maximum number of clues

**required**to solve a Sudoku puzzle? You can give more, but those aren't required. They're just extra numbers to make it easier on humans, not necessary to constrain the solution space to a unique answer.

posted by Malor at 9:20 AM on March 14, 2012

Malor, Devil's Advocate answers your question, since there's an ambiguous grid missing 4 numbers. There cannot be one missing 3 since changing any number has consequences for (at least) 3 others.

posted by Obscure Reference at 9:23 AM on March 14, 2012

posted by Obscure Reference at 9:23 AM on March 14, 2012

Oh, duh, I didn't think that through, you're right. Never mind. :-)

posted by Malor at 9:24 AM on March 14, 2012

posted by Malor at 9:24 AM on March 14, 2012

Actually, thinking about it some more, I'm not sure I did. If you have that ambiguous grid, that means you aren't providing enough clues. Ergo, it cannot be solved, ergo you didn't choose your clues correctly. You did not constrain the solution space to one answer.

So my original question appears to still be correct, but could use a little rewording for clarity: What is the maximum number of clues

posted by Malor at 9:29 AM on March 14, 2012

So my original question appears to still be correct, but could use a little rewording for clarity: What is the maximum number of clues

**required**to to uniquely specify a single Sudoku variant?posted by Malor at 9:29 AM on March 14, 2012

*Sudoku puzzles are like crosswords for illiterates.*

Yes, in much the same way that brussels sprouts are like unicycles for plumbers.

posted by DevilsAdvocate at 9:30 AM on March 14, 2012 [8 favorites]

Malor: that's what I was getting at with my restatement of your question. If by "maximum number of clues required to uniquely specify..." you mean that removing

posted by DevilsAdvocate at 9:32 AM on March 14, 2012

*any*one of the clues leaves a puzzle that does not have a unique solution, then that is an interesting, and to my knowledge unsolved, question.posted by DevilsAdvocate at 9:32 AM on March 14, 2012

Someone should apply this method to find out the average number of attempts before you reach NumberWang.

posted by Saxon Kane at 9:35 AM on March 14, 2012 [1 favorite]

posted by Saxon Kane at 9:35 AM on March 14, 2012 [1 favorite]

*I've actually been wondering about this very fact for years. Glad to see it's been figured out. Like many, I'm sad the solution wasn't more... elegant.*

Me too, and me too ... and me too! But if you try every single possibility, it seems like a finite thing to solve. My guess was always 23. I am completely self-taught, though - I've never read a single article or book about Sudoku.

*Is it just me, or is being a "Sudoku fan" akin to being a "Tic Tac Toe fan"?*

*Sudoku puzzles are like crosswords for illiterates.*

*It's basically just a dull number puzzle*

Comments from people who can't beat any Sudoku puzzles on Fiendish. ;)

Sudoku is awesome. Squiggly sudoku is super awesome. Suck it, haters. (Why would anyone want to shit on a completely inoffensive

*game*many people enjoy? Now Word Finders ... those fuckers are the scum of the earth.)

posted by mrgrimm at 9:59 AM on March 14, 2012 [1 favorite]

*So where can I find these 17-clue Sudoku puzzles?*

The paper lists one example:

000801000

000000430

500000000

000070800

000000100

020030000

600000075

003400000

000200600

and this grid:

6 3 9 2 4 1 7 8 5

2 8 4 7 6 5 1 9 3

5 1 7 9 8 3 6 2 4

1 2 3 8 5 7 9 4 6

7 9 6 4 3 2 8 5 1

4 5 8 6 1 9 2 3 7

3 4 2 1 7 8 5 6 9

8 6 1 5 9 4 3 7 2

9 7 5 3 2 6 4 1 8

... supposedly has 29 different 17-clue puzzles.

But yes, the "fiendish" level Sudoku puzzles that I play usually have 25-28 numbers. I would figure less numbers would make the puzzles easier...

I'll try to solve the one above and let you know.

posted by mrgrimm at 10:09 AM on March 14, 2012 [1 favorite]

*So where can I find these 17-clue Sudoku puzzles?*

From the previously link:

"Currently I have a collection of 49,151 distinct Sudoku configurations with 17 entries"

posted by mrgrimm at 10:17 AM on March 14, 2012 [1 favorite]

I hate to be so dismissive, but it does seem like mere trivia. Non-brute-force proofs feel like they advance our understanding, or at least reflect an understanding. Brute force proofs are both inscrutable and hard to generalize.

From the article:

posted by benito.strauss at 10:26 AM on March 14, 2012 [1 favorite]

From the article:

This new algorithm has many other potential applications than just sudoku. To begin with, it is applicable to any instance of the hitting set problem, and such situations frequently occur in Bioinformatics (e.g., gene expression analysis), Computer Networks and Software Testing. ... The set cover problem has applications to interference in cellular networks. ... Indeed, the minimum number of clues problem is an instance of a whole family of problems in combinatorics, where one studies critical sets.Read the paper; they've done some cool stuff.

posted by benito.strauss at 10:26 AM on March 14, 2012 [1 favorite]

My favorite part of newspaper Sudokus is where they say that "even though you use numbers to fill in the grid, no math is involved, just logic!".

Because that says that logic isn't part of math.

Which is what the topologists and functional analysts in grad school claimed too.

posted by benito.strauss at 10:28 AM on March 14, 2012 [1 favorite]

Because that says that logic isn't part of math.

Which is what the topologists and functional analysts in grad school claimed too.

posted by benito.strauss at 10:28 AM on March 14, 2012 [1 favorite]

But is Sudoku mathematical logic? (Honestly, I don't know. If I had to guess, I'd say no.) You can obviously substitute anything for the numbers, but that doesn't make it non-mathematical ...

(I always thought of Logic as part of philosophy, with a certain subset applied to math. But I am far from being a mathematician, logician, or philosopher...)

posted by mrgrimm at 11:35 AM on March 14, 2012

(I always thought of Logic as part of philosophy, with a certain subset applied to math. But I am far from being a mathematician, logician, or philosopher...)

posted by mrgrimm at 11:35 AM on March 14, 2012

Sudoku is less mathematical logic, and more combinatorial design theory (see the wiki article on Latin Squares). Maybe the process of "filling them in" is more logic-based, but the problem of determining if a partially filled in latin square can be completed is surely in the realm of combinatorics, no?

posted by King Bee at 11:42 AM on March 14, 2012 [3 favorites]

posted by King Bee at 11:42 AM on March 14, 2012 [3 favorites]

*Sudoku puzzles are like crosswords for illiterates.*

"Rush about, firstly bringing back in trash" (7).

posted by howfar at 11:47 AM on March 14, 2012

rubbish

posted by Obscure Reference at 3:09 PM on March 14, 2012

posted by Obscure Reference at 3:09 PM on March 14, 2012

hey

I stand by my original statement. An empty grid is "solvable".

posted by mary8nne at 3:13 PM on March 14, 2012

**Malor**Just because a solution is non-unique does not mean its not a solution.I stand by my original statement. An empty grid is "solvable".

posted by mary8nne at 3:13 PM on March 14, 2012

It's not really quite doing logic or math. It's more like you're pretending to be a constraint satisfaction algorithm. I'm not sure what you'd call that. "Declarative programming cosplay," maybe.

posted by nebulawindphone at 3:16 PM on March 14, 2012 [6 favorites]

posted by nebulawindphone at 3:16 PM on March 14, 2012 [6 favorites]

*Sudoku puzzles are like crosswords for illiterates.*

heh, i've won the Harpers Puzzle twice (and beat it most months), and I LOVE sudoku. crosswords are mostly memorization and learning the conventions and the repeated (esp. 3-4 letter) answers like ERNE and EIRE. (I still love them too.) I like cryptic crosswords better, but only because I'm good at anagrams.

posted by mrgrimm at 4:01 PM on March 14, 2012

True dat. The only reason I've ever heard of Eero Saarinen was my mom is a crossword nut.

posted by nebulawindphone at 4:10 PM on March 14, 2012

posted by nebulawindphone at 4:10 PM on March 14, 2012

Kenken puzzles are like a more logical less algorithmic version of Sudoku. Check them out if you're looking for a puzzle.

posted by Wulfhere at 4:16 PM on March 14, 2012 [1 favorite]

posted by Wulfhere at 4:16 PM on March 14, 2012 [1 favorite]

I lubs me some sudoku when I've got to wheedle away a bit of time traveling or whatever, but don't want to get caught up too deep in a book. I cheat a bit on the hardest ones, and I sincerely doubt 17 numbers would be enough for me to even get started. Being math challenged, it took me a while to figure out how to do them, but I showed my 10 yo granddaughter, and it took her one try to figure it out. Minds are funny.

Dogs, but I

posted by BlueHorse at 6:17 PM on March 14, 2012

*Now Word Finders ... those fuckers are the scum of the earth.*Dogs, but I

**loath**those things!! Seems like all the teachers from 5th grade on give them as busy work to students, and there's not a single kid I know that likes them.posted by BlueHorse at 6:17 PM on March 14, 2012

*Sudoku puzzles are like crosswords for illiterates.*

...whereas trotting out that hackneyed sound byte is what, exactly?

posted by obiwanwasabi at 1:38 AM on March 15, 2012

The

I like Sudoku, and Ken-Ken, and the

posted by clorox at 2:07 AM on March 15, 2012 [1 favorite]

*Harper's*puzzle has been a little disappointing the past few months. Too many "unknown location" themes*, too many errors (forgivable as none were puzzle-breaking), not nearly enough non-grid grids, and too many of the answers feel forced. Hopefully Maltby's just in a little slump and he picks it up over the summer. To be fair, though, they're still way better than a straight cryptic crossword. Not having the overall theme makes them too plain.I like Sudoku, and Ken-Ken, and the

*New York Times Magazine*'s Acrostic, but with each of those the last bit of the solve just feels like busywork; like driving 500 miles only to be stuck in traffic five blocks from your destination and there's no parking.posted by clorox at 2:07 AM on March 15, 2012 [1 favorite]

*Hopefully Maltby's just in a little slump and he picks it up over the summer.*

I thought the Valentine's Day puzzle (which was tough, and did not finish in time to submit, yet I liked) was created by someone else. I swore there was a sub recently.

The Triumvirate one (December?) was bullshit. I've seen that theme used like 5 times over the years.

*Kenken puzzles are like a more logical less algorithmic version of Sudoku. Check them out if you're looking for a puzzle.*

Oh believe me, I grew up with Games magazine and the only reason I don't subscribe now is because of the ubiquitous free puzzle games everywhere.

I actually do enjoy Ken-Ken the most. Kakuro is a bit of a grind (I was DEEP into kakuro for a while), as Sudoku certainly can be, but each one of those has its own pleasures, and infinite variations. I always enjoy seeing new twists.

BUT, I don't find Ken-Ken to be as hard as the hardest Sudoku, which isn't necessarily bad, but solving a difficult Sudoku is like you're a thief in D&D in an unlit dungeon, trying to find the secret door amidst thousands of square feet of walls. There is (usually, on the most difficult puzzles) 1 path, and there are usually 2-3 very hard-to-find secret doors along the way. The pleasure derived from spotting those secret doors is unique and considerable to me.

When the secret doors involve something beyond the usual "eliminate squares down to two, eliminate down rows and columns, etc. etc." the pleasure is much greater.

*It's more like you're pretending to be a constraint satisfaction algorithm. I'm not sure what you'd call that. "Declarative programming cosplay," maybe.*

But ... isn't that pretty much any number puzzle? Couldn't you say the same thing about chess?

A grind-it-out algorithmic approach will solve any Sudoku ... given enough time. But if you are trying to solve it as

*fast*as possible, a holistic solving approach, a meta-algorithm perhaps, will save minutes. That is, there's no way for a human to think like a machine.

Another analogy might be trivia contests. All questions can be answered via google, shazam, imdb, etc. in 10 seconds, yet people still go to trivia nights.

A doofus with an earpiece getting instructions from a computer could win a Sudoku competition, sure, but couldn't a chess player do the same?

Also, a computer can take steps backwards. A human with a pen cannot. (A human on a phone can easily, which changes the game quite a bit.)

Here's the solution to the 17-puzzle clue I posted above:

396841752

218795436

574326918

465179823

739582164

821634597

642918375

953467281

187253649

The path via sudoku.sourceforge.net

START

1. The cell (7,7) is the only candidate for the value 3 in Column 7.

2. The cell (7,3) is the only candidate for the value 2 in Row 7.

3. The cell (7,2) is the only candidate for the value 4 in Row 7.

4. The cell (3,4) is the only candidate for the value 3 in Column 4.

5. The cell (2,4) is the only candidate for the value 7 in Column 4.

6. The cell (9,6) is the only candidate for the value 3 in Row 9.

7. The cell (8,6) is the only candidate for the value 7 in Column 6.

8. The cell (8,5) is the only candidate for the value 6 in Row 8.

9. The cell (9,5) is the only candidate for the value 5 in Box [3,2].

10. The cell (2,6) is the only candidate for the value 5 in Row 2.

11. The cell (3,6) is the only candidate for the value 6 in Box [1,2].

12. The cell (8,2) is the only candidate for the value 5 in Row 8.

13. The cell (7,5) is the only candidate for the value 1 in Column 5.

14. The value 9 is the only candidate for the cell (7,4).

15. The value 8 is the only candidate for the cell (7,6).

16. The cell (5,5) is the only candidate for the value 8 in Column 5.

17. The cell (3,3) is one of 2 candidates for the value 4 in Row 3.

18. The cell (1,5) is the only candidate for the value 4 in Row 1.

19. The cell (6,7) is one of 2 candidates for the value 5 in Column 7.

20. The cell (1,8) is the only candidate for the value 5 in Row 1.

21. The value 6 in Box [2,3] must lie in Column 8.

The value 7 in Box [1,3] must lie in Column 7.

The cell (3,2) is one of 2 candidates for the value 7 in Row 3.

22. The cell (1,7) is the only candidate for the value 7 in Row 1.

23. The value 1 in Box [1,3] must lie in Row 3.

The value 8 in Box [1,3] must lie in Row 3.

The values 1 and 8 occupy the cells (3,8) and (3,9) in some order.

The cell (1,9) is one of 2 candidates for the value 2 in Row 1.

24. The value 9 is the only candidate for the cell (3,7).

25. The value 6 is the only candidate for the cell (2,9).

26. The value 2 is the only candidate for the cell (3,5).

27. The value 9 is the only candidate for the cell (2,5).

28. The value 2 is the only candidate for the cell (8,7).

29. The cell (2,1) is the only candidate for the value 2 in Row 2.

30. The cell (9,2) is one of 2 candidates for the value 8 in Column 2.

31. The value 1 is the only candidate for the cell (2,2).

32. The value 8 is the only candidate for the cell (2,3).

33. The cell (6,1) is the only candidate for the value 8 in Row 6.

34. The cell (6,3) is one of 2 candidates for the value 1 in Row 6.

35. The value 6 is the only candidate for the cell (6,4).

36. The value 5 is the only candidate for the cell (5,4).

37. The value 1 is the only candidate for the cell (4,4).

38. The cell (6,9) is the only candidate for the value 7 in Row 6.

39. The cell (4,3) is the only candidate for the value 5 in Row 4.

40. The values 2 and 6 occupy the cells (4,8) and (5,8) in some order.

The cell (6,8) is one of 2 candidates for the value 9 in Row 6.

41. The value 4 is the only candidate for the cell (6,6).

42. The cell (9,8) is the only candidate for the value 4 in Column 8.

43. The cell (8,1) is one of 2 candidates for the value 9 in Row 8.

44. The value 3 is the only candidate for the cell (1,1).

45. The value 4 is the only candidate for the cell (4,1).

46. The value 3 is the only candidate for the cell (4,9).

47. The value 7 is the only candidate for the cell (5,1).

48. The value 1 is the only candidate for the cell (9,1).

49. The value 4 is the only candidate for the cell (5,9).

50. The value 7 is the only candidate for the cell (9,3).

51. The value 9 is the only candidate for the cell (9,9).

52. The cell (5,2) is the only candidate for the value 3 in Row 5.

53. The cell (4,2) is one of 2 candidates for the value 6 in Row 4.

54. The value 2 is the only candidate for the cell (4,8).

55. The value 9 is the only candidate for the cell (5,3).

56. The value 9 is the only candidate for the cell (1,2).

57. The value 6 is the only candidate for the cell (1,3).

58. The value 9 is the only candidate for the cell (4,6).

59. The value 2 is the only candidate for the cell (5,6).

60. The value 6 is the only candidate for the cell (5,8).

61. The cell (3,8) is one of 2 candidates for the value 1 in Row 3.

62. The value 8 is the only candidate for the cell (3,9).

63. The value 8 is the only candidate for the cell (8,8).

64. The value 1 is the only candidate for the cell (8,9).

posted by mrgrimm at 8:40 AM on March 15, 2012

*I thought the Valentine's Day puzzle (which was tough, and did not finish in time to submit, yet I liked) was created by someone else. I swore there was a sub recently.*

When I saw it the shape reminded me of the old puzzles from the

*Atlantic*. I did a little better than my recent average on it -- not having to guess the length of every across answer helped. By the way, are there any other publications that regularly feature a cryptic crossword with an extra twist? And who are the people mentioned to from time to time?

*BUT, I don't find Ken-Ken to be as hard as the hardest Sudoku*

I'm pretty sure that Shortz or whoever's in charge of the

*NYT*Ken Ken puzzles has really toned down the difficulty since they first came out. The Sunday 7x7 used to be diabolical. I remember having to break down half the cells in the grid into odd/even possibilities and then brute forcing from there. Now the toughest thing I have to do is factor some ridiculous multiple of 7. (Or 18. I hate it when 18 shows up.)

posted by clorox at 9:13 AM on March 15, 2012 [1 favorite]

It's more like you're pretending to be a constraint satisfaction algorithm. I'm not sure what you'd call that. "Declarative programming cosplay," maybe.But ... isn't that pretty much any number puzzle? Couldn't you say the same thing about chess?

Oh, totally. I mean,

*chess*chess is a bit different, because it's multiplayer and because there's no guarantee of solvability or uniqueness. In Sudoku someone has promised you that there's one and only one "winning" sequence of moves from the starting position, and you can use that promise to constrain your thinking about the puzzle. Mabe a better analogy would be a chess problem of the "white to mate in five moves" variety.

posted by nebulawindphone at 9:23 AM on March 15, 2012

I used to love The Atlantic puzzles, but haven't looked at them in years. I think maybe they got rid of it? It was always easier than Harper's, but sometimes more elegant and/or fun. I think the clues were easier, but the twists more interesting.

Yeah, and they were definitely available online, cuz I remember printing them out a work ... here they are. Looks like it stopped in Jan/Feb. 2006. Lots of changes at the Atlantic in recent years, I suppose. ... actually it looks like Emily Cox stopped in August 2009, and Henry Rathvon gave it up a few months later.

I'm not a chess expert, but I think one could probably argue that a computer playing a person has 1 optimal response to every human move. It's not simple, but Deep Blue must use an algorithm to decide which move to make, right?

posted by mrgrimm at 9:28 AM on March 15, 2012

Yeah, and they were definitely available online, cuz I remember printing them out a work ... here they are. Looks like it stopped in Jan/Feb. 2006. Lots of changes at the Atlantic in recent years, I suppose. ... actually it looks like Emily Cox stopped in August 2009, and Henry Rathvon gave it up a few months later.

*Mabe a better analogy would be a chess problem of the "white to mate in five moves" variety.*I'm not a chess expert, but I think one could probably argue that a computer playing a person has 1 optimal response to every human move. It's not simple, but Deep Blue must use an algorithm to decide which move to make, right?

posted by mrgrimm at 9:28 AM on March 15, 2012

Chess puzzles are meant to have a single optimal sequence of moves, by which the player can guarantee a win (or, in some puzzles, can force a draw out of a bad-looking situation). In other words, any individual chess puzzle represents a solved game.

But chess as a whole isn't solved. Outside the endgame, you can't always be

Deep Blue and its ilk do play algorithmically. But they don't always do an exhaustive search of possible moves and responses. Rather they use heuristic algorithms until late in the game — meaning, roughly, that they're mostly drawing conclusions like "This move seems to improve my position" rather than "I am certain that this is the best possible move" or "I am certain that this move will lead to victory regardless of what my opponent does."

posted by nebulawindphone at 9:45 AM on March 15, 2012 [1 favorite]

But chess as a whole isn't solved. Outside the endgame, you can't always be

*certain*that the move you are making is the right one. For instance, we know that some opening moves tend to do better than others. But we have no idea whether there is a single best opening move — and if there is one, we don't know what it is. This is why really good chess players can still have personal preferences when it comes to the openings they like to play.Deep Blue and its ilk do play algorithmically. But they don't always do an exhaustive search of possible moves and responses. Rather they use heuristic algorithms until late in the game — meaning, roughly, that they're mostly drawing conclusions like "This move seems to improve my position" rather than "I am certain that this is the best possible move" or "I am certain that this move will lead to victory regardless of what my opponent does."

posted by nebulawindphone at 9:45 AM on March 15, 2012 [1 favorite]

« Older If only it were this quick. | One down, many to go. Newer »

This thread has been archived and is closed to new comments

posted by Mooseli at 6:07 AM on March 14, 2012 [2 favorites]