Uno Backtracking Algorithmn

I was playing a game of Uno with my girlfriend and she ended up beating me. She had placed all of her cards and I had roughly 15 or so left in my hand. This is when she told me that if I could place all of my cards she would call it a tie. As I began to place the cards down, attempting to come up with a system, I realized that this is a good problem to solve using backtracking.

So I got to work the next morning building the environment for my Uno backtracking algorithm. First I decided to create 2 classes: Card and Deck, to organize my code. I went here to make sure that I was including the right number of cards.

Card class

I started with the Card class since the Deck class would be holding objects cards. I created a simple class with a constructor that holds 3 variables: Color, Number, and Special. Color and number are self explanatory as the majority of uno cards have a color and a number. Special was to be used for uno cards such as: Draw 2, Wild Card, Reverse, etc. Note some special cards have a color but none have a value. So the general makeup of my card class looked like this: I added some helper methods such as checking if two cards have matching Colors, Numbers, or if one is a wild card. These were all used in my method isCompatable() to find valid moves that my backtracking algo could take.

Deck Class

My deck class simply held a list of Card items. It has a method in its constructor called build which will add each neccessary card to the deck and shuffle. I added another funtion draw() which can pop a card off of the list of cards.

Program Design

My code begins with drawing a number of cards to the user, this number is at default 10 but can be changed with command line arguments. It then draws a topcard to the discard deck, which is simply a list of all discarded cards, and will eventually be the solution.

The program will then begin its recursive backtracking where it will loop through the cards attempting to play each card then recursively checking if that card leads to a solution. If all cards have been placed, a solution has been found.

Sample Output

Conclusion

This project was a good review on backtracking algorithms and in my opinion using a game like Uno made it more enjoyable over something like the typical n-queens algorithm. I found it interesting to use larger card sets and look at the way the program solves this problem. I've noticed it likes to use as many cards as possible for one color than hop between different colors by matching numbers, then using wild cards as a last resort to get somewhere else. My source code is available if anyone is interested at looking through the code or using it as starting point. I have also made a youtube video walking through the code and the general idea of backtracking algorithms if anyone is interested in learning this paradigm or needs a review.