Multiple-Valued Problem Solvers -- Comparison of Several Approaches

• Main Authors: Steinbach, Bernd, Posthoff, Christian
• Format: Conference Proceeding
• Language: English
• Subjects: Boolean equation; Educational institutions; Electronic mail; Encoding; Equations; intersection; Kernel; Mathematical model; multiple-valued model; multiple-valued problem; SAT-solver; soft computing; Sudoku; Vectors; XBOOLE
• ISSN: 0195-623X; 2378-2226
• DOI: 10.1109/ISMVL.2014.13

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 81 -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.