Solving Games in Java (Part I) - Practical Java Projects

Before we start working on our solvers we need a skeleton of our program to be able to handle user's input, convert that that input into game entities and prepare everything for the solver to work with

Our main entity we are going to work with is a board. We need to represent it in a convenient way so that it doesn't bring us any problems in the future.

We want our user to supply a board in a very simple way to make his life easier. And this input has to be converted to our board representation so we can work with it in all future episodes.

We are going to have a look at abstract code which will explain how our first solution is going to work using depth-first search. A very nice step by step example will make it easier to grasp the contents if you have problems understanding the abstract code.

In order to make decisions whether the given word is valid or not we need to check if it is contained in the dictionary. There are many different dictionaries out there. We have some constraints on the dictionary and therefore provide a way of getting a dictionary that requires almost no work to clean it up so that it fits for our purposes.

Every single solver will need the ability to read a dictionary and get the list of words from it. We are going to build an abstract class which will provide a method for our solvers to use to get the dictionary words easily.

Before solving the game we need to set everything up: read the dictionary file, setup all the variables which are going to be needed during the search, declare the method we are going to use as a core search method.

We are going to build a core of our depth-first solver which is going to generate all possible words which can be found on the given board.

We are going to execute our first solver to see how it performs. We are going to verify it using a real game.

Another solution is going to be presented to show you how we can approach the same problem from a different angle.

Once again we are going to build the infrastructure of our solver to set everything up that is needed for our new solver to function well.

The core of our second solver that is going to go over the whole dictionary and try finding each word on the board.

It is time to execute our second solver and compare the results with the first one.

We are going to point out the problems with the first solver and propose another solution that is going to be based on our first solver but will try to fix its bottlenecks.

For our third solver we are going to use a data structure named Trie. This episode contains all the information you need to understand how it works, how it is built, how it is queried for the information that we need.

We start building our Trie data structure. The overall functionality is described via methods we need.

We are going to fill in the gaps in our Trie data structure to make it work in a way that we require it to.

For the final time we are going to set everything up for our last solver. We need to prepare our Trie data structure before we start using it.

The core of our final solver that is going to be based on the first solver but will add extra pruning which will help us to avoid generation of many useless words (which are not valid)

It is time to compare our final solver with the others. We are going to run it against the real game and then try to find a limit at which it works very well.