Featured

Maze Generator in Excel using VBA

The following video shows a maze being created in Excel using a depth-first search algorithm using backtracking:

How it Works

The program works by randomly selecting a cell from a predefined range on a worksheet. It then looks at all the neighbouring cells that haven’t been visited to see which cell it can move to next. It randomly picks one of these  cells and moves to it by removing the dividing border between the current cell and the new location it wants to move to. It keeps on repeating this process until the entire board range is filled. If it moves to a cell where there are no possible onward moves, it simply goes back to the previous cell, and looks for any unvisited cells from that location. It will keep on retracing it’s steps to find any neighbouring cells that haven’t been visited, before it resumes picking a direction randomly again.

Introducing the Stack

The current location of the cell is stored within a data structure known as a Stack. The stack holds the history of the programs current path. Since a stack is a LIFO (last in first out) data structure, the first cell on the stack is always the current location in the program. Hence, removing the object that is at the top of the stack will always leave the previous location as the top item. This is how the program moves recursively. By adding the current location and removing it when necessary from the Stack in order to go back and reevaluate its path. In VBA a stack can be implemented like so:

However, it is better to wrap the Stack up in its own class and create class methods that are typically associated with stacks. This is so that we have an abstract view of the stack to work with. The class methods we create include adding items to the stack (known as Push), removing the last item added (known as Pop), and retrieving the item that is at the top of the stack. The following code is a class called clsStack which is used in the solution above:

Making use of a Dictionary

In addition to monitoring the current cell, the program also needs to keep track of all visited cells. These can be stored in any data structure like an array or a collection. However, storing the items in a dictionary is particularly beneficial, because a dictionary has its on Exist method, which can be used to check if a cell has been visited or not. Storing items in a dictionary involves assigning a unique key to the value that is being added to the dictionary. The Exist method looks for the key within the items stored in the dictionary, so the solution makes use of this by storing the cell address as the key (since this will always be unique), and the cell object as the value. Like the stack the dictionary object is wrapped up in its own class. Below is the dictionary class called clsVisited:

Custom Range Object Wrapper

The Stack and Dictionary classes, are the main data structures used in the solution. However, I also created another data class called clsNextCell. This is because for every cell that the program considers moving to, I wanted to assign the location of that cell in relation to the current cell as a reference point. So the clsNextCell class is essentially a data wrapper for each range object in the maze but with an additional attribute called Direction. The code for this cell is found below:

And the Rest..

The remainder of the code consists of standard Excel formatting techniques which are used to animate the movement of the maze. I also introduced a very slight delay in the movement of the current cell to keep the animation smooth for the video. You can explore the formatting techniques in the solution from the link below. Hopefully, this post has given you some insight into simple maze creation, as well the possible uses of stacks and dictionaries in VBA code.

You can download the application from the video from here (however please take time to read the disclaimer  about content found on this site).

Share :Facebooktwittergoogle_plusredditpinterestmail
Featured

Solving the Chess Knight’s Tour using Excel VBA

The Knight’s tour is an ancient mathematical problem that dates back to the 9th Century AD. The problem consists of finding a path that allows the Knight chess piece to visit every single square on a chessboard once only.

Whilst there have been many different approaches to solving this problem, one of the earliest known methods was introduced in 1823 by H.C Von Warnsdorf. This post describes an implementation of his rule using Excel and VBA to solve the problem. A video showing the completed solution in action can be found below:

How this Works

To begin with, the application randomly picks a square from an 8×8 chessboard, and then moves the Knight (according to the rule) to a new square until all of the squares have been visited. The diagram below shows the legal moves that the Knight is allowed to make:

From the centre square it can visit any of the locations marked with an X, and can jump over visited squares to get to that location. To cover the whole board, the Knight needs to make 63 moves. The Knight’s path can be tracked by the sequence of numbers it leaves behind.

Implementing the Rule

Warnsdorf’s rule works by identifying all possible moves from a given square, and then selecting the square to move to that has the least amount of onward moves. Any visited squares are not included in the count of onward moves. If there is more than one square that matches the selection criteria, then the square chosen is picked at random from these matching contenders.

In the diagram, the Knight can move to any square with a number in it. The numbers represent the number of onward moves from that particular square. The next square to move to will be the one with the lowest number which in this case  happens to be 2. Since there are 2 squares with 2 onward moves, either of these squares can be chosen next.

About the Code

The Excel application itself consists of 3 main elements. The first element is the Knight Tour Class which handles most of the work:

The class consists of methods relating to move identification and  piece animation, as well as  properties which allow the board range and piece font to be specified. The code for the class is presented here in its entirety:

 
The second element is a main subroutine that runs the entire program using the methods and properties of the Knight tour class. It is fairly short because it does not have much work to do (the program’s complexity is handled by the class!). In a nutshell, all it does is create an instance of the Knight class, tells the instantiated object where the board is, picks a random square to start with, and then keeps moving the Knight to a valid square until no more moves can be found. The code is presented below:

 
The third element is the graphical display. The chessboard is represented using standard Excel cell formatting techniques.  However, the Knight chess piece itself is created using a third party TrueType font called Chess Alpha created by Eric Bentzen. The installation of this font occurs when the workbook is opened and it is uninstalled when the workbook is closed. The installation is handled by a separate class in the project. You can read more about the class in this post.

That covers the entire project in full. You can  download the solution in the video from here (however please take time to read the disclaimer about content found on this site).

Share :Facebooktwittergoogle_plusredditpinterestmail
Featured

Tetris Game in Excel

This is an Excel version of the popular game Tetris which I wrote using VBA. The objective of the game is to score as many points as possible, by creating completed rows of bricks from the falling bricks. A player is able to control each of the falling bricks using the keyboard arrow keys. The application comes complete with sound effects, and an external log that keeps hold of high scores.

You can download the application in the video from
here (however please take time to read the disclaimer about content found on this site).

Share :Facebooktwittergoogle_plusredditpinterestmail