Category Archives: Personal

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.

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

Missing Berkeley

Since I couldn’t sleep, I started looking through old pictures on compy. I reminisced about the good old days; I wondered what so-and-so was doing now; I saw friends as they were years ago; I missed Berkeley.

I also found this old post from my previous blog of 100 random memories that I had the foresight to catalogue. What a throwback.

1. going to foothill to eat dc
2. late niet jack runs
3. sc and war3
4. fellowship hopping
5. ee40
6. cleaning henru and jon’s apt on channing
7. 2002 summer interns
8. moving into royston
9. soda
10. living at ken’s before i moved to berkeley
11. visiting sobay my first year summer; denny’s and cars with dave h.
12. carrying a 3-seater hardwood couch with dave h. from royston to past GPB at 11pm (0.84 miles if you go thru campus if you were wondering)
13. visitors from upenn
14. shk, ben and jerry’s, mcdonalds, the opening of tako, pyramid, cheeseboard, ibhoagies, shogun, sushi house
15. driving up the mountain (kamu, dave h.)
16. sleeping at 7am, waking at 5pm
17. pulling all nieters to correct my sleeping schedule
18. using various cards to break into apts for people who locked themselves out
19. sae vs. axio
20. pizza at westminster as a frosh
21. singing on sproul, in dwinelle, vlsb, around campus
22. ms. jackson-benedict
23. 102, 108, 110, 203, 210, 303, 304, 306, 308, 310, 401, 402
24. bb gun wars
25. batting of a roll of paper towels in the garage
26. singing in the stairwells, garage, and laundry room
27. laundry room floodings
28. 20th, 21st bdays
29. underhill before it grew a dc on one end
30. old couples
31. visiting stanford with therapists
32. spring break 2003
33. joe’s summer in 203
34. the faces of people i saw around campus that i’ll probably never talk to again
35. friends i’ll always remember
36. pool in foothill
37. meeting special incoming frosh each year
38. extension
39. telegraph commons
40. first pres FIVE 45
41. going to unit 2 dc for brunch and the unit 3 dc after church
42. turkey and mashed potato niets
43. passing by the triad restaurant in oakland chinatown with therapists
44. going to chinatown with my parents on a saturday afternoon
45. cheesecake on too many occasions to list
46. shopping
47. pinole and all its goodness
48. emery bay
49. ikea when it first opened
50. replacing my recliner with a couch
51. dual monitors
52. oldddd friends from saratoga
53. rsf (225 baby)
54. running at the clark kerr track
55. the mountain
56. finding goats one time on the mountain
57. finding out they are placed there to eat the grass to prevent wildfires
58. winter retreats
59. worship
60. small groups
61. buying that light from ikea that makes my eyes hurt
62. sleeping on my couch on hot summer niets
63. settlers
64. going to jack in my bathrobe
65. holdem
66. being caught for supposedly cheating
67. friends and scrubs at derek’s
68. bbqs at will’s, kevin’s
69. buying 48 cans of soda at a time cuz they’re on sale at safeway
70. visitors from other ucs
71. weekends away
72. crazy friends’ ex-gfs
73. late-niet ludeness
74. equinox
75. clubbing (that one time i went)
76. never having gone up the campanile or the big c (yet) [STILL!]
77. driving down to la/sd
78. testimony
79. kelly getting beaten by a girl
80. plotting to take several cs61a midterms after having taken the class, standing up after 10 minutes and saying “wait, was that it?”
81. starting this xanga
82. walking home one niet with grr from an aacf thing up channing
83. visiting 6a40
84. watching endless streams of generations populate royston
85. hooking dan up with the waitress at tanaka
86. singing at clc
87. visiting ebac
88. watching matrix 14 times at my apt with so many different groups of people
89. watching lotr fotr at emery bay
90. driving to get food from the tacobell/kfc on telegraph
91. seeing friends randomly on campus every time i went
92. doe library at niet
93. turning in homework at 3am at soda
94. running around the block at 2am one time cuz i was bored
95. taking history of Christian thot zzzzz
96. helping ta move from unit 1 to royston in the rain
97. coming up with the nickname tenis
98. accountability, discipleship, and chess
99. mooey coming as a frosh
100. missing berkeley everytime i was away

The Queen Is The Queen Of Canada??

Wow, I am ignorant. I did not know that the same Queen of England, Elizabeth II, is the Queen of Canada and a whole bunch of other places! She owns!

In addition to the United Kingdom, Elizabeth II is also Queen of Canada, Australia, New Zealand, Jamaica, Barbados, the Bahamas, Grenada, Papua New Guinea, the Solomon Islands, Tuvalu, Saint Lucia, Saint Vincent and the Grenadines, Antigua and Barbuda, Belize, and Saint Kitts and Nevis, where she is represented by Governors-General. The 16 countries of which she is Queen are known as Commonwealth Realms, and their combined population is over 129 million.

http://en.wikipedia.org/wiki/Elizabeth_II_of_the_United_Kingdom

I Just Ruined 4 Years Of Suspense

Over the past two months, I have been very careful to limit the places I go to browse for cool stuff to post. You see, several years ago I had the ending of the 6th Harry Potter book ruined for me because someone posted the spoiler as a thread title at a forum I frequent. I couldn’t miss it and I didn’t.

Tonight, I made my new blog title a self-describing truism. I came across a link that read, “Full Disclosure: Harry Potter 0day.” And I clicked it. I had a brief lapse of good judgment and I clicked it. I know what “full disclosure” means. I know what “0day” means. And I clicked it.

In the 4 seconds it took to scan the page, I have possibly ruined 4 years of suspense. I may know what happens at the end of the Harry Potter series. I am an idiot.

Sure, it’s likely that this is a hoax and that the person who posted the spoiler is just looking for attention, but it might be real. Either way, it will definitely be in the back of my mind for the duration of Book 7.

Article 1 about the claimed spoiler

Article 2 about the claimed spoiler

*The spoiler*