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)

赞助商链接

更多相关文章：
**
***数独游戏*

*数独游戏*_一年级数学_数学_小学教育_教育专区。*数独游戏*(一)四阶数独: 游戏规则: 1) 16 方格每行、每列分别填上 1 至 4 的数字,不能重复,也不能 遗漏。...**
***数独游戏*课程_图文

*数独游戏*课程_法律资料_人文社科_专业资料。*数独游戏*课程标准一、课程背景与特点 新修订的《小学数学课标》非常重视小学生数学兴趣的培养,提出“使学生具有学习数 学...**
***数独*解题的基本技巧完整篇

*数独*解题的基本技巧完整篇_*游戏*_生活休闲。*数独*解题的基本技巧完整篇---由浅入深的学习以前已经写过类似的文章,不过好像太偏向于高难度的技巧,像是 X-Wing, Y-...**
***数独游戏*

新民小学六上数学 实践活动课 活动单*数独游戏* 活动目的:了解数独的相关知识,丰富学生的课余生活,培养学生的数感和逻辑推理 能力。 活动过程: 活动一:初步了解数独...**
第11讲 专题:***数独游戏*的编程

第20 讲*数独游戏*的 Matlab 编程 1 数独问题简介 九宫图:9*9 矩阵,要求每行、每列、每个小宫的九个格子不重复的填入 1~9 的九 个数字,且一个数在所在的...**
高难度的***数独*_你敢挑战吗?--益智游戏_*数独游戏*_数独技...

高难度的数独_你敢挑战吗?--益智游戏_*数独游戏*_数独技巧_游戏_生活休闲。学习*数独游戏*掌握数独技巧之必看 直观法 1 唯一解法 1 区块摒除法 8 基础摒除法 4 唯...**
***数独游戏*的入门规则

*数独游戏*的入门规则_游戏_生活休闲。*数独游戏*的入门规则数独是一种填数的小游戏,从出现到现在已有几十年的历史了,从最初刊登到 报纸和书籍上,现在搬到电脑上,玩...**
***数独游戏*

*数独游戏*_法律资料_人文社科_专业资料。123 浙江建设职业技术学院 *数独游戏* 设计说明书(2016/2017 学年第一学期) 题目:*数独游戏* 专业班级:计算机 15-1 班 学生...**
***数独游戏*要求和规则

*数独游戏*要求和规则_六年级数学_数学_小学教育_教育专区 暂无评价|0人阅读|0次下载|举报文档*数独游戏*要求和规则_六年级数学_数学_小学教育_教育专区。*数独游戏*要求...**
***数独游戏*

___*数独游戏*___ 设计地点:___理工楼319___ 2014/5/18 答辩成绩: 指导教师:_李平__ 完成日期:___ ___ 成绩:___ 一、设计题目(包括输入、输出、功能...
更多相关标签：

新民小学六上数学 实践活动课 活动单

第20 讲

高难度的数独_你敢挑战吗?--益智游戏_

___