Crossword Puzzle Solution Generator

     In my artificial intelligence graduate course this semester, we had a term project to create a LISP crossword puzzle game. The game has two modes, an automatic and a manual mode. In automatic mode, the computer is programmed to automatically fill in the grid, whereas the user may choose to play manually through manual mode. In automatic mode, the program generates as many solutions to the crossword puzzle as it can in the limited time span of 30 CPU seconds or until it reaches a maximum of 100 solutions. The program was given a wordlist of over 100,000 English words contained in the text file wordsEn.txt and an arbitrary grid data file as input.

Technical Approach and Intelligence

     My program uses a depth-first search backtracking algorithm to fill in the grid with words from the wordlist until the puzzle is solved while backtracking if no solution for an entry is found. An entry is defined as the horizontal or vertical lines of empty cells that are to be written. The depth-first search approach starts with an empty entry (root node), writes to it, and moves to its first neighbor (first child node). The same process trickles down for all neighbors’ neighbors. If a neighbor is already written to, it will then move to its second neighbor and so on until all neighbors are filled and we move back up to the entry that calls it. If there is no solution for an entry, we retrace back to the calling entry, find a different solution for that entry, and repeat the process until all entries are filled and the puzzle is solved.

     In order to speed up search time and reduce the chances of the program searching through dead end solutions, I applied a couple of heuristic to minimize the number of backtracks and improve performance.

     The problem was approached with the “First Fail principle: try first where you are more likely to fail”. One heuristic that was used was the least constraining variable heuristic where the crossword puzzle is solved by first filling in entries with the greatest number of constraints. The constraints that is of the most interest, is the number of intersections of letters a word entry has with other entries of different directions. In other words, an entry with 3 neighbors will have a constraint of 3. However, because we are using a depth-first search approach, it is important to also sort each entry’s neighbors by greatest number of constraints. This allows us to visit neighbors that have more intersecting positions first. Another way of looking at this heuristic is that it looks at one additional level of constraints, and permits us to starting writing at a position in the grid that is of the highest degree of complexity in terms of constraints and limits the number of backtracks. 

     To break ties between entries with the same constraints, the entry with the smaller domain size will be chosen to maximize choices for the remaining entries.

letter frequency of text

    Another heuristic that was employed was to check if the letters at each intersection begins with an e, t, a, o, i, n, s, h, or r. These letters have the highest frequency of appearance in the English dictionary as portrayed by the figure below. This approach was taken so that intersecting letters that have low frequency won’t be chosen and hence lead to a dead end which would cause more backtracking. Admittedly, as with other greedy heuristics, this heuristic might have an adverse effect where the only possible intersecting letters for two entries are one of the letters that were not allowed. In this sense, we are omitting search sensitivity for speed.

     Finally, words in the same domain were not shuffled and were instead sorted in alphabetical order. This is another strategy to limit the searches for words to fill an entry because words at the beginning of the alphabet have a higher frequency of appearing.

Results

     The algorithm was tested using 14 test grids with varying degree of complexity. Mostly, the program was able to generate 100 solutions for each test grid with an average run time of 0.3 second per grid. For extremely cluttered grid with high solving difficulty, the program was unable to generate a solution within the 30 second time frame permitted. Out of the 77 class projects, my algorithm ranked 8th in speed and completeness which I thought was pretty impressive. 

     Overall, this was a challenging but fun project. I especially enjoy finding new and creative ways to improve my algorithmic efficiency. It was also my first time programming in LISP, and boy was it a major battle. Debugging and finding documentations on the language prove to be quite difficult. However, there are many benefits that I've discovered upon using the language such as the "nth" function and the straightforwardness of the code.

The French Press

The french press coffee maker is officially my favorite investment this fall! The coffee it yields is so much more flavorful and aromatic than a regular drip-brewed coffee maker. Why? Because the direct contact of coffee and water traps the essential oils and flavor that is otherwise lost in the paper filters of regular coffee makers. 

To brew the coffee, I start off by stirring the ground coffee and boiling water together in the beaker, let it brew/steep for 4-5 minutes, then press the plunger to trap the coffee grounds towards the bottom of the beaker. I use my favorite standard coffee which is Starbucks Expresso Roast whole beans. To prepare it, I add to the coffee a tbsp of condense milk and a tbsp of milk in a medium sized mug or tumbler. Topped with some whipped cream or milk froth and you have a yummy concoction!

So what are you waiting for? Join the bandwagon, get it at Amazon.com for $19, and enjoy!

Smart List

Smart List was an idea my friend and I came up with for our senior project. We wanted to take advantage of the Google Places API that was recently released to the public as of May 2011, and create a unique and useful Android app. Hence, we decided on the idea of a task managing system/to-do list which would voice alert  (proximity alert) you whenever you're near your errands' locations. You need only to enter the name of a place such as Wholes Food and it would return a list of all Wholes Food in the area which you can pick from and view on the map to do a task such as Groceries. Additional features include displaying a map of where all the tasks are located, an alarm system to set when the errands are due, and the option to email the list of all errands. 

After 3 months of careful design, implementation, and user testing, we finally have a finished and working product! It has been an amazing experience getting to work with Android. We definitely faced some problems with how often to poll for the GPS location so as not to overload the battery consumption. Our solution was to set different polling rates based on whether the users' position (longitude and latitude) changes over time. If the user is at home, the GPS will poll every 10 minutes whereas if the user's location changes rapidly (perhaps he/she is in a car driving), we would poll it every 5 seconds. It manages to work pretty well, I would say.

Some Views of Smart List

Add Task Activity

Home Activity

Proximity Alert

Map of all Tasks

RIP Dennis Ritchie

Only days after Steve Jobs' death, we also lost the inventor of the C programming language and the Unix operating system, Dennis Ritchie. Not many has heard of him and certainly no biography has been released only 2 weeks after his death, but let us pay a tribute to the genius whose shoulders we all stood on. RIP Dennis Ritchie, the king of the invisible world.

"Ritchie was under the radar. His name was not a household name at all, but . . . if you had a microscope and could look in a computer, you'd see his work everywhere inside." - Paul E. Ceruzzi

Philosophical Musing

I've always been an idealistic person, always intrigued by things, feelings, and situations that are sensational, captivating. I like reading books with an exemplary hero, an element of magic, adventure, or flights of fantasy. I like associating love with those rare magnetic moments that envelope your entire being. More wildly, I like imagining the fate of the universe and mankind resting on our own creation. That is, I’m speaking of sentient machines. Artificial intelligence has always been a fascinating subject to me. Of course we are decades, possibly centuries away from true AI. But, if we are to create sentient beings in the image of our likeness, as it is the only way we know how, we must first reverse engineer the human brain and decipher our own intelligence, which in itself is another phenomenon.

The other day in AI class, my professor brought up something very interesting. He asked us to tell him the phone number of the White House. We immediate acknowledge that we do not know. And that, quite frankly, is the genius of the human brain. We did not have to search our memory bank to come up or not come up with an answer. We instantly know that we do not have that information; whereas, computer systems must have a searching process in their database. If we are able to understand how our human brain can bypass this search method, perhaps we can shift the paradigm of how knowledge can be attained.

RJ and I often discuss about living forever by preserving our brain and reconstructing our memories onto another stronger body/host. He believes that if something has all the same memories as you, then it is essentially you. I, on the other hand, believe that just because a host has all of your memories does not make it you. It’s like cloning a person, you’re missing an important element and that is the human consciousness. If my conscious no longer exists, it is just someone else with my memories. Perhaps if we were born in the next century, we would have the answer to this puzzle. I often question if it is a blessing to be born in my age for the reason that I do not have to witness some sort of Apocalypse that would end my race, or that it is a curse not to be able to witness the ultimate advancement of my species.

Emo Philips: “I used to think that the brain was the most wonderful organ in my body. Then I realized who was telling me this.”

Lucid Dreaming

This morning, I got up at 6am for no apparent reason, had breakfast, and went back to bed. This was when I experienced my first real lucid dream. In my dream, I was bothered by the fact that certain events were not logical, and came to the realization that I was, in fact, dreaming. Of course this has happened before, but this time I remember from what RJ and I read on wikipedia that you can actually control your lucid dreams. So I concentrated on staying in the dream, while repeating a chant "this is a dream" over and over so my subconscious would not take over. My awareness made every detail in the dream crystal clear; it felt SO real. I then will myself to fly. It took a lot of concentration and struggling, but then I was suddenly airborne. It was simply exhilarating! I remember laughing in awe. :)

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

School Starting Fall 2011

It's that time of year again as students hustle and bustle like bees back on to campus. Frankly, I love the positive energy and excitement in the air. It's rather contagious. :)

Classes are very interesting so far, Artificial Intelligence and Bioinformatics being my favorite to attend. The engaging and enlightening discussions make the hour past by much more swiftly. In fact, I had a good laugh in my Bioinformatics class the other day that I'd like to share. 

Now Bioinformatics is a class that analyzes DNA and protein structure using computer science. My professor was in the middle of his discussion about DNA and how each parent contributes 23 chromosomes to their offspring. The last chromosome being the XY chromosome that determines the gender: XX for female and XY for male. 

A student in the back raised his hand and asks, "Is there any chance you can get a YY permutation?" Of course the entire class immediately argued that the female can only give an X, whereas the male can give either an X or a Y. My professor ponders and said... "No, well except... ah never mind..." he laughed it off.

'Unless what?', I thought. Then I started to laugh. A few of the other classmates caught on with the implication and laughed along with me realizing that he was referring to two gay men. Yes, we're childish, don't judge. :P

The professor then continues on with his lecture. "Now when there are more or less than 46 chromosomes, we get mutations like Down Syndrome. Of course mutations can be desirable, but most likely they are not," he stated. At this moment, the same student choose to raise his hand and asked, "Would you happen to know what mutation is necessary to obtain the X-MEN Syndrome?" That rallied a round of laughter from the class.

The professor played along and said, "If I tell you... I'm afraid I'll have to kill you. That information is classified." 

"So you do not deny the existence of the X-MEN formula?" He teased.

Class was then shortly over. Everyone came up and high fived our "class clown" for the entertaining conversation. 

I'm hoping the rest of the semester will be this enjoyable. :)

New Apartment

Today marks the third day at my new townhouse. Besides some missing furnitures that we still have to move over on Tuesday, we've had mostly everything unpacked and neatly arranged. I'm glad to say that the apartment looks tidy and well decorated, and I'm feeling amazingly content right now. I'd have my zen moments in the new kitchen cooking dinner for RJ, Tunhi, and James. We'd then sat down in the living room, put on some nice music, light up the laserpod, and just enjoy each other's company and the food. I made chicken curry last night and crispy tilapia with corn and mashed sweet potatoes today. It's the perfect relaxing atmosphere I've always wanted to come home to.

Today I drove around town to buy the little household items that we still needed. It's amazing how I find joy in the tiniest things. For example, the kitchenware isle at Walmart could peak my interest for at least half an hour as I browse the store. Since the moving rush in Gainesville, the work desk that I've had my eyes on were out of stock. I finally found it in the Walmart across town. Once home, I sat down for the next hour to screw the parts together myself. Needless to say, I feel pretty acomplished. In the evening, RJ and I would go for a swim in the luke warm, sparkling pool. When the summer heat dies down and the days get breezier, I plan to spend more time by the pond, feeding the turtles, and reading a book on the swingset. The puzzle pieces are finally starting to fall into place right now.

Divergent

Yesterday, I stumbled upon the book Divergent by Veronica Roth. Having seen it widely displayed at various bookstores, readers' blogs, and websites despite it being a deput novel and only recently released (May 2011), I figured there must be a reason for all of the hype in such a short period of time, so I decided to give it a try. 

After skimming through the summary, I'm surprised that it reminds me of the Hunger Games by Suzanne Collins, one of my favorite books. They are both dystopic young adult novels centering around a strong heroine with a keen and incredible instinct for survival, but that's where the similarities end. After consuming the book in literally a day, I can safely say that Divergent has it's own unique identity. 

In Beatrice's world, society is divided into 5 factions: Abnegation, Erudite, Candor, Dauntless, and Amity, which are those who value selflessness, intelligence, honesty, bravery, and peace, respectively. The people in these factions act accordingly if not adhere strictly to their "personality" in an attempt to form the "perfect society". 

My first impression was that it would seem illogical to categorize each individual human being into one of these categories. If you think about it, we all have more than one of these traits, if not all, in each of us. Of course that disregard for human complexity proves to be the fatal flaw in this ideology. Beatrice and those who turned 16 that year, has to take a test to determine which faction they belong to. Everyone has one result and it is kept a secret; however, they may choose a different faction to join at the initiates ceremony. Beatrice's result, however, was met with complications as it is inconclusive, making her a Divergent, something she is told is extremely dangerous. She has to fight to keep that secret from ever surfacing, else her life would be in danger.

I won't spoil the rest of the story, but I would recommend all Hunger Games fans to pick this book up! It's an excellent read. It is not yet at the level of the Hunger Games series, but most definitely almost there!

The Order of the Engineer

Today RJ and I attended the Order of the Engineer ring ceremony that was held for graduating engineers. In the ceremony, we took an oath which pledges to uphold the standards and dignity of the engineering profession. In the process, we signed a certificate of obligation and were presented with a stainless steel ring to be worn on the pinky finger of our writing hand. 

A memorable moment was when a professor recalled the story (rumor) of how the first iron rings were made from the steel of a beam from the Quebec Bridge, which collapsed in 1907 due to poor planning and design. He advised us that if somewhere along the road, when our dreams fade and we happen to lose sight of our goals, he hoped that the engineer's ring will serve as a reminder of our oath. 

It was definitely a humbling experience. I reflect back on my 4 years at the University of Florida and can honestly say that I'm satisfied with the path that I've chosen: to become a computer software engineer. Of course there is the huge incentive of my major having the one of the highest employment growth and salary among the engineering profession, but there's also that respect and admiration I have for everything computer engineers have done. The technological progress that is accelerating as we speak is truly astounding. Computers have aided every profession whether directly or indirectly, serving as the backbone of our society. I imagine if all computers are to shutdown right this instant, the world would be in a total state of chaos. And this is exactly why I've chosen this career choice. I want to be a part of this technological phenomenon, this incredible synergy.