![[ Paint by Numbers Example ]](images/pbn_counter.jpg)
Paint By Numbers ( aka Nonogram, Grafi Logika, etc)
Given information about each row and column of a bitmap in the form of
lengths of runs of black, determine the bitmap. Sometimes the
solution is not unique -- in the case of a checkerboard, this
information yields two distinct solutions.
This game, entitled "Paint by Numbers," as published in GAMES magazine in the early 1990s is known as a Constraint Satisfaction Problem (CSP). Since a solution is easy to verify, the problem falls into the class NP. There are a variety of programs to solve this problem, but none of these solvers is perfect.
In 1996, Nobuhisa Ueda and Tadaaki Nagao proved several interesting NP-completeness results for Paint by Numbers. Specifically, given an instance of the problem, the following questions are NP complete:
- Is there a solution?
- Given a solution, is there another?
![[ Complexity Graph for Paint by Numbers ]](images/pbn_complexity.png)
My solver is based on deriving truths for each row and column, thus reducing the given problem to a simpler one. Of course, deriving truth about a board doesn't help when the board is ambiguous, as in the case of a checkerboard. Even more madenning -- in accordance with the above NP results -- there are instances with unique solutions where it appears that exhaustive search is the only way to verify this fact, as in the example to the left.
![[ 3 Solar mass Star ]](images/3m_star.jpg)
A Day in the Main Sequence Life of a 3 Solar Mass Star
Project for Jim Sowell's Stellar Astrophysics Class -- what do current
scientific models predict about the inner workings of stars? (Fall
2001) PDF
Generators, Relations, and the Free Group
At
Budapest Semesters in Mathematics my topology professor introduced
free groups to us not in terms of the standard "extends uniquely to a
homomorphism onto an arbitrary group", but instead immediately in terms
of generators and relations. In addition, instead of only considering
a certain class of "reduced words," my instructor took the definition
that all words were admissible, but that they formed equivalence classes.
Proof of group structure under concatenation is then trivial, but then
the properties of the Free Group are left a mystery. Here I provide a
proof that, given this alternate definition, every equivalence class of
words has as a member a single reduced word. (Spring 2002)
TEX PDF
Designed by myself and Peter Pociask as part of Georgia Tech's Introduction to Aerospace Engineering. (Spring 1999)
A small game copied from the 80's Shareware DOS game Hexxagon. It gave Sanjay Bhatia, my partner, an excuse to learn DirectX and myself an excuse to play around with minimax and alpha-beta pruning. WARNING: The graphics code is a little buggy here. (Spring 1999) ZIP / Windows EXE
An animation for graphics class. Parameterized object movement based on path objects and global timing. Code in C++ (Winter 1999) tgz / C++
Advanced Networking and Services started sponsoring a competition called ThinkQuest in 1995 to encourage educational content on the web. I led a small team in High School to put together a site about math, and as part of this summer endeavour I wrote a paper and a Java program on how to make Stereograms. (Summer 1996)
| cnk.zip / cnk.exe | A simple DOS program to split a large file into several smaller files. Useful when you've just got a floppy drive. (zip file includes trivial src) (1994) |
| cipher.zip / cipher.exe | A simple DOS program to generate a random alphabetical substitution code, and then to filter a text file through it. Useful for the entertainment section editor for a newspaper. (zip file includes trivial src) (1997) |
| deboggle.c | Takes a 4 by 4 matrix of letters, and, using the system dictionary, enumerates all Bog-words in the matrix. (2000) |