The Mathematics of Hexakai

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 a board of every odd size, which we'll prove later in this post. My supposition is that we can also construct a board of any even 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(n-1)}{2}$.

Impossible Boards

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

Size 2

Size 4

Size 6

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 boards of size 5 and 7 can satisfy cannot be satisfied by boards of size 8 or 10, and the smallest even size that can satisfy it is 12.

I believe that there are no other "impossible" sizes beyond 6. For odd sizes this is proven in the next section, which constructs a valid board of every odd size. For even sizes I haven't mathematically proven it, 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.

Every Odd Size Is Possible

To state this precisely, number these diagonals $a = 0, 1, \ldots, n-1$ and number the positions along each one $b = 0, 1, \ldots, n-1$. The value of the cell at position $b$ of diagonal $a$ is:

Here, $x \bmod n$ is the remainder when $x$ is divided by n, which is what wrapping back around to 0 means. The board is valid when n is odd because all three rules of the game hold:

• Diagonals running down-right. Along one of these diagonals, $a$ is fixed and $b$ takes each of its n values. The values $2a + b$ are n consecutive numbers, and n consecutive numbers always wrap around to give every value from $0$ to $n-1$ exactly once.
• Diagonals running down-left. Along one of these, $b$ is fixed and $a$ takes each of its n values, so the values go up in steps of 2. When n is odd, stepping by 2 visits every value before it returns to where it started. For a size of 5, the steps from 0 are 0, 2, 4, 1, 3. So each of these diagonals also contains every value exactly once.
• Rows. Moving one cell along a row raises $a$ by 1 and lowers $b$ by 1, so $a + b$ is the same for every cell in the row. Since $2a + b = a + (a + b)$, the values along a row are $a$ plus a fixed number. The cells of a row all have different values of $a$, and there are at most n of them, so no value repeats.

This also shows why the same construction fails for every even size. The rows and the down-right diagonals are still fine, but the down-left diagonals are not: when n is even, stepping by 2 returns to its starting value after only $\frac{n}{2}$ steps, without visiting the values in between. For a size of 6, the steps from 0 are 0, 2, 4, and then 0 again, so every down-left diagonal would contain each of its values twice.

We might hope to rescue the idea for even sizes by starting each diagonal some other number of values higher than the one before it. Call that number the step, so that the construction above has a step of 2. For the down-left diagonals to contain every value, the step must share no factor with n other than 1. Otherwise it returns to its starting value too early: a step of 2 does so whenever n is even, and a step of 3 does so whenever n is divisible by 3. When n is even, every step that passes this test is odd. One step always passes it: $n - 1$, which amounts to going backward by one value on each diagonal.

The rows break instead. With a step of $k$, the value of a cell is $(ka + b) \bmod n$, which is $(k - 1)a$ plus the fixed number $a + b$ along a row, so the values along a row go up in steps of $k - 1$. An odd step makes $k - 1$ even, and stepping by an even amount through an even number of values returns to its start after at most $\frac{n}{2}$ steps. Any row with more than $\frac{n}{2}$ cells therefore repeats a value, and for sizes of 4 and above, such rows appear before the center row is reached. With the backward step, the first collision is in row $\frac{n}{2} + 1$. For a size of 8, the values are $(b - a) \bmod 8$, and the fifth row reads 4, 6, 0, 2, 4, with the same value at both ends.

The two requirements can never be met together. The down-left diagonals need the step $k$ to share no factor with n, and the center row, which is n cells long, needs $k - 1$ to share no factor with n. One of $k$ and $k - 1$ is always even, so when n is even, one of them always shares the factor 2 with it. I also checked this by computer for every even size up to 30, including the variations where the values along each diagonal go up by a step other than 1, and none of them produces a valid board.

The construction therefore proves that a complete Hexakai board exists for every odd size, no matter how large. It says nothing about even sizes in general, because it only shows that this family of methods fails for them. Even sizes of 8 and above still need another method, and so far the only evidence I have for them is that my algorithm has generated boards of every even size from 8 to 16.

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, b to 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 (ordered by first occurrence, $f(e, X)$), $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:

1. Create an empty mapping between names you find in the template expression and the order in which you found them.
2. 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.

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.

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 row 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.

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 +1 to map it back properly, because columns are counted from 1: the first cell of a row on the flipped board is the last cell of that row on the original board, not one past it.

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.

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.

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 have one of each value.

180-Degree Rotation

We can yield a third transformation, a 180-degree rotation, by applying both reflections, 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

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 .

The column-uniqueness constraint is much harder to satisfy than the ordinary rules of the game, and the sizes that allow it follow no obvious pattern. An exhaustive computer search shows that no template of size 3, 8, 9, or 10 adheres to it, while templates of size 5, 7, 11, and 12 do. Size 12 is the smallest even size with such a template. The board below is one example: no value repeats in any of its rows, diagonals, or vertical columns, so it can be diagonally reflected and rotated by 90-degrees.

Even sizes are not ruled out, then, but sizes 8 and 10 are, and I haven't searched beyond size 12. 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.

Single Cell Constraints

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.

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.

Sum of Constraints

We can determine the total number of constraints on the board by summing the number of constraints on each cell. Each cell in the ith row constrains the same amount of cells as the other cells in its row, so we can re-use the formula above. As is typical with mathematics involving Hexakai boards, the formula above splits between two cases, one for the top half of the board, including the middle row, and one for the bottom. We can handle these cases separately with two summations:

In Hexakai, if a cell constrains another cell, it is also constrained by that cell. In other words, if cell A constrains cell B, then cell B necessarily constrains cell A. Therefore, we can treat a constraint as a bidirectional relationship. With this in mind, the function above double-counts constraints. To rectify this, we'll revisit the function and break it down into two parts: constraints to cells within the same row, and constraints to cells within different rows. In the former, for each cell, we only need to count constraints to cells to its right, since the constraints to its left will have already been counted. In the latter, we only need to count constraints to cells lower on the board. We'll call these forward constraints, since we're only considering constraints farther along in the board.

Combining the two, we can derive the total number of constraints on the board, simplified to the cubic below:

The table below compares the values of this function for each game size and its corresponding numbe of cells.

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.

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. The first group of cells we select receives the first value, the second group receives the second value, and so on, so every sequence of selections is exactly one board. Note that we don't multiply by $n!$ here, as we do when deriving boards from a template: the groups are already selected in order, and that order is what decides which value each group receives. Dividing this function by $n!$ would instead give the number of templates, since a template doesn't care which group is which. The total function is:

This provides a significant increase in precision by substantially lowering the upper bound. For example, when $n=10$, the refined upper bound is more than 40 million times smaller than 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:

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: $100$ vs $6$ for $n=3$ and $28,977,204,320,064$ 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:

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!$.

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

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:

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 relating this problem to an existing problem whose complexity has already been determined. This is done through a process called problem reduction: converting one problem into another, so that what is known about one tells us something about the other.

First, though, it helps to have a ceiling. The bluntest way to fill a Hexakai board is brute force: try every value in every cell and keep the arrangements that follow the rules. There are n values to choose from and $n^2$ cells on the board, so brute force examines up to $n^{n^2}$ arrangements. This monstrous super-exponential figure matches the original upper bound estimate of $n^{n^2}$ 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.

Computer scientists sort problems into classes according to how hard they are, and one of the most interesting classes is called NP-complete. A problem is NP-complete when it meets two conditions: a proposed solution can be checked quickly (the problem is in NP), and it is at least as hard as every other problem in NP (the problem is NP-hard). The natural Hexakai version of the question is the one a player faces: given a puzzle board, can its empty cells be filled in to make a valid complete board?

That problem is in NP. To check a filled-in board, we only need to confirm that no two cells that constrain each other share a value, and we've already seen that the number of constraints on a board is a cubic function of n.

The second condition is where problem reduction comes in. We need to show that a problem already known to be NP-complete can be converted into a Hexakai puzzle. There is a natural candidate. A Hexakai board is essentially a Latin square, a grid in which every row and column contains each value exactly once, where Hexakai's two diagonal directions play the roles of the square's rows and columns. Hexakai then adds the constraint that its rows, which run along one diagonal direction of that square, also contain no repeated values. Completing a partially filled Latin square was proven NP-complete by Charles Colbourn in 1984, and Sudoku was proven NP-complete in 2003 by Takayuki Yato and Takahiro Seta, who embedded a Latin square puzzle inside a larger, mostly prefilled Sudoku puzzle. Colbourn's result doesn't carry over to Hexakai automatically, because the additional constraint makes it a different problem. The same idea of embedding does work, though: any Latin square puzzle can be converted into a mostly prefilled Hexakai puzzle that has exactly the same solutions. Hexakai is therefore NP-complete, as non-trivial single player games that involve assigning values and eliminating possibilities typically are. The full proof is more formal than the rest of this post, so I've given it its own section at the end, just before the conclusion.

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.

Proof: Hexakai Completion is NP-Complete

This section proves the claim made above: deciding whether a partially filled Hexakai board can be completed is NP-complete. It is more formal than the rest of this post, and you can skip to the conclusion without losing anything else. The proof converts any Latin square puzzle into a Hexakai puzzle with exactly the same solutions. The idea of embedding a Latin square puzzle in a larger, mostly prefilled grid is inspired by the projection argument Yato and Seta used to prove that Sudoku is NP-complete.

Throughout, the proof views a Hexakai board as if it were a Latin square with one additional constraint that the diagonal direction must also have no duplicate values. Turn the board so that its two diagonal directions become the rows and columns of a square grid, each of which must contain every value exactly once, just as in a Latin square. The game's horizontal rows then become the grid's anti-diagonals, the lines that run from the bottom-left to the top-right, and the additional constraint is that no anti-diagonal may contain the same value twice.

Definitions

The proof relies on the following terms and notation.

• Decision problem: a question with a yes or no answer that is asked about an input, such as "can this puzzle be completed?"
• Polynomial time: a number of computational steps bounded by a fixed power of the input size, such as $N^2$ or $N^6$, as opposed to an exponential like $2^N$.
• NP: the class of decision problems for which a "yes" answer can be confirmed in polynomial time when we're handed a proposed solution, called a certificate.
• Polynomial-time reduction: a procedure that converts every input of one problem into an input of another in polynomial time, such that both have the same yes or no answer. If problem X reduces to problem Y, then Y is at least as hard as X.
• NP-hard: a problem that every problem in NP reduces to. To show a problem is NP-hard, it is enough to reduce a single known NP-hard problem to it.
• NP-complete: a problem that is both in NP and NP-hard.
• Latin square: a grid with $n$ rows and $n$ columns, filled with $n$ symbols such that every row and every column contains each symbol exactly once. The number $n$ is its order.
• Latin puzzle: a Latin square with some cells left empty. The filled cells are its clues.
• Latin subsquare: a smaller Latin square sitting inside a larger grid. It is made of the cells where $k$ chosen rows cross $k$ chosen columns, when those $k^2$ cells use only $k$ different symbols and each of those symbols appears once in every chosen row and every chosen column. The chosen rows and columns do not need to be next to each other. Step 3 uses this.
• Completion: a way of filling every empty cell of a puzzle that keeps its clues and satisfies its rules.
• Anti-diagonal: in a square grid, the set of cells that share the same value of row index plus column index. Each one is a line of cells running from the bottom-left to the top-right.
• Bijection: a pairing between two sets in which every member of each set has exactly one partner. A bijection from a set to itself rearranges the set without repeating or skipping anything.
• Modular arithmetic: $x \bmod m$ is the remainder when $x$ is divided by $m$, and $x \equiv y \pmod m$ means that $x$ and $y$ leave the same remainder. When $m$ is odd, we can also divide by 2: dividing by 2 means multiplying by $\frac{m+1}{2}$, because $2 \cdot \frac{m+1}{2} = m + 1 \equiv 1 \pmod m$.
• Base $m$: every whole number from $0$ to $m^3 - 1$ can be written in exactly one way as $a + bm + cm^2$, where the digits $a$, $b$ and $c$ each lie between $0$ and $m - 1$.

One note on variables. Everywhere else in this post, n is the size of a Hexakai board. In this section only, $N$ is the size of the Hexakai board, $n$ is the order of a Latin puzzle, and $m$ is an odd number derived from $n$.

The Problem and the Result

Hexakai Completion. This is the problem of deciding whether a Hexakai puzzle can be solved. We are given a Hexakai puzzle of size $N$, drawn as a grid with $N$ rows and $N$ columns in which each cell is either empty or holds one of $N$ values. We are asked whether the empty cells can be filled so that no value repeats in any row, any column, or any anti-diagonal.

Rows and columns have $N$ cells, so each must contain every value exactly once. Anti-diagonals have between $1$ and $N$ cells, so they only forbid repeats.

This grid is the Hexakai board redrawn, turned so that its two diagonal directions run straight across and straight down. The table below shows how the two correspond. For the rest of this section, "row" and "column" refer to the rows and columns of this grid, not to the horizontal rows of the game board.

Latin Square Completion. This is the problem of deciding whether a Latin puzzle can be solved. We are given a Latin puzzle of order $n$, and we are asked whether it has a completion. Colbourn proved this problem NP-complete in 1984.

Theorem. Hexakai Completion is NP-complete.

Proof Outline

The proof shows membership in NP, then converts any Latin puzzle into a Hexakai puzzle with exactly the same completions, in four steps:

1. Pad. A Latin puzzle of order $n$ becomes a Latin puzzle of odd order $m = 2n + 1$.
2. Build a Hexakai base board. A formula gives a complete Hexakai board of size $N = m^3$.
3. Find a Latin subsquare. The base board contains $m^2$ cells, where $m$ of its rows cross $m$ of its columns, that form a Latin square on $m$ of its symbols and that the anti-diagonal rule never constrains.
4. Fill the subsquare. Erase the Latin subsquare and write the padded Latin puzzle in its place. The Hexakai puzzle can be completed exactly when the Latin puzzle can.

Membership in NP

A completed grid is a certificate of $N^2$ values. Checking it means confirming that it agrees with the given clues and that none of the $N$ rows, $N$ columns and $2N - 1$ anti-diagonals repeats a value, which takes time polynomial in $N$.

Step 1: Padding to Odd Order

Every Latin puzzle of order $n$ converts to a Latin puzzle of odd order $m = 2n + 1$ with the same completions. This is needed for even $m$ because the base board in Step 2 only works for odd $m$, so this step acts as as additional preparation.

Construction. Let $P$ be a Latin puzzle of order $n$ on the original symbols $1, \ldots, n$. Add $n + 1$ new symbols $k(0), \ldots, k(n)$, and treat the argument of $k$ modulo $n + 1$, so that $k(n + 1)$ is $k(0)$ and $k(-1)$ is $k(n)$. Index the first $n$ rows by $u$ and the first $n$ columns by $v$, each from $0$ to $n - 1$. Index the $n + 1$ extra rows by $w$ and the $n + 1$ extra columns by $w'$, each from $0$ to $n$. The padded puzzle $P'$ is made of these blocks:

For $n = 2$, writing the new symbols as a, b and c, the padded puzzle is:

The shaded cells are the empty cells of $P$. The heavy lines separate the four blocks.

Lemma 1. The completions of $P'$ are exactly the completions of $P$ placed in the top-left block.

Proof. Every completion of $P'$ contains a completion of $P$. Row $u$ already holds $k(u), k(u + 1), \ldots, k(u + n)$ in its top-right cells, which is every new symbol. Its $n$ top-left cells must therefore hold the $n$ original symbols, once each. Columns forbid repeats, so the top-left block is a Latin square on $1, \ldots, n$ that agrees with the clues of $P$.

Every completion $L$ of $P$ extends to a completion of $P'$. Put $L$ in the top-left block and check each line:

• Row $u$. $L$ supplies each original symbol once, and the top-right cells supply each new symbol once.
• Column $v$. $L$ supplies each original symbol once. The bottom-left cells hold $k(w + v)$ for $w = 0, \ldots, n$, which is each new symbol once.
• Extra row $w$. The bottom-left cells hold $k(w), \ldots, k(w + n - 1)$, which is every new symbol except $k(w + n) = k(w - 1)$. The diagonal cell supplies $k(w - 1)$. The off-diagonal cells hold $(w' - w) \bmod (n + 1)$ for the $n$ values $w' \neq w$, which is each of $1, \ldots, n$ once.
• Extra column $w'$. The top-right cells hold $k(w'), \ldots, k(w' + n - 1)$, which is every new symbol except $k(w' - 1)$. The diagonal cell supplies it. The off-diagonal cells hold $(w' - w) \bmod (n + 1)$ for the $n$ values $w \neq w'$, which is each of $1, \ldots, n$ once.

From here on, $m$ is odd and at least 3, and the Latin puzzle has order $m$.

Step 2: The Base Board

For every odd $m$ there is an explicit complete Hexakai board of size $N = m^3$.

That some board of this size exists is already guaranteed. When $m$ is odd, $m^3$ is odd too, and we showed earlier in this post that a complete board exists for every odd size. The reduction needs more than existence, though: it needs a board that also contains the Latin subsquare found in Step 3, so this step builds a particular one. Its formula uses the same idea as the earlier construction, a shift of 2 from one row to the next, applied to each base $m$ digit.

Notation. Number the rows and the columns from $0$ to $N - 1$, and write each row index $i$ and column index $j$ in base $m$. The digits $a, b, c, p, q, r$ each lie between $0$ and $m - 1$:

The $N$ symbols are the triples $(x, y, z)$ of digits, and $x$, $y$ and $z$ are the first, second and third parts of the symbol. Written as a single number, the triple is $x + ym + zm^2$.

Definition. The base board $B$ puts this symbol in row $i$, column $j$, with each part taken modulo $m$:

Lemma 2 (rows). Each row of $B$ contains every symbol exactly once.

Proof. Fix $i$, so $a$, $b$ and $c$ are constants. The map from $(p, q, r)$ to the symbol adds a constant to each digit modulo $m$, which is a bijection on triples.

Lemma 3 (columns). For odd $m$, each column of $B$ contains every symbol exactly once.

Proof. Fix $j$, so $p$, $q$ and $r$ are constants. Since $m$ is odd, we can divide by 2 modulo $m$, and the row digits can be recovered from the symbol $(x, y, z)$ in turn: $a = (x - p)/2$, then $b = (y - q - 2a)/2$, then $c = (z - r - b)/2$, all modulo $m$. Different rows therefore give different symbols, and a column has as many cells as there are symbols.

Note: why Step 1 was needed. This proof is the reason for padding the Latin puzzle to an odd order, and it is the one place where an even $m$ would break the base board. When $m$ is even, we cannot divide by 2 modulo $m$, because doubling no longer gives every remainder: $2a$ and $2\left(a + \frac{m}{2}\right) = 2a + m$ leave the same remainder. The row digit $a$ only ever enters the formula for $B$ as $2a$, so two rows whose first digits are $a$ and $a + \frac{m}{2}$, and whose other digits match, would hold exactly the same symbols in every column. With $m = 2$, for example, the first two rows of the board would be identical, and every column would repeat a symbol. Step 1 guarantees this never happens, because $m = 2n + 1$ is odd for every $n$.

Lemma 4 (anti-diagonals). No anti-diagonal of $B$ contains a symbol twice.

Proof. Suppose cells $(i, j)$ and $(i', j')$ satisfy $i + j = i' + j'$ and hold the same symbol. Write the digits of the second cell with primes.

1. Reducing $i + j = i' + j'$ modulo $m$ gives $a + p \equiv a' + p'$. The first parts of the symbols give $2a + p \equiv 2a' + p'$. Subtracting, $a \equiv a'$, so $a = a'$ and then $p = p'$.
2. Remove $a + p$ from both sides of $i + j = i' + j'$ and divide by $m$, which leaves $(b + q) + (c + r)m = (b' + q') + (c' + r')m$. Reducing modulo $m$ gives $b + q \equiv b' + q'$. The second parts, with $a = a'$, give $2b + q \equiv 2b' + q'$. Subtracting, $b = b'$ and then $q = q'$.
3. What remains is $c + r = c' + r'$. The third parts, with $b = b'$, give $2c + r \equiv 2c' + r'$. Subtracting, $c = c'$.

So $i = i'$, and the two cells are the same cell.

By Lemmas 2 to 4, $B$ is a valid complete Hexakai board whenever $m$ is odd. Lemma 4 holds for every $m$; only Lemma 3 needs $m$ to be odd.

Step 3: The Latin Subsquare

A Latin subsquare of a grid is a smaller Latin square sitting inside it. To find one, choose $k$ of the grid’s rows and $k$ of its columns, which do not need to be next to each other, and look only at the $k^2$ cells where a chosen row crosses a chosen column. If those cells use just $k$ different symbols, with each symbol appearing once in every chosen row and once in every chosen column, then together they form a Latin square of order $k$, and we call them a Latin subsquare of order $k$.

The base board contains a Latin subsquare of order $m$ that behaves like a free Latin square: only $m$ symbols can go in its cells, and the anti-diagonal rule never constrains them.

Definitions.

• A subsquare cell is a cell in row $u$ and column $v(m + 1)$, for $u$ and $v$ from $0$ to $m - 1$. These are the $m^2$ cells where the first $m$ rows cross every $(m + 1)$th column, starting with the first. A subsquare row or subsquare column is one that contains subsquare cells. Lemma 5 shows that these cells form a Latin subsquare, which is where their name comes from.
• A filler cell is any cell that is not a subsquare cell.
• The special symbols are the $m$ triples $(d, d, 0)$ for $d$ from $0$ to $m - 1$. Every other symbol is ordinary.

Lemma 5 (the Latin subsquare). The subsquare cell in row $u$, column $v(m + 1)$ holds the special symbol with $d = (2u + v) \bmod m$. Consequently:

• the subsquare cells form a Latin square on the special symbols, which makes them a Latin subsquare of order $m$ in $B$, and
• in every subsquare row and subsquare column, the filler cells hold each ordinary symbol exactly once and no special symbol.

Proof. Row $u$ has digits $(u, 0, 0)$. Column $v(m + 1) = v + vm$ has digits $(v, v, 0)$. The formula gives $(2u + v, 2u + v, 0)$. For fixed $u$ the map from $v$ to $2u + v$ is a bijection modulo $m$, and for fixed $v$ the map from $u$ to $2u + v$ is a bijection because $m$ is odd. So each special symbol appears once among the subsquare cells of each subsquare row and subsquare column. By Lemmas 2 and 3 each symbol appears only once in a whole row or column, so the special symbols appear nowhere else in those lines.

Lemma 6 (separate anti-diagonals). No two subsquare cells lie on the same anti-diagonal.

Proof. The subsquare cell at row $u$, column $v(m + 1)$ lies on anti-diagonal $u + v(m + 1)$. Since $u$ is less than $m + 1$, this number determines both $u$ and $v$.

Lemma 7 (isolation). For $m \ge 3$, the only cell on a subsquare cell's anti-diagonal that holds a special symbol is the subsquare cell itself.

Proof. Let the subsquare cell be at row $u$, column $t(m + 1)$, and let $s = u + t(m + 1)$ be its anti-diagonal. Then $s \le (m - 1) + (m - 1)(m + 1) = m^2 + m - 2$.

Take any cell on this anti-diagonal, with row digits $(a, b, c)$ and column digits $(p, q, r)$. Its symbol is special exactly when its first two parts agree and its third part is $0$:

The cell's row index plus its column index equals $s$, and $s \lt 2m^2$, so $c + r \le 1$. Three cases remain:

So the subsquare cell is the only one.

Step 4: The Reduction

Writing a Latin puzzle into the Latin subsquare gives a Hexakai puzzle with exactly the same completions.

Construction. Let $Q$ be a Latin puzzle of odd order $m \ge 3$, with its symbols renamed $0, \ldots, m - 1$. Define the Hexakai puzzle $G$ of size $N = m^3$:

• every filler cell holds its value from the base board $B$, as a clue;
• the subsquare cell at row $u$, column $v(m + 1)$ holds the special symbol $(d, d, 0)$ if $Q$ has the clue $d$ at row $u$, column $v$, and is empty otherwise.

Lemma 8 (equivalence). The completions of $G$ correspond one-to-one with the completions of $Q$.

Proof. From $Q$ to $G$. Let $L$ be a Latin square completing $Q$. Fill each empty subsquare cell with the special symbol named by $L$, and check each line of the result:

• Subsquare rows and columns. By Lemma 5 the filler cells hold each ordinary symbol once. The subsquare cells now hold each special symbol once, because $L$ is a Latin square. Every symbol appears exactly once.
• Other rows and columns. They are unchanged from $B$, so they are valid by Lemmas 2 and 3.
• Anti-diagonals with a subsquare cell. By Lemma 6 there is only one subsquare cell on the line. The other cells are unchanged from $B$, so they have no repeats among themselves (Lemma 4), and none of them is special (Lemma 7). The subsquare cell holds a special symbol, so it repeats nothing.
• Other anti-diagonals. They are unchanged from $B$, so they are valid by Lemma 4.

From $G$ to $Q$. Take any completion of $G$. In a subsquare row, the filler cells already hold every ordinary symbol (Lemma 5), so the $m$ subsquare cells must hold the $m$ special symbols, once each. The same holds for each subsquare column. Reading the subsquare cells as a grid with $m$ rows and $m$ columns therefore gives a Latin square on the special symbols that agrees with the clues of $Q$.

The two directions undo each other, so the correspondence is one-to-one.

Proof of the theorem. Membership in NP is shown above. For hardness, take any Latin puzzle $P$ of order $n$. Apply Step 1 to get a puzzle of odd order $m = 2n + 1 \ge 3$, then the construction above to get a Hexakai puzzle $G$. By Lemmas 1 and 8, $G$ can be completed exactly when $P$ can. $G$ has $(2n + 1)^6$ cells, and each is computed by a fixed number of arithmetic steps, so the conversion runs in polynomial time. Latin Square Completion is NP-complete, so Hexakai Completion is NP-hard, and since it is also in NP, it is NP-complete.

Remark. The conversion preserves the number of completions, not just whether one exists. Results about counting completions, or about whether a Latin puzzle's completion is unique, therefore carry over to Hexakai as well.

Example of Concept

A Latin puzzle of order 3 becomes a Hexakai puzzle of size 27, in which 720 of the 729 cells are filler cells. Since 3 is already odd, padding is skipped and $m = 3$.

The symbols are written as the numbers 0 to 26. The subsquare cells are rows 0, 1 and 2 crossed with columns 0, 4 and 8, and the special symbols are 0, 4 and 8. This is the top-left corner of the base board, with the subsquare cells highlighted:

The highlighted cells are the nine subsquare cells. They hold only the special symbols 0, 4 and 8.

Columns 9 to 26 of these rows hold the symbols 9 to 26, and rows 3 to 26 complete the board. The subsquare cells lie on anti-diagonals 0, 4, 8, 1, 5, 9, 2, 6 and 10, which are all different.

All of the Latin puzzle lives in the first three rows, so it is fair to ask why the other 24 rows are needed. There are three reasons:

• A Hexakai board is square. Each of the first three rows is 27 cells long and holds 27 different symbols, and a Hexakai board that uses 27 symbols has 27 rows and 27 columns. Three rows on their own are not a Hexakai puzzle, so they could not serve as an input to Hexakai Completion.
• The rows are that long for a reason. The three subsquare columns are spread apart, at columns 0, 4 and 8, so that no two subsquare cells share an anti-diagonal. The filler cells between and beyond them use up every ordinary symbol in each of those rows, which is what leaves only 0, 4 and 8 for the subsquare cells.
• The rest of the board must be known to work. A completion has to fill all 729 cells without breaking a rule. If rows 3 to 26 were left empty, or filled carelessly, the puzzle might have no completion at all for reasons that have nothing to do with the Latin puzzle. The base board from Step 2 settles this in advance: rows 3 to 26 are given as clues, they are already valid, and they also use up every ordinary symbol in columns 0, 4 and 8.

Because those 24 rows are entirely clues, they add nothing to solve. All of the difficulty of the Hexakai puzzle sits in the nine subsquare cells, which is exactly the difficulty of the Latin puzzle.

Take this Latin puzzle and rename its symbols so that 1 becomes 0, 2 becomes 4, and 3 becomes 8:

The shaded cells are empty.

The Hexakai puzzle is the base board with its nine subsquare cells replaced by the right-hand grid: a 0 at row 0, column 0, a 4 at row 1, column 4, and seven empty cells. Each of rows 0 to 2 and columns 0, 4 and 8 is missing only special symbols, so the seven empty cells can only take 0, 4 or 8.

This Latin puzzle has exactly one completion, so the Hexakai puzzle does too:

Try It Yourself

The tool below generates a random Latin puzzle of order 3 and shows the Hexakai puzzle of size 27 that the reduction builds from it. The Latin puzzle's symbols 1, 2 and 3 are renamed to the special symbols 0, 4 and 8, and its nine cells are written into the subsquare cells, which are outlined on the large board. Every other cell of the board is a filler cell and never changes. Any way of completing the Latin puzzle completes the Hexakai puzzle, and the reverse is also true.

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?
• Every odd board size is possible, as shown above. How can I mathematically prove that all even 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?