Forbidden ‘For-Loops’ — Math I Swore I’d Never Use
Recently, I’ve been creating a Sudoku solver in Unity to highlight the methods one might use to progress in any given position. The first few basic methods went relatively easily.
- Lone Square: if there is one empty square left in a group, that square is the remaining value
- Hidden Single: if there is only one potential square for the value 4 in a given group, that square must be a 4 regardless of its other possibilities.
The deeper Sudoku methods go, however, the more nuanced they become. At depth, the scenarios in which they’re applicable become more hyper specific, and the result is simply that you get to eliminate a possibility from a square, instead of figuring out its value.
The first methods to have given me pause are called Hidden Triples and Naked Triples, both of which compare a series of circumstances between 3 squares. When programming these same methods for only 2 squares, the rules are staggeringly simple. In Naked Doubles, if two squares in a group have the same two sole possibilities, then no other square in their group can have those possibilities. When accounting for a third square, however, edge cases start to appear. In what can be called ‘jagged’ triples, three squares may not necessarily have the same exact possibilities, but they may still represent the same identical outcome. Take the example below:
Squares d4, e4, and f4 have slightly different possibilities, but there is no outcome in which they don’t collectively become the values 1, 4, and 7. Therefore, no other squares in Row 4 (or the middle box) can be 1, 4, or 7.
As shown above, the addition of a third square becomes problematic because the ways in which you can combine potential variations and still arrive at the same collective result rises exponentially with each added square. Determined to find myself an elegant solution for these triples, I soon found myself drowning in tediously nested for-loops and if-statements that would account for one scenario but disqualify two others.
It wasn’t long before I relented my aspirations of efficiency and defaulted to a tried and true, reliable, and old faithful friend of mine.
Brute Force
Disregarding optimization, the most straightforward approach that occurred to me here went something like this:
- Account for every possible 3 square combination in every group
- Combine the 3 squares’ possibilities into a list
- Reduce the list into only unique instances (rough draft logic)
The dread here sets in when you start to calculate the number of potential combinations there are, for every group, for every 3 square combination:
- At its purest, 9 combinations in sets of 3 is (9*9*9) or 729 passes.
- Since we don’t need a Square to ever be compared to itself, we can reduce this to (9*8*7) or 504 passes.
- The number grows again when you consider this must happen for each of the 9 groups, coming out to 9*9*8*7, or 4536 potential iterations! It even further balloons when considering there are several methods that measure different combinations of 3 or more squares.
Once I added Sudoku logic and saw the method was properly detecting the patterns, I noticed that my brute force method was firing 6 times for every instance of the recognition.
For Row4 and the middlemost Section, you can see that the function is recognizing every possible combination of squares d4, e4, and f4. Wondering if there was a fast and simple way to reduce this repetition, I explained the scenario to ChatGPT, and in a rare instance of genius, rather than insisting to me that the word ‘strawberry’ has to r’s, it essentially told me “here’s something you can do instead of declaring the duplicate checks they way you are”.
Suspicious and interested, I plugged in its suggestion to find that the new iteration count would be 84, which immediately seemed way too low. What I didn’t see at the time was that 504 / 6 = 84, and 6 was the number of instances my method was firing when I only needed one: a perfect reduction. I asked for a bit of explanation, but the AI kept repeating that this was part of the binomial coefficient formula.
Optimization
I don’t relish taking advice that I don’t understand, because it’s not a good way to grow, and because you have no way of knowing when that advice might be wrong, contextually or in general. So in my default suspicion, I spent some time trying to learn however a human could have figured this out, and however this gibberish formula could equate to a for-loop structure.
First, I listed every iteration of (i, j, k) that occurs.
When visualized, it becomes apparent what the for-loop structure is doing. Pick any set of 3 in the table above. Essentially, every successive number is always larger than the one before it (j = i+1, and k = j+1). Given the previous rule, a number can therefore never be higher than the maximum minus the number of successions (i < n-2), i.e., the maximum of (i) is the number of objects to choose from (n) minus the number of for-loops that it contains, or the amount of numbers that will follow it. Given that successive numbers must always be larger, we can never start at 8, because 8, 9, 10 chooses a number that was not in the available choices of (1–9).
To dive a little further, I wanted to visualize the pattern of which numbers were being qualified/disqualified and in what order.
It’s important to note that while this visualization displays number combinations, the numbers are arbitrary and can represent anything. This can be done for all letters of the alphabet for instance, or more practically, imagine 50 players competing in a 3-man (1v1v1) tournament, and every possible match must be played before the results are tallied.
So it’s understandable what the for-loops are doing and why this is effective, but how did a human being ever equate the formula to a programmatic for-loop structure? Some of this can be gleaned from breaking down the portions of the nCk formula.
You can see the original iteration count (504) on top and the amount of times each combination will appear (6) on bottom, which comes out to the 84 unique combinations disregarding of order.
As for how a human could ever equate this to the for-loop structure, that’s something in which I could only partially recognize the patterns. In programming you must often either accept a partial understanding and move on in hopes that the rest will come at a later time, or you must bid farewell to your productivity rate. As to the rest, for now, I have to accept that those whose shoulders I’m standing on just had a better understanding of math and combinatorics than I.
Well, thanks for those giants.