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)

更多相关文章：
**
***九宫格数独游戏*题目.doc

*九宫格数独游戏*题目 - *九宫格数独游戏*题目 如果有想了解*数独游戏*的朋友可以给我留**
6、有趣的***数独游戏*.doc

6、有趣的*数独游戏* - 六、有趣的*数独游戏* 目标导航 ? 认识数独,了解数独的游戏规则和数独的基本技巧。能采用排除、假设等方法 完成一些简单的*数独游戏*。 ? 通过...**
***数独游戏*题目.doc

*数独游戏*题目_教学案例/设计_教学研究_教育专区。 您的评论 发布评论 用户评价 这是我最近看到的关于非多酷用户最好的文章 2018-06-19 23:34:01 *数独游戏*...**
***数独游戏*的玩法和技巧.doc

*数独游戏*的玩法和技巧 - *数独游戏*的玩法和技巧 *数独游戏*是一款比较经典的益智游戏,玩好*数独游戏*首先要了解*数独游戏*的特 点、要求,然后就是要运用一些原则和技巧,...**
***数独游戏*设计与源码.doc

*数独游戏*设计与源码_IT/计算机_专业资料。文档介绍了*数独游戏*的设计并贴了源码 **
***数独游戏*题目简单.doc

*数独游戏*题目简单 - 难度系数 1 完成时间___分钟 7 3 6 5 1 1 **
四宫格***数独游戏*.ppt

四宫格*数独游戏* - 4宫格数独 四宫格(数独) 填数游戏: 使每行、每列、每 个**
破解***数独游戏*9×9的规则.doc

破解*数独游戏*9×9的规则 - 破解*数独游戏*九乘九的规则 先注意其中一个方格,限定**
***数独*六宫格智力*游戏*练习.doc

数独六宫格智力游戏练习 - 玩转学习“*数独游戏*” 姓名: 班级: *数独游戏* 1 *数独游戏* 2 *数独游戏* 3 *数独游戏* 4 *数独游戏* 5 *数独游戏* 6 数...**
***数独*入门-儿童*数独游戏*第1级-唯一法4X4.pdf

数独入门-儿童*数独游戏*第1级-唯一法4X4_家庭教育_幼儿教育_教育专区。数独入门,儿童*数独游戏*,培养逻辑思维能力 1 、 2 、 2 2 3 2 3 3 2 2 3 2 1 3 ...**
***数独游戏*题目(简单).doc

*数独游戏*题目(简单) - 难度系数 1 完成时间___分钟 7 3 6 5 1 **
***数独游戏*设计论文.doc

*数独游戏*设计论文 - XXXXXX 大学信息工程学院 C++面向对象实习报告 题 目: *数独游戏*的设计与实现 学姓 号名 0000000000 XXX 计算机科学与技术 XX 班...**
***数独*入门-儿童*数独游戏*第4级-二余法4X4.pdf

数独入门-儿童*数独游戏*第4级-二余法4X4_家庭教育_幼儿教育_教育专区。数独入门,儿童*数独游戏*,培养逻辑思维能力。 1 、 2 、 2 4 2 、 1 2 3 4 3 4 1...**
***数独*六宫格智力*游戏*练习.doc

数独六宫格智力游戏练习 -*数独游戏* 1 *数独游戏* 2 *数独游戏* 3 *数独游戏* 4 *数独游戏* 5 *数独游戏* 6 *数独游戏* 7 *数独游戏* 8 数独...**
简单的***数独游戏*求解程序(matlab).doc

简单的*数独游戏*求解程序(matlab) - function S=sudoku(**
***数独游戏*打印.doc

*数独游戏*打印 - 几个*数独游戏*题,给数独爱好者... *数独游戏*打印_游戏_生活休闲。几个*数独游戏*题,给数独爱好者 您的评论 发布评论 用户评价 很好,值得借鉴,*数独游*...**
小学***数独游戏*校本课程教材_图文.doc

小学*数独游戏*校本课程教材 - 小学*数独游戏*课程标准 一、课程背景与特点 新修订的**
高难度的***数独* 你敢挑战吗?--益智游戏 *数独游戏* 数独技巧.doc

当前位置:琳琅在线 >> 益智游戏 >>*数独游戏* &g**
***数独游戏*中级技巧.doc

*数独游戏*中级技巧 - 数独中级技巧 技巧 9 摸着石头过河(通过一个九宫的信息推**
EXCEL***游戏*-*数独*.xls

EXCEL游戏-数独 - 功能说明: 1. 提供不同难度的*数独游戏*生成和自动解题 更多相关标签：

6、有趣的

四宫格

破解

数独六宫格智力游戏练习 - 玩转学习“

数独入门-儿童

数独入门-儿童

数独六宫格智力游戏练习 -

简单的

小学

当前位置:琳琅在线 >> 益智游戏 >>

EXCEL游戏-数独 - 功能说明: 1. 提供不同难度的