One concept that people always struggle to get their head around is recursion. It really is rather straightforward and elegant but in execution it is always difficult to get right. Even if you include recursion in your code habitually, you usually have to think hard every time. In this section we are going to use recursion to solve two challenges involving generating roadmaps, and generating sudoku puzzles.
What is recursion
Google the word recursion and you get this.. i guess its the Google guys’ idea of a joke.
For our purposes, recursion is where a procedure calls itself. Why ? Well many reasons, for example navigating a tree structure when you don’t know how many branches there are or how deep it goes is a typical use. Another is in games programming, such as in route planning, chess move assessment, or sudoku generation – anything you have to try something out, then retrace and try something else is a typical candidate for recursion . VBA is capable of recursion, but gets clunky quickly. Recursion can generate a requirement for lots of extra memory as you trace down various paths and come back again, so releasing up that memory quickly is essential – something that VBA is not that good at. Nevertheless, for most uses, recursion is VBA is very acceptable and straightforward. If you are a ‘recursion newbie’, you may want to first read Getting started with recursion.
If you are going to write recursive procedures the error below will be your constant companion, so let’s get introduced now – it almost always means that you have not provided an escape route and you keep calling yourself forever and ever…
In this section I’ll introduce you to how to use recursion to economically resolve some problems that might otherwise need very convoluted solutions, and we will use this to create some procedures for two projects we will work on throughout this section on VBA. One is to generate a roadmapper tool to look at how to traverse tree structures, the other is to create a sudoku puzzle generator.
I’m going to be actually writing these as we go along. So there will be a steady build up code when i get some time to work on it. The finished products will be available for download. This means that you will need to replace each version if you are following along. Each version will be a working piece of code that does something a bit more than the previous one.
Coding style
Although it’s the recommended way in VBA, i do not follow the ‘Hungarian Style’ as I think its known. This is where you precede each variable with a 3 letter code to define its type – rngInput, strName, objWorkbook, clsEmployee for example. Sorry about that, but I just don’t like it. I find it hard to notice the difference between variables as I lose the will to live before i’ve finished reading the prefix as they all kind of blur into an undifferentiated mess.. I do usually use a single letter type prefix rInput, sName and prefix all private variables in a class with a p (pName). For objects I usually use the Uppercased letters – cShapeContainer would be sc, WorkBook would be wb and so on – but it wont be very strictly applied. Sorry if it bothers you, but that’s how it is. I’m a C programmer by nature so i find it hard to not be as brief as possible.
Challenge 1 – roadmap generation
For these series of pages on recursion, our first challenge is to write an application that will generate a roadmap from a set of excel data. We will use this example elsewhere, but for now we are going to focus on the use of recursion to make this possible. Consider the following data, and roadmap and think about how one would be generated from the other, given that we cannot know in advance the shape and depth of the tree structure represented by the roadmap.
Starting from this data
create this roadmap
The high level structure of our solution is going to be as follows
call getParameters() call getData() call generateTreeStructure() call createScale() call layoutShapes() call groupShapes()
We are going to use Microsoft shapes and group them together, so that whatever we generate can be just cut and pasted into any Office Application, for example Powerpoint. The main focus of this section on recursion is on creating and moving around the tree structure to organize our input data into a presentable hierarchy, Read on as we work out the tree structure we will need to be able to create generalized roadmaps like these.
Challenge 2 – sudoku puzzle generation
I’m assuming you are familiar with what a sudoku puzzle is. We are going to create an application that can generate sudoku puzzles. There are thousands of sudoku applications around, and all of them can solve sudoku puzzles, but most of them rely on a library of known puzzles, because generation time is unpredictable. We are going to write one that generates sudoku puzzles ‘on the fly’ . The most complex part of that is the use of recursion to try out various paths to see if the puzzle we are creating continues to be solvable , and if not, to backtrack and try something else. We are going to focus on that in this section
To generate a sudoku puzzle, you must first be able to solve one. You need to be able to have 2 modes of solving – one that is based on ‘brute force’ – meaning that you can solve it by trying different things till you find something that works, and another mode that is based on the known techniques of sudoku solving that you wish to implement, and that has a unique solution. The first is needed to generate a potential candidate puzzle (all you do is try to ‘brute force’ solve a blank puzzle, seeded with random or strategically placed starting numbers), and the second is needed to verify that the candidate is solvable using the implemented sudoku techniques so that a human can solve it, and come up with a puzzle for which there is only one solution.
The high level structure of our solution is going to be as follows
call getParameters() while not bSolvable ( generatePuzzle ()) wend call displayPuzzle()
and we will be generating sudokus using VBA
Read on as we figure out what structure and recursive procedures we need to make this all work