Feature Articles: Communication Science that Enables corevo®—Artificial Intelligence that Gets Closer to People
Efficient Algorithm for Enumerating All Solutions to an Exact Cover Problem
We introduce an algorithm that finds all solutions to an exact cover problem. Many real-world tasks including designing apartment layouts and electric circuits can be formulated and solved as exact cover problems. Our algorithm can solve exact cover problems up to 10,000 times faster than the previous method. Moreover, our method compresses and stores all solutions and so can efficiently find the solutions that satisfy several constraints. Therefore, our algorithm can efficiently find good solutions to exact cover problems found in the real world.
Keywords: algorithm, data structure, exact cover problem
1. Exact cover problems
Most people have had some experience with puzzles such as crosswords, Sudoku, and Rubik’s cubes. Many computer science researchers have tried for decades to design algorithms* that can solve these puzzles by using computers. As a result, several efficient algorithms have been developed that can solve these puzzles much faster than humans can.
However, puzzles that are difficult for humans are also difficult for computers. Rubik’s cube and Sudoku are known to be NP-complete problems, and they become drastically more difficult as the problem size increases. For example, if we increase the number of squares on each face of a Rubik’s cube to 16, 25, 36,…, then solving the puzzle requires exponentially more time. This inherent difficulty of puzzles is why researchers are continuing to pursue more efficient algorithms that can solve large and complex puzzles.
We have developed a new algorithm that can efficiently find all the solutions of an exact cover problem, a fundamental problem in combinatorics. An example of an exact cover problem is to find a set of rows of a binary matrix X (a matrix whose elements are either 0 or 1), where the selected rows must contain exactly one numeral 1 in every column. An example of an exact cover problem is shown in Fig. 1. If the matrix shown in the figure is given as the input, then the set of rows (1, 3) has exactly one 1 in every column and is thus a solution to the exact cover problem. An exact cover problem may have multiple solutions. This example problem also has another solution (2, 3, 5). Our algorithm can find all of the solutions to this exact cover problem.
Our algorithm can also be used to find all the solutions to puzzles that can be formulated as exact cover problems. A polyomino is a puzzle that involves arranging tiles on a board using a set of pieces consisting of square cells, where all pieces are used and each cell on the board is covered by square cells, with no spaces left uncovered and no pieces overlapping. This is a typical example of a puzzle that can be formulated and solved as an exact cover problem.
The example in Fig. 2 shows how tetromino puzzles, a kind of polyomino where every piece is made by connecting four square cells, can be formulated as an exact cover problem. Every column of the problem matrix corresponds to a cell of the 4×4 input board (thus, there are 16 columns), and every row corresponds to an arrangement of a piece. If the cell corresponding to the j-th column is covered by the arrangement of a piece corresponding to the i-th row, we set matrix element xij to 1. Otherwise, we set xij to 0. A solution to the exact cover problem formulated in this way represents a set of arrangements of pieces covering all of the cells on the board with no overlapping pieces. Hence, it is a solution to the tetromino puzzle.
Other than puzzles, several real-world problems can be formulated and solved as exact cover problems. For example, designing the layout of an apartment can be regarded as solving a polyomino puzzle, where every piece corresponds to a room. The problem of designing the layout of an electric circuit can also be formulated and solved as an exact cover problem that is similar to a polyomino puzzle. Hence, our algorithm can find good solutions to these problems.
2. Algorithm for solving exact cover problems
Exact cover problems are known to be NP-complete. Donald E. Knuth’s algorithm DLX is accepted as a state-of-the-art algorithm for finding all solutions to an exact cover problem . DLX solves a problem by performing an exhaustive search. Given input binary matrix X, DLX selects the first row and checks whether or not it is a solution to the exact cover problem. If it is not a solution, then it selects the pair of the first and second rows and checks whether or not that combination is a solution. DLX repeatedly adds rows to the current set of rows and checks whether it is a solution. If adding the i-th row to the current set makes more than two 1’s appear in a column, then it cannot be a solution. Therefore, DLX removes the most recently added row from the set and adds a different row to the set to continue the search procedure. In this way, algorithm DLX finds all solutions by repeatedly adding and deleting rows to the set of rows to check all possible combinations of rows. Although the exhaustive search procedure is straightforward, DLX accelerates the search by exploiting a specialized data structure.
DLX can efficiently find all solutions to an exact cover problem if the number of solutions is limited. However, since it is an exhaustive search method, it takes an excessive amount of time if there are many solutions. Real-world exact cover problems sometimes have a huge number of solutions. For example, small polyomino puzzles can have more than one billion solutions.
Our new algorithm improves DLX to achieve practical speeds even when there are huge numbers of solutions . The key idea of the proposed algorithm is to store all the solutions found in a search. If an exact cover problem has many solutions, then it is highly likely that they will be similar in several ways. For example, there are many solutions to a polyomino puzzle that has the same placement of pieces on the left half of the input board. If we memorize all the solutions, they can be used as hints to find similar solutions and thus accelerate the search procedure.
Although storing all the solutions may increase the search speed, memorizing billions of solutions in a naïve manner is unrealistic. Our algorithm uses the data structure called a zero-suppressed binary decision diagram (ZDD) to store the set of found solutions. A ZDD represents the set of solutions as a directed graph. We show in Fig. 3(b) an example ZDD that represents the set of two solutions (Fig. 3(a)) of the tetromino puzzle in Fig. 2. This ZDD has two paths that start from the root node and end at terminal node T. These two paths correspond to the two solutions. Since a ZDD shares partial paths, it yields a small graph that can represent huge numbers of solutions. The ZDD in the figure shares two common edges of paths in order to reduce the size of the graph.
For example, a tetromino tiling problem with a board size of 10×10 has 7,213,560,548,906,621 solutions. If we use the naïve representation, the computer would require 100 petabytes (1018 bytes) of memory. In contrast, with our ZDD approach, the set is represented as a directed graph with 16,476,396 nodes. Such a ZDD requires only 300 megabytes (106 bytes) of memory and could therefore be handled by a modern smartphone. This compressed representation drastically speeds up the computation process. Our method is up to 10,000 times faster than DLX at finding all solutions to exact cover problems. Moreover, our algorithm is the first one capable of finding all the solutions to a tetromino tiling problem with a 12×12 board size. We confirmed that there are 13,664,822,582,333,502,156,627,512 solutions to the problem.
3. Application to real-world problems
Since our method represents the set of found solutions as a ZDD, we quickly identify solutions that satisfy several conditions. With this feature, our method can find good solutions to real-world problems. For example, the problem of designing the layout of an apartment is known to be an exact cover problem . By using our algorithm to construct a ZDD that represents the set of all possible floor plans, and then interactively adding conditions that match the buyer’s requirements, we can efficiently find satisfactory arrangements. A demonstration system that uses our algorithm to find acceptable apartment layouts is shown in Fig. 4. Because our algorithm can find all possible room arrangements for an apartment, we can browse them as a list. Moreover, we can add conditions on possible floor plans and efficiently identify floor plans that satisfy the additional conditions.
Our new algorithm for solving exact cover problems is fast and can efficiently store all the solutions. These features enable the interactive discovery of desirable solutions by setting conditions in practical situations, which is especially beneficial for problems such as finding a desired floor plan. We are planning to improve the data structure in order to find the optimum solutions to practical exact cover problems.