Previous page: The Rules
After writing only 5 times as much as I planned to before this part, I finally get to the original point of the original page (which is now 4 pages), which I had nearly forgotten:
The cell by cell solution to the rule set that resulted in the featured grid. The next section shows the highlights and is told in a story-like, possibly fictionalized way, but the full solution is available at the bottom of the page.
The Program versus The Grid
Before we begin, an introduction to the competitors:
Grid ID #2213 (“The Grid”)
not as innocent as it looks
There is only one way to defeat The Grid: fill each of it’s 512 cells with 4 colors according to the aforementioned rules.
The Grid will instantly vaporize anyone – or any program – that attempts to violate any of these rules.
ColorSystems.exe (“The Program”)
The Program will attempt to defeat The Grid, armed with the following:
- Four Colors
- Knowledge of the rules required to defeat The Grid
- A Perfect Memory
- An Eraser
- Two Formulas: A formula that tells it which cell to fill with color next, and a formula that tells it how often to pick each color for that cell.
For details on these, see the Grid Generation page.
The First Cell
Cell Color Keys:
white – All 4 colors available
light gray – 3 colors available
green border – the last cell assigned a color
cyan border – the next cell to assign a color
pink highlight – cells that belong to one of the distribution groups of the current cell. When a cell is filled, there is no pink, but the color will be a bit brighter than it would be otherwise.
The Program starts with the top left cell in the inner central rectangle (row 8, column 15) and randomly picks a color, which is yellow. The Program starts here because the cells within the 8 cell rectangle have the smallest pink zones.
This selection caused 6 of the 8 cells around it to turn to a light shade of gray – indicating that these cells have only 3 color choices.
Note that the program’s next choice is one of the 6 light gray cells.
Cell 2
New Color Key:
dark gray – 2 colors available
After picking a color for just two cells, there are already two cells where the options have been cut in half: these cells can’t be either blue or yellow, because they would violate the adjacency rules. Notice that the cyan border is around a dark gray cell.
Rule 1 about Cell Selection
The Program doesn’t like choices. Therefore, it will always pick a cell with fewer available colors (darker shade of gray) over a cell with more available colors.
Cell 4
New Color Key:
black – only 1 available color.
After The Program chose yellow over purple for the 4th cell, the central rectangle has reached the maximum amount of yellow. The black cell can’t be blue or red (red can’t touch red on the left/right, and no color can touch the same color at the corner) and it can’t be yellow, so the only remaining color is purple.
The Program also could have chosen purple for the cell, and the black cell would have stayed dark gray. Color selection is random, but the colors are weighted such that it will generally select colors that are more available over colors that are less so. In this case, yellow was picked despite having a 27% chance versus a 73% for purple. These are the odds based on:
The Color Selection Formula
Each color is weighted based on the product of the available count of that color in each of the cell’s distribution groups. In this case, there was only 1 yellow left in the central rectangle and 3 yellow left in the cell’s column, while there were 2 and 4 purple remaining respectively. Thus, yellow was given a weight of 1*3=3 and purple a weight of 2*4=8, and the odds of choosing yellow were 3/11 (the cell’s row and 4×4 block groups did not impact the odds, since neither yellow or purple had been used in either group yet).
Cells 5-8
The selection of yellow for the 4th cell set off a chain reaction: after it was forced to pick purple for the 5th cell, the 6th cell turned black, with the 6th cell color causing the 7th cell to turn black and the 7th causing the 8th.
The 8th cell finished the smallest distribution group of the 88 groups – the 8 cell central rectangle.
Note that after The Program picked yellow for the 4th cell, the rest of the colors in the rectangle were predetermined, but there was only 1 black cell at that time. These images are a snapshot of what The Program knows at the time – it didn’t know that the 8th cell needed to be purple until it had filled the 5th, 6th, and 7th cells.
Cell 27
By choosing yellow the the cell in the 19th column and 10th row (abbrev: [19,10]), the remaining 11 cells in the 19th column must be either red, blue, or purple, making it the first of many columns to turn to gray.
Cell 30
Cell 30
new color keys:
magenta border: potential failure (conflict)
A cell can only shift one shade of gray darker each time a color is picked for another cell. Further, only the cells that are part the newly colored cell’s distribution groups or adjacency restrictions can get darker.
The two black cells are connected via an adjacency restriction, thus there is a chance that setting the color for one cell will eliminate the only remaining color from the other cell, resulting in a failure.
Even if the black cells weren’t connected, there is still a chance of a failure after filling both of the cells – the first cell could shift a dark gray cell to black which might be connected (and therefore magenta) to the 2nd cell.
With two magenta cells, the failure rate is about 32%, compared to 8% for two black cells that are not connected.
When a failure occurs, The Program throws a fit and then crashes (it also might go backwards and try changing the color of previous cells it assigned a color, depending on it’s mood).
Note that there is no cyan bordered cell – when there are multiple black cells (regardless of their border color), The Program fills them all in at once and then checks for conflicts (when there is a conflict, The Program is fast enough with it’s eraser to clear the cells before The Grid realizes that it’s rules have been violated).
color key clarification:
cyan bordered black cell – a cell with only 1 color choice that is not connected to any other black cell.
Cell 33
The yellow cell completes the first of the 32 4×4 block distribution groups.
Cell 73
The yellow cell [20,12] completes the 4th of the inner most 4×4 blocks, together accounting for 64 of the 73 filled cells.
The Program has stayed within this zone partly because the cells were generally grayer than the rest of the grid, but also because of the 2nd rule of cell selection:
Rule 2 of Cell Selection:
All else being equal – pick the cell that has the most potential to reduce other cell’s choices.
When a distribution group is running out of cells – The Program senses the inevitable black cell(s) that it craves (it really doesn’t like to make choices).
Along with the central rectangle and the smallest ring around it, 6 of the 88 distribution groups have now been completed.
Cell 101
After 8 of the columns have turned gray (including 1 dark gray), the 11th row is the first row to do so. Eight of the 12 filled cells in that row are purple, and the remaining 20 cells must be filled with another color.
Cell 128 (End of 1st Quarter)
With 25% of the cells filled, it’s a good time to take an inventory:
- 9 of the 88 distribution groups are finished: 6 blocks and 3 central rectangles (or rings).
- 60 of the 128 color choices have been forced (black).
- Based on the number of multiple black/magenta cells encountered, the predicted survival rate to this point is 3.6% (if The Program didn’t go have the ability to go back and correct it’s mistakes, which it does, and has done, in order to reach this point).
- Over a third (36%) of the remaining cells are down to 3 or fewer available colors.
Cell 159
Another column shifts to gray, and for the first time fewer than half of the remaining cells are white. White will pop above 50% for one last time at cell 175, before dropping below it permanently two cells later.
Cell 182
Blue overcame 10 to 1 odds and was the choice for C(23,4), causing 6 cells in that row to turn magenta (with a stray black/cyan cell in the column) At 68%, the failure rate under these conditions is twice that of any other single point thus far.
Cell 200
The 17th column is the first to be completed, and there are 4 of each color in the column.
Cell 256 (Halftime)
While the percentage of white has dropped to 44%, it has been relatively stable since first dropping below 50% almost 100 cells ago.
The program has been able to offset most of the expanding gray by filling in several of the gray columns.
And while it doesn’t look all that bad, 63 of the 88 distribution groups remain, and there will be collisions between these groups.
For comparison, this is what The Grid’s predecessor (ID #2197) looked like at the halfway mark:
Now that makes it look easy (which it was, but only in a relative sense).
Satisfied with it’s accomplishments thus far and in no hurry to defeat The Grid, The Program took an extended three day halftime break before resuming the fight (a true statement, explained somewhere else, possibly on this page).
Cell 360
At least one color has been eliminated from all but one of the 16 rows – which have between 7 and 12 empty cells remaining.
Cell 388 (End of 3rd Quarter – 1)
A touchdown of 6 cells – 3 red and 3 yellow – brings the total fill past 75%, with a two point conversion attempt to follow.
Because the rest of the action occurs on the edges of the grid, I’ve grayed out the cells in completed columns but not connected to the current color selection(s).
Cell 393 – (End of 3rd Quarter – 2)
The program has now completed three-quarters of three-quarters of the distribution sets. Only the adjacency rules and a minor bug (see: the stray purple cell in the bottom right) have caused it to stray outside the 5th to 28th columns so far.
The only problem: it hasn’t completed a single row yet, leaving 34 of the 88 distribution groups unresolved.
Cell 412
With exactly 100 cells remaining, there are officially no cells with the original 4 colors available. However the excessive gray felt a bit drab, so I have declared white as the new light gray, and made dark gray a bit lighter than it was before.
Cell 454
The first of 16 rows drops, finally.
Cell 457
The Program has enjoyed relative peace since reaching the 3rd quarter mark (cell 393), as only 17 of the 142 magenta cells encountered were seen in the last 64 cells. This peace however, is about to come to an abrupt end.
While the odds of reaching this point without making any mistakes are astronomically low at about 1 in 100 trillion, The Program has made significant use of it’s eraser to make it here.
The Grid’s Last Stand
Cell 458
The selection of purple triggers three cells to turn magenta.
Magenta cells: 3
Odds of survival: 46.4%.
Cell 461
The Program survives the first blow, but The Grid has countered with double the firepower.
Magenta cells: 6
Odds of survival: 23.5%
Cumulative (starting at cell 458): 9 magenta cells, 10.9% odds of survival.
Cell 467
A wave of blue (and one purple) has set off a bigger wave of magenta.
Magenta cells: 10
Odds of survival: 10.2%
Cumulative: 19, 1.1%
Cell 477
After surviving 10 magenta cells against all odds, 9 more are thrown at The Program.
Magenta cells: 9
Odds of survival: 12%
Cumulative: 28, 0.13%
Cell 486
Another bullet is dodged by The Program. The Grid has only 26 cells remaining but is not out of steam, yet.
Magenta cells: 8
Odds of survival: 17.1%
Cumulative: 36, 1 in 4,350
Cell 494
Sensing danger, The Grid sends half of it’s remaining 18 cells at The Program.
Magenta cells: 9
Odds of survival: 12%
Cumulative: 45, 1 in 36,200
Cell 503
The Program has survived the worst of it, but is not quite done. A failure here, and it would wipe out everything it has accomplished since cell 458 (it does have an eraser, and it can change previous decisions, but it has not had a decision to change since then).
Magenta cells: 2 (+1 cyan-bordered black cell)
Odds of survival: 63.3%
Cumulative: 47 (+1), 1 in 57,180
Cell 506
The smoke has cleared.
Cell 512
The Program defeats The Grid with the same color that it started with, at the cell furthest away from where it began: yellow.
Summary
The Program accomplished a major feat filling in 90% of the cells without violating any of the rules, and then crossed it’s fingers and hoped that everything would fall into place, and it did, handing The Grid it’s first ever defeat in millions of attempts.
The Full Battle
Everything did not fall into place the first time for The Program. It took The Program about 11,000 moves (cell color selections), and liberal use of it’s eraser, to find the solution. The following chart shows the progress made in the first 800 moves:
The red line shows how much of the grid was filled at each move number. The blue circles show the points where The Program fixed a previous mistake so that it could move forward. Every color selection above and to the left of the circled point was erased by The Program.
The magenta line to the left of the first blue circle shows when the first mistake was made, which occurred on the 258th cell that it filled with color. It took 161 moves to find the mistake, with the cells filled reaching as high as 280 before reaching a conflict.
The Program showed rust by choosing the wrong color on it’s first choice coming out of it’s 3 day halftime break. “Oops,” said the Program, during an interview that took place in the fantasy world I live in where programs that I write can talk.
The Program actually had made 4 mistakes before the halftime break, but had forgotten them by the time it resumed it’s task (these required only 25 additional moves, anyway).
More on Mistakes
- Mistakes are sometimes found and corrected in as few as 2 moves – the 2nd mistake in the chart above at cell 345 is an example of this.
- Conversely, there is practically no upper limit to the moves required to identify a mistake.
- The ups and downs between the mistakes are not actually mistakes as a conflict was inevitable regardless of the color choices.
- There is no way to know if a decision was a mistake or not until the grid has been completely filled according to the rules.
It took The Program considerably more moves to complete the last 112 cells:
While there were only 2 more mistakes made in the 4th quarter compared to the 3rd quarter, it took a lot longer to identify them. The progress from the 438th cell to the 440th cell was particularly challenging: It took 4,630 moves to fix the mistake on move 438, and another 3,650 moves to fix the mistake it made immediately afterwards. “I really hate when that happens”, The Program remarked during the interview.
The charts however tell only a small part of the real battle.
The War
The Program made the 1st 256 moves 3 days before it made the last 10000+ moves in order to defeat Grid ID #2213. In reality, there were many more moves made on the 1st day than the last. The War began with the conclusion of a previous war:
Day Zero: A New Alliance
Grid ID #2213’s baby sister, Grid ID #2197 (“La Cuadricula”), is defeated by The Program. For the first time, The Program enlisted the aid of it’s far inferior creator (also known as “The Man”) to defeat a member of the grid family. “I didn’t really need any help, but he was getting impatient”, said the Grid, regarding this alliance. “All he did was suggest that I start over from a different point than I always do (the beginning), and now he’s stealing the credit for all of my effort. If only he gave me the halfway decent hardware that I deserve, he wouldn’t have to wait so long, anyway.”
The different point The Program referred to was cell 380 instead of cell 1 – with the color of the first 380 cells taken from a previous attempt that failed but came close to being successful.
Day One: The War Begins
The Program makes it’s first million attempts at defeating “The Grid”, none of which are successful. A handful of the better attempts are saved for possible later use, with the best attempt reaching 495/512 cells filled before reaching a conflict.
Day Two: Human Intervention
Grudgingly, The Program (still not convinced that it needs a “head start”) agrees to use the best attempts from the last day as a starting point. Most of these retries never made it more than a cell or two further than the original attempt, but there was one exception: A 492 cell attempt that was able to reach 509 out of 512 cells by using the first 360 cells of the initial attempt. Considerable time was spent on further retries of this 492 cell attempt. With a starting point ranging from cell 320 to cell 390, several other retries also reached the 509 cell mark, but none of them succeeded.
“I told you that you got lucky once and that it was a stupid idea to begin with. This is what happens when faulty biological neural pathways interfere with superior micro-circuitry,” a smug Program quipped at it’s creator at the end of the day.
Day Three: Exploring Other Paths
The Program spent most of day three was spent on fresh attempts at conquering ID #2213. One of these reached 498/512 cells – the closest The Program had come to filling The Grid beginning with cell 1. This attempt, along with a couple other attempts that reached 490+ cells, were retried at various starting points. None of these retries made significant progress over the originals.
Day Four: A New Plan
Frustrated with the lack of progress on day three, The Man came up with a modification of the two step plan used to defeat La Quadricula.
First, the two step plan:
Step 1: Have The Program start at cell 1 and make a lot of quick attempts at The Grid. The goal of these attempts is not to defeat The Grid, but rather to save the best attempts, and use one of these to defeat The Grid.
Step 2: Go for the kill: Use the best of the attempts from Step 1 as the seed for longer attempts, with the hope that one of these will defeat The Grid.
For step 2, the starting point is set to a point where most of the decisions have been made, such that it could be reasonably expected that The Program will find a solution, if The Grid’s rules aren’t already impossible based on the previously made choices.
The modification is to this plan is to add another step between step 1 and 2:
Step 1A: The same as step 2, except set the starting point for retries much further back where there are many more decisions to make. The best of these attempts are then used to seed the attempts for Step 2.
| Step | 1 | 1A | 2 |
| Start Cell | 1 | 257 | 361 |
| Max Moves | 10K | 50K | 200K |
| Decisions | 200 | 85 | 45 |
| Max Penalty | 511 | 255 | 151 |
The max penalty
Max Moves determines when The Program gives up and tries again from the start cell.
Max Penalty (total cells minus start cell) is included to emphasize that a wrong decision at cell 256 can potentially lead to a much longer diversion than a wrong decision at cell 360.
The 492 cell attempt from day one seemed like the logical choice to seed the new Step 1A. Based on how close the retries of this attempt came to success, The Man was reasonably certain that the first mistake was made somewhere between cell 256 and cell 360.
The Program, which is much more agreeable for a brief instant following the pressing of one it’s buttons, went along with this “pointless” idea.
464 seconds later, after The Man pressed of one of these buttons, Grid ID #2213 was defeated, well before the new Step 2 had begun.
Next page: The Investigation
The Full Cell By Cell Solution
Below are images for all of the 512 color selections.
Next page: The Investigation