Algorithm X

This Will Be Important Later

You may have already finished all the Sudoku puzzles without any problem-space reduction. I strongly suggest you consider following through with what I'm about to propose and the reason is because of Killer Sudoku Solver and Killer Sudoku Extreme Challenge. 100% of any effort you put forward on this exercise will benefit you when you solve the Killer Sudoku puzzles, which begin with all the same rules as Sudoku and then add a few details you can tackle later.

Initial Challenge - Lone Singles

My initial challenge is for you to implement the reduction technique covered in the previous pages. On the website Learn-Sudoku.com, this technique is referred to as Lone Singles. For any cell that has been reduced to a single candidate, that value may be removed from the candidate lists of all other cells in the same groups. With just this one reduction technique, you can achieve the following results on each of the CodinGame Sudoku puzzles...without any backtracking.

Level 2 Challenge - Hidden Singles

Going back to Learn-Sudoku.com, let's add another fairly easy technique, Hidden Singles. A hidden single is a cell in a group that has one candidate that does not appear in the candidate list of any other cell in the group. Because this candidate only appears in a single cell in the group, it is known where the candidate belongs. Adding this one additional basic technique will improve your results.

Ultimate Sudoku Logic Challenge

Learn-Sudoku.com has several more reduction strategies. Can you implement enough to solve every traditional Sudoku puzzle with logic alone? I will keep my own progress updated in a table at the end of this playground. If you take on this challenge, I do have one suggestion for your data structure. I have found it helpful if each cell has pointers to the groups to which it belongs. Conceptually, the object model has one small addition shown below.

As the SudokuGroups are being filled with SudokuCells, it is easy enough to give each cell 3 pointers, one to each of the groups where it is a member. I have used a named tuple to hold these three pointers. In the constructor, the new groups attribute is initialized to None.

CellGroups = namedtuple('CellGroups', 'row col box')

class SudokuCell():

    def __init__(self, value: str, all_possible_values: str):
        self.value = value
        self.candidates = set(all_possible_values) if value == UNKNOWN else {value}
        self.groups = CellGroups(None, None, None)

As the groups are being built in the SudokuSolver constructor, give each cell a tuple of pointers to the groups to which it belongs.

        for row in range(size):
            for col in range(size):
                box = row // box_size * box_size + col // box_size
                cell = self.grid[(row, col)]

                rows[row].cells.append(cell)
                cols[col].cells.append(cell)
                boxes[box].cells.append(cell)

                cell.groups = CellGroups(rows[row], cols[col], boxes[box])

Solving Logic Puzzles Logically

Many Sudoku puzzles can be solved without making any guesses. Click here to see my progress toward solving as many logic puzzles as possible, strictly with logic, no guessing and no backtracking.