Elsevier

Operations Research Letters

Volume 38, Issue 6, November 2010, Pages 582-584
Operations Research Letters

How ∗ not ∗ to solve a Sudoku

https://doi.org/10.1016/j.orl.2010.09.001Get rights and content

Abstract

We prove the NP-hardness of a consistency checking problem that arises in certain elimination strategies for solving Sudoku-type problems.

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 S models the grid squares.

  • A finite color set C models the digits from 1 to 9.

  • A family B of subsets of S models the rows, columns, and 3×3 sub-grids. These subsets are called blocks, and they all have the same cardinality as C.

  • A function C:S2C models the initial situation of the Sudoku.

The function C specifies for every element sS the set C(s) of colors that can feasibly be assigned to s. If C(s) contains a single element, then the contents of the grid square s is fixed right from the beginning. If C(s)=C, then the grid square s is initially empty, and any color in C may be assigned to it. The goal is to find a coloring γ:SC of the elements such that γ(s)C(s) for all sS, and such that in every block BB every color is assigned to exactly one element.

A common approach to Sudoku puzzles are elimination strategies that step by step eliminate colors from the feasible color sets C(s), 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 C(s) 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 BB; color sets C(s) for all sB; a fixed element s0B and a fixed color c0C(s0).

  • Question: Does there exist a coloring γ:BC such that every color in C is assigned to exactly one element in B, such that γ(s)C(s) for all sB, and such that γ(s0)=c0?

Whenever a one-block strategy detects a NO instance of One-Block Elimination, it makes progress by eliminating the color c0 from set C(s0). According to Provan [4] this simple strategy solves about 90% of all Sudoku puzzles; for the remaining 10% it reduces the search space considerably.

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 B1,B2B; color sets C(s) for all sB1B2; a fixed element s0B1B2 and a fixed color c0C(s0).

  • Question: Does there exist a coloring γ:B1B2C such that every color in C is assigned to exactly one element in B1 and to exactly one element in B2, such that γ(s)C(s) for all sB, and such that γ(s0)=c0?

In this technical note we will prove that Two-Block Elimination, in fact, is an intractable problem.

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 X={x1,,xn} of n logical variables; a set K={k1,,km} of m clauses over X where every variable occurs twice as negated and once as unnegated literal.

  • Question: Is there a truth assignment for X that satisfies all clauses in K?

Note that [3] only says that the satisfiability problem remains NP-complete if each variable

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 c0 to element s0 we jump from a solvable situation into an unsolvable situation. But the instance constructed above does not reflect this behavior: Color c0 is the only feasible color for element s0, 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)

  • D. Berthier

    The Hidden Logic of Sudoku

    (2007)
  • A.E. Brouwer

    Sudoku puzzles and how to solve them

    Nieuw Archief voor Wiskunde (Vijfde Serie)

    (2006)
There are more references available in the full text version of this article.

Cited by (5)

  • Combining Hopfield neural networks, with applications to grid-based mathematics puzzles

    2019, Neural Networks
    Citation 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 Networks
    Citation 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 Networks
    Citation 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.

  • Some notes on the 3-factor analvsis of 9x9 Sudoku

    2015, Research Journal of Applied Sciences
View full text