Solving Sudoku Puzzles Using Logical Candidate Methods

In this article, I describe a basic algorithm that attempts to solve a sudoku problem using four main logical methods.  Sudoku problems can be solved using brute-force and back-tracking algorithms, however I decided I wanted to base my algorithm on logical techniques rather than guessing. This approach does not guarantee a solution, but when its techniques have been exhausted and the puzzle is still not solved, a backtracking algorithm can be used to finish the puzzle in perhaps a more efficient amount of time than a backtracking algorithm alone could.

Principles

Easy sudoku puzzle with 30 clues
Easy sudoku puzzle with 30 clues
  • The sudoku puzzle is divided into 9 rows, 9 columns, and 9 3x3 boxes.

  • A line is defined as a row or column of 9 squares.

  • The parent containers for a particular square are the row and column lines that the square lies on and the box that the square is part of.

  • One and only one of each integer in the interval [1, 9] is present in each row, column, and box.

  • The certain value of a square is the number that must be present because it has either been defined at the start to be in this position or all the other candidates for this position have been eliminated.

  • The candidates for a particular square are the possible values for this square as a consequence of the current certain values.  These are often represented using pencil marks when the puzzle is solved by a human.  The set of candidates for the current square will be denoted as X.

The following function, n(a, S), is also defined, which takes parameters a, an integer in the interval [1, 9], and S, a collection of the candidate sets for each square in a collection of squares, and returns the number of squares in S for which a is a candidate:

\[ n(a, S) := \sum\limits_{s \in S} \chi_s(a) = \sum\limits_{s \in S} \left\{ \begin{array}{ll} 1 & \mbox{if } a \in s \\ 0 & \mbox{if } a \notin s \end{array} \right. \]

This could perhaps be better be defined as the multiplicity of value a in a multiset of candidates of child squares in the collection of squares, however to my knowledge Python does not have support for multisets, and so collections of sets are used.

First Steps

First, the candidates for every blank square on the sudoku grid are found.  The candidates cannot be any of the certain values of the parent containers, so the set of candidates of the current square is the relative complement of the certain values of the parent containers, C, with respect to {1, 2, … , 8, 9} (the possible values for a square with no constraints).

\[ X = \{1, 2 ... 8, 9\} \setminus C \]

During this procedure and at any other time in the program, if a new certain value is found, the following methods are performed on the coordinates of the square.  The recalculating method is added to the front of the operation queue as it requires little calculation and has a very high utility.  The other methods are added to the back of the operation queue to be executed when recalculation due to this certain value and any consequential certain values has finished. If no certain values are found, the methods are called on each box and line in turn as appropriate.

These methods usually remove candidates for squares and result in certain values being found by elimination of candidates or deduction from the values of other candidates in the parent containers, however if this is fruitless, the program cannot solve the puzzle using its logic, so an alternate approach such as backtracking should be used.

Recalculating and Unique Candidates

When a new certain value is found, due to principle 4, the certain value cannot be a candidate for any other squares in the parent containers of this square.  Letting a be the certain value and P the set of the candidates of all the squares in the parent containers excluding the updated square:

\[ X = \{a\} \Longleftrightarrow a \notin P \]

Therefore, the recalculating algorithm removes the new certain value from the candidates of all the squares in the parent container excluding the updated square.  This sometimes leads to a new certain value being found due to elimination of other candidates for a square. This value is a unique candidate (also known as a hidden single), and the recalculate method is then performed with this new square, as stated above.

Single Appearance

This method assigns a value to a square by finding a value which appears as a candidate of only one square in a line or box.  Letting S be the squares within the parent line or box and the value *a *be a candidate:

\[ \text{ If } a \in X \land n(a, S) = 1 \text{ then } X = \{a\} \]

I accomplished this in the program using the following code:

def single_appearance_using_coords(self, square_coords):
    for i in range(1, 10):
        appearance = None
        for coords in square_coords:
            nums = self.nums_for_coords(coords)
            if i in nums:
                if len(nums) == 1 or appearance is not None:
                    appearance = None
                    break
                appearance = coords
        if not appearance:
            continue
        # If a value is only possible once in a box / line, then the position of this possibility is where it lies
        self.set_nums_for_coords(appearance, set([i]))
        self.calc_list.insert(0, lambda coords=appearance, i=i: self.recalc_due_to_update(coords, set([i])))

The single appearance and recalculation methods are often enough to solve “easy” and sometimes “medium” difficulty sudoku puzzles, however the next two methods have proved very useful in solving harder problems.

Locked Candidates

A Locked Pair Suppose a line with a set of child squares L, intersects a box with a set of child squares B.  Letting a represent a candidate:

\[ \text{ If } n(a, B)-n(a, L \cap B) = 0 \text{ then } \\ a \in L \cap B \text{ and so } \\ a \notin (L \setminus B) \]

The principle of this method is that if a candidate is “locked” into only one row or column in a box i.e. it only appears along one line in a particular box, it must appear in one of the squares on this line within the box. Therefore, this candidate cannot appear outside of the box on this line, so the candidate can be removed from all squares outside the box on this line.

For example, in this grid on the right, the candidate 4 only appears in the second column of the first box (shown in yellow), so 4 can be excluded as a candidate in the second column of the remaining two boxes (shown in red).

Here is my implementation:

def locked_candidates(self, s_coords=None, b_coords=None):
    box = SudokuBox(self, s_coords=s_coords, b_coords=b_coords)
    single_line_vals = box.single_line_vals()
    for line, val in single_line_vals:
        square_coords_not_in_box = set(line.square_coords()) - set(box.square_coords())
        for coord_pair in square_coords_not_in_box:
            nums = self.nums_for_coords(coord_pair)
            if val in nums:
                nums.discard(val)
                self.set_nums_for_coords(coord_pair, nums)
                if len(nums) == 1:
                    self.calc_list.insert(0, lambda coords=coord_pair, nums=nums: self.recalc_due_to_update(coords, nums))

And here is the box.single_line_vals() method:

def single_line_vals(self):
    # Note: excludes the certain numbers
    cert_numbers = self.cert_numbers()
    single_line_vals = []
    for orientation in [L_VERT, L_HORIZ]:
        possibility_list = []

        for i in range(3):
            line = SudokuLine(self.parent, (self.coords[0]*3+i%3, self.coords[1]*3+i%3), orientation)
            possibilities = self.possibilities_on_line(line) - cert_numbers
            possibility_list.append((line, possibilities))

        for i in range(3):
            line = possibility_list[i][0]
            line_possibilities = possibility_list[i][1]
            other_lines_possibilities = set()
            for possibilities in possibility_list[:i] + possibility_list[i+1:]:
                other_lines_possibilities |= possibilities[1]
            unique_line_possibilities = line_possibilities - other_lines_possibilities
            single_line_vals.extend([(line, val) for val in unique_line_possibilities])
    return single_line_vals

Conjugate Groups

Conjugate PairsSuppose a group of squares, G, exists in a line or box such that the cardinality of the set of candidates of the group, C, is equal to the cardinality of G. If this is the case, then the set of candidates of the other squares in the line or box, Q must not include any of the candidates in C.

\[ C := \bigcup G \\ \text{ If } |G| = |C| \text{ then } Q \cap C = \varnothing \]

In the example on the right, there is a conjugate pair {5, 6} (shown in yellow) in the first box and the first column, so 5 and 6 can be removed from the candidates of all other squares in the first box and the first column (shown in red).

This method works because if a group of squares exist in a line or box with the same number of shared candidates as the size of the group, then the values of the squares can only collectively be the shared candidates, as each square must be unique due the squares being in a shared line or box.  Consequently, other squares within the line or box that the group resides in cannot have these values as candidates.

Here is my implementation:

def conjugate_groups_using_coords(self, group_coords):
    group_squares = [(coords, self.nums_for_coords(coords)) for coords in group_coords]
    for n in range(2, 8):
        possible_conjugate_squares = [square for square in group_squares if len(square[1]) != 1 and len(square[1]) <= n]
        possible_conjugate_groups = itertools.combinations(possible_conjugate_squares, n)
        for poss_group in possible_conjugate_groups:
            nums_union = set()
            for square in poss_group:
                nums_union |= square[1]
                if len(nums_union) > n:
                    break
            if len(nums_union) != n:
                continue
            update_coords = [square for square in group_squares if square not in poss_group]
            for coord_pair, nums in update_coords:
                old_nums_len = len(nums)
                nums -= nums_union
                if old_nums_len == len(nums):
                    continue
                self.set_nums_for_coords(coord_pair, nums)
                if len(nums) == 1:
                    self.calc_list.insert(0, lambda coords=coord_pair, nums=nums: self.recalc_due_to_update(coords, nums))

Solver Demo

In this video, this sudoku is being solved.  The first pale green highlights show the grids for which the initial candidates are being calculated.  The orange squares are those that are currently being examined by either the single appearance, locked candidates, or conjugate groups method.  When candidates have been modified by one of these methods, the colour of their square changes: blue for the single appearance method, gold for the locked candidates method, and pink for the conjugate groups method.  If a certain value has been found by recalculation of possible candidates, its square turns green.  A delay of \( 100 + 200\log\left(1 + \frac{n}{100}\right) \) ms has been added between the methods, where n is the operation index.

Acknowledgements

The images used as examples for the Locked Pair and Conjugate Pair strategies are cropped versions of this image and this image respectively. The original images are sourced from sudopedia.enjoysudoku.com, a mirror of sudopedia.org (dead link at time of writing). The original images are available under the GFDL, so the cropped derivative images displayed are licensed by requirement under the GFDL.

The sudoku puzzle solved in the video, Sudoku Puzzle Hard For Brute Force, is available under the GFDL, and so the solution to this puzzle in the video is also licensed under the GFDL.