Multiple-Valued Problem Solvers -- Comparison of Several Approaches

Solving a multiple-valued problem means to assign values to a given set of multiple-valued variables such that certain conditions are satisfied. The solution of a multiple-valued problem is a subset of vk v-valued tuples of the length k, where k is the number of variables and v is the number of their possible values. This paper compares several approaches which solve such problems. These approaches are applied to the well-known Sudoku problem of 9⁸¹-valued variables. Hence, the search space for this finite problem has a size of 981 (approximately 1.9 * 1077). We take as an example one of the most difficult Sudoku problems where 17 entries are given, the smallest number which results in a unique solution. Additionally, we remove one of these entries to get a more difficult multiplevalued problem for which a set of solutions exists. We show how the required model can be built. Several approaches and the respective solution are explained. Utilizing XBOOLE on a GPU, all 44,664 solutions of a 25-clue Sudoku were found 20 times faster than by a SAT-solver. Although the explored approaches are utilized for a special multiple-valued problem, the conclusions can also be utilized for other multiple-valued problems.