Goto

Collaborating Authors

Results


How I Solved Sudoku With a Business Rules Engine - KDnuggets

#artificialintelligence

On a family trip a few months back, I was flipping through an airline magazine and landed on the puzzles page. There were three puzzles, "Easy", "Medium", and "Hard". At the top of the page a word that would become my obsession over the next couple of months: "Sudoku". I had heard about Sudoku puzzles, but I had never really considered trying one. I grabbed a pencil from one of the kids and started with the "Easy" puzzle. It took me quite some time (and I tore the paper in one spot after erasing too many times) but I eventually completed the puzzle.


Solving Sudoku with Ant Colony Optimisation

arXiv.org Artificial Intelligence

In this paper we present a new Ant Colony Optimisation-based algorithm for Sudoku, which out-performs existing methods on large instances. Our method includes a novel anti-stagnation operator, which we call Best Value Evaporation.


OptNet: Differentiable Optimization as a Layer in Neural Networks

arXiv.org Artificial Intelligence

This paper presents OptNet, a network architecture that integrates optimization problems (here, specifically in the form of quadratic programs) as individual layers in larger end-to-end trainable deep networks. These layers encode constraints and complex dependencies between the hidden states that traditional convolutional and fully-connected layers often cannot capture. In this paper, we explore the foundations for such an architecture: we show how techniques from sensitivity analysis, bilevel optimization, and implicit differentiation can be used to exactly differentiate through these layers and with respect to layer parameters; we develop a highly efficient solver for these layers that exploits fast GPU-based batch solves within a primal-dual interior point method, and which provides backpropagation gradients with virtually no additional cost on top of the solve; and we highlight the application of these approaches in several problems. In one notable example, we show that the method is capable of learning to play mini-Sudoku (4x4) given just input and output games, with no a priori information about the rules of the game; this highlights the ability of our architecture to learn hard constraints better than other neural architectures.


Difficulty Rating of Sudoku Puzzles: An Overview and Evaluation

arXiv.org Artificial Intelligence

How can we predict the difficulty of a Sudoku puzzle? We give an overview of difficulty rating metrics and evaluate them on extensive dataset on human problem solving (more then 1700 Sudoku puzzles, hundreds of solvers). The best results are obtained using a computational model of human solving activity. Using the model we show that there are two sources of the problem difficulty: complexity of individual steps (logic operations) and structure of dependency among steps. We also describe metrics based on analysis of solutions under relaxed constraints -- a novel approach inspired by phase transition phenomenon in the graph coloring problem. In our discussion we focus not just on the performance of individual metrics on the Sudoku puzzle, but also on their generalizability and applicability to other problems.


Redundant Sudoku Rules

arXiv.org Artificial Intelligence

The rules of Sudoku are often specified using twenty seven \texttt{all\_different} constraints, referred to as the {\em big} \mrules. Using graphical proofs and exploratory logic programming, the following main and new result is obtained: many subsets of six of these big \mrules are redundant (i.e., they are entailed by the remaining twenty one \mrules), and six is maximal (i.e., removing more than six \mrules is not possible while maintaining equivalence). The corresponding result for binary inequality constraints, referred to as the {\em small} \mrules, is stated as a conjecture.


Difficulty Rating of Sudoku Puzzles by a Computational Model

AAAI Conferences

We discuss and evaluate metrics for difficulty rating of Sudoku puzzles. The correlation coefficient with human performance for our best metric is 0.95. The data on human performance were obtained from three web portals and they comprise thousands of hours of human solving over 2000 problems. We provide a simple computational model of human solving activity and evaluate it over collected data. Using the model we show that there are two sources of problem difficulty: complexity of individual steps (logic operations) and structure of dependency among steps. Beside providing a very good Sudoku-tuned metric, we also discuss a metric with few Sudoku-specific details, which still provides good results (correlation coefficient is 0.88). Hence we believe that the approach should be applicable to difficulty rating of other constraint satisfaction problems.


Heuristic Reasoning on Graph and Game Complexity of Sudoku

arXiv.org Artificial Intelligence

The Sudoku puzzle has achieved worldwide popularity recently, and attracted great attention of the computational intelligence community. Sudoku is always considered as Satisfiability Problem or Constraint Satisfaction Problem. In this paper, we propose to focus on the essential graph structure underlying the Sudoku puzzle. First, we formalize Sudoku as a graph. Then a solving algorithm based on heuristic reasoning on the graph is proposed. The related r-Reduction theorem, inference theorem and their properties are proved, providing the formal basis for developments of Sudoku solving systems. In order to evaluate the difficulty levels of puzzles, a quantitative measurement of the complexity level of Sudoku puzzles based on the graph structure and information theory is proposed. Experimental results show that all the puzzles can be solved fast using the proposed heuristic reasoning, and that the proposed game complexity metrics can discriminate difficulty levels of puzzles perfectly.


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.