Implementation

Central to this algorithm is the implementation of sets and cells. A region 6 maze is 16 by 16 cells, which gives a total of 256 cells. The most efficient method to implement a set is 8 bytes, and use one bit to represent one cell.

This requires the linearization of the two dimensional cells. Given that a cell is on row $r$ and column $c$, the easiest linearization is $16r+c$. This uniquely assigns a number for each cell in a maze.

From the linear bit number, we can compute which byte in a set to retrieve and which bit of it represents the cell. The byte number is simply $\lfloor{\frac{16r+c}{8}}\rfloor$. But this is easy to compute because it really is just 2*r+c/8 in any programming language. Note that the division can be implemented by right shifts.

The bit number is also easy to compute, it is simply c % 8 in C. Smart compilers automatically convert this to use bitwise and as in c & 7.

It is useful to define a structure in C to represent a set. This can be a definition like the following:

struct Set {
  char bytes[NUM_ROW * NUM_COL / 8];
};

Note that now you can pass a struct Set by value if you want to. Otherwise, it is impossible to pass an array by value in C.

Once a set is defined, you need to define ADT (abstrct data type) methods. The following are useful methods:

• count counts the number of elements in a set
• add adds an element to a set
• remove removes an element from a set
• find finds the first available element from a set

It is best to use the linearized number as parameter or returned value for these methods. The remaining task is to delinearize a linear number used to represent a cell. Assuming l is the linearized number, the row number is l/16, whereas the column number is l%16. Again, these operations can be replaced by right shifts and bitwise and.