The Mathematics of Hexakai

Post created: 1/22/2025

Author: Brandon Quinn

Introduction

Hexakai is built upon a fascinating mathematical foundation. In this post, I'm going to canvas some of the avenues of mathematical investigation I took when creating Hexakai, giving a reasonably concise overview while balancing specificity with accessibility. I've included some mathematical notations and functions, but overall, this is about concept, not calculation, so an inability to read this notation will not take much away from the conceptual explanations offered. Some of these concepts, such as constraints, are directly useful to the gameplay experience. Other concepts, such as templates, are useful to me as the developer of the Hexakai apps. I've decided to publish this mathematical overview for those who are interested in mathematics - either generally or as they pertain to games, those who deep dive into their hobbies, and above all, those who are fundamentally curious.

Types of Boards

This post will refer to two types of boards:

Complete Board: a board that contains all values and no empty cells.
Puzzle Board: a board that has at least one empty cell and is therefore unsolved.

Most of the analysis here will refer to complete boards.

Fundamental Properties of Hexakai

Hexakai isn't bound to a single board size. While the canonical board size is 10, boards can be constructed in sizes 3, 5, 7, and 8-16. Mathematically speaking, we can also construct a trivial board of size 1, and my supposition is that we can construct a board of any size greater than 16, though I've not yet rigorously proved this is the case. Games of size 2, 4, and 6 are impossible to construct. This is a fascinating limitation that we'll dive into later in this post.

When a board's size is greater than 10, we'll typically use letters A, B, C, and so-on to represent values greater than 9, corresponding to 10, 11, 12, etc.

For the rest of this post, we'll use the variable n to refer to the size of a given game of Hexakai. When we discuss games of size n, the discussion will pertain to properties that hold for every possible board of Hexakai using n as a refernece point when the math comes into play.

These basic properties hold for all Hexakai boards:

The board has a total of $n^2$ cells.
There are $4n-4$ cells on the edges of the board.
There are $(n-2)^2$ cells on the interior of the board.
There are $4$ corner cells.
The sum of values in each diagonal, and the center row, is $\frac{(n-1)(n-2)}{2}$.

Impossible Boards

It is impossible to construct any valid complete Hexakai boards of sizes 2, 4, or 6.

Size 2

This is a board of size 2, where each cell can have a value of 0 or 1. Once we set the top cell to a value of 0 or 1, we must set the leftmost cell to the other value. With those values set, what do we assign to the cell marked with an X?

The X cell is constrained by two other cells with two distinct values. We’ll call this the contradictory cell since any value we assign contradicts the rules of the game.

Regardless of which cells you assign first, or which values you assign to them, this situation will always arise with one of the cells on this board. Therefore, it is impossible to construct Hexakai boards of size 2.

Size 4

This is a board of size 4, where the value of each cell ranges from 0 to 3. First, we’ll assign 0, 1, and 2 to the top three cells. On the top-left diagonal, the next cell, marked "Y," can only have a value of 2 or 3, and on the top-right, the next cell, marked "Y," can only have a value of 1 or 3. Regardless of which values are assigned, the cell in the center of the third row will be surrounded by cells with values 1, 2, and 3, leaving 0 as its only possible assignment.

The problem is, which cell in the center row will be assigned a value of 0? It can’t be the leftmost or rightmost cell because they both include the topmost cell in their diagonals which already has a value of 0. It also can’t be the two middle cells, because they share a border with the cell marked 0 above, and that cell above can only have a value of 0. Therefore, the middle row cannot be assigned 0, and thus, it is impossible to construct the board.

Note that we started with values 0, 1, and 2 in this example, but the same problem will arise regardless of what values are set here. If we were to set the top cell to 1, then it would be impossible to assign 1 to any cell in the middle row, and the same holds for the other values. From a human perspective, we can tell there is an issue as soon as we hit the middle row, but if a computer were to attempt to create the board, it wouldn’t fail until it tried to assign the last cell of the middle row, as the first three cells can still receive values 1-3. This cell, which is the 10th cell of the board, is the contradictory cell for boards of size 4.

Size 6

This is a board of size 6, where the value of each cell ranges from 0 to 5. The proof of impossibility for boards of size 6 is significantly more complex than the previous proofs discussed. Instead of deriving it by hand, I modified my board generation algorithm to find exactly where the problem using the same top-down approach used for the analysis of the board of size 4. It found that the 27th cell, marked "X," is the contradictory cell.

If we look backward from the contradictory cell, we see that it is being constrained by 8 cells excluding cells that are below it or to its right: 4 from its diagonal up right, 3 from its diagonal up left, and 1 to its left. For this cell to be contradictory, every value 0-5 must already appear within those 8 cells. The diagonal up right contains 4 out of 6 of those values, so the remaining diagonal and cell to the left of the constraint cell contain the remaining two values.

Beyond Size 6

I haven't yet dedicated time to determining what higher-level mathematical constructs describe the root causes for the impossibility of the board sizes we've reviewed. From my experience writing the algorithm that generates Hexakai boards, I've observed that generating boards of even size is computationally more difficult than boards of odd sizes. Suprisingly, I can generate boards of size 11 faster than size 10, a phenomenon that usually doesn't take place due to the geometric growth of this type of algorithm. As we'll discuss later, a certain additional constraint that some odd sized boards can satisfy cannot be satisfied by any even sized boards.

I believe that there are no other "impossible" sizes beyond 6. I haven't mathematically proven this, but my supposition is supported by the following facts. In each impossible size beyond 2, the contradictory cell is closer to the bottom than in the previous impossible size. Furthermore, in general, there are more boards of size n than there are of boards $n-1$. Despite the observed higher level of difficulty in generating even sized boards, the number of possible boards still increases geometrically as n increases, implying that the additional space and values available allow us to satisfy the relationships imposed by the constraints in increasingly more ways. Therefore, I believe that beyond boards of size 6, there will always be multiple ways to satisfy the constraints and create valid complete boards.

Triangle Numbers

The concept of triangle numbers wasn't created specifically for Hexakai, but it is an integral component of its mathematics, so I'll dedicate this section to introducing it. A triangle number is a positive whole number that is derived from adding all the numbers $1 + 2 + \ldots + x$. For example, the third triangle number is $1 + 2 + 3 = 6$ and the xth triangle number is $1 + 2 + \ldots + x$. Conceptually speaking, a triangle number counts the number of building blocks in an equilateral triangle, a triangle whose side lengths are all the same, as exemplified in the diagram below.

This diagram visualizes the first five triangle numbers: 1, 3, 6, 10, and 15. The first triangle number is a trivial case, one dot. The second triangle number has two dots on the bottom, two dots on the left slope, and two dots on the right slope. The third triangle has three in each, the fourth has four, etc. Additionally, for each triangle, the top row has one dot, the next has two, then three, etc. The formula to derive the xth triangle number is $T(x) = \frac{x(x-1)}{2}$. We've actually just seen a slightly modified version of this in the section above when we discussed the sum of values in each diagonal.

A Hexakai board can be constructed by stacking two triangular arrangements of hexagons, a triangle of size $T(n)$ on the top, and an upside-down triangle of size $T(n-1)$ on the bottom (where n is the size of the Hexakai board). Triangle numbers appear frequently in calculations related to Hexakai regarding board sizes, value distributions, and even board generation algorithms.

Board Templates

A board template a Hexakai board whose cells are comprised of variables instead of values. For simplicity, variables will be denoted as lowercase letters. Templates play a crucial role in analyzing the mathematics of the game as well as implementing algorithms to generate games.

In the display below, the first board is a board template of a Hexakai game of size five (i.e., n=5) and the second board is a complete board whose variables have been substituted for values - a becomes 4, b becomes 1, etc. This process works both ways: given a board template, we can assign a value to each variable and derive a complete board, and given a complete board, we can replace values with variables and derive a template. We'll discuss that process in more detail shortly.

In a board template, the name of any given cell is the variable that occupies it. For example, the name of the topmost cell in the board template above is "a," and the names of the two cells directly under are "b" and "c." We can derive a complete board from a template by replacing all cell names with cell values. The right board above can be derived by setting the value all cells named a to 4, bto 1, and so on. The replacement must be consistent: every cell with a given name must receive the same value, and no two names can receive the same value.

Board templates can be used to generate multiple boards by replacing the names with different values. The simplest replacement is to set a to 1, b to 2, c to 3, and so on, but there are numerous ways to make replacements. In general, we can generate $n!$ boards of size n by replacing each name with values $0, 1, \ldots, (n-1)$ such that no two names correspond to the same value. On a board of size 10, for example, a single board template can generate $10! = 3,628,800$ boards.

Template Expressions

We don't need to draw out an entire Hexakai board to denote a board template. We can also express a template via more concise template expression, a single string of letters that chains the cell names together. The template expression for the board template above is abcdebcadeebcaddebcadecab. To derive a template expression from a template, take the name of the top cell, make that the first character in the expression, then proceed to the first cell in the next row, append, move to the right and append each character until you're at the end of the row, move to the next row, and so on. At the end of the process, you'll have a template expression of size $n^2$, one character per cell on the board. Both types of expressions - board templates and template expressions - represent the same underlying structure of the board.

Technically, multiple templates, whether they are board templates or template expressions, can describe the same underlying board structure. For example, the template string for the diagram above, abcdebcadeebcaddebcadecab, and the template string edcbadcebaadcebbadcebaced, both refer to the same underlying structure and therefore can be used to generate the exact same boards. All template expressions that map back to the same structure form a group. In other words, a group of expressions consists of all expressions which refer to the same underlying structure. To avoid the hassle of dealing with template expressions that might correspond to the same structures, we can introduce a canonicalization process that will ensure we're only dealing with one unique template expression per board structure.

Canonical Template Expressions

A canonical template expression is a template expression whose variables are denoted in a form of alphabetical order. To define this more precisely, we need to discuss some of the properties of template structures. Each cell name will appear exactly n times in the template expression. Naturally, there must be a position in the template string where it first appears. The first three names always appear in the first, second, and third positions. Subsequent variables are not bound to appear in the fourth, fifth, or higher positions, but they typically first occur relatively close to the beginning of the string. For a given name X, we will denote X's first occurrence in the template expression e as $f(e, X)$. As a utillity, we'll define the ith letter of the alphabet at $alph[i]$, so we can refer to letters by index in the equation below (i.e., $alph[6]$ is the sixth letter of the alphabet, f).

A template expression e is in canonical form (i.e., it's a canonical template expression) if, for each ith name X (in order of occurrence), $f(e, X) = alph[i]$. That is, the first time each ith variable appears, its name must be the ith letter.

The following procedure derives the canonical template expression from any given expression:

Create an empty mapping between names you find in the template expression and the order in which you found them.
For each index in the template expression:
1. If your mapping doesn't contain the name at that index (i.e., you haven't encountered it yet), add it to the mapping, setting its value as the letter that comes directly after the last unique letter you've found.
2. In the original template, replace the name at this index with the name that exists in your mapping.

When this procedure is complete, the resulting expression will be a canonical template expression. We'll call this procedure the template canonicalization procedure.

Template Indexing

Template indexing is the process of accessing cell names at specific indices within a template expression. This section outlines how to map back and forth between template expression indices and their corresponding rows and columns on the board. I’ve included this for completeness, as the later sections in this chapter use row and column values instead of index values for calculations. Note that we'll be referring to columns instead of diagonals in many cases for simplicity. A column refers to the index position within a row, so in this sense, columns correspond to diagonals running down-left. Also note, I'll be using the variable i to refer to index, not to the imaginary number.

Mapping Rows and Columns to Indices

In a template expression, each ith character can be mapped to a corresponding row r and column c, and vice verse. We'll start with the latter - the function below, called index, takes a row, column, and gamesize as parameters and calculates the index that cell will belong to in a template expression.

$$ \text{index}(r, c, n) = \left\{ \begin{array}{l@{\;}l} \displaystyle \frac{r(r - 1)}{2} + c & \text{if } r \leq n, \\[12pt] \displaystyle n^2 - \frac{(2n - r + 1)(2n - r)}{2} + c & \text{if } r > n. \end{array} \right. $$

This function is split into two cases: the first case covers the middle row and up, and the second case covers all rows below the middle row. In the first case, it's a matter of calculating how many rows appear above the current row of the index, plus the column position in the current row. The second case is more complex. The term $n^2$ calculates the total size of the board. The term $\frac{(2n - r + 1)(2n - r)}{2}$ calculates the number of cells that encompass row r and all rows below it. These together give us the number of cells above the current row. The last term $c$ adds the column index to the previous sum, yielding the final index.

Mapping Indices to Rows

We can also move in the opposite direction - mapping indices to their corresponding rows and columns, though these computations are more complex. I've separated this into two functions, one that maps the index to the row in which it belongs, and the other to the column in which it belongs.

$$ \text{row}(i, n) = \begin{cases} \left\lceil \frac{\sqrt{8i + 1}}{2} - \frac{1}{2} \right\rceil & \text{if } i \leq \frac{n(n+1)}{2}, \\ 2n - \left\lceil \frac{\sqrt{8(n^2 - i + 1) + 1}}{2} - \frac{1}{2} \right\rceil & \text{if } i > \frac{n(n+1)}{2}. \end{cases} $$

This function takes a similar approach to the previous by handling the two halves of the board separately. The last index of the top half of the board is $\frac{n(n+1)}{2}$ which is the nth triangle number and corresponds to the number of cells on the top half of the board, including the middle row. In the first case, the term $\frac{\sqrt{8i + 1}}{2} - \frac{1}{2}$ is the inverse of the triangle number formula and is based on the quadratic formula. This essentially maps the nth triangle number back to n. The $\lceil \rceil$ braces indicate that we should round up the answer to the next highest whole number. This is necessary because, if the previous term doesn't receive a triangle number, but a number that exists between two triangle numbers (corresponding to a cell in the beginning or middle of a row), we need to round up to correctly specify its column as the next available one. In the second case, the term $n^2 - i + 1$ does two things: it flips the bottom of the board upside down and maps the index to a position on that flipped board. Indices closer to the middle row will map to higher values, and indices closer to the bottom of the board will map to lower values. The surrounding term $\left\lceil \frac{\sqrt{8(n^2 - i + 1) + 1}}{2} - \frac{1}{2} \right\rceil$ operates the same as the quadratic formula in the previous case, essentially swapping i with the previous term, and we subtract this from $2n$ to map the resulting row back to the original Hexakai board.

Mapping Indices to Columns

The column function works with the same fundamental concepts but is notably more complex. To help simplify the expression, we'll reuse the row function above.

$$ \text{col}(i, n) = \begin{cases} i - \frac{(\text{row}(i, n) - 1) \cdot \text{row}(i, n)}{2} & \text{if } i \leq \frac{n(n+1)}{2}, \\[10pt] \text{row}(n^2 - i + 1, n) - \left(n^2 - i + 1 - \frac{(\text{row}(n^2 - i + 1, n) - 1) \cdot \text{row}(n^2 - i + 1, n)}{2}\right) + 2 & \text{if } i > \frac{n(n+1)}{2}. \end{cases} $$

This is conceptually very similar to the previous functions. We split it into two cases again, one for the bottom portion of the board and one for the bottom. In the first case, the term $\frac{(\text{row}(i, n) - 1) \cdot \text{row}(i, n)}{2}$ corresponds to the number of cells in the rows above the row in which the index resides. We subtract this from i, and what remains is the column. In the second case, we flip the board upside down again and map the index to that flipped board, almost exactly the same as what we did in the previous function. The term $n^2 - i + 1$ corresponds to the index of the cell on that flipped board (just like the last function). The term $row(n^2 - i + 1)$ gets the corresponding row on that flipped board, but we're using it here to indicate how many cells belong to that particular row, since the row number and count of cells in that row are equivalent to the top half of a board (or a flipped bottom half with flipped values). The term $\frac{(\text{row}(n^2 - i + 1, n) - 1) \cdot \text{row}(n^2 - i + 1, n)}{2}$ counts the number of cells above the row as derived from the previous term. This is subtracted from $n^2 - i + 1$ to get the column position in that flipped board, and that result is subtracted from $row(n^2 - i + 1)$ to map it back to the column on the original board. However, we need a +2 to map it back properly, +1 from the subtraction of the larger inner term from the first row term, and another +1 from the subtraction of the inner row triangle number calculation from the $n^2 - i + 1$ figure.

Template Transformations

A template transformation is a procedure for deriving a new template from an existing by applying a set of predefined modifications. All hexakai boards can be transformed by reflecting them horizontally and vertically, and some can also be transformed by reflecting them diagonally, or by rotating them. Each of these transformations are defined below.

Horizontal Reflection

For each cell at row r and column c, use the colH function below to calculate $y=colH(r,c,n)$ and swap cell names at r,c with r,y, ignoring cells that have already been swapped. Once complete, apply the template expression canonicalization procedure to derive its canonical form.

$$ \text{colH}(r, c, n) = \begin{cases} r - c + 1 & \text{if } r \leq n, \\ 2n - r - c + 1 & \text{if } r > n. \end{cases} $$

This transformation is valid because the contents of each row remain invariant. Even though the diagonals are reversed in direction, the contents of each diagonal also remain invariant. Therefore, each row and diagonal will continue to contain no duplicates, and each diagonal, plus the center row, will still have exactly one of each value.

Vertical Reflection

For each cell at r,c, use the rowV function below to calculate $x=rowV(r,c,n)$ and swap cell names at r,c with x,c, ignoring cells that have already been swapped. Once complete, apply the template expression canonicalization procedure to derive its canonical form.

$$ \text{rowV}(r, c, n) = 2n - r $$

180-Degree Rotation

We can yield a third transformation, a 180-degree rotation, by applying both rotations, one after another, in either order.

By applying the two transformations separately, then together, we can yield three more valid templates for a total of four. These four templates can be used to create a total of $4\cdot10! = 14,515,200$ separate boards.

Diagonal Reflection

Unlike the other transformations, diagonal reflection can only be applied to a subset of templates. If a template conforms to the additional constraint that each vertical columns - cells that are positioned above and below each other in the same horizontal position and are not touching - also has no repeated values, it can be subject to the diagonal reflection transformation. Otherwise, it cannot, because applying the transformation would violate the game's rules that no diagonals or rows have repeated values. This board visualizes the vertical columns - each cell shares the same value as other cells in its vertical column. Cells marked with 4 and 5 are the only cells in their own vertical columns.

The procedure is, for each cell at r,c, calculate $x=rowD(r,c,n)$ and $y=colD$ and swap names at r,n with x,y, ignoring cells that have already been swapped, then canonicalize the template.

$$ \text{rowD}(r, c, n) = 2(c - 1) + 1 + |n - r| $$

$$ \text{colD}(r, c, n) = \begin{cases} c & \text{if } r \leq n \text{ and } c \leq \lfloor r / 2 \rfloor \\ r - c + 1 & \text{if } r \leq n \text{ and } c > \lfloor r / 2 \rfloor \\ c + r - n & \text{if } r > n \text{ and } c \leq \lfloor (2n - r) / 2 \rfloor \\ 2n - r - c + 1 & \text{if } r > n \text{ and } c > \lfloor (2n - r) / 2 \rfloor \end{cases} $$

This is valid, assuming the additional constraint previously discussed is satisfied, for the following reasons. Every diagonal in the down-right direction and the down-left direction remain intact, but their positions within the diagonal are mirrored. As a result, every vertical column in the old template becomes a row in the new template, and vice versa.

If a diagonal reflection can be applied to a template, then 90-degree rotations can also be applied by combining diagonal reflection with vertical and/or horizontal reflection. These can also be used to derive diagonal reflections along other axes within the board, yielding a total of eight templates .

There are no templates in even-sized games of Hexakai that adhere to the additional column-uniqueness constraint, and therefore, no even-sized board template can be diagonally reflected or rotated by 90-degrees. I haven't yet studied this phenomenon specifically, but I suspect it has some relation to my observation that my algorithm for generating Hexakai boards has much more trouble on even sized boards than it does on odd sized boards.

Cell Constraints and Their Relationships

Every cell constrains, and is constrained by all cells that lie within its row and two intersecting diagonals. This means that, for any given cell c, if c is assigned a value v, no other cell that c constrains can also be assigned v. Similarly, if any cell that constrains c has a value v, c itself cannot receive that value.

For a game of size n, each cell is constrained by the $2 \cdot (n - 1)$ cells in its two diagonals, and by the other cells in its row, which varies from $0$ to $n - 1$ depending upon the size of its row. The topmost cell and bottommost cell don't have any row constraints, so they only constrain $2 \cdot (n - 1)$ cells. Cells in each subsequent row of size r constrain an additional $r - 1$ cells. The middle row of any board is larger than all other rows with its n cells, so each cell in that row constrains $3 \cdot (n - 1)$ cells. The closer a cell is to the middle row, the more cells it constrains, and the farther away, the fewer.

All cells constrain the same number of cells they are constrained by. If a cell x constrains cell y, then cell y also constrains cell x. For any given cell at row r and column c, the number of cells it constrains can be calculated by the function below. Note that the function doesn't include a parameter for the column because the column position doesn't affect how many cells any given cell constrains.

$$ \text{constrains}(r, n) = \begin{cases} 2(n - 1) + (r - 1) & \text{if } r \leq n, \\ 2(n - 1) + 2n - (r - 1) & \text{otherwise.} \end{cases} $$

This concept can be used directly when solving boards of larger sizes and higher difficulties. If you need to apply a tentative assignment strategy, many of which are discussed on my post on Hexakai strategies, finding the cells that constrains the higher number of other cells and focusing your tentative assignments on those will almost certainly significantly reduce the amount of time you spend on the wrong tentative assignment.

Information Clustering and Distribution

This section won't involve a formulaic analysis, but it is worth discussing the general ideas behind information clustering and distribution pertaining to puzzle boards. In this context, information refers to non-empty cells, information clustering refers to the degree at which non-empty cells are clustered, and information distribution refers to the degree at which non-empty cells are distributed throughout the entire board. Consider the two puzzle boards below:

The first board was generated using the Standard generator pattern, available under "Advanced Options" on the main app. The second board was generated using the Top Heavy generator pattern. The first board has a much higher degree of information distribution, whereas the second board has a much higher degree of information clustering at the top and empty-cell clustering, or missing-information clustering at the bottom. The second board is both harder to generate and harder to solve because of its lack of information distribution.

Imagine playing through the second puzzle yourself. A natural strategy would be to solve the topmost cell, which must have a value of , then proceed with making assignments to the leftmost and rightmost cells, then work toward the middle. However, the ambiguity suddenly and significantly increases as you apply this strategy to the point where you'll almost immediately need to use advanced strategies, including advanced forms of tentative assignment. This is essentially because all of the information provided by the original, hard-coded cells is clustered within the portion of the board that's already solved, thereby reducing their constraining power on the empty cells.

We can measure the level of complexity, uncertainty, and entropy using various approaches. My app uses a measure of uncertainty, which can also stand as a measure of complexity or as an estimation of entropy, to generate boards according to the difficulty level the user has selected. There are numerous ways we can approach such a measurement. A simple starting point would be to count the number of possible values each empty cell can be assigned at face-value (without applying strategies to dive deeper into the board), add them together, and divide them by the size of the board, something like the equation below, where i is the index of the cell and num_values counts the number of values that can be potentially assigned to it.

$$ \text{uncertainty}(i) = \frac{1}{n^2} \sum_{i=1}^{n^2} \text{num_values}(i) $$

In this board, we have a total of 25 cells, 14 of which are empty. In the first empty cell, we can potentially assign 3 values: , , or . The next cell has only one potential value, , so the running sum so far is 4. The following empty cell can have two values, bringing the running sum up to 6. The total sum over the entire board is 26. Then, by dividing against the size of the board, we get the final result of $\frac{26}{25} = 1.04$. This gives us a potentially useful measure, but what exactly does 1.04 mean? What are the lowest and highest values we can get from this measure? Do those make sense, and how can we improve this?

First, this measure will be more useful if we can confine it to a range between 0 and 1, where 0 indicates the simplest possible board, a complete board, and 1 represents a totally ambiguous board, possibly a board with no empty cells. We can normalize the equation above to that range by dividing the entire function by n:

$$ \text{uncertainty}(i) = \frac{1}{n^3} \sum_{i=1}^{n^2} \text{num_values}(i) $$

This is more useful, as it gives us a normalized range of output, and the value tends to increase as the number of empty cells, and even the percieved difficulty of the board, increase. I use a more sophisticated version of this function that considers cell constraints and other board-specific properties in my board generation algorithm to help determine the level of uncertainty of the generated boards to ensure they match the requested difficulty of the game to be generated.

Calculating the Number of Boards

Complete Boards

We will start by defining an upper bounds for the total number of complete boards for a game of size n. Each game has $n^2$ cells, and each cell has a range of $n$ values which we can assign it, so our upper bound is $n^{n^2}$. This figure is significantly higher than the actual number and represents the number of total boards that can be derived by assigning all permutations of all values on the board, ignoring Hexakai's usual constraints.

To improve, let's consider the number of boards that have each of n possible values exactly n times. We can calculate this by determining the number of ways we can select n individual cells from a board with $n^2$ cells, denoted as ${n^2\choose n}$, then multiply this by the number of ways we can select n more cells from the remaining $n^2 - n$ cells, and repeat until all cells are selected. Finally, multiply the entire thing by $n!$, which represents the number of ways we can assign each value to each cell group, similar to the process of creating complete boards from template expressions. Essentially, the product is attempting to estimate the number of templates, then the $n!$ gives us the number of boards we can derive from those templates. The total function is:

$$ \text{count}(n) = n! \cdot \left( \prod_{k=0}^{n-1} \binom{n^2 - k \cdot n}{n} \right) $$

This provides a significant increase in precision by substantially lowering the upper bound. For example, when $n=10$, the refined upper bound is roughly 8% of the previous upper bound. However, this bound is still much higher than the true value. When we select n cells from the remaining $n^2 - k \cdot n$ during each iteration (as well as from the first $n^2$ cells), we're not filtering for selections that have more than one value on the same row or diagonal. In other words, we're not considering the constraints of each cell in this calculation. To remedy this, I'll include a term that lightly considers constraints using the lower bount of $2 \cdot (n - 1)$, which is the number of cells the top and bottom cells each constrain. I'm picking those to ensure that we use the lower bound of constrain to ensure we don't over aggresively filter out possible selections. I'm going to subtract cells in each product iteration to ensure we don't filter out cells that were already selected: $2 \cdot (n - 1) - k \cdot n$, and finally, I'll use a $max(0, ...)$ to ensure that, once we reach a few iterations, we're not filtering anymore, favoring inclusion over exclusion. The full function is:

$$ \text{count}(n) = n! \cdot \prod_{k=0}^{n-1} \binom{n^2 - k \cdot n - \max(0, 2(n-1) - k \cdot n)}{n} $$

This gives us another substantial tightening of the upper bounds, but it is still very high. For smaller values of n, the estimates are ridiculously large compared to the actual values: $600$ vs $6$ for $n=3$ and $3,477,264,518,407,680$ vs 360 for $n=5$. I haven't calculated the true values for $n>5$, but I suspect this estimation function actually becomes more accurate as n becomes larger, mainly because the number of possible templates grows astronomically for each increase in n.

This function estimates the number of complete boards for each game size to be:

n	Count
3	600.00
5	3.48 × 10¹⁵
7	1.70 × 10³⁹
8	3.36 × 10⁵⁵
9	8.87 × 10⁷⁴
10	3.95 × 10⁹⁷
11	3.66 × 10¹²³
12	8.49 × 10¹⁵²
13	5.87 × 10¹⁸⁵
14	1.42 × 10²²²
15	1.39 × 10²⁶²
16	6.28 × 10³⁰⁵

If I were to attempt to refine this further, I would need to design an algorithm that searches through possible valid groupings, finds and filters non-visited constraining cells, and calculates the exact number of cells to filter at each iteration of the product, or more likely, transform this entirely into a graph-based search, something far too complex to represent as a single, simple mathematical function.

Puzzle Boards

We can think of puzzle boards as versions of complete boards with some or many cells removed, so long as the puzzle has exactly one solution - you shouldn't be able to fill in cells in more than one way that leads to a valid board, and it must be possible to find a solution. There are exponentially more puzzle boards than complete boards. I've not mathematically calculated the number of puzzle boards that can exist, but my algorithm for generating Hexakai boards can only remove up to roughly 80% of the cells on a board while maintaining the constraints above, so I suspect the theoretical limit lies somewhat near this value and will use it in our analysis here.

Consider a process that starts with a complete board and systematically removes cell values. For any given board, the number of cells we can remove, which we'll refer to as q, can range from 1 to $0.80 \cdot n^2$. For each value of q, there are at most ${n^2\choose q}$ ways of selecting q cells from a complete board to make it a puzzle board. This is an upper bound estimate, since some selections will result in invalid puzzle boards, a number that will grow as q becomes larger.

For a single complete board, the upper bound estimate for the number of puzzle boards it can yield is given in the function below. To determine the upper bound of the number of boards that can be generated from a template, multiply the result of the function by $n!$.

$$ \text{puzzles}(n) = \sum_{q=1}^{0.80n^2} \binom{n^2}{q} $$

To determine the upper bound for the total number of puzzle boards for each game size n, multiply the two functions together:

$$ \text{nPuzzles}(n) = \text{count}(n) \cdot \text{puzzles}(n) = \left( n! \cdot \prod_{k=0}^{n-1} \binom{n^2 - k \cdot n - \max(0, 2(n-1) - k \cdot n)}{n} \right) \cdot \left( \sum_{q=1}^{0.80n^2} \binom{n^2}{q} \right) $$

This function estimates the number of puzzle boards for each game size to be the values shown in the table below. These values are certainly large overestimations, as they're composed of two generous upper bound estimations whose errors multipy together, especially for smaller values of n:

n	Count
3	3.01 × 10⁵
5	1.17 × 10²³
7	9.56 × 10⁵³
8	6.19 × 10⁷⁴
9	2.15 × 10⁹⁹
10	5.01 × 10¹²⁷
11	9.72 × 10¹⁵⁹
12	1.89 × 10¹⁹⁶
13	4.39 × 10²³⁶
14	1.43 × 10²⁸¹
15	7.47 × 10³²⁹
16	7.27 × 10³⁸²

Algorithmic Complexity

The process of generating valid Hexakai boards, both complete and puzzle, has significantly higher complexity than the mathematical functions we've discussed so far, especially when considerations of space and time efficiency are raised. When software engineers and computer scientists analyze problems that algorithms can solve, such as the problem of generating a valid Hexakai board, we measure the algorithm's complexity (essentially a measure of efficiency) based on how much space it needs and how many computational steps it requires.

There are two ways we can measure these. We can execute an algorithm repeatedly with different inputs and measure how much space they consume in terms of bytes and how much time they consume in terms of some unit of time, such as milliseconds, or we can analyze the algorithm from a theoretical perspective and determine how much space and time they consume with respect to the input size based on the nature of the algorithm itself. The former is important when creating software that is intended to be used by customers to ensure that actual performance falls within an acceptable threshold. The latter is important when engineers and scientists want to assess the core nature of the problem that they’re trying to solve, learn how large the problem becomes when its inputs grow, and if their problem is closely related to any other problems. For example, how closely is generating a board of Hexakai related to the biological process of protein folding, or finding the best move to make in a game of chess, or to generating a Sudoku board? In this section, we’ll focus our analysis on the theoretical aspect.

The input size for the algorithm that generates Hexakai boards is n, the size of the board to be generated. Our analysis of the space and time consumed by the process of generating a Hexakai board will be written in terms of n. We don’t need to find the exact function or formula that describes exactly how much space and time would be consumed, we’re only interested in a "big-picture" approximation, or more precisely, an asymptotic estimate.

We could find this approximation by diving deep into my board generation algorithm, analyzing each step with excruciating detail and assessing how they all fit together. That would be highly tedious, time consuming, and error prone. Instead, we’ll take the equally valid approach of converting this problem, the problem of generating a Hexakai board, to an existing problem whose complexity has already been determined. This is a process called problem reduction.

This problem is reducible to a problem called graph coloring. Graph coloring is the process of assigning colors to a mathematical node-based graph in a way that no two nodes within the graph which share an edge have the same color. This doesn't refer to graphs like bar charts or x,y plots; but a mathematical object with nodes and edges that connect those nodes. An example is shown below:

Consider this graph, which has nodes a, b, c, d and edges between a,b, a,c, b,c, and b,d. How many different colors would we need to give each node a color without assining any two nodes connected by an edge the same color?

We can assign 3. Start by assigning the first color to node a. Then, since b is connected to a, it can't be assigned the first color, so assign it the second color. Then, since c is connected to both a and b, it can't be assigned the first or second color, so assign it the third color. Finally, since d is not connected to a or b, we can assign it the first or third color, precluding the need for a fourth color.

That process is vaguely similar to the process of solving a board of Hexakai. If we were assigning values instead of colors, it would be even more similar. We can further bridge these two problems together. We'll start by converting an empty Hexakai board to a graph:

This graph represents the cells in a Hexakai game of size 3. Notice that there are the same number of nodes in this graph as there are in the corresponding Hexakai game. Each node has a direct relationship with each cell in the game and, in this graph, is labeled as (row,col), indicating which cell it corresponds to.

The edges represent constraint relationships. In a game of size 3, the cell at the top, (1,1), is constrained by the cells in both of its diagonals. In this graph, this is represented by the fact that the (1,1) node is connected to four other nodes with edges. Every other node is similarly connected to every node whose cell would be constrained by it in terms of rows and diagonals. The question here is, can we make assignments to all nodes on the graph from a selection of 3 colors, and if so, what arrangement(s) can we make?

Yes, we can. Let’s say that we’ve run an existing graph coloring algorithm to determine how we can assign colors that match our constraints that no two nodes which share an edge also share the same color. The output tells us to assign colors in this manner:

(1,1): 1^st color
(2,1): 2^nd color
(2,2): 3^rd color
(3,1): 3^rd color
(3,2): 1^st color
(3,3): 2^nd color
(4,1): 2^nd color
(4,2): 3^rd color
(5,1): 1^st color

It doesn't matter which actual colors we select, so long as we cleary state which colors are the 1st, 2nd, and 3rd and stick to that assignment throughout.

The process of coloring that graph yielded something that resembles a valid Hexakai board assignment. Each nth color corresponds to a value of n for each given cell. We only need to make the minor adjustment of subtracting 1 from each cell value to ensure they range from 0-2 as per the rules of the game. Once we do that, we’ll have our board.

This process holds for any Hexakai game of size n. In fact, for my app, I could have chosen to re-use an existing graph coloring algorithm to generate Hexakai boards, with only a small amount of modification to convert the colored graphs to valid boards, such as subtracting 1 from each value and randomizing the color selections, instead of creating my own from scratch. In practical terms, this would be inefficient compared to my own custom-tailored algorithm, but in theoretical terms, it would be perfectly sound to do so.

Since we’ve reduced the problem of generating Hexakai boards to the problem of graph coloring, we know that their algorithmic complexities are equal, asymptotically equal to be precise. The problem of graph coloring has been studied extensively - the question of whether we can assign q colors to r verticies is known to have a time complexity of $q^r$. The variable q, which represents the number of colors we have to choose from, corresponds to n, the size of a given game of Hexakai, and the variable r, the number of nodes in the graph, corresponds to the number of cells on the board, $n^2$. This yields the monstrous super-exponential time complexity of $n^{n^2}$, which actually matches the original upper bound estimate of $n^{n^2}$ number of boards for a given size n.

Before continuing, note that while this estimate of $n^{n^2}$ would be prohibitively high on its own, there are numerous strategies that we can, and I do, employ to significantly reduce that complexity in a practical sense, even if the theoretic upper bound remains intact. Strategies like search space elimination, search heuristics, and precomputation all serve to make board generation possible despite this high upper bound, even as n approaches larger values like 16.

Graph coloring belongs to an interesting class of algorithms called NP-complete. Since we’ve reduced the problem of generating Hexakai boards to the problem of coloring graphs, we’ve proven that the problem of generating Hexakai boards is also NP-complete. Typically, non-trivial single player games that involve assigning values and eliminating possibilities also belong to this category. It is possible to write efficient algorithms to solve problems in this category, but it requires sophisticated implementations and significant search space reductions - the elimination of large groups of invalid assignments - to be feasible for large, or medium input sizes, in a practical sense.

There is an interesting open problem in computer science called P versus NP which considers how different classes of algorithms relate to each other. This problem was first introduced in 1971 and is still unsolved to this day. The Clay Mathematics Institute established seven Prize Problems in May of 2000, one of which is the P versus NP problem, and will award one million dollars to anyone who can solve it. It would be an interesting turn of events, surreal, if Hexakai were to somehow be involved in the solution to P versus NP.

Conclusion

The information we've covered greatly aided my efforts in making Hexakai fast in execution and vast in the number of boards it can generate. There are still some open questions I'd like to address if and when I can dedicate time, including:

What higher level constructs preclude boards of sizes 2, 4, and 6? In other words, how can I systematically prove these are impossible, instead of proving each one case-by-case?
How can I mathematically prove that all board sizes beyond size 6 are possible, or find one that isn't?
Why are even size boards harder to generate than odd size boards? How much harder are they, precisely?
Is there an abstraction of the concept of a template group I can use to more efficiently find more templates?
Mathematically speaking, in what scenarios is the strategy of tentative assignment required?
How does the analysis of a puzzle board change if we drop the assumption that it has exactly one valid solution?