 |
 |
| A Sudoku Puzzle... | ...and its solutions numbers marked in red Source: Wikipedia |
Pankaj Prateek & Jeetesh Mangwani
ABSTRACT
Constraint programming has finally reached the masses, with many newspapers posing them as their daily constraint problem. Many enthusiasts use comlex propagation schemes to find solutions of rather simple looking puzzles like Sudoku, being unaware of the fact that these are constraint satisfaction problems. In this project, we try to understand the sudoku puzzle with a constraint point of view and generate solutions satifying those constraints using Progressive Stochastic Search.
1. Introduction
Sudoku originated in USA in the 1970s, but it was actually in Japan in the 1980s tat it gained mainstream popularity. It was here where it was given the name "Sudoku" which can be loosely translated as "solitary number".
|
|
|
| A Sudoku Puzzle... | ...and its solutions numbers marked in red Source: Wikipedia |
1.1 Problem Definition
A Sudoku square of order n consists of n4 variables formed into a n2 x n2 grid such that:
A Sudoku Problem consists of a partial assignment of the variables in a Sudoku square. The objective is to find a completion of the assignment which extends the partial assignment and satisfies the constraints. Non-redundant hints are added until the partial assignment guranttees a unique solution.
1.2 Motivation
After being mesmerised at stochastic algorithms overpowering the deterministic ones for NP-complete problems, we decided to test this superiority ourselves. Looking for interesting NP-puzzles, we came across "Sudoku"; that motivated us to dig deeper in this field.
All Sudoku puzzles do not have the logic-solvable property. Sudoku has been proved to belong to the class of NP-complete problems, implying that a polynomially bound algorithm for solving all problem instances is not possible. It is claimed that even for Sudoku squares of order 3, there are 6,670,903,752,021,072,936,960 valid arrangements.
Given the above, it is suggested to consider other type of search methods with Sudoku. Consequently, in this project, we use Progressive Stochastic Search to search the solution of the Sudoku puzzle given partial assignments.
However, the success of this type of approach depends on the size of the search space. In situations where the search space is not of manageable size - probably because the problem was not well-posed (the partial solutions didn't guranttee a unique solution) or the order was high - the potential timing implications may turn out to be quite impractical.
2. Our Approach
2.1 Modelling the Sudoku problem as a Constraint Satisfaction Problem (CSP)
The Sudoku puzzle will be modelled as a grid of n4 cells - each of which represents an integer variable which initially will have a domain of 1 through n2. Constraints can be added in the form of "alldifferent" constraints and using the pre-filled cells in the grid. Combinations of such constraints will reduce the domain sizes of some variables. This reduces the problem to find a bijection between n2 variables and n2 values satisfying the constraints.
Initially, we fill all those logically-deductible values in their correspoding squares. This reduces the search space to the point where only guesswork can lead to progress. It is here that PSS takes over the reign and completes the partial assignment to completeness.
2.2 Progressive Stochastic Search
Stochastic Search methods often solve some standard CSPs much faster than other Tree search approaches. Typical stochastic search algorithms first generate a complete initial variable assignment and repair the assignment by heuristic local search with reference to a cost function until a solution is found. The problem with this is that the algorithm might get stuck on a plateau or in a local optima. Traditionally, random restarts are used to avoid these. But in this approach, the information gained in the search process is lost in each restart. Another approach is to use heuristics and associate weights with the constraints violations and define the cost function as a weighed sum od these violations. This approach helps significantlly in avoiding local optima.
A typical stochastic search method for solving CSPs is a hill-climbing algorithm. The search moves from a point in the search space to a neighbouring point if the latter has a better cost value, thus, driven solely by "potential energy". The goal is to reach the optima point, which generally correspponds to the solution of the CSP.
In this project, we use Progressive Stochastic Search (PSS). Progressive Stochastic Search characteristically maintains a list of variables, which dictate the sequence of variables to be repaired. Unlike hill-climbing, when a variable is designated to be repaired in PSS, it always chooses a new value even if its original value gives a better cost. Intutively, the search can be thought to be mainly driven by a "force" so that the search is able to "rush through" the local minima and plateaus. Random restarts are not necessary and epsensive heuristic learning can be replaced with simple path marking.
References