oalib
Search Results: 1 - 10 of 100 matches for " "
All listed articles are free for downloading (OA Articles)
Page 1 /100
Display every page Item
Techniques for Solving Sudoku Puzzles  [PDF]
Eric C. Chi,Kenneth Lange
Mathematics , 2012,
Abstract: Solving Sudoku puzzles is one of the most popular pastimes in the world. Puzzles range in difficulty from easy to very challenging; the hardest puzzles tend to have the most empty cells. The current paper explains and compares three algorithms for solving Sudoku puzzles. Backtracking, simulated annealing, and alternating projections are generic methods for attacking combinatorial optimization problems. Our results favor backtracking. It infallibly solves a Sudoku puzzle or deduces that a unique solution does not exist. However, backtracking does not scale well in high-dimensional combinatorial optimization. Hence, it is useful to expose students in the mathematical sciences to the other two solution techniques in a concrete setting. Simulated annealing shares a common structure with MCMC (Markov chain Monte Carlo) and enjoys wide applicability. The method of alternating projections solves the feasibility problem in convex programming. Converting a discrete optimization problem into a continuous optimization problem opens up the possibility of handling combinatorial problems of much higher dimensionality.
The Model and Algorithm to Estimate the Difficulty Levels of Sudoku Puzzles  [cached]
Chungen Xu,Weng Xu
Journal of Mathematics Research , 2009, DOI: 10.5539/jmr.v1n2p43
Abstract: Sudoku is a number placement mathematical puzzle based on logic. The purpose of this paper is to discuss suitable models and algorithm to generate Sudoku puzzles of varying difficulty. It is generally recognized that hand-made puzzles are more enjoyable than those generated by computer. Our goal is to establish models to generate Sudoku puzzles of varying difficulty, which are as enjoyable as hand-made ones. As we believe that puzzles generated by simulating the design process of hand-made ones will also be of much enjoyment, we established our first model -No Brute-Force. Brute-Force technique is excluded from this algorithm, for there is no enjoyment in solving puzzles using it. We have implemented the algorithm with a JAVA program. We conclude that it is possible and reasonable to generate Sudoku puzzles of varying difficulty as enjoyable as hand-made ones.
Difficulty Rating of Sudoku Puzzles: An Overview and Evaluation  [PDF]
Radek Pelánek
Computer Science , 2014,
Abstract: 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.
Algorithm Based on Genetic Algorithm for Sudoku Puzzles
基于遗传算法求解数独难题

LIU Yan-feng,LIU San-yang,
刘延风
,刘三阳

计算机科学 , 2010,
Abstract: To solve the Sudoku puzzles,above all,they were changed into a combinatorial optimization problem.Then,a genetic algorithm with specialized encoding,initialization and local search operator was presented to optimize it.The experimental results show the algorithm is effective for all difficulty levels Sudoku puzzles.
The paramagnetic and glass transitions in sudoku  [PDF]
Alex Williams,Graeme . J. Ackland
Physics , 2012, DOI: 10.1103/PhysRevE.86.031109
Abstract: We study the statistical mechanics of a model glassy system based on a familiar and popular mathematical puzzle. Sudoku puzzles provide a very rare example of a class of frustrated systems with a unique groundstate without symmetry. Here, the puzzle is recast as thermodynamic system where the number of violated rules defines the energy. We use Monte Carlo simulation to show that the "Sudoku Hamiltonian" exhibits two transitions as a function of temperature, a paramagnetic and a glass transition. Of these, the intermediate condensed phase is the only one which visits the ground state (i.e. it solves the puzzle, though this is not the purpose of the study). Both transitions are associated with an entropy change, paramagnetism measured from the dynamics of the Monte Carlo run, showing a peak in specific heat, while the residual glass entropy is determined by finding multiple instances of the glass by repeated annealing. There are relatively few such simple models for frustrated or glassy systems which exhibit both ordering and glass transitions, sudoku puzzles are unique for the ease with which they can be obtained with the proof of the existence of a unique ground state via the satisfiability of all constraints. Simulations suggest that in the glass phase there is an increase in information entropy with lowering temperature. In fact, we have shown that sudoku have the type of rugged energy landscape with multiple minima which typifies glasses in many physical systems, and this puzzling result is a manifestation of the paradox of the residual glass entropy. These readily-available puzzles can now be used as solvable model Hamiltonian systems for studying the glass transition.
Heuristic Reasoning on Graph and Game Complexity of Sudoku  [PDF]
Zhe Chen
Computer Science , 2009,
Abstract: 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 improved strategy for solving Sudoku by sparse optimization methods  [PDF]
Yuchao Tang,Zhenggang Wu,Chuanxi Zhu
Mathematics , 2015,
Abstract: We proposed several strategies to improve the sparse optimization methods for solving Sudoku puzzles. Further, we defined a new difficult level for Sudoku. We tested our proposed methods on Sudoku puzzles data-set. Numerical results showed that we can improve the accurate recovery rate from 84%+ to 99%+ by the L1 sparse optimization method.
Solving Single-digit Sudoku Subproblems  [PDF]
David Eppstein
Computer Science , 2012,
Abstract: We show that single-digit "Nishio" subproblems in nxn Sudoku puzzles may be solved in time o(2^n), faster than previous solutions such as the pattern overlay method. We also show that single-digit deduction in Sudoku is NP-hard.
Sudoku as a special transportation problem  [PDF]
Mansour Moufid
Computer Science , 2012,
Abstract: Sudoku is a popular combinatorial puzzle. A new method of solving Sudoku is presented, which involves formulating a puzzle as a special type of transportation problem. This model allows one to solve puzzles with more than one solution, keeping the constraints of the problem fixed, and simply changing a cost matrix between solutions.
The Chaos Within Sudoku  [PDF]
Maria Ercsey-Ravasz,Zoltan Toroczkai
Physics , 2012,
Abstract: The mathematical structure of the widely popular Sudoku puzzles is akin to typical hard constraint satisfaction problems that lie at the heart of many applications, including protein folding and the general problem of finding the ground state of a glassy spin system. Via an exact mapping of Sudoku into a deterministic, continuous-time dynamical system, here we show that the difficulty of Sudoku translates into transient chaotic behavior exhibited by the dynamical system. In particular, we show that the escape rate $\kappa$, an invariant characteristic of transient chaos, provides a single scalar measure of the puzzle's hardness, which correlates well with human difficulty level ratings. Accordingly, $\eta = -\log_{10}{\kappa}$ can be used to define a "Richter"-type scale for puzzle hardness, with easy puzzles falling in the range $0 < \eta \leq 1$, medium ones within $1 < \eta \leq 2$, hard in $2 < \eta \leq 3$ and ultra-hard with $\eta > 3$. To our best knowledge, there are no known puzzles with $\eta > 4$.
Page 1 /100
Display every page Item


Home
Copyright © 2008-2017 Open Access Library. All rights reserved.