Creating Sudoku Puzzles.docx
- 文档编号:17850874
- 上传时间:2023-08-04
- 格式:DOCX
- 页数:40
- 大小:408.59KB
Creating Sudoku Puzzles.docx
《Creating Sudoku Puzzles.docx》由会员分享,可在线阅读,更多相关《Creating Sudoku Puzzles.docx(40页珍藏版)》请在冰点文库上搜索。
CreatingSudokuPuzzles
CreatingSudokuPuzzles
MingweiMa,WeiweiHu,HengGu
Summary
WedevelopacreatingfunctionofSudokupuzzles,
whichreferstofourmainfactors:
randomcandidatepuzzle,uniquenesschecking,difficultycheckingandrulechecking.Accordingtothefourfactors,wedevelopanalgorithmtoconstructrequiredpuzzles.Similarly,ithasfourmainsteps:
(1)CreatingaSudokusolution;
(2)RemovingthecellsrandomlyandformingacandidateforSudoku;(3)Solvingthecandidateinstep2anddeterminingthedifficultylevel;(4)Printingthepuzzle.Thefourstepscandeterminethevaluesoftheparametersofthefourfactors.WeimplementthealgorithmwhichcanguaranteeauniquesolutionandconstructSudokupuzzlesofvaryingdifficulty.
Wedevelopmetricstodefineadifficultylevelbyaccumulatingthedifficultyscore.Thescorecanshowhowmucheffortmustbeexpendedtosolvethepuzzle.Wedividethescoreinto5ranges:
40-60,61-75,76-90,91-200andabove200,whichrepresent5differentlevelofdifficulty.Obviously,themoredifficultthepuzzleis,themoretimeitexpends.Theaveragetimeofdifferentlevelsare(fromeasytodifficult)1s,3s,7s,11s,20s.
Wedesignabinarycomparisonmodel,whichgreatlyreducescomparisonfrequenciesofdifferenttechniques,andminimizethecomplexityofthealgorithm.
DuetothedifferentdifficultylevelofSudokupuzzles,thealgorithmcomplexityisdifferent.Whencreatingeasypuzzles,thecomplexity
.However,whencreatinghardones,thecomplexity
.Thetotalcomplexityofthealgorithmis
.
Contents
1.Introduction……………………………………………2
RulesofSudoku…………………………………………2
RestatementoftheProblem………………………………3
2.VariablesandSymbols……………………………………3
3.Definitions…………………………………………………4
4.ProblemAnalysis…………………………………………5
5.OurModel…………………………………………………5
6.ProblemSolving…………………………………………6
CreatingaSudokuSolution………………………………6
RemovingtheAppropriateNumberofCellsRandomly.……6
SolvingtheCandidateandDeterminingtheDifficultyLevel.…7
OurBinaryModel…………………………………7
UniquenessChecking……………………………11
DifficultyChecking………………………………11
PrintingthePuzzle……………………………………12
7.AnalysisoftheAlgorithmComplexity…………………13
8.Conclusions………………………………………………14
9.ModelAssessment………………………………………15
References……………………………………………16
Appendixes……………………………………………17
CreatingSudokuPuzzles
1.Introduction
Sudokuisapuzzlegamethatistakingtheworldbystorm.ThenameSudokuistheJapanesewordfor"placementpuzzle".SudokusweptJapaninthemid-1980's.Beforethat,however,apuzzleconstructorintheUnitedStatesnamedHowardGarnescreatedthefirstpuzzleofthistypein1979.Itwascalled"NumberPlace"insteadofSudoku.ItwaspublishedintheDellMagazineMathPuzzlesandLogicProblems[1].
Sudokupuzzlesare9×9grids,andeachsquareinthegridconsistsofa3×3subgridcalledminigrid.Thegoalistofillinthesquaressothateachcolumn,row,andminigridcontainsthenumbers1through9exactlyonce.Andsomesquaresalreadycontainnumbers,whichlendcluestowardthesolution.WhiletherulesofSudokuissimple,itisreallyachallengetosolveaSudoku.
Figure1showsapartiallyfilledgridatthestartofaSudokupuzzle.
Figure1:
ASudokupuzzle.
Fromamathematicalperspective,ithasbeenproventhatthetotalnumberofvalidSudokugridsis6,670,903,752,021,072,936,960[2].
RulesofSudoku
TherulesofSudokuareextremelysimple.Eachnumber1-9canappearonlyonceineachcolumn,onceineachrow,andonceineachsmall3×3grid.Figure1showsaSudokugridwithitsnineminigrids.
Everypuzzlehasjustonecorrectsolution.Figure2showstheuniquesolutiontotheSudokupuzzlementionedinFigure1.
Figure2:
Theuniquesolution.
RestatementoftheProblem
WeareaskedforanextensiblealgorithmwithauniquesolutiontoconstructSudokupuzzlesofatleast4difficultylevels.Thecomplexityofouralgorithmisrequiredtobeanalyzedandbeminimizedwithoutreducingallrequirements.
2.VariablesandSymbols
:
CandidateSudokupuzzle
:
Ruleparameter
:
Uniquenesscheckingparameter
:
Difficultycheckingparameter
:
ANDbitmanipulation
:
ORbitmanipulation
:
EITHER-ORbitmanipulation
:
Candidateelementinthesamecell
:
F{thesoleelementinthesamerow}
:
F{thesoleelementinthecolumn}
:
F{thesoleelementinthesameminigrid}
:
ThevalueofORbitmanipulationforalltheelementsinthesamerow
:
ThevalueofORbitmanipulationforalltheelementsinthesamecolumn
:
ThevalueofORbitmanipulationforalltheelementsinthesameminigrid
n:
Scaleoftheproblem;
:
Totalcomplexity;
:
Complexitycausedbycyclictimesofthemainprogram;
:
AlgorithmcomplexityofconstructingaSudokusolution;
:
Algorithmcomplexityofrandomexcavation;
:
Algorithmcomplexityofsimplesolving;
:
Algorithmcomplexityoftrialtechnique.
3.Definitions
·Difficultyscore
IntheprocessofsolvingaSudokupuzzle,acellisconfirmedbyaparticulartechniqueeachtime,weaddpointstoacounter(thenumberofpointsweadddependsonthetechniqueapplied).Whenthepuzzleissolved,thetotalpointsaccumulatedservesasanindicationofthetotalamountofeffortneededtosolvethepuzzle.Thetotalpointsaccumulatedarecalleddifficultyscore.
·Difficultylevel
Accordingtodifficultyscoresweclassifydifficultylevelsasfollows.SeeTable1
.
Difficultyscore
40-60
61-75
76-90
90-200
above200
Difficultylevel
Simple
Medium
Mediumdifficult
Difficult
Extremely
difficult
Table1:
DifficultyLevelsCorrespondingtoDifficultyScores.
·Uniquenesschecking
Checkthepuzzlewhetherithasoneandonlyonesolutioninordertoguaranteeauniquesolution.
·Rulechecking
Checkthesolutionwhethersomecellsviolatetherules,soastoensurethepuzzlesolvedsuccessfully.
·Difficultychecking
Checkthedifficultyscorewhetherintheacceptablerangeoftherequireddifficultylevel.
·CRME
Whenwetrytoplaceanumberinacell,wehavetoexaminetherowandthecolumnandscanwithinitsminigrid.Accordingtotherulestoeliminatethepossiblevaluesalreadypresentinrow,columnorminigrid.Ifthereisonlyonepossiblevalueforthecell,thenumberforthecellisconfirmed.SowecallthetechniqueCRME(Column,RowandMinigridElimination).
·Uniquenesstechnique
Sudokupuzzlesstipulatethatthenumber1to9mustappearrespectivelyonceineverygroup.Accordingtothisrule,ifsomenumberamongcandidatenumbersoftheemptycelldoesnotappearamongothercandidatenumbersoftheemptycellthenthisnumberisexactlytheoneshouldbefilledinthisemptycell.
·Trialtechnique
Ifthereareseveralcandidatenumbers,andtheabovetwotechniquescannotdeterminethenumberthatshouldbefilledin,thenthetrialtechniqueshouldbeapplied.Bythistechnique,acandidatenumberisfilledinthisemptycell,andthenthepuzzleissolved.Ifacontradictionemerges(e.g.,thereisnocandidateintheemptycell),itshowsthatthiscandidatenumbershouldbeeliminated.
4.ProblemAnalysis
Itisdifficulttocreateapuzzle.ButifwehaveasolutiontoacertainSudokupuzzle,wecangetanewSudokupuzzleeasilybyremovingnumbersfromthiscompletedSudokupuzzlesolution.Soourdifficultiesaretoguaranteeauniquesolutionandmakethedifficultyscoreintheacceptablerangeofrequireddifficultylevel,respectively.Thesetwodifficultiescanbesurmountedbyuniquenesschecking,difficultycheckingandrulechecking.Fromthisprocess,anextnewdifficultyemerged,whichishowtogetthedifficultyscoreofthenewSudokupuzzle.Thisdifficultycanbesurmountedinthefollowingstep,i.e.,howtosolvethepuzzle.Wedevelopconvenientandeffectivetechniquestosolvethepuzzle.Intheprocesswecangetthedifficultyscoreanddifficultylevelaccordingtodefinition.
5.OurModel
Accordingtotheanalysisoftheproblem,wecangetthefollowingfunctions:
Ourobjectivefunctionis
where
.
Thevariablexisavalidseedvalue.Wecanuseittocreateanewcandidatepuzzlerandomly.
ThevalueofRcanbedeterminedbythisfunction.
Thealgorithmofthisfunctioncanbeseenin6.1and6.2.
IfS=U=D=1,thenPFun=R,sowecreateaqualifiedpuzzle.
6.ProblemSolving
6.1CreatingaSudokusolution
WerandomlycreateasolutionwhichdoesnotviolatetherulesoftheSudoku.Wecangetmanydifferentsolutionsbyrandomlyswitchingtwocolumnsorrowsinagroup,orrandomlyswitchingtwobiggroups,orexchangingallpositionsfortwonumbers.Thisisasimplebuteffectiveapproachtogenerateanewsolution[2].
Forexampleasthefollowingfigure3,therow1,2,3areinthesamegroup.Wecanexchangetherow1androw2andgetanewsolutionasfigure4.
Figure3(left)4(middle)5(right):
Switchingsamples.
Anotherexample,weexchangeallpositionsfornumber1and2andgetanewsolutionasthefigure5.
Algorithm:
Step1.Getavalidsolution
Step2.Randomlyswitchtwocolumnsorrowsinagrouporswitchtwobiggroups
Step3.Randomlyswitchallpositionsfortwonumbers.
Theprogramcanbeseeninappendix2(build.m).
6.2Removingtheappropriatenumberofcellsrandomly
Inthisstep,wecangetacandidate(R)fortheSudokupuzzles.Also,wecangetthevalueofSveryeasily.
Algorithm:
Step1.Letcounter=0;
Step2.Ifthecounter>requiredvalue,returntheresult;
Else,enterthenextstep.
Step3.Selectingtwonumbers(1-9)astherownumberiandcolumnnumberj.
Step4.IfthecellA(i,j)isempty,returntostep3,
Else,enterthenextstep.
Step5.Letthecellbeemp
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Creating Sudoku Puzzles
![提示](https://static.bingdoc.com/images/bang_tan.gif)