The Rules

Main page:  Solving a Hard Problem

see this on the interactive viewer

The grid has 16 rows and 32 columns, and the cells are 3 times as tall as they are wide. 

This page explains the rules that the grid follows.

The rule set is currently the most difficult that my program has solved*. 

The rule set consists of two types of rules:  distribution sets and adjacency restrictions.  

*as of the time of this writing.  

Distribution Sets

Distribution Group – a group of cells where the number of cells of each color must be equal. 

Distribution Set – a set of distribution groups that covers the entire grid without overlapping. 

Each color is evenly distributed per the following distribution sets: 

The Standards

1. Each single row (16 groups of 32 cells, 8 of each color):  

The black lines highlight 8 of the rows on the left and the other 8 rows on the right.  

2. Each single column (32 groups of 16 cells, 4 of each color): 

Consequences of the Row and Column Distribution Sets

Based on these two rules alone, the following is true: 

• Each cell belongs to a unique pair of distribution groups (1 row, and 1 column).
  • Example:  the cell in row 1 and column 1 is (surprisingly) the only cell in row 1 and column 1.  
• Each cell is either connected to, or 1 step away from, every other cell in the grid. 

To demonstrate the second: 

While the two red cells with the green border aren’t directly connected, they are 1 step away from each other via the yellow and purple cells with the cyan border (the 4 cells together form the corners of a rectangle).  The color chosen for the top left cell of the rectangle might influence the color for the bottom left cell, which might influence the color for the bottom right cell.  

Because of these two properties, the row and column distribution rules are the starting point for almost every rule set that I give my program to solve.

Color Conflicts

To understand the problem posed by these distribution sets, consider the task of filling an empty grid of cells according to these rules: 

• At some point, there is only going to be one cell remaining in each row – and only one color to fill the cell according to the rule. 
• At some point, there is only going to be one cell remaining in each column, and only one color.  
• At some point, a single cell will be the only cell remaining in a row and a column. 
• What happens if the row says that cell has to be one color, and the column says it has to be another?  

This is what I call a color conflict:

Color conflict – when there are no colors remaining for a cell that would not break one of the rules of the grid. 

The above describes only one of the scenarios that can cause a color conflict.  

A color conflict can occur any time that the total number of colors eliminated by a cell’s distribution groups is greater than or equal to the total number of colors for the grid.  With these two sets, this can happen when there 2 colors remaining in each the row and the column of an empty cell: 

This  shows a 4×4 grid with the same rules (1 of each color per row/column). 

Without knowing the colors, the odds of a conflict in this scenario are 1 out of 6 compared to vs. 3 out of 4 when there is only 1 color left in both the row and column. 

A 3rd Dimension

In addition to the row and column distribution sets, the colors are also evenly distributed per:

3.  Each non-overlapping block of 4 row by 4 column cells (32 groups of 16 cells, 4 of each color): 

Building on the problem posed by the row and column distribution sets, there are now 3 groups that must agree on a single color when a cell is encountered that completes one of each group.  This reduces the odds of agreement from 1/4 to 1/16 (with a random approach to filling out the grid, which obviously is not the best one).  

The additional set is equivalent to adding a 3rd dimension to the 2-dimensional grid, where the row of a cell is the Y coordinate, the column is the X coordinate and the Z coordinate is the block of 4×4 cells that it belongs to (assigning a number to each of the 32 blocks). 

Before my program generated this specific grid, the most difficult rule set it had solved followed all of the same rules but with a modified version of this one:

viewer link to this grid

The blocks are twice as wide, which has the advantages of making them proportional to the grid size and also bit prettier (in my opinion) when viewed with half of the blocks darkened as they are here. 

I’ll admit, I was initially conflicted over which rule set to feature on this page (particularly since, I had written most of the page based on the original grid, since the featured grid didn’t exist yet).  

Ultimately, I was convinced to start over with the new grid for three reasons: 

1. It was a lot harder for my program to solve the rule set with the smaller blocks.  This difference is extremely evident in the cell by cell solutions for the original grid vs. the featured grid, and the cell by cell solution was the original reason for this page. 
2. The featured grid also satisfies the original rule set – thus, I can pretend the smaller block rule doesn’t exist if I want.  Conversely, the original grid doesn’t satisfy any of the 32 4×4 block distribution groups.  
3. I like the way the featured grid looks compared to the original.  
4. 8888.

A Centralizing Force

And now, the final distribution set where the colors are distributed equally: 

4. Each rectangle of cells that is exactly centered and the same proportion as the full grid.  There are 8 of these (including the full grid), but because they overlap, they reduce to a small rectangle in the center and 7 rings around it. 

This is the only set where the groups are not the same size. 

While there are only 8 of these groups, the addition of this distribution set ends up having roughly the equivalent impact as the 4×4 block distribution set on the difficulty of the rule set.

A big reason why is that this additional rule set forces the program to take an entirely different approach to filling the grid with color.  

The following images show the average sequence the program followed to fill a grid for another rule set that has 3 distribution sets, and that same rule set but with the addition of the central rectangle set: 

The maps are based on 100 grids from each set.  The color of the cells shift from blue to red to green to cyan in order of when the program typically assigned that cell a color.  

The checkerboard appearance of some areas is a result of the adjacency restrictions of the rule sets.    Here are individual examples of each: 

There is significant variation between the individual grids – and much more variation with the central rectangle set than without.  Here is the 2nd image at 50% along with 3 others from that set:

Sadly, these interesting shapes go away once the rest of the cells are filled.  

Of course, the program doesn’t have to start at the center even with the central rectangle groups – it could follow a similar linear path like the other set.  However, it is far more successful when it starts at the center than when it does not.   Conversely, it is far less successful when it starts at the center when there isn’t a central rectangle distribution set.  

Note that there is no specific code that tells the program where to start and what path to follow.  See The Program vs. The Grid or Grid Generation for details.  

Summarizing the Distribution Sets

There are 4 distribution sets with a total of 88  groups of cells where the colors must be evenly distributed

The smallest distribution group is an 8 cell rectangle in the center.  Additionally, a hidden distribution group can be deduced from the following groups:

1. The distribution groups in the first and the last row. 
2. The distribution groups in first, second, last, and second to last columns.
3. The outermost central ring, the 120 cells of which cover all of the cells in the above groups (but none outside of these groups).

Here is what that hidden distribution group looks like: 

Like the 2Rx4C central rectangle group, this hidden group (the only hidden group that can be deduced from the 88 groups) is also 8 cells.  This means that the smallest two distribution groups consist of the 8 cells closest to, and furthest away from, the center of the grid. 

8888

Each cell belongs to a unique set of 4 overlapping distribution groups, 1 from each set

The highlighted cells show all of the distribution groups that the blue cell with the green border belongs to.  

The Distribution Sets Make My Head Spin

There original problem that I was posed at the start of this project had just two rules – the row and the column distribution sets.  Until I wrote the program that solved it, I was not sure if even this problem was solvable.*  

Keeping track of 4 sets and 88 distribution groups alone is really difficult for a human.  Dealing with the conflicts is practically impossible for anyone without the aid of the computer.*

It turns out, however, that my program doesn’t have too much trouble solving the problem.   To make it really challenging for the machine, there needs to be another type of rule on top of the  distribution rules. 

*- One of the parameters I was given for this project is that the color of each cell should be chosen randomly (unless that color would break a rule).  This eliminates any pattern based solution to a rule set, which would otherwise make the problem not that hard for a human.  For example: 

This grid satisfies all of the distribution groups, but not the adjacency restrictions. 

Adjacency Restrictions

In addition to the distribution sets, the colors in the grid also adhere to the following rules: 

1. The cells to the top left, top right, bottom left, and bottom right of a cell cannot be the same color as that cell. 
2. The cells to the left or the right of a red or yellow cell cannot be the same color as that cell. 
3. The cells above and below a blue or purple cell cannot be the same color as that cell.  

Of the 8 cells surrounding each cell, only 2 of the 8 cells can be of the same color:

This rule can limit the options of two cells to only one color by filling the cells without the X with two colors different from the center color: 

The cells to the top and the bottom of the blue cell must be red, while the cells to the left and the right of the red cell must be blue.

In fact, there are actually 4 cells with only one color choice on each side:  

The forced color assignments of red on the left side force the top left and bottom left cells to turn yellow (what if that column had only 1 of it’s 4 yellow remaining?)  On the right side, the top left and top right cells now must be purple.  

This sort of chain reaction is common and is one of the main challenges for any rule set with both distribution and adjacency rules.  

Along with the four distribution sets, this completes the rule set that was followed while creating the featured grid.  

The Restrictiveness of the Rules

Adjacency vs. Distribution

The adjacency and distribution rules both potentially restrict the number of colors available for each empty cell in a partially filled grid. 

As shown above, adjacency rules begin restricting colors as soon as one cell is filled with color.  On the other hand, distribution groups need to run out of a color before they restrict any colors, thus their impact is significantly less when the grid is relatively empty.  

In order to show the relative impact of each type of rule on the overall restrictiveness, my program calculated how many choices it would have had for each cell at the time it assigned the cell a color with the adjacency rules only, the distribution rules only, and all of the rules.    

This chart shows the results:

This table shows the average number of choices for the first 256 cells vs the last 256 cells: 

	Adj	Dist	Both
1H	2.2	2.85	1.42
2H	2.22	1.99	1.28
Total	2.21	2.44	1.35

Where the distribution rules show a relatively flat line compared to the adjacency rules in the chart, the roles are reversed in the table.  

The Conflict Problem, Revisited

Here is another simplified version of the problem:

There are 88 distribution groups, and the last empty cell of each will have only 1 color choice.  Whichever cell this is will probably have 2 colors available based on the adjacency restrictions.  The chances of the adjacency restrictions conflicting with none of the last cells in the distribution groups are roughly the equivalent of winning a coin toss 88 times in a row.  

All of this is assuming that the rest of the grid was filled without any conflicts, which is an awfully big assumption. 

A more mathematical approach to describing the problem: 

By converting the color choices for both the adjacency and distribution rules to percentages, it is relatively easy to calculate how often a conflict should occur based on these percentages. 

This predicts that that the adjacency and distribution rules should conflict about 16% of the time – and 82 times on average for a 512 cell grid.  This is not understating the problem:  the formula also predicts an average of 1.37 color choices per cell, which includes the predicted 82 conflicts which have zero choices.  At 1.35 color choices, the actual average was less than the prediction, even without any zeroes (of course, a zero would mean that the grid does not meet all of the rules).  

Why This Rule Set? 

1. It’s really hard

The rule set is about as restrictive as possible without: 

1. Adding arbitrary distribution groups or other rules. 
   • Can you think of another logical way to divide the board into sectors that is significantly different than the 4 distribution sets?  I can’t. 
   • Here is an example of an “other” arbitrary rule:   the color of any cell where the row and column numbers are both prime cannot be red, unless the cell to the left of it is blue, in which case, the cell must be red, unless the cell to the right of it is yellow and the cell above it is purple.
2. Becoming either impossible, or trivial to solve. 
   • There is a point where the number of choices are reduced so much that it makes it possible for a computer program to test every single combination and either solve the problem or prove that the problem is impossible to solve.   

However, it’s not the average number of choices available that make the rule set hard – as long as the choices are valid, the number of colors available doesn’t matter.  What makes it hard is the illusion of choice – there might appear to be 2 colors available for a cell, but 1 of the colors will lead to a conflict in another cell, thus there is really only 1 choice available.  And even that, doesn’t make it all that hard. 

A Giant Maze

What makes a maze hard?  

1. The number of choices (forks) along the correct path
   • If you only have to cross one fork on the ideal path then you only have to get lucky once.  
2. The length of the incorrect paths
   • A short, linear dead end is only a minor distraction. 
3. The complexity of the incorrect paths
   • A path that has multiple forks, but leads to a dead end regardless of the choices made is a much greater nuisance than a path without forks that leads to a single dead end.  

A maze analogy

This maze consists of 3 types of rooms that have walls but no ceiling. 

The correct path from start to finish (which emanates a glow such that you can see it from a distance, including the starting point) goes through 150 passageways and 50 forks.

There is something special about this maze:  Each path along the fork leads to a different dimension such that no room is the same, even the location is shared :

Imagine that you have gone through 149 passageways and 50 forks from the start (not counting any dead ends that you might have investigated along the way), and arrive at a room that is directly next to the finish. If only the room were the 150th passageway that leads to the finish, you would be done, but alas, it is a dead end.

The path taken so far might look something like this: 

where the green dot is the start, the red dot is the finish, and the forks are numbered from 1 to 50.  

Now you must go backwards, at least to the last fork encountered before this dead end.  Being so close to the finish, you shouldn’t have to go too far back, right?  

What if it turns out that it was the not the 50th fork, but the 1st fork after the start where you went wrong – and that every path after this initial decision leads to a dead end? 

Even this scenario might not be that bad, if the paths through the question marks each lead to a single, short dead end.  Maybe you only have to peek into the ? room at each fork to find the dead end while working your way backwards to the original wrong choice.  

Unfortunately, the alternate paths of  the 2nd through 50th forks lead to not 49, but 100 million dead ends.  Further, it requires going through 1 billion rooms to find all of these dead ends.  You can attempt to “cheat” the maze by not investigating all of them and instead head back to the 1st fork, but this is a gamble that is likely to lose (at least without additional information about the maze).  

This is almost exactly the scenario that my program encountered while creating the featured grid – with one significant difference:  It had to go through about 300 rooms and make over 100 correct decisions before it reached the starting point of this maze.  

This is a really hard rule set to solve.  

2. There Is a Struggle, A Story, and a Mystery Behind The Solution

It wouldn’t have been nearly as interesting if I had simply given my program the rules, clicked a button, and then (after some wait) the program produced a solution.  

This is how my program solved every rule set prior to the predecessor of this rule set (with the 4Rx8C blocks). While the hardest of these rule sets took a long time (up to 2 days) for the program to make the first grid, I didn’t have to do anything but wait for the program to finish after pressing the button.  

Almost two weeks after the featured grid was created, there are still mysteries regarding the solution that I am investigating.  These are made even more interesting since the program has not been able to finish another unique* grid that follows the rule set since.  

* – as part of my investigation, other grids were created that shared most of the same cell/colors as this one.  

3. It is All About the Image

See this on the interactive viewer.  You can also see many other grids with different rule sets on the viewer for comparison.

There is a distinctive aesthetic quality to the image that is a product of the rules.

The adjacency restrictions are a major contributor to the distinctiveness of the patterns seen in the image.  Before I found this combination – with 2 colors limited to vertical “lines” and 2 colors limited to horizontal “blocks”, I had a couple of other favorite sets of adjacency rules.

Here are two from one set: 

 

viewer link

viewer link

For these, there are still horizontal blocks and vertical lines only, but a color can have both.  These adjacency rules restrict 4 of the 8 colors around each cell, as opposed to 6, and my program can make them pretty quickly – faster than I can look at them.  

I liked the variety of the images from these rules, mostly based on the varying sizes of the blocks – which is why I included two images.  

My previous computer generated art project has many more pages on this site dedicated to it than this one, and I spent a lot more time on the program as well.  This project was all about finding “diamonds in the rough” from thousands of randomly generated grids, with both automated and manual processes.  

I did not want to do the same thing with this project, and spend my time looking at thousands of these images trying to find a favorite.  

Here is an example of another set of adjacency rules that I also like:

viewer link

This was probably the first rule set that has individual color adjacency restrictions that I really liked.  If you are still reading this by this point, I probably don’t need to explain what the restrictions are for each color.  

Before this rule set, I had tried out many different ways to add restrictions to individual colors, usually starting from the 4/8 corner “X’s” of the rules for the two images above this.  While I didn’t dislike them – they took my program a lot longer to make, and they generally looked like you would expect them to. 

For example, if I made it so one color is restricted to vertical lines, the resulting grids would end up looking like a more vertical version of grids with just the basic 4 corner restrictions.  

When I saw the first grid with 4 colors, and the 2 block/2 line color restrictions, there was something more to the image that I didn’t expect to see.  I didn’t know exactly what or why, but I liked it.  Now I have a better idea of the why, and to help show this, here is one of images from above demonstrating the adjacency restrictions: 

The main thing to note is that these color combinations have restricted a lot of cells.  Thus, they end up being quite uncommon to see in the actual grids.  Blue next to purple and yellow above/below red is not seen a lot.  What is seen more, is basically everything else.  The colors also end up having a natural lust for expansion in the only way that they can – with blue and purple expanding horizontally, and red and yellow expanding vertically.  

At first, I had to make serious compromises to the distribution sets in order for my program to be able to even make a grid with these adjacency restrictions.  

I had to put in a lot of additional programming effort to get my program to be able to make a grid with these restrictions and without compromising the distribution sets.  This was made even harder due to this “lust” for expansion, as the colors kind of don’t want to be distributed evenly.  

The distribution sets also make a significant impact on the images, though in a much more subtle way than the adjacency restrictions.  

In particular, there are hidden patterns behind the scene that become clearer in the images with alternating dark rows/columns, which I will re-post to save scrolling: 

While these images were initially intended to show the row and column distribution sets only, the influence of the central rectangle and to a somewhat lesser extent, the 4×4 block distribution sets are also evident (more so than the images that show those groups).  

For comparison, this is from a grid with most of the same rules, but no central rectangle set: 

link to full image on the interactive viewer.

You might have to look closely to see the differences – but they are there to be found.  

The viewer also allows you to view the distribution groups in this way:

Clicking on show will darken half of the distribution groups for that set, then click on “Darken” to make these even darker. 

Here are a couple of other grids similar rule sets to compare the featured grid to: 

http://doug-osborne.com/ColorSystems.html?id=52654

http://doug-osborne.com/ColorSystems.html?id=54632

The overall combination gives the featured grid an appearance of both randomness and order that I really like.  I do not think it is necessary to know any of the rules in order to enjoy looking at the product of the rules.  It was two weeks after I saw the full image that I noticed the patterns in the alternating row/column images that gave the left side of my brain enough concrete evidence to start believing the (usually ignored) right side.  

Next page:  The Program vs. The Grid