Ramblings: Aug 22 2007 posted 8/23/2007 12:29:14 AM | 3 kudos what's this?     report abuse tagged: life, rambling, work

koyaanisqatsi

Work has been crazy. I was supposed to deploy new code tonight and found that my application didn't produce the same numbers as the prototype for a few loans. Was at work till 9pm trying to find the problem in my code.

I happen to be a mystery buff -- I love mysteries of all sorts: books, movies, games, etc. I recalled the law of deduction, made famous by Sherlock Holmes in The Sign of the Four:

When you have eliminated the impossible, whatever remains, however improbable, must be the truth

So I put my code down and started to look at the prototype. Within 20 minutes I found an error in the prototype. *sigh* I spent 7 hours looking for a bug in my code that didn't exist. I fixed the prototype, fired off an email to the other people in my group and left work at 9:30pm.

Thank you, Sir Arthur Conan Doyle. If it weren't for you, I shudder to think how much longer I would've spent at work.

I've been persona non grata at MD for a while and have been losing touch with my friends here. I apologize for that. The NYU semester is starting Sept 4, and I've been trying to get as much work and social stuff done before the semester starts because once classes begin, I'm going to be persona non existis. I feel like the semester is this giant black storm system headed this way. Off in the horizon, but fast approaching. Please pardon my absence -- I'm trying to live life to the fullest before the semester saps my life away.

I wanted to gloat more over NobelBreed, I mean LongRanger, some more, but the truth of the matter is, it really means so little in the scheme of things. My education, career, and social life are way more important than some crazy guy pretending to have a doctorate and a high paying job. In the end, it really makes no difference.

So today is cause for minor celebration. I got home totally exhausted, so I curled up on the couch to some Telemann on recorder and did a "challenging" sudoku:

_ 6 _ | _ _ _ | 3_ _
_ 9 _ | 1 _ 7 | 2 _ _
_ _ 1 | 5 _ _ | 6 _ _

_ _ 6 | _ 3 _ | _ _ 9
_ _ _ | _ 4 2 | _ _ _
8 _ _ | _ _ 9 | _ _ 6

_ _ _ | _ _ _ | _ _ 8
2 1 4 | _ 5 _ | _ _ _
_ _ _ | _ _ _ | 4 _ _

I've certainly solved plenty of challenging sudokus before. I usually get them pretty quickly, although occasionally I'll hit one that has a fairly significant "logjam": I'll hit a point where I look and look and look, but can't make further progress.

Usually I'll put the sudoku down for a day and come back to it, and then there's a hidden triple or something staring me right in the face. I'll eliminate a couple of candidates, and then the whole puzzle falls to pieces in my hands. But there's like this one lynch pin that just jams the entire thing up.

Well, that happened with this puzzle. But I couldn't find any naked pairs or triples. No Gordonian rectangles jumped out at me. I recalled something called an x-wing pattern that I never really learned. Did a quick Google search, learned the technique, and after staring at the puzzle for about 10 minutes, found an x-wing pattern. If you try the sudoku above, the x-wing was a "7" in squares (5,2), (5,3), (7,2), and (7,3). That eliminated all the 7 candidates in rows 5 and 7, which revealed a hidden double, which revealed two naked singles. After that, the puzzle just melted like butter under a hot knife.

So tonight is the first night I used the x-wing pattern to solve a sudoku. It was very gratifying.

There's a couple of more techniques that I've heard about but don't know how to apply: sword fish, jelly fish, x-y wing, and Gordonian polygons.

One important question in mathematics is the idea of completeness: whether a subset of objects can be used to attain every other object in the set. If you've ever taken calculus, you've actually used the idea without knowing it. The set of Taylor polynomials: x^0, x^1, x^2, x^3, ... is complete in the sense that every other differentiable function can be attained by some (possibly infinite) set of Taylor polynomials. The same idea goes for Fourier series, except the complete set is a (possibly infinite) combination of sin(nx) and cos(nx).

A question that's been nagging at me is: what set of sudoku techniques form a complete set for the solution of any valid sudoku.

For example, scanning would not form a complete set: you cannot solve an arbitrary sudoku using scanning. Perhaps the easiest ones you can, but for anything but the most trivial puzzles, you'll find you can't solve them solely using scanning.

I'd love to know what the smallest set of techniques is that will always get me to a solution. I spent a few minutes Googling trying to find the complete set of techniques, but couldn't find any. I'm guessing that to answer such a question, one would need to formulate an arbitrary sudoku in some abstract manner and start proving theorems about what you've just modeled. This has been done for the Rubik's cube, but it appears that this has not been done for sudoku. Yet.

Copy & paste to friend: (Click inside box; Ctrl + C to copy; Ctrl + V to paste)

Blogs by koyaanisqatsi: Why Are Geeks Often Atheist? New Fundamental Constant of Nature Sex With Strangers: Initial Results I Ate Way Too Much Sex With a Stranger Hastur I Am Not Gay, Nor Have I Ever Been Gay Ramblings: Aug 22 2007 Ramblings: August 4 2007 Energy: Dedicated to Monsterboy (part II) Energy: Dedicated to Monsterboy (part I) A 3:30am Riddle AIDS and the 80's Response to a Blog on Immigration Blog Riddle: Skinning a cube