Solve Sudoku with Algorithm X

In this article, we consider Knuth's “Algorithm X” and its application for solving sudoku. The beauty of the algorithm is that Sudoku is solved quickly without programming any advanced solution techniques.

It all started, in fact, with the puzzles from Project Euler , where to get the answer, you need to solve 50 sudoku. And it seems that I received an answer to it by writing a program for solving a rather stupid search, but somehow there was some dissatisfaction with the speed of the solution. After seeing how normal people solve sudoku, I found that Algorithm X, invented by Donald Knut, is being used for this.

Algorithm X

This algorithm solves the problem of accurately covering the set. Or, if you want, it collects a "discrete puzzle", having information on the shape of the available pieces available. More formally:

• There are many s
• There is a set of subsets Y of this set
• The problem is to choose from Y such elements Y * that each element from S is contained in only one of the sets included in Y *
• That is, the union of all sets in Y * constitutes (covers) the set S , and at the same time in Y * there are no pairwise intersecting sets

For example, consider the sets

S = {1, 2, 3, 4, 5} and

Y = { A = {1, 2},

B = {2, 3},

C = {1, 5},

D = {1, 4},

E = {5}}

The sets B , D, and E form an exact covering of the set S.

For the Knuth algorithm X, the set Y is represented as a binary matrix, where the rows correspond to the elements Y , and A _{i, j} = 1, if S _j is in Y _i . Those. for the example above:

The exact coverage search algorithm is as follows:

• Input data: sets S and Y ; Stack
  
  
  
  sets potentially included in the coverage (it may initially be empty or already have some elements)
  
  
  1. If the set S is empty, then the desired cover is on the stack.
  2. If the set Y is empty, the covering was not found.
  3. We look for an element s in the set S that is included in the minimum number of sets in Y.
  4. Choose from Y all lines X containing s .
  5. For each set X, repeat 6-9.
  6. Add X to the Stack
     
     
     
     stack as a potential coverage element.
  7. We form sets S ' and Y' : S ' is S from which all elements contained in X are removed, Y' is sets from Y that do not intersect with X.
  8. We call algorithm X for S ' , Y' and Stack
     
     
     
     .
  9. If it was found in step 7 that coverage is impossible, remove the element from the top of Stack
     
     
     
     and go to the next X. If a solution is found, return it.
  10. If there is no solution for any X , the task is not solved for this input.

In general, nothing particularly complicated. Essentially - the usual search in depth. By the way, we note that if you initially set the stack to be nonempty, then the problem can be formulated as "find the exact coverage that includes elements that already lie on the stack."

The subtlety is that in practice this algorithm is used for problems where the sets in Y are "small", i.e. the matrix is ​​very sparse, because of which, for example, searching for intersections between columns during standard storage in the form of a matrix takes an unacceptably long time.

Therefore, Knut supplements this algorithm with a "dancing link" mechanism . The matrix is ​​represented in the form of a two-dimensional doubly linked list: for each row in the list, only the column numbers are stored, where units are contained in this row. The list also contains links to the next and previous element in a row and column. Such an organization allows you to remove columns and rows from a sparse matrix during O (1) time compared to O ( m * n ) when stored in a two-dimensional array.

Interestingly, Ali Assaf offers an alternative to the mechanism of dancing links using associative lists, which allows you to implement the X algorithm in literally several dozen lines in high-level languages.

The idea is to store both columns and matrix rows in associative lists. In columns we store row indices, at the intersection with which there are nonzero elements, in rows, respectively, column indices. Moreover, we will store indexes in rows in an orderly manner, in an array, we note that in Knuth's algorithm, it is essentially not necessary to modify rows, therefore optimization for quickly removing an element from a row is not needed. But the columns will be set in the form of sets, because when you delete a row from a matrix, you need to remove its identifier from all columns (and when you delete it from all columns, the row disappears "by itself").

Consider the implementation of the algorithm on Julia.

The matrix from the example will now look like this:

 Y = Dict( 'A' => [1, 2], 'B' => [2, 3], 'C' => [1, 5], 'D' => [1, 4], 'E' => [5] ) S = Dict( 1 => Set(['A', 'C', 'D']), 2 => Set(['A', 'B']), 3 => Set(['B']), 4 => Set(['D']), 5 => Set(['C', 'E']) )
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

For the algorithm to work, you need a function that takes out lines from the matrix that intersect with the given one, and a function that returns these lines to their place.

 function extract_intersects!(rows, columns, base_row) buf = [] for elt in rows[base_row] #        push!(buf, pop!(columns, elt)) #         for intersecting_row in buf[end] for other_elt in rows[intersecting_row] if other_elt != elt delete!(columns[other_elt], intersecting_row) end end end end return buf end function restore_intersects!(rows, columns, base_row, buf) #       base_row  ,      for elt in Iterators.reverse(rows[base_row]) columns[elt] = pop!(buf) for added_row in columns[elt] for col in rows[added_row] push!(columns[col], added_row) end end end end
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

For these two functions to work as they should, just ordered storage of the elements in the rows of the matrix was required. In the extract_intersects!()



Function, at each iteration of the outer loop, those rows that intersect with base_row



but do not contain elements viewed in previous iterations are removed from the matrix. This ensures that when we insert the columns in restore_intersects!()



In the reverse order, in the innermost loop at the time of the call push!(columns[col], added_row)



the columns[col]



column will already be returned to the matrix, and all deleted ones extract_intersects!()



elements from the columns will be returned to their original place.

Now algorithm X itself:

 function algorithm_x(rows, columns, cover = []) if isempty(columns) return cover else #       m, c = findmin(Dict(k => length(v) for (k, v) in columns)) for subset in collect(columns[c]) push!(cover, subset) #     #   subset  buf_cols = extract_intersects!(rows, columns, subset) s = algorithm_x(rows, columns, cover) #     - ,  s == nothing || return s restore_intersects!(rows, columns, subset, buf_cols) pop!(cover) end #      columns[c] , #        return nothing end end
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Sudoku

There is an algorithm, the matter is small - to present Sudoku as a task of finding the exact coverage.

We formulate the requirements that must be met by a solved sudoku:

1. Each cell contains a number from 1 to 9 (or up to n ² if squares of a different size are solved).
2. In each line, each number occurs once.
3. In each column, each number occurs once.
4. In each quadrant, each number occurs once.

Each of these requirements must be fulfilled exactly 1 time, i.e. they form the set that needs to be covered. It has exactly 4 n ² elements (columns in the matrix).

The subsets that we consider are formed by substituting a specific number in a specific cell. For example, the number 9 at the intersection of 1 row and 4 columns "covers" a subset "in cell (1,4) is a number, in 1 row there is a number 9, in 4 columns there is a number 9, in 2 quadrants there is a number 9" (implying the usual Sudoku 9 × 9).

After that, the solution algorithm is written trivially.

 #    9×9,      #   -   (row, col, num) #  : # (0, row, col) -   row  col   # (1, row, num) -   row   num # (2, col, num) -   col   num # (3, q, num) -   q   num function xsudoku(puzzle::AbstractMatrix{Int}) rows = Dict() cols = Dict() #   for row in 1:9, col in 1:9, num in 1:9 r = [] quad = ((row-1)÷3)*3 + (col-1)÷3 + 1 push!(r, (0, row, col), (1, row, num), (2, col, num), (3, quad, num)) rows[(row, col, num)] = r end #   for type in 0:3, n1 in 1:9, n2 in 1:9 cols[(type, n1, n2)] = Set() end for (rk, rv) in rows for v in rv push!(cols[v], rk) end end # s -    #  ,     ,    s = [] for i in 1:9, j in 1:9 if puzzle[i, j] > 0 elt = (i, j, puzzle[i,j]) push!(s, elt) #    ,       extract_intersects!(rows, cols, elt) end end # ,   -   success = algorithm_x(rows, cols, s) success != nothing || return nothing #      ret = similar(puzzle) for (i, j, num) in s ret[i,j] = num end return ret end
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Let's check on some example:

  julia> @time xsudoku([0 0 0 0 0 0 4 0 0; 3 0 6 0 0 0 0 0 0; 0 0 0 1 9 6 0 3 0; 0 7 0 0 0 0 0 1 0; 8 0 0 2 5 0 0 9 0; 0 4 0 0 0 0 8 0 0; 0 6 0 4 0 9 0 0 8; 0 0 5 0 0 0 0 2 0; 0 0 0 5 0 0 0 0 7]) 0.006326 seconds (54.91 k allocations: 3.321 MiB) 9×9 Array{Int64,2}: 1 5 7 8 3 2 4 6 9 3 9 6 7 4 5 2 8 1 2 8 4 1 9 6 7 3 5 6 7 2 9 8 4 5 1 3 8 3 1 2 5 7 6 9 4 5 4 9 6 1 3 8 7 2 7 6 3 4 2 9 1 5 8 4 1 5 3 7 8 9 2 6 9 2 8 5 6 1 3 4 7
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

It seems to work, and the speed is acceptable.

It should be noted that no techniques specifically for sudoku (such as here or here ) were laid down in the algorithm, except for a specific representation of the desired set and covering elements.