Crazy Sudoku
W.L.X.
posted @ Wed, 20 Feb 2008 08:30:00 +0800
in 建模
, 1019 readers
I participated in Mathematical Contest in Modeling (MCM) in the past few days. We chose problem B: Creating Sudoku Puzzles, a difficult task for me and my teammates. We worked hard together — lots of coding and writing. The following are the problem and the abstract of our paper.
PROBLEM B: Creating Sudoku Puzzles
Develop an algorithm to construct Sudoku puzzles of varying difficulty. Develop metrics to define a difficulty level. The algorithm and metrics should be extensible to a varying number of difficulty levels. You should illustrate the algorithm with at least 4 difficulty levels. Your algorithm should guarantee a unique solution. Analyze the complexity of your algorithm. Your objective should be to minimize the complexity of the algorithm and meet the above requirements.
What is Sudoku?
The Sudoku puzzle, a logical game originating from the Latin square has been popular all over the world in recent years. A Sudoku board of order n consists of n^4 cells formed into n^2×n^2 subgrids with numbers from 1 to n^2 (or n^2 different symbols), ensuring that the entries in each row, each column, and each subgrid are all different. A Sudoku puzzle consists of some clues (several cells are already given preset numbers) and guarantees a unique solution. The objective is to fill in the empty cells and satisfy the constraints.
Abstract
We studied the Sudoku modeling, solving, generating and difficulty rating in this paper.
Binary integer programming (BIP) was used to model Sudoku puzzle. Four groups of constraints were obtained from the rules of the game. A heuristic objective function was used to speed up computation. We also proposed a linear programming approach to the problem. Branch-and-bound algorithm and the Knuth’s Algorithm X were implemented respectively to solve the BIP problem. Both algorithms were tested with 10,000 Sudoku puzzles, and the Knuth’s Algorithm X performed better. It took Algorithm X 26 milliseconds to solve a puzzle on average. It also found all the solutions to any board. This feature was used to check the uniqueness of the solution.
The difficulty metric was based on the effort needed for a human to solve a Sudoku, i.e., reasoning and memorizing. Reasoning and memorizing were modeled as logic deduction and backtracking process. Advanced solving techniques were converted into the two basic techniques. A so-called ”Difficulty Index” (DI) was calculated to apply quantitative analysis to difficulty. A random generating technique was adapted to construct puzzles, ensuring a wide difficulty range. Knuth’s Algorithm X settled substantial computation coming with random generating manner. With these features, we could construct Sudoku of a given difficulty with a unique solution.
A large number of tests were analyzed to study the distribution of running time. According to statistics data, the running time of the generating algorithm is approximately proportional to DI.
Develop an algorithm to construct Sudoku puzzles of varying difficulty. Develop metrics to define a difficulty level. The algorithm and metrics should be extensible to a varying number of difficulty levels. You should illustrate the algorithm with at least 4 difficulty levels. Your algorithm should guarantee a unique solution. Analyze the complexity of your algorithm. Your objective should be to minimize the complexity of the algorithm and meet the above requirements.
What is Sudoku?
The Sudoku puzzle, a logical game originating from the Latin square has been popular all over the world in recent years. A Sudoku board of order n consists of n^4 cells formed into n^2×n^2 subgrids with numbers from 1 to n^2 (or n^2 different symbols), ensuring that the entries in each row, each column, and each subgrid are all different. A Sudoku puzzle consists of some clues (several cells are already given preset numbers) and guarantees a unique solution. The objective is to fill in the empty cells and satisfy the constraints.
Abstract
We studied the Sudoku modeling, solving, generating and difficulty rating in this paper.
Binary integer programming (BIP) was used to model Sudoku puzzle. Four groups of constraints were obtained from the rules of the game. A heuristic objective function was used to speed up computation. We also proposed a linear programming approach to the problem. Branch-and-bound algorithm and the Knuth’s Algorithm X were implemented respectively to solve the BIP problem. Both algorithms were tested with 10,000 Sudoku puzzles, and the Knuth’s Algorithm X performed better. It took Algorithm X 26 milliseconds to solve a puzzle on average. It also found all the solutions to any board. This feature was used to check the uniqueness of the solution.
The difficulty metric was based on the effort needed for a human to solve a Sudoku, i.e., reasoning and memorizing. Reasoning and memorizing were modeled as logic deduction and backtracking process. Advanced solving techniques were converted into the two basic techniques. A so-called ”Difficulty Index” (DI) was calculated to apply quantitative analysis to difficulty. A random generating technique was adapted to construct puzzles, ensuring a wide difficulty range. Knuth’s Algorithm X settled substantial computation coming with random generating manner. With these features, we could construct Sudoku of a given difficulty with a unique solution.
A large number of tests were analyzed to study the distribution of running time. According to statistics data, the running time of the generating algorithm is approximately proportional to DI.
Mon, 13 Feb 2023 16:54:02 +0800
Thank you for yet another great informative article, I’m a loyal visitor to this blog and I can’t stress enough how much valuable tips I’ve learned from reading your content. I really appreciate all the hard work you put into this great site. 二手mac
===================
There is noticeably a lot of money to know about this. I suppose you have made specific nice points in features also. 여우알바
Thu, 23 Feb 2023 00:54:53 +0800
Good info, good to be knowledge and distributed to the public 여우알바