Archive for July, 2009

Cash for Clunkers

Friday, July 31st, 2009

I’m not sure how congress managed to conceive of and pass legislation that actually makes sense, but the “Cash for Clunkers” program is the one stimulus that seems to work. After bailing out the auto industry and amid high unemployment, the idea of paying consumers much more than their auto trade-ins are worth if they buy a new (hopefully American – whatever that really means) car is simply brilliant. The $3500-$4500 cost to the taxpayer leverages its stimulating effect on the economy by getting the consumer to spend a lot more of their money at a time when an increase in consumer participation in the recovery is needed. The fact that the program went through the (hopefully first) billion dollars in only 5 or 6 days indicated the degree of pent up demand for big ticket items like automobiles. The additional impact the program has on boosting the overall fuel efficiency of the cars on the roads is a further win for the economy since it reduces the demand for foreign oil and lessens the trade deficit.

How can it be that congress managed to pass this into effect? I’m stunned. Perhaps there is hope for us after all.

Sudoku

Sunday, July 12th, 2009

I’ve been doing sudoku for a couple of years now and I have developed a simple notation that keeps track of what numbers can go where in the 3×3 blocks. I do not track all combinations, only 6 basic “shapes” and their various permutations (rotations and reflections). I have found these simple shapes are all that is needed to work almost any puzzle. The more complex patterns you may think are important eventually simplify to one of my basic shapes as your solution for the puzzle progresses. The notation is very simple, easy to learn, and easy to manage (alter/edit as the solution progresses). A key property of any notation is that it needs to be easy to interpret and unambiguous in its meaning. I’ve seen a lot of people working puzzles by filling each block with all of the possible numbers that can go in each square. That is hideously busy, difficult to read, and impossible to manage. It can be an effective technique near the end of solving some of the most difficult puzzles though, so I won’t completely deny its value because I have resorted to using it exactly twice.

Adjacent

Adjacent

First a bit on how to read my figures. The black numbers are the numbers that the puzzle either started with or we have added in trying to solve the puzzle. The blue numbers are the ones that limit where in a 3×3 block that same number can be placed. The possible locations are denoted by numbers in gray. Finally, my notation is indicated in red. When working a puzzle I use a very fine mechanical pencil. I prefer 0.3mm lead, but that can be hard to find. A good clean soft eraser is also a must. With that out of the way, here are the six basic shapes I use to work sudoku puzzles.

The first I call Adjacent. When a number’s location is limited to only two cells that are adjacent, either in the same row or column, I place that number in the center of the line shared by the two cells. In this example I’m considering the possible locations of the number 2 in the Left Middle 3×3 block. The bottom two rows are blocked and the top row already has one value filled. The only two possible locations are next to each other. So, I place a small 2 on the line between those cells.

Line

Line

The next shape I call Line. It is an extension of the Adjacent shape in that it is comprised of three cells in the same row or column instead of just two as found in Adjacent. If the pattern falls in a column, I place the number centered vertically and near the left edge of the center cell. If it is a row, I’ll place the value centered at the bottom of the center cell. It is important to apply the notation consistently since the primary meaning is derived from the location of the values. It will be hard at first to remember where everything is supposed to go. It will also be difficult to read what the notation is telling you. As with anything, practice makes a big difference and I hope you’ll find this can be learned quickly.

Ends

Ends

The third pattern which contains cells within a single row or column I call Ends. It is exactly what is sounds like. The possible locations are at opposite ends of a row or column. Since the pattern spans the full length of a row or column, I’ve chosen to place the value in the center block. If the pattern is found in a column, place the value centered on the right side of the center cell (yes, in the cell where the number cannot actually go). If it is in a row, place the value centered at the top of the center cell. You should note that this is exactly opposite from where you’d place the value if the pattern was the Line and this demonstrates the importance of applying the notation consistently.

Block

Block

The next pattern is the Block. It is formed by a 2×2 sub-square in the larger 3×3 sudoku cells. The notation places the value on the intersection of the lines where the four cells of the block share a common corner. Each of the 4 cells does not have to be empty for the notation to be valid. If one of the cells already had a value filled in, you would still use this notation to indicate that the value could go in any of the remaining three cells. There is also one way to have two of the cells already filled in and still use this notation. If the two empty cells touch only at the common corner, like two white squares on a checker board, then this notation applies. The other pattern of two squares is actually the Adjacent shape.

Corners

Corners

The Corners pattern is somewhat similar to the Block. For this pattern, the locations are found in the 4 corners of the 3×3 sudoku cell. As was the case with the Block pattern, one or two of these cells can be filled with a value already and the notation is still valid. The two empty cell form has the two possible cells in different rows and columns (kitty corner, catty corner, cady corner, … whatever you call it). The notation goes in the outer most corner of one of the corner cells. I prefer to place the notation in the corner of a cell that is on the outside edge of the whole 9×9 puzzle grid. If that is not possible (e.g., the center 3×3 grid) then I go with the upper left if it is empty. Which cell you select is not too critical for this pattern.

The L

The L

The last pattern is a three cell pattern that has many permutations. It is called the L. It is a combination of the Adjacent and Ends patterns where one of the cells is common to both. This means that the long axis of the two patterns forms a right angle, hence the name L. The notation places the value in the cell at the corner of the pattern. The value is placed in the outermost corner of that cell which is also between the two touching cells (of the Adjacent pattern). Just look at the image.

As you use the notation, you will eventually need to place multiple numbers in the same pattern (e.g., both 2 and 8 need to be in the same Adjacent). Simply place the numbers close to each other, either side-by-side or one over the other, you’ll quickly learn which way works best in each situation. Being able to write small is a big help. The real power of the notation is that it allows you to see at a glance that some of the cells are not available. If two numbers are assigned to the same Adjacent (or Edge) pattern (e.g., 2 and 8 as in the previous example), then the cells of that pattern cannot be used to make any other pattern for another number. Four values assigned to the same Block means those four cells are out of play for any other numbers/patterns. You may not yet know where each number goes in these full patterns, but you do know that they do end up in there somewhere. The beauty of the notation is that there are no conflicts in position so the placement and interpretation of the notes is unambiguous.

So that is my notation. Try it out and let me know how it works for you. I’m always interested in hearing about more tips and tricks too.

I received a book of Sudoku puzzles for giftmas 2007. The title is “X-treme SUDOKU” by the editors at Nikoli Publishing. The book offers 160 difficult puzzles and 160 more very difficult puzzles – 320 in all. I found the book to be a fabulous waste of time when I had no choice other than to waste time (e.g., waiting in the doctor’s office). I just finished the book and feel like I have accomplished something. There were two puzzles that stood out as being deviously difficult – at least for me. (Hint: try solving the puzzle in my first figure!)

Alternate Launch Abort System

Saturday, July 11th, 2009
MLAS Video (click to view)

MLAS Video (click to view)

I know this was just a test to demonstrate a proof of concept for an alternate launch abort system for Constellation, but it does seem to be quite complex and rather impractical given all of the excess mass of the system. Nevertheless, it worked amazingly well and will hopefully contribute to the overall safety of NASA’s new vehicle. It was tinkered together in a very short time. Some folks have great jobs!