Having a discussion with some friends one day about the easiest way to verify whether or not a completed 9×9 Sudoku puzzle is valid, meaning that all rows, columns and 3×3 sub-grids contain all digits from 1 to 9, I began formulating a way to solve these puzzles using a computer. Within that same week I inevitably sat down and began coding it out.
Certain that this very program had been written by CS students the world over, I wanted to add something else to this project to make it just a little more difficult. So, motivated by the IOCCC, I decided to try my hand at obfuscated code and solve the problem in as few lines as possible.
The algorithm I developed was simple. Starting at tile x, a list x is generated containing all of the possible values tile x could assume without interfering with its relevant non-empty neighbors, where neighbors refers to tiles in the same row, column and sub-grid as tile x. If tile x has a predefined value that must be solved around, that is tile x‘s only valid value. Tile x then assumes a value, the first and lowest numerical value contained in list x or its predefined value. The process is then repeated for tile x+1.
This is done for all 81 tiles (0 to 80), 0 representing the top-left tile and 80 representing the bottom-right tile. Once list x has been generated for tile x and tile x has assumed the first value in that list, the program recursively calls for the generation of list x+1 and the assignment of tile x+1‘s value.
If no values can be generated for arbitrary tile x then then tile x-1 moves on to assuming the next value in list x-1. And we try again generating list x for tile x. If, however, list x-1 were to run out of values for tile x-1 to assume, tile x-2 would assume the next value in list y-2. This is the recursive nature of the algorithm. Whenever arbitrary list x runs out of possible values that tile x could assume, or is unable to generate any valid values, that means that the list of values that the program has assumed to be correct so far (ie tile 0 to x) is not going to work and we must go back to the last tile that has any remaining values in its list and start from there.
If we run out of values in list 0, this means that the Sudoku puzzle is unsolvable. On the other hand, if a valid list x is generated for tile 80, this means that the combination of assumed values for all 81 tiles play nicely and we have found a solution for our Sudoku Puzzle.
So what did I come up with? 20 lines of mumbo jumbo c that accepts a Sudoku puzzle in the form of a 9×9 grid and spits out the first solution it comes up with
int g[81][11];
int tile(int x)
{
int a;
for(a=1; a<10 && x<81 && !g[x][10]; a++)
g[x][a] = 1;
for(a=0; a<9 && x<81 && !g[x][10]; a++)
g[x][g[x/9*9+a][0]] = g[x][g[x%9+9*a][0]] = g[x][g[x%9/3*3+x/27*27+a/3*9+a%3][0]] = 0;
for(a=0; a<10 && x<81; a++)
if(g[x][a])
{
g[x][0] = a?a:g[x][10];
if(tile(x+1))
return printf(x%9?"%d ":"%d \n",g[x][0])|1;
}
g[x][0] = g[x][10];
return x>80;
}
int main()
{
int x;
char c[9];
for(x=0; x<81 && (x%9 || scanf("%s",c)|1); x++)
g[80-x][10] = g[80-x][0] = (c[x%9]-48);
return tile(0);
}
The code, being obfuscated and all, is pretty hard to follow. Some people make a sport out of understanding obfuscated code completely out of context. It’s definitely a great way to excerpter your code comprehension skills and I definitely recommend trying to figure out exactly what the heck is going on inside this little snippet of code by yourself. But if you don’t quite feel like fumbling through some high schooler’s code, don’t fret. I will be dissecting my code line by line and explaining what it all does.
Before we dive into the main method. let’s take a look at the top line.
int g[81][11];
This is essentially our Sudoku puzzle. It holds a list of 11 numbers for each of the 81 Sudoku tiles, and is a more literal example of the tile xand list x constructs I was referencing in the algorithm explanation. So how exactly is this data organized? It’s simple actually. It contains the only 11 numbers I need to know in order to solve any Sudoku puzzle for each of the 81 tiles. These numbers are:
g[x][ 0] – the current value of tile x assumes.
g[x][ 1] through g[x][9] – a boolean value representing whether or not this index is a valid value which tile x can assume.
g[x][10] – the value that tile x must assume. ie if you are solving a puzzle where the top-left most tile must be a 6: g[0][10] = 6. If the top-left most tile was blank and the current value must be solved for: g[0][10] = 0.
Now lets head over to the main method and start exactly where the computer starts.
int x;
char c[9];
for(x=0; x<81 && (x%9 || scanf("%s",c)|1); x++)
g[80-x][10] = g[80-x][0] = (c[x%9]-48);
This is the loop that reads the puzzle in from the console and stores the appropriate data in our g[][] structure. scanf("%s",c) is called every time y is an even multiple of 9, so the buffer c[] is filled at the beginning of every new line, and then 9 iterations are spent copying the data from the newly filled buffer c[] over to the appropriate position ing[][].
(c[x%9]-48) takes the character value and returns the appropriate integer value. With 48 being the ASCII value for '0' simply subtracting 48 does this rather easily.
g[80-x][10] sets the 10th number in list x to the integer value returned by (c[x%9]-48). Remember, g[x][10] holds tile x‘s predefined value, with a value of 0 meaning tile x must be solved for.
g[80-x][0] sets the first value in list x to the integer value returned by (c[x%9]-48). Remember, g[x][0] contains the current value that tile x is assuming. If tile x has a predefined value, then that is the only value that it can ever assume, so it is set right off the bat. However, if g[x][10] contains a value of 0, meaning that tile x‘s value must be solved for, then then current value stored int g[x][0]doesn’t’t matter and will be altered shortly.But what is with the whole [80-x] thing? Well, the for loop is essentially reading the input grid from top-left to bottom-right and storing the values linearly into our g[][] structure. Except the [80-x] is fooling with out indexes and inserting these values into our g[][] structure backwards. Meaning the top-left value in our grid is now position 80 and the bottom-left value is our starting index, 0. But why are we doing this? Remember, the algorithm is recursive, as it solves the puzzle, it is crawling deeper and deeper inside of its self, building up a stack trace. Once a solution is found, it starts popping off method calls and returning to the root method. As it is doing this, it stops real quick to print out the value that it has found to be correct for that method call (read: tile). So what does all this mean? It means that it prints out the solved grid backwards! So, creating the grid backwards means it will print out the solution exactly how we want it.
I would like to point out that this could have been simplified had I chosen to accept input as an argument, but I wanted this program to actually be somewhat functional. Who wants to type in an 81 character Sudoku puzzle all in one line?
return tile(0);
This is the method call that starts solving our puzzle. It is a recursive function and i’m telling it to start by solving tile 0, the now the bottom-left corner. The only reason I am returning its value back to the operating system it to make my compiler stop whining about how main() isn’t returning a value.
int tile(int x)
Okay, let’s dive into the magical method tile(). This is the method that does the solving and exactly how it accomplishes this is pretty straight forward. Upon entry, a list for tile x is generated of all the possible values that tile x could assume without interfering with any of its neighbors values. It then assumes that first value in that list. If tile x has a predefined value, no list is generated and its assumed value is still set as its predefined value from when g[][] was generated earlier. After assuming a value (or keeping its assigned value as it’s assumed value) it calls itself, this time solving the next tile in the puzzle.
tile() returns a boolean value. 1 for success, 0 meaning it was unable to assume a value. Each time tile() calls itself attempting to solve for the next tile it checks weather or not the next call was successful or not. The only way for a tile() to return successful is if it was able to assume a value for tile 80, meaning it found a combination of numbers that solves the puzzle all the way to the last tile. Once a value for tile 80 is assumed. the tile() method call responsible prints out its value and returns successful. method call 79 (who called method call 80) sees that method call 80 has found the last puzzle piece, prints out its value and returns successful. Method call 78 sees that method call 79 sees that method call 80 found the last puzzle piece and prints out its value and returns successful. This happens all the way up the stack, until it reaches call 0 which returns successful and the program exits. Now do you understand why I had to put the values in backwards, it printed out starting from method call 80
So now you know what happens right as the algorithm nears completion. But there are tons (hundreds) of failures down the line of method calls. tile() can return 0 for failure, I did’t implement this just for fun. This does’t mean that the algorithm is flawed, well I guess that depends how you define ‘flawed’. The algorithm is based on trial and error, tile() returning unsuccessful just means that the program didn’t guess the correct values for all 81 tiles in a row.
So, what does it mean when arbitrary call x returns unsuccessful while trying to solve tile x? It means that there are no more values that it can assume without interfering with any of its neighbors, it ran out of values in list x or list x came up empty. Say we got down to call 6, it generates a list of values tile 6 can assume without interfering with its neighbors, assumes the first value in that list 6 and makes the next call for tile() to do the same for tile 7. Method call 7 is unable to come up with any values that tile 7 could assume without interfering with any of its neighbors, so method call 7 returns unsuccessful. Call 6, who invoked call 7, sees that call 7 returned unsuccessful and assumes the next value in list 6 and invokes call 7 again. But if call 6 ran out of numbers to assume in its list it too would return unsuccessful and then call 5 would have to assume the next value in list 5 and invoke call 6 again. This will happen all the way back up the chain of calls until it gets to a method call who has another value in its list it can assume and execution starts over from that point. The sort of back and forth motion can happen several hundred times while finding the solution for a single puzzle. However, if call 0 returns unsuccessful, that means the puzzle was unsolvable. There is no one called before call 0 to choose a different value so call 0 to try again.
Alright, lets see how tile() does all of this.
int tile(int x)
The first thing we notice is that tile() returns a boolean like I mentioned earlier. 1 for success, 0 for failure. It takes one parameter, int x, x denoting which tile the call is going to solve for.
int a;
This is just the declaration of the variable that is used in all three for loops inside tile(). c does’t like us declaring variables inside the first parameter of for loops.
for(a=1; a<10 && x<81 && !g[x][10]; a++) g[x][a] = 1;
Okay, our first for loop, with index a as mentioned earlier. Right now, only pay attention to the first conditional in the second parameter and this is simply a for loop that counts from 1 to 9. But what is it doing with these values? Well if we look at the second line we can tell that it is setting the index 1 through 9 in the list for tile x to 1. If we remember what all of the index mean we can tell that this is marking all values from 1 to 9 as possible values that tile x can assume. Alright, before I explain what the other conditionals mean, let’s take a look at the next chunk of code
for(a=0; a<9 && x<81 && !g[x][10]; a++) g[x][g[x/9*9+a][0]] = g[x][g[x%9+9*a][0]] = g[x][g[x%9/3*3+x/27*27+a/3*9+a%3][0]] = 0;
Again, only paying attention to the first conditional in the second parameter of the for loop, this is just a loop counting from 1 to 9 with an index of a. So if we look at the second line, which is being iterated, this is where everything happens. The previous loop went through and marked ALL values for tile x as possible values which can be assumed. This loop goes through and marks off all of the values which cannot actually be assumed with a 0. So after this loop, the values left marked with a value of 1 in list x can be assumed by tile x. If we break the bottom line up into three lines it becomes a little less intimidating.
g[x][g[x/9*9+a][0]] = 0; g[x][g[x%9+9*a][0]] = 0; g[x][g[x%9/3*3+x/27*27+a/3*9+a%3][0]] = 0;
Okay, so this is the same code as before, just broken up in to three lines. The first line is responsible for marking off all values on the same row as tile x that are already being assumed by other tiles as unassumable. The second line does the same except for tiles on the same column as tile x. The third line does this for the 9 tiles inside tile x‘s 3×3 sub-grid and is a little bit more complicated.
I’m not going dive into exactly how the code does what it does, but I will explain the algorithm. Lets just focus on the first line, who marks off all assumed values on the same row as tile x as unassumable. Every tile on this row (or the whole grid for that matter) has a value ranging from 0 to 9, 0 meaning that the tiles final value must still be assumed. As we are iterating through all 9 tiles in tile x‘s row we grab each tile’s currently assumed value and mark that index in list x as 0 (unassumable). So obviously if there is a tile with a value of 5 on our row we cannot use that value, so we mark index 5 in list x as unassumable. But what about tiles with a value of 0 (undetermined)? well, they have no affect on us (or anyone else) because they are not actually assuming any value yet. So, we come across a tile with a value of 0 (undetermined), our code is going to mark index 0 in list x as 0 (unusable). Well, this just marks tile x‘s currently assuming value as 0, marking tile x as unassumed, which it already is.
Okay remember how I said to ignore the last two conditions in the second parameter of our for loops? Well it’s time to take a look at what they actually do. x<81 && !g[x][10], these two conditionals are essentially like putting the for loops inside an if statements because these values are never affected by the value of a. These two for loops and their combined process of determining what values tile x can assume only need to run if x<81, we are not at or past tile 81, meaning we are off the gird and !g[x][10], list x index 10 has a value of 0 meaning that tile x‘s value is not predetermined.
for(a=0; a<10 && x<81; a++)
if(g[x][a])
{
g[x][0] = a?a:g[x][10];
if(tile(x+1))
return printf(x%9?"%d ":"%d \n",g[x][0])|1;
}
Now that we know what values we can assume, its time to start assuming them one by one in an effort to find one that works.
for(a=0; a<10 && x<81; a++)
Again using a as our index we have a for loop that counts from 0 to 9. Note the second conditional in our for loop, this loop also only runs if we are on the grid (tile 80 or less).
g[x][0] = a?a:g[x][10]; if( tile( x+1 ) ) return printf(x%9?"%d ":"%d \n",g[x][0]) | 1;
This code from inside the if statement is execute for all values of a 0 through 9 where list xindex a is non zero.
g[x][0] = a?a:g[x][10];
This sets g[p][0], the value tile x is currently assuming. If a equals 0, meaning index 0 for list x is be non zero, meaning that tile x has a predefined value that is MUST assume. If tile x has a predefined value then a list of possible values to assume was never generated and this code will only be run once since. If, however, a has a value greater than zero, meaning that tile x has no predefined value and a is a value that can be assumed by tile x, we set a as the value that tile x is currently assuming
if( tile( x+1 ) ) return printf(x%9?"%d ":"%d \n",g[x][0]) | 1;
Now that we have an assumed value it’s time to try it out by solving for the next tile and seeing if it returns successful or not. We do this by calling tile( x+1 ) inside of an if statement. Note the x+1 in tile( x+1 ) is calling for the solution of the next tile. If this call returns successful that means that all the way down the line of calls, call 80 found a solution for the last tile and we are now shooting back up the chain of calls (stack) and each tile prints out their assumed value and returns successful letting its parent call know to do the same.
return printf(x%9?"%d ":"%d \n",g[x][0]) | 1;
This is the code executed when the child call returns successful. It’s basically a fancy way of printing out the assumed value and jumping to a new line if the tile is a multiple of 9, creating a 9×9 grid. The | 1 on the end is to ensure that printf(), a void method, return a value of 1 representing a successful execution.
So what happens when the tile( x+1 ) child call returns unsuccessful? we keep on iterating through out list of values, assume the next one and call tile( x+1 ) again. If we run out of values to assume on our list we exit the for loop and jump to this bit of code
g[x][0] = g[x][10]; return x>80;
This block of code will execute under two, non mutually exclusive, conditions. If and arbitrary method call to tile() runs out of values to assume we will first reset its assumed value to its original using the first line. If we have made it to the end of tile()‘s method body and x has a value less than or equal to 80 that means we haven’t found a value for tile 80 yet and therefore must make our way back up the chain of method calls and try again from that first tile that can assume another value. Remember how the last three for loops had the x<81 conditional that acted like an if statement? Well this is where that comes into play. If tile() was executed with a value of 81, meaning that tile 80 found the last puzzle piece and the executed for the solution of piece 81. tile() is smart enough to know that it is only solving for 81 pieces and doesn’t execute any code when told to solve for a piece after piece 80. So it jumps right to the end and returns successful. It realizes that if you are calling for the solution of piece 81 that you have found all of the pieces and therefore have completed the puzzle. This sets off the chain reaction that shoots up the chain of method calls and causes everybody to print out their assumed value.
Now that you hopefully understand how everything works, it time to have a little fun. Here are three of the worlds harders Sudoku puzzles for you to try out, the code should solve each of them in a fraction of a second.
100007090 850002400 005300000 030020008 720000009 800000020 009600500 004000000 070010500 005300900 000107002 400005300 010080002 305000900 010070006 600004000 040000000 003200080 300000010 000080070 060500009 040000007 017000000 004000030 007000300 000036040 000009700 http://reidhoruff.com/request.php?url=obfuscated_sudoku
<i>cu Lì!</i> 