Java Sudoku Solver

Jo has really been into Sudoku the past few months. Being the nerd that I am, I spent the past few weeks coding up a Sudoku solver that you can check out at http://www.ben61a.com/sudokusolver/. (If you’re not familiar with the game, read about it on its Wikipedia entry.) It has been, and continues to be, an interesting project because solving Sudoku turns out to be relatively complicated.

The first work item I completed was a fast solver. The solver first translates a Sudoku into an exact cover problem. It then uses the Dancing Links technique, originally suggested by Donald Knuth in this paper, to efficiently find all solutions to the exact cover problem. In the case of a well-formed Sudoku, there is only one solution. That exact cover solution is then translated back into a Sudoku solution grid.

Next, I used this Dancing Links solver to create a puzzle generator. This simple generator starts with a blank grid and adds a random digit to a random cell over and over. After each addition, I use the fast solver to see if there is only one solution; if so, then we have a new Sudoku. If there are no solutions, we have to backtrack because the last digit added messed up the puzzle. I used my puzzle generator to create 50,000 puzzles (it took about 8 hours or so because of the massive number of fast solves that are done).

Unfortunately, the nature of the algorithm used by the fast solver suffers two problems:

  1. It can’t give any clues as to how to solve a Sudoku in a stepwise, human-logic-based manner
  2. There is no way to judge difficulty aside from counting the number of hints given in the Sudoku

To remedy both problems, I wrote a new solver that uses human-logic-based solving techniques. Whereas the fast solver can solve any well-formed Sudoku, my new logic-based solver can only solve around 98% of puzzles since some require more advanced logic techniques that I just haven’t coded yet. These are the major solving techniques I have coded so far:

  • Singles
  • Naked Pairs
  • Locked Candidates
  • Naked Triples
  • Naked Quads
  • Hidden Pairs
  • X-Wings
  • Coloring

Based on the number of types of techniques a puzzle requires to be solved, I was now able to classify puzzles in an (admittedly) subjective manner:

  • Easy if the only technique required is Singles
  • Medium if the only techniques required are Singles, Naked Pairs, or Locked Candidates (and it’s not an Easy puzzle)
  • Hard if it’s not an Easy or Medium puzzle
  • Evil if my logic-based solver cannot solve it using any of its techniques

Surprisingly, 47739 of the 50000 generated puzzles (95.5%) were classified as Easy (only required Singles). That’s crazy! As for the rest, 755 were Medium, 493 were Hard, and 1013 were Evil.

Finally, I put a user interface on top of the logic-based solver and put it online as a Java applet, linked above. It’s really just a first blush at a UI, so I know there can be much improvement.

Anyway, I’d love to hear your impressions and feature ideas, so leave a comment!

Several notes:

  • Because of the sheer size of storing 50000 puzzles even just as strings, I made a decision to only include 250 Easy, 250 Medium, and 250 Hard puzzles in the applet. This means that when you click “Easy,” you will only be given a puzzle from a pool of 250 puzzles.
  • I’m thinking about porting my poker and Sudoku applets to Flash since no one uses Java =p. It looks like I’d need to buy some Adobe software to do that though (not to mention learning Flash), but it sounds fun. Look for that in the future.

1999 Honda Civic MPG

Over the past 8 years, I’ve kept a book of every gas fill-up I’ve ever done for my 1999 Honda Civic. It catalogs the date, odometer reading, number of gallons in that fill-up, and total cost of the fill-up. For the first time, I took that book out of my car to input the data into an Excel sheet. After 30 minutes of furious 9-keying, I had all 329 visits entered. After another 15 minutes of playing with Excel 2007’s graphing, I had this:

Yearly Average MPG

Analysis

  • My overall average MPG for the time period is 29.77
  • 1999 (30.16 average MPG)
    • I was breaking the car in, which probably accounts for the above-average MPG
  • 2000-2003 (27.86 average MPG)
    • I lived in Berkeley, which meant almost entirely city driving
  • 2000-2005 (28.78 average MPG)
    • I had 17″ rims on my car instead of the stock steelies and wheel caps
    • I’m too lazy to weigh the 17s + low profile tires and compare them to the 14″ steelies and normal tires I have on now, but I imagine having the 17s accounted for a lot more weight, which means lower MPG
    • This, in combination with city-only driving, probably accounts for the below-average MPG from 2000-2005
  • 2005-2006 (30.82 average MPG)
    • I lived in Los Angeles, where I drove extremely little
    • The only time I drove was to come back home to the Bay Area, which increased my gas mileage
  • 2007+ (32.83 average MPG)
    • I’ve been driving with a gas-efficient mindset, which probably accounts for the 3 MPG gain
    • The MPG gain may be even higher because as cars age, they typically get lower MPG

If you’re wondering, my driving habits are:

  • Accelerate only to 2,500 RPM before shifting into a higher gear (manual transmission)
  • Cruise at 1,500 RPM (which means I’m typically in 4th gear for 30MPH and 5th gear for anything higher)
  • Pay attention to upcoming red lights to cruise for as long as possible
  • Stick to 65 MPH on the highway

Here are some other graphs that I generated:

Yearly Average Cost/Gallon

MPG Between Fill-Ups (w/ 20-Period Moving Average)

Cost/Gal Per Fill-Up

Why I Eat My Fries First

Whenever I eat at In-N-Out with someone new, they comment on how it’s interesting that I eat my fries first. I do it because I happen to think that fries and burgers are about the same “goodness” when first cooked. However, the goodness of fries decreases exponentially over time (to a point) whereas a burger’s goodness decreases more linearly. This means that I can maximize intake of goodness by eating my fries first.

If you like fries more than the burger, the case is even clearer:

But how about those who like the burger much more than fries? I think such people will still maximize their intake of goodness by eating fries first:

Note that if you can finish your burgers and fries within 5 minutes of them being cooked, it shouldn’t matter as much which you eat first.

Maybe later on, I’ll think about doing an analysis that takes into account the decreasing goodness of food over the course of a meal (that is, a food item eaten when one is hungry always has a higher goodness value than the same food item eaten when one is not as hungry). I think the conclusion will be the same, though.

Eat your fries first.

WikiMapia

I love maps and I am loving WikiMapia. It not only helps me identify landmarks when I’m going to an unfamiliar place, but it also lets me learn about things I didn’t know existed in places that I’m extremely familiar with. Last week, I learned that there are several pieces of the Berlin Wall right next to my church in some office complex.

Check out the South Bay and zoom in to see more: http://wikimapia.org/#lat=37.391164&lon=-121.997509&z=13&l=0&m=a&v=2

I’ve already added a few places =]

Edit: Jo found “Happy, happy, happy guy” !!!! Hahahahahaha

MySong – Microsoft Research

Most folks never get a chance to answer this question, since writing music takes years of experience… if you don’t play an instrument or spend lots of time around music, you’ll probably never get to write a song.

MySong, introduced in our CHI 2008 paper, automatically chooses chords to accompany a vocal melody, allowing a user with no musical training to rapidly create accompanied music. MySong is a creative tool for folks who like to sing but would never get a chance to experiment with creating real original music. Come on, you know who you are… you sing in the car, or in the shower, or you go to karaoke clubs, or you just once in a while find yourself singing along with catchy commercial jingles. MySong is also a great tool for songwriters who want to quickly experiment with melodies and accompaniments.

Check out the video!

http://research.microsoft.com/%7Edan/mysong/

What I Learned At Work Today

I’m guessing a lot of people figured this out long ago, but I’m going to call it out just in case you never realized.

It’s really annoying when the paper toilet seat cover falls into the toilet before you have a chance to turn around and sit on it. I figured out today that you can minimize the chance that the cover will fall in by placing it such that the crease from the fold points up instead of down:

The reason the cover falls in is because the water seeps into the center flap, pulling it downward. Pointing the fold crease up causes more resistance against that downward pull. Win!

Poker Programming

Nerd alert! I recently got back into programming in Java. I started by retrofitting my old Texas Hold’em Odds Calculator so 1) it runs about an order of magnitude faster, and 2) it includes icons for the card suits.

Tenis suggested a new applet to work on: He wants an applet for Texas Hold’em that, given his starting hand, tells him what opponent starting hands would likely beat him and what opponent hands he would likely beat. Because of the sheer combinatorics, I scoped the problem down and refined it a bit: Given your starting hand and the flop, list the percent chance that the given starting hand will beat or be beaten by all other possible starting hands.

I took up the challenge and tonight I finished the engine behind the applet; I still have to write the user interface, which can take a while. While I go do that, here’s some math and sample input/output (let me know if you see any bugs):

Math

  • There are 1,326 (52 choose 2) possible starting hands in Texas Hold’Em
  • Since we’re given your starting hand and the flop, we are left with 1,081 (47 choose 2) starting hands that oppose you
  • We compare your starting hand against each of the 1,081 opponent starting hands one at a time
    • For one such comparison, we know your starting hand, your opponents’ starting hand, and the flop, which leaves 45 cards in the deck for the turn and the river
    • In other words, there are 990 (45 choose 2) possible combinations for the river and turn
  • This means that to analyze one starting hand + flop combination, the applet examines 990 combinations for each of the 1,081 opponent starting hands, or 1,070,190 hand comparisons (990 x 1,081)

Edit: Here’s the first draft of the new Texas Hold’em Matchups calculator