Solving Single-digit Sudoku Subproblems

2012/02/23 by David Eppstein, Eppstein, David · 1 citation
Engineering · #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1202.5074

Abstract

We show that single-digit "Nishio" subproblems in nxn Sudoku puzzles may be solved in time o(2ⁿ), faster than previous solutions such as the pattern overlay method. We also show that single-digit deduction in Sudoku is NP-hard.

Cited by

• Project Patti: Why can You Solve Diabolical Puzzles on one Sudoku Website but not Easy Puzzles on another Sudoku Website?

Related

• Minuet: A method to solve Sudoku puzzles by hand
• A Study Of Sudoku Solving Algorithms: Backtracking and Heuristic
• There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem
• Difficulty Rating of Sudoku Puzzles: An Overview and Evaluation
• Techniques for Solving Sudoku Puzzles