How ∗ not ∗ to solve a Sudoku
Introduction
A Sudoku is a combinatorial number-placement puzzle where the objective is to fill a 9×9 grid with digits so that (i) each column, (ii) each row, and (iii) each of the nine 3×3 sub-grids that compose the grid contains all the digits from 1 to 9. The puzzle provides a partially completed grid, and the goal is to extend this to the full grid. Sudoku puzzles and their variations have become very popular in recent years. We refer the reader for instance to [1], [2] for mathematical results and observations on mathematical solution approaches to Sudokus. Provan [4] considers the following mathematical model of Sudoku-type problems.
- •
A finite ground set models the grid squares.
- •
A finite color set models the digits from 1 to 9.
- •
A family of subsets of models the rows, columns, and 3×3 sub-grids. These subsets are called blocks, and they all have the same cardinality as .
- •
A function models the initial situation of the Sudoku.
A common approach to Sudoku puzzles are elimination strategies that step by step eliminate colors from the feasible color sets , until each set has been cut down to a single element. Provan [4] investigates a particular family of elimination strategies which he calls one-block strategies. Every single step of a one-block strategy can eliminate a single color from a single set by drawing conclusions based on a single block. Hence one-block strategies are centered around the following algorithmic problem.
Problem: One-Block Elimination
Input: A block ; color sets for all ; a fixed element and a fixed color .
Question: Does there exist a coloring such that every color in is assigned to exactly one element in , such that for all , and such that ?
It is easy to see that the problem One-Block Elimination is a bipartite perfect matching problem, and hence is well behaved and solvable in polynomial time. Provan [4] derives the following beautiful characterization result from this: A Sudoku can be fully solved by a one-block strategy if and only if a certain underlying linear equation system has a non-negative solution over the real numbers. Provan poses the open question whether there also is a good description of two-block strategies that are centered around the following problem.
Problem: Two-Block Elimination
Input: Two blocks ; color sets for all ; a fixed element and a fixed color .
Question: Does there exist a coloring such that every color in is assigned to exactly one element in and to exactly one element in , such that for all , and such that ?
Theorem 1 Problem Two-Block Elimination is NP-complete.
This hints at a negative answer to Provan’s open question: Whenever NP-hardness rears its ugly head, there is little hope for beautiful characterizations and fast algorithms.
Section snippets
The hardness proof
We prove the NP-hardness of the problem Two-Block Elimination by a reduction from the following variant of the satisfiability problem (see [3]).
Problem: Satisfiability
Input: A set of logical variables; a set of clauses over where every variable occurs twice as negated and once as unnegated literal.
Question: Is there a truth assignment for that satisfies all clauses in ?
A more realistic variant of two-block elimination
There is something extremely dissatisfying about the NP-hardness construction in the preceding section: Every Sudoku puzzle in the real world has a solution. Whenever we invoke an algorithm for Two-Block Elimination while solving a Sudoku, we want to know whether by assigning color to element we jump from a solvable situation into an unsolvable situation. But the instance constructed above does not reflect this behavior: Color is the only feasible color for element , and the
Acknowledgements
This research has been supported by the Netherlands Organisation for Scientific Research (NWO), grant 639.033.403, by DIAMANT (an NWO mathematics cluster), and by BSIK grant 03018 (BRICKS: Basic Research in Informatics for Creating the Knowledge Society).
References (4)
The Hidden Logic of Sudoku
(2007)Sudoku puzzles and how to solve them
Nieuw Archief voor Wiskunde (Vijfde Serie)
(2006)
Cited by (5)
Combining Hopfield neural networks, with applications to grid-based mathematics puzzles
2019, Neural NetworksCitation Excerpt :Convergence of Hopfield networks has been explored (Cao, 2001; Cao & Tao, 2001). In relatively recent literature, various authors considered in different ways the use of such networks for solving Sudoku puzzles (Babu, Pelckmans, Stoica, & Li, 2010; Dahl, 2009; Gabor & Woeginger, 2010; Hopfield, 2008; Maass, 2014; Moon, Gunther, & Kupin, 2009; Wu, Hsu, & Lio, 2014). More recently, in the last few years, various authors have considered the broader are of neural networks solving constraint or reasoning problems, with a subset of the work considering Sudoku puzzle solving as an (or the) example (Barzegarjalali & Parker, 2016; Berg Palm, Paquet, & Winther, 2018; Binas, Indiveri, & Pfeiffer, 2016; Fonseca Guerra & Furber, 2017; Sevgen, Arslan, & Samli, 2017).
Set selection dynamical system neural networks with partial memories, with applications to Sudoku and KenKen puzzles
2015, Neural NetworksCitation Excerpt :In the recent literature Hopfield (2008), Sudoku were considered in a Hopfield neural network framework, using energy functions and a neural network coprocessor. Subsequent work by other authors continued to treat this application in various ways (Babu, Pelckmans, Stoica, & Li, 2010; Dahl, 2009; Gabor & Woeginger, 2010; Moon, Gunther, & Kupin, 2009; Wu, Hsu, & Lio, 2014). In this paper, we continue this train of thought.
Sudoku associative memory
2014, Neural NetworksCitation Excerpt :Given partial clues, the game aims to restore the original Sudoku pattern. It has attracted much attentions in the fields of mathematics and neural networks (Babu et al., 2010; Dahl, 2009; Gabor & Woeginger, 2010; Moon, Gunther, & Kupin, 2009). As in Hopfield’s TSP work (Hopfield, 2008; Tank & Hopfield, 1986), where the constraints of binary Latin square encoding have been formulated as penalty terms in an energy function of deriving interactive neural dynamics, this section presents a theoretical framework of deriving neural relaxation for Sudoku restoration.
Organizing business forums with integer linear programming
2019, Pesquisa OperacionalSome notes on the 3-factor analvsis of 9x9 Sudoku
2015, Research Journal of Applied Sciences