Combinatorial Explorations in Su-Doku

arXiv.org Artificial Intelligence

Su-Doku, a popular combinatorial puzzle, provides an excellent testbench for heuristic explorations. Several interesting questions arise from its deceptively simple set of rules. How many distinct Su-Doku grids are there? How to find a solution to a Su-Doku puzzle? Is there a unique solution to a given Su-Doku puzzle? What is a good estimation of a puzzle's difficulty? What is the minimum puzzle size (the number of "givens")? This paper explores how these questions are related to the well-known alldifferent constraint which emerges in a wide variety of Constraint Satisfaction Problems (CSP) and compares various algorithmic approaches based on different formulations of Su-Doku.


An Interactive Constraint-Based Approach to Sudoku

AAAI Conferences

The Sudoku Puzzle, originally named Number Place, was created by Howard Garns in 1979, and originally appeared in the Dell Pencil Puzzles and Word Games magazine. Nikoli began publishing Sudoku Puzzles in 1986 and introduced the Sudoku name, trademarked in Japan. More recently, newspapers across the United States have begun publishing puzzles daily.


Ludii and XCSP: Playing and Solving Logic Puzzles

arXiv.org Artificial Intelligence

Many of the famous single-player games, commonly called puzzles, can be shown to be NP-Complete. Indeed, this class of complexity contains hundreds of puzzles, since people particularly appreciate completing an intractable puzzle, such as Sudoku, but also enjoy the ability to check their solution easily once it's done. For this reason, using constraint programming is naturally suited to solve them. In this paper, we focus on logic puzzles described in the Ludii general game system and we propose using the XCSP formalism in order to solve them with any CSP solver.


Teaching Artificial Intelligence Across the Computer Science Curriculum using Sudoku as a Problem Domain

AAAI Conferences

Artificial Intelligence (AI) is a field of both great breadth and depth. Thus, determining undergraduate material for an AI course can be problematic. Fortunately, AI is continually searching for new perspectives on problem solving that eventually propagate into the Computer Science mainstream. An approach is proposed for undergraduate AI education that utilizes these aspects of exploration and propagation. The approach introduces important individual techniques early in the computer science curriculum to form a foundation for the upper-level AI course focusing on research methods.


Generating and Solving Logic Puzzles through Constraint Satisfaction

AAAI Conferences

Solving logic puzzles has become a very popular past-time, particularly since the Sudoku puzzle started appearing in newspapers all over the world. We have developed a puzzle generator for a modification of Sudoku, called Jidoku, in which clues are binary disequalities between cells on a 9 9 grid. Our generator guarantees that puzzles have unique solutions, have graded difficulty, and can be solved using inference alone. This demonstration provides a fun application of many standard constraint satisfaction techniques, such as problem formulation, global constraints, search and inference. It is ideal as both an education and outreach tool. Our demonstration will allow people to generate and interactively solve puzzles of user-selected difficulty, with the aid of hints if required, through a specifically built Java applet.