9512.net

# 数独游戏

Team 08

Page 1 of 11

Team Control Number For office use only T1 T2 T3 T4

6937
Problem Chosen

For office use only F1 F2 F3 F4

B

______________________________________________

Team 08

Page 2 of 11

Creating Sudoku Puzzles
Abstract: In this paper,we establish a modle of creating sudoku puzzles,which is
relatively easy to understand.Generally speaking,large numbers of people believe that the more the blanks,the easier the Sudoku puzzles are.However,this is not the fact.According to the following three aspects:(1)the number and location of known grids,(2) exhaustive search method,(3)game skills,we assign different weight to this three factors.Based on the three regulations,we obtain a final score range on each difficulty level.To illustrate the judgment of grade of the sudoku,we take a specific for example.The next step we take is considering from the opposite of sudoku puzzle.Firstly,we establish a complete endgame that without one blank[1],and then wipe out a certain number of digits according to the difficulty level.At the same time,we adopt depth-first search to guarantee the uniquness of solution of each sudoku puzzles that we create.The depth-first search is based on the candidated numbers on each blank.We try possible digits one by one to test whether the solution is unique or not.The other difficulty of this algorithm is to make the complexity both in time and in space lower.We assume that the storage space is not the limitation of the question.The uniqueness of solution is guaranteed.We regard the depth-first traversal as the better method and obtain that the time complexity is O n 2 .Finally,we propose some improvements for this algorithm that we can’t realize. Keywords: Sudoku Puzzle;Difficulty Level; Time Complexity;Depth-first Traversal

( )

Team 08

Page 3 of 11

1 Introduction: Sudoku puzzles first appeared in newspapers in the late 19th century,when French puzzle setters began experimenting with removing numbers from magic squares. Sudoku is a numeric crossword puzzle solved by logical analysis and intellectual activity.A certain number of grids have been filled with figures.The goal is to fill up the blank space of 9×9 grids with digits so that each column,each row and each of the 3×3 subgrids contains all the digits from 1 to 9.At the same time,each number can appear only once in each column,each row and each of the 3×3 subgrids.There is only one number in each grid[2]. The goal is to create an algorithm to construct Sudoku puzzles of varying difficulty. Besides,we define difficulty level by means of developing metrics.The algorithm and metrics should be extensible to a varying number of difficulty levels.In the case of guaranteeing a unique solution,we analyse and optimize the algorithm to minimize the complexity of algorithm. The graph of Sudoku puzzle is shown in Figure 1.The digits from 1 to 9 present 9 3×3 subgrids.

Figure 1 The Graph of Sudoku Puzzle

2 Basic Assumptions and Definition (1) In this paper,the size of Sudoku puzzles is defined as 9×9 grids,not involving other sizes of grids. (2) We assume that space complexity has no impact on algorithm.That is,the computer

Team 08

Page 4 of 11

has enough internal storage to satisfy the storage condition. (3)Exhaustive algorithm can be achieved in limited time. 3 Questions Analysis: Sudoku must have a unique solution that can be obtained logically without guessing. Therefore,we need meet the above requirements and rules of Sudoku in the process of modeling it.First and foremost,we develop metrics to define difficulty level by three aspects that the number of known grids,the location of known grids and exhaustive search method.Moreover,we illustrate the algorithm with 4 difficulty levels on the basis of defined difficulty level.Ultimately,we design Sudoku puzzles by way of contrary opinion.In other words,set up a complete Sudoku puzzles firstly and then a certain number of holes are dug out one by one under the circumstances that taking a test for uniqueness of solutions after every diging. 4 Establishment and Solution of Model
4.1 Definition of difficulty level

It is essential to satisfy the condition that Sudoku puzzles has a sole solution and the number of known grids is 17 at least.therefore, we develop metrics to define difficulty level by three aspects that the number and location of known grids, exhaustive search method and some game skills. (1)Define difficulty level by the number and location of known grids[3]: Players solve the problem through reasoning the number of unknown grid.The number and location of known grids determined the information which are provided to players.Consequently,it can be regarded as a criteria for the classification. Given the reasons above,we construct a two-dimensional array to respectively present the number and freedom degree of blank of waiting Sudoku to show difficulty coefficient.Define a two-dimensional array S : Where:
S : the freedom degree array of Sudoku puzzle; l :the sum of all the blanks’ freedom degree;

S ij :the freedom degree of blank in row i column j in Sudoku array S ,
i = 1,2, L ,9; j = 1,2, L ,9 ;

q i :the number of all the blanks in row i , i = 1,2, L ,9 ; q j : the number of all the blanks in column j , j = 1,2, L ,9 ;
G : the freedom degree array of 3×3 subgrids; g mn :the freedom degree of blank in the same 3×3 subgrids removing that of the same

Team 08

Page 5 of 11

row and the same column, m = 1,2,3, n = 1,2,3 ;
Then

S ij = qi + q j + g mn , l = ∑ S ij Based on the value of l ,assign a certain score to it correspondingly.
Table1: Difficulty Level Defined by The Number and Location of Known Grids

Difficulty Level Forth level
Third level Second level First level

l 16 ≤ l 14 ≤ l < 16

Score
5 4 3 2

11≤l <14
l < 11

(2) Define difficulty level by exhaustive search method: Exhaustive method,often referred to as enumeration,is the method that list individual element One by one from possible set.According to constraints given by the subject, find all the solution that make the problem valid. We attempts to fill each blank with digits from 1 to 9,from top to bottom and left to right.Meanwhile,test whether the filled digits satisfy three constraints that each number can appear and must appear only once in each column,each row and each of the 3×3 subgrids.If three constraints can be satisfied,the filled number is valid.If a blank can’t be filled with the digits from 1 to 9,then return to the former blank and replace the number by other untried.Repeat until all the feasible solutions are searched.
Table2: Difficulty Level Defined by Exhaustive Search Method

Complexity of exhaustive search complicated easy (3) Define difficulty level by game skills:

Score 2 1

Many people think that the difficulty of Sudoku puzzles depends on the number of digits which has filled in puzzles.Generally sppeaking,the more the filled digits,the easier the puzzle to be solved.However, in fact, that’s not the case.This requires that there are other ways to determine difficulty level.

Team 08

Page 6 of 11

First level:The game that can be solved by means of Single Number, Hidden Singles or Pairs. Second level: The game that need Hidden Pairs, Locked Candidates and Naked Triples except the method of first level. Third level: The game that need Hidden Triples or X-Wing and so on. Forth level: The game that must apply Forcing chains to solve the problem. Based on different difficulty level,we assign a certain score to it correspondingly.
Table3: Difficulty Level Defined by Game Skills

Difficulty Level Forth level Third level Second level First level

Score 4 3 2 1

(4)In conclusion,we define difficulty level in the light of combinging three methods above.At first,we define some variation.To the same Sudoku puzzles: x : the score obtained by the number and location of known grids.
y : the score obtained by exhaustive search method.
z :the score obtained by game skills.

w1 : the weight of x ; w : the weight of y ;
2

w3 : the weight of z ; sc :the final score. Then: sc = w1 x + w2 y + w3 z . Among:

w1 =0.5; w2 =0.3; w3 =0.2.
Table4:Definition of Final Difficulty Level

Difficulty Level Forth level
Third level Second level First level

sc
4 ≤ sc 3 ≤ sc < 4 2 ≤ sc < 3 sc < 2

Team 08

Page 7 of 11

Next we will take the following figure for example

Figure2 a sudoku puzzle

For the first sight,we may think this is a easy one and then we calculate it now.The score of average freedom is 4 ,the complexity score is 2 and the game skills score is 3.Finally the final score received is 4 × 0.5 + 2 × 0.2 + 3 × 0.3 = 3.3 .Threrfore it
belongs to the third level.It doesn’t mean the lower difficulty level that the number of blanks is relative more,because it is not absolute.
4.2 The establishment of Sudoku puzzles

Algorithm of generating Sudoku is divided into the following three steps:generate the endgame,"dig"on the endgame,implement equivalent transformation for completed puzzle. (1) Generate the endgame: First of all,construct a random Sudoku matrix with only the first line filled with numbers.There are different digits from 1 to 9 in the first row. With the method Solving Sudoku,we get a random result.It is worth noting that the result is not the uniqueness.In this way,we receive a Sudoku matrix that meet the whole constraints of Sudoku puzzle . We define the Sudoku matrix M : Where

i :the number of row, i = 1,2, L ,9

j : the number of column, j = 1,2, L ,9

Team 08

Page 8 of 11

If there is a number in the grid of row i column j ,then assign the number to M ij . If there is not a number in the grid of row i column j ,then define M ij =0. For each grid,if M ij isn’t equal to 0,then the digit of the grid is the result.Else if
M ij is equal to 0,then list all the digits that can fill in the grid. Afterwards,start from

the place where the number of possible values is the least.The possible values are substituted one by one.Finally,we make use of Recursion repeatedly until the digit of all the frids are determined. (2)"Dig"on the endgame: In brief,wipe the word and use the method of anti-solving to verify the uniqueness.Concretely speaking,erase a number a, (a = 1,2,L,9 ) from the figure firstly.Afterwords,fill the position again with an arbitrary number

b, (b ≠ a, b = 1,2,L,9) .If we obtain a result with the program of solving Sudoku
solution,we can say that Sudoku solution is not unique after erasing this number.Then return to erase the other figures to verify the uniqueness of Sudoku solution.Wipe off the number in the grid one by one according to the order of matrix subscript.In this way,a Sudoku puzzle with a unique solution can be obtained. (3)Implement equivalent transformation for completed puzzle: To guarantee the polytropy of producing final grids,we exchange a few lines and a few columns to final grids randomly or exchange each line and each corresponding column.As amatter of fact,the latter is the transposition of final grids.In the meantime,the rules of defining Sudoku puzzle should be satified. Sudoku puzzles produced by the same difficulty level are more multifarious.Increase the challenge of the game as well.
4.3 Analysis of algorithm

The complexity of generating Sudoku puzzle is mainly shown in the generation of endgame and uniqueness confirmation after erasing some blank from endgame. To generate a endgame,firstly establish an empty sudoku matrix.Nine digits from 1 to 9 are arranged fully. Randomly select a list as the first line of matrix. At this point generate a Sudoku puzzle with only the first line filled with digits.With the procedure established for solving Sudoku, a complete Sudoku matrix are got. As the first line number is selected randomly,Sudoku having more than one solution,the results obtained with the procedure is random.Accordingly,the complete Sudoku matrix obtained is random. For different difficulty levels,the time complexity of establishing endgame are the

Team 08

Page 9 of 11

same.However,in the process of establishing different levels games by erasing some blanks,the time complexity are different.This is because the number of blank we want to erase is different.At the same time,adopt depth-first traversal to ensure unique solution after erasing some blanks in the process of erasing blanks. The complexity of different difficulty level game is relative to the number of blanks of the same level,while the complexity of the depth-first traversal is O n 2 .Therefore the complexity of different difficulty level game is O an 2 ,where a stands for the

( )

( )

average freedom degree of each difficulty level.As to the space complexity, nowdays, storage space is not the limitation of the problem.Consequently,we don’t take storage space into consideration. 5 Advantage and disadvantage First,we developed Sudoku algorithm by way of contrary opinon.Consequently, our algorithm was easy and ikonic enough to be understood by anyone.Second,compared to other rules of Sudoku puzzle,we considered relative complete factors in the process of defining difficulty level.Third,we analysed and optimized the algorithm to minimize the complexity of algorithm. However,due to limited time,we only analyzed our modelto calculate the time complexity,no specific algorithms and the others,such as genetic algorithms or Monte Carlo algorithm for further comparison. References [1]Qiong Wang,Sheng Zhou.2010.Solving,Evaluation and Algorithm Generation of Sudoku Problem. Jounal of NanJing Normal University.10(3). [2] http://www.sudokulive.net/. 2011-1-22 [3] ZhiFang Zhao.JingXin Guo.2008.Algorithm Analysis of Generating Sudoku. Neijiang Keji.29(7). Appendix (1)function B=shudu(A)
[a,b]=find(A==0); if isempty(a) B=A; else for i=1:length(a) I{i}=[]; t=1:9;

Team 08

Page 10 of 11

for j=1:9 if A(a(i),j)~=0 t(A(a(i),j))=0; end if A(j,b(i))~=0 t(A(j,b(i)))=0; end end for j=(ceil(a(i)/3)*3-2):(ceil(a(i)/3)*3) for k=(ceil(b(i)/3)*3-2):(ceil(b(i)/3)*3) if A(j,k)~=0 t(A(j,k))=0; end end end I{i}=find(t~=0); if isempty(I{i}) B=[];return; end z(i)=length(I{i}); end [p,q]=min(z); for j=1:p C=A;C(a(q),b(q))=I{q}(j); B=shudu(C); if ~isempty(B); return; end end end

(2)clc,clear
format long g a=perms([1,2,3,4,5,6,7,8,9]); n=factorial(1:9);

Team 08

Page 11 of 11

m=n(9) A=zeros(9); k=fix(rand(1)*m) for i=1:9 A(1,i)=a(k,i); end shudu(A)