This page details the process that my program uses to generate each grid. Before it begins the real work of assigning colors to cells such that all of the rules are met, the program needs parameters and then performs a setup phase based on those parameters.
Grid Parameters
- Rows
- Columns
- Number of Colors
- Rules
Before I show the setup, here is a simplified view of the Grid object:
The Grid
*- only the cells relevant to color assignment are included in the adjacent cells. For example, if there is a horizontal adjacency restriction but no vertical adjacency restriction, the cells to the left and right of the cell are included but the cells above and below the cell are not.
Each group stores a list of cells that it contains, as well as a list of colors and the number of each color available for the group.
Each cell stores the groups that it belongs to, as well as all of it’s adjacent cells.
Grid Setup
The setup phase is designed to minimize the amount of work done assigning colors to cells. After the setup phase, the original parameters and rules are no longer needed to fill the grid with colors, though the program does validate each rule afterwards (mostly to make sure that I didn’t break anything in the code).
Filling the Grid with Colors
The color assignment loop:
A cell’s connected cells include it’s adjacent cells as well as all cells that belong to any of it’s distribution groups.
The rollback loop is the most difficult part of the process to conceptualize, and thus will get another chart of it’s own.
Cell Selection
The program determines the next cell to assign a color to based on the following criteria, in order of importance.
- Number of colors available (lower wins)
- Number of distribution groups the cell belongs to (higher wins)
- Sum of the product of the available color counts in each distribution group (see: Color Selection)
- Original order (typically sorted by row and then column, but at this point it could be random without much difference).
When comparing two cells, the cell with fewer available colors always wins. If equal, the cell with more distribution groups wins, and so on down the list.
Color Selection
Color selection for a cell is random, but weighted based on the number of each color remaining in each of the cell’s distribution groups. This is determined by multiplying the values for each group. Here is an example for a cell with two groups and four total colors:
| Color | Group 1 | Group 2 | Product | Percent |
| Red | 1 | 2 | 2 | 15.4% |
| Yellow | 2 | 4 | 8 | 61.5% |
| Blue | 3 | 1 | 3 | 23.1% |
| Green | 4 | 0 | 0 | 0.0% |
| Sum | 10 | 7 | 13* |
If a cell’s adjacency rules restrict one of the colors, the product is set to 0 for that color and the percents are recalculated. For example, if red would violate an adjacency rule, then the product sum becomes 11, with yellow having an 8/11 (72.7%) and blue having a 3/11 (27.3%) chance of being selected.
This product sum, minus the restricted values (11), is used for the 3rd criteria in cell selection.
Updating Values After Color Selection
The following occurs after a color is selected for a cell:
- The cell is removed from the available cells for the full grid and in each group that it belongs to.
- The color count is decreased for each of the cell’s groups.
- The groups notify* each of the remaining cells that their color count/product for the chosen color needs to be calculated.
- Each of the cell’s relevant adjacent cells are notified* to recalculate their adjacency restrictions.
*- I say notify, because these calculations aren’t actually performed until they are needed.
This is designed to minimize the amount of calculation necessary, while maintaining information completeness for cell selection.
Validation
After color selection, all of the related cells without an assigned color are checked to see if there are any colors available that meet both the group and adjacency restrictions. If any of the cells fail the check, the color selected for the original cell is not valid* and the rollback loop begins.
*-the color can still be selected for the cell depending on the results of the rollback loop.
The Rollback Loop
The rollback loop begins with the last cell assigned a color:
The rollback loop exits once it assigns a new color to a previous cell and the cells related to it all pass the check. Each time a cell’s color is changed or cleared, the update sequence above is triggered. When the loop goes back to a previous cell, the colors that were eliminated by the loop for the current cell become available again.
In theory, the loop can go back to the very first cell assigned a color for that grid, in which case it will cause my program to crash. It will also have proven that it is impossible to create a grid with the original parameters and rule set, a fact that will only be known to the computer program for the brief instant before it crashes.
A Basic Example
In this made-up example, the “program” proves that whichever color selected for Cell 0 is impossible, but in order to do so it had to eliminate all 3 colors from Cell 1, which required eliminating both colors from Cell 2, and so on.
A Couple Of Real Examples
Here are a couple of examples from grids generated by my program. The following chart shows how my program applied this process to fill a 576 cell grid:
Each color selection increases the number of filled cells by exactly one, but the filled cells can drop by more than one since the rollback process goes back to the first cell with more than one available color. This is why there are relatively sharp drops, especially towards the end when the options are limited and many of the color selections are forced (only 1 color available).
At one point, the program had filled 546 of the 576 cells, and about 100 color assignments later, it was back to just 483 cells filled. This is far from unusual – I actually picked this particular chart because it follows a relatively smooth progression while demonstrating a few common patterns that I’ve seen in these charts: the quick early rise, the plateau around 400 cells, and the jaggedy finish.
The next example went down a far less smooth path to completion. The chart skips the first 400 cells, which are much of the same.
The program showed incredible resolve to deal with so many setbacks and finally achieve success, some 30,000 color assignments after it started.
Summary
The color assignment loop (which contains the rollback loop) is designed to identify impossible conditions as quickly as possible. If allowed to run ad infinitum, the end result is either a grid that meets the given parameters, or a definitive proof that it is impossible to create a grid that meets all of the given parameters.
Unfortunately, it is limited by both the processing power of my computer and the practically impossible to calculate, but nearly endless, amount of combinations that it would have to test in order to prove impossibility. Thus, I had to write some ugly code that gives up on a grid at some point and tries again from scratch under certain scenarios. Worse, it is extremely hard to define these scenarios in a generalized way for the wide variety of rule sets I throw at it, but the program is far more successful when I give it a way to start over compared to when I don’t.
Back to Color Grids