Sudoku Grader

If the Sudoku grading program runs through all algorithms without being able to apply any of them when the grid is not yet solved, there is a substantial issue at hand. It is important to know if the puzzle actually can be solved. Because the grading algorithm does not concern itself with strategies more difficult than Swordfish, it is paramount to know at least that the puzzle has a solution in order to differentiate between giving the highest strategic difficulty score and alerting the user that the puzzle is in fact impossible. To solve this requires a new solving technique: brute force.

Programming the brute force solving technique can be done in many ways, some of which will run quicker than others. A decent brute force technique that, while not the fastest available, is recursive backtracking. The idea behind this approach is to take the grid, guess a value for the first spot, and if the grid is still valid, guess a value for the next empty spot until the grid is filled (Jensen 1). If the grid is not valid, then another guess for the value will be inserted into the empty space. If no guesses result in a valid grid, then the guessing continues at the previous empty cell in the same manner. This process repeats itself in a recursive fashion, backtracking whenever it creates an invalid grid. If the grid is never filled, then the puzzle cannot possibly have any solutions. Alternatively, editing the logic slightly, one can also determine if a puzzle is impossible because it has multiple valid solutions. With a means of finding the puzzle’s strategic difficulty, it is time to begin constructing the grader’s scale.

The final common advanced strategy is named Swordfish. Swordfish works like X-Wing, except that instead of looking for a candidate occurring only twice in two rows or columns, Swordfish is looking for a candidate that occurs two or three times in three columns, in the same three rows. Again, the idea is that wherever this candidate actually occurs in each of the three columns, it will set off a chain reaction that will force the candidate into a spot in each of the shared rows (Penny Publications 6). The strategy works not only for columns against rows, but also rows against columns. Figure 10 demonstrates this perfectly. First of all, note that in the second, sixth, and fifth rows the candidate 6 occurs twice. These occurrences have been highlighted. Because between the three rows, all of the candidate occurrences are limited to exactly three columns, Swordfish can be applied. Swordfish works because it is known that one of two cells in the rows in question will contain a 6, and the cell that gets the 6 will force a cell in another row but the same column not to be a 6, dictating a cell in that other row to have the value 6, in turn setting the location of the final 6 in the last final row. Because the chain of events, no matter which cell is initially determined to be 6, will lead to a 6 being a value in each column in one of the highlighted cells, other cells in those columns but not in the three rows containing 6 as a candidate can have that candidate removed, as indicated with red x-marks in the example. This is not a strategy for the faint of heart.

Fortunately, Swordfish is simpler to implement and utilize than it is to fully understand. Looping through all possible combinations of three rows or three columns and then all candidates 1-9, the algorithm will check to see that all three rows’ cells containing the given candidate number exactly two or three cells and are members of the same three columns. At this point, the candidate can be removed from each column in question in cells outside of the three rows. That is all it takes to program this final Sudoku strategy. But there is still a slight problem.

Up until this point, all of the solving techniques have been fairly basic and straightforward. But there are a couple of more advanced strategies that are common enough that it is worth including them in the grading system. The first of these strategies is called X-Wing. X-Wings are built upon the premise that if in two separate rows a certain candidate appears only in the exact same two columns, then that candidate can be removed from all other cells in that column (Penny Publications 4). The strategy also works looking for the two same rows from the two same columns. Figure 9 provides an excellent example of an X-Wing situation. In the 5^th and 8^th columns, the only cells that have 5 as a potential candidate have been highlighted. Because these highlighted cells are in exactly two rows, X-Wing can be applied, and 5 can be removed as a candidate from three cells in those rows, as marked with red cross-outs.

While certainly a more advanced algorithm, X-Wing does not prove significantly more difficult to program. The straightforward approach to take is to loop through all possible combinations of boxes of initial x-position of 1 through 8 and initial y-position of 1 through 8 and terminal x-position between the initial x and 9 and y position between the initial y and 9. These will cover every possible way for an X-Wing to occur. With each box bounded by initial and terminal x and y positions, it is now a matter of determining whether the conditions for X-Wing apply. To do this, the computer simply goes through each candidate in the top left box, and checks to see if this candidate occurs only twice in either both rows or both columns. If it does, it then verifies that the candidate occurs in the corners of the box, and performs candidate removal if so. That takes care of solving all X-Wings. But there is one more peak to climb.

Behind Naked Subsets, the next most difficult solving strategy is Hidden Subsets. This strategy is reminiscent of Naked Subsets, but is based on the exact opposite philosophy. The idea is that if a group of cells of size x in a row, column, or block is the only group of cells to contain a certain x candidates, though not necessarily only those candidates, it is a hidden subset (Armstrong). Within this hidden subset, all candidates can be removed that are not one of the x candidates in question. This sounds a lot like Naked Subsets, but Figure 8 helps to display the difference. The highlighted cells are the only cells to contain 1, 6, or 8 in their candidate sets. Because there are exactly three cells fostering these values, there is a hidden triple, and any other candidate values in these three cells can be eliminated. The middle-left cell now only contains 1, 6 and 8 as candidates, the bottom-center 6 and 8, and the bottom right 1, 6, and eight.

Programming Hidden Subsets, unsurprisingly, is very similar to programming naked subsets. Again, a common framework will be applied to different subset sizes. The strategy will again loop through all columns, blocks, and rows, and obtain all possible combinations of x cells in these columns, blocks, or rows. The difference is that now, of all of these combinations, the algorithm is going to find the number of candidates in these x cells, removing duplicates, and compare this to the number of candidates outside of the x cells, removing duplicates. If these two numbers subtracted equal x, then a hidden subset has been found. Now it is just a matter of seeing if any candidate removals can be made in those x cells. If none can be made, then it is time to move onward to the truly advanced strategies.

Naked Subsets is the next most difficult strategy. Naked subsets come in a few varieties: Naked Pairs, Naked Triples, and Naked Quads. All three use the same logic, but Pairs is typically easier to use and spot than Triples and Quads.

The idea behind a naked subset is that because in a row, block, or column x cells share a combined candidate set of size x, all candidates in that subset may not occur elsewhere in the row, block, or column. For instance, in Figure 7, the candidates 5 and 7 occur in the top-left and bottom-center cells. This means no other cells in the block may contain a 5 or a 7 in their candidate set, as between these two cells, 5 and 7 will be used. 7 can be removed as a candidate from the top-center cell and the middle-left cell. This example also depicts a naked triple, though it may be difficult to see. To have a hidden triple, one must have three cells that share three candidates. It is not necessary for all three cells to have all three candidates. All that is needed is a candidate set of size 3 when combining the candidate sets of three cells and removing duplicates. Adding the candidate sets of the top-right, middle-right, and bottom left cells one gets {1,2,3} + {1,2} + {1,3) = {1,2,2,3,3}, and removing duplicates, simply {1,2,3}. So between three cells, there are exactly three candidates, so it follows that those candidates must be used between those three cells and thus cannot be in any other cells in the block. 1 can be removed as a candidate from the middle-left cell.

Each size of naked subset should be represented as its own separate strategy, but these strategies will all share the same common framework. First, the programmed algorithm should loop through all columns, rows, and blocks individually. While looking at each row, column, or block, first all possible subsets of a given size sharing that same number of candidates must be found. To accomplish this, one can find all possible combinations of x empty cells, and then check to see which of these combinations have a combined candidate set with x unique candidates. With all of these combinations found, the program may then proceed to check if these naked subsets of size x allow for any candidate exclusion to take place. If no candidate exclusion ever takes place, then it is onward and upward to the next strategy.

With all of the value-setting strategies covered, it is now time to delve into the candidate exclusion strategies. The most basic candidate exclusion strategy that the program will utilize is Locked Candidates, which has two flavors. Rather than simply call the strategy Locked Candidates, sometimes the individual cases, Block-Row/Column interactions and Block-Block interactions, are named.

The Block-Row/Column Interactions strategy concerns itself with pinpointing a certain candidate to a single row or column of a block. If this candidate can only appear in this row or column, then outside of the block in that row or column one can eliminate that candidate. Figure 5 depicts a Block-Column/Row interaction. Because in the middle block, 5 may only occur in the blue spots, and these spots are in the same column, it follows that 5 cannot be a candidate for any of the highlighted squares.

To program this strategy, a slightly different approach can be taken. For each number 1-9, one can look at each block. By finding all cells that contain the number in that block, and determining if all of these cells share a row or column by comparing the cells’ positions, the strategy can be applied. If a Block-Row/Column interaction is found, then the program searches through all of the cells in the row or column the rule is being applied to, and if the cell is not in the block and contains the candidate, the candidate is removed. If no candidates are removed, despite having found a Block-Column/Row interaction, it will not count as an application of the strategy because no headway has been made, and solving will continue.

The next form of Locked Candidates, Block-Block interactions will then be used. This is a very similar strategy, except that it deals with two blocks. The idea behind the strategy is that if between two of three blocks in the same row or column, a certain candidate only occurs in two rows or columns, it can be eliminated from those rows or columns in the third block. Figure 6 demonstrates this for the candidate 5. In the first two blocks, 5 can only be a candidate in the cells with blue circles, which are limited to two rows, so this means 5 cannot be a candidate in these yellow columns in the third block. One can describe the strategy using an alternate method as well. If in any row or column, a certain candidate may only appear in one block, then in that block the candidate cannot occur anywhere but in that row or column (Armstrong). Looking at figure five again, one can see that in the third row, the only cells where 5 may occur are the red cells, which all share the same block. This means that being in the same block, the yellow cells cannot have 5 as a candidate.

With this new description of Block-Block Interactions, it becomes somewhat easier to program. The program need only look through every number x 1-9 and in every row and column, check to see if x occurs as a candidate only in a single block. This is accomplished by comparing the position of all cells in a given row or column able to contain x and verifying that they are in the same block. If no removals are able to be made from that block, then the strategy continues until it can remove a candidate or has exhausted all possible row/column, and candidate combinations. If it exhausts all possibilities, then it is time to move on to a more difficult strategy.

Now the final value-setting strategy remains: Hidden Singles. The Hidden Singles strategy says that if a cell in a given row, column, or block is the only one to contain a candidate x, then the cell’s value must be x. Slicing and Slotting is a specific case of this strategy. For example, in Figure 4, although by simple candidate exclusion the highlighted cell may contain all values except for 5, 2, 1, 4, and 7, because it is the only cell in the block with 9 as a candidate, its value must be 9. As long as only one cell in a row, block, or column has a certain candidate available, that cell’s value must be that candidate’s value.

With the Sudoku framework described earlier, implementing this strategy is rather simple. For each empty cell in the puzzle, the program can compare the candidates of that cell with the candidates of all of the empty cells in that cell’s row, column, or block. For each of the cell’s candidate x, the program checks if any of the other cell’s candidate sets contain x, and if not, sets the cells value to x. That is all there is to it.

The next easiest strategy is Singles. This relies on logic similar to Simple Singles, except that instead of looking at the row, column or block separately, it looks at all three together. A blank cell can be any integer from one to nine. If another cell in its row, column, or block contains a certain value, you can remove that value from the empty cell’s set of candidates. This technique can be called simple candidate exclusion. If after simple candidate exclusion or another, more advanced candidate exclusion method to be covered later, only a single value x remains as a possible candidate for the cell, one can set that cell’s value to x. Figure 3 illustrates this. The highlighted cell cannot be a 5, 4, or 6 because these values are all in the same block as that cell. Furthermore, the cell cannot be an 8 or a 9 because those values are already in the same row as that cell. Finally, the highlighted cell cannot be a 2, 1, or 3 because these values are used in the same column. This leaves the only possible value to be 7, so the highlighted cell’s value is 7. Note that Simple Singles is actually a special case of this strategy.

It is in programming this strategy that the logical structure for a Sudoku grid’s representation emerges. First of all, the grid itself must contain 81 cells. It must have 9 rows, columns, and blocks, each containing 9 cells. Lastly, and most importantly, each cell must have a set of possible candidates and a position. With this structure set, the strategy can begin to be implemented. Once, when the program is first run, simple candidate exclusion should be applied to all empty cells. To do this, the program finds the row, column, and block a cell is a part of using the cell’s position, and then loops through every filled cell in that row, column, or block and keeps track of which values theses filled cells hold. Every unused value is added as a potential candidate of the cell in question. Now, with the simple candidate exclusion complete, each cells candidate set is filled. It is important that simple candidate exclusion is performed only once, because performing it again, as described above, will undo any candidate exclusion performed by more advanced methods.

With all of this back work done, it is time to perform the actual Single strategy itself, and it is pleasantly simple. If an empty cell’s candidate set contains only one value, then that cell will be given that value. In order to keep all empty cells’ candidate sets consistent, after setting the cells value, the cell’s value will be removed from all cells in the same row, column, or block’s candidate set. This candidate removal occurs whenever a cell’s value is set, be it by the Simple Single, Slicing and Slotting, Single, or Hidden Single strategy.

Although it is not conceptually the next-easiest strategy, Slicing and Slotting is the second-easiest strategy to spot and use. Slicing and slotting is looking for all occurrences of a certain value, and seeing if the locations of the value throughout the grid force a cell to be the only one in its block to be able to contain that value. Figure 2 illustrates this quite well. Because the 2 cannot occur in the first and third columns, and in the third row, and there is only one remaining empty cell outside of these rows or columns in the first block, the 2 must occupy that empty position.

Programming Slicing and Slotting is a somewhat less straightforward matter. One effective way to do so is to loop through all empty cells, and within this loop go though all values x not assigned in that cell’s block. Now, check all rows and columns going through the block for each of these x. If the columns and rows, combined with the already filled cells, account for all cells in the block but that empty cell, then that cell’s value can be set to x, and the strategy has completed successfully. Otherwise, the strategy continues until it finds a cell on which to apply the strategy, or it moves on to the next solving technique.

The first and easiest strategy to attack is certainly Simple Singles. This strategy relies on the basic rule of Sudoku, which states that each row, column, or block must contain the complete set of integers one through nine. This means that if a row, column, or block already has eight of nine cells filled with a value, it follows that the unfilled cell must contain whatever value the other eight cells do not. For example, in Figure 1, the bottom right cell must contain nine because it is the last remaining unused value in the block. Programming this strategy is straightforward. One can go through each empty cell, and if by looking at the row, column, or block it is the only empty cell, then assign it the remaining value.