库珀如何选择随机数独板-数模讲座20

HowtoChooseaRandomSudokuBoardJoshuaCooperUSCDepartmentofMathematicsRules:Placethenumbers1through9inthe81boxes,butdonotletanynumberappeartwiceinanyrow,column,or3

3“box”.Youstartwithasubsetofthecellslabeled,andtrytofinishit.137874859281668712847181375965428326159924761347533129465875394596137223695844296ASudokupuzzledesignerhastwomaintasks: 1.Comeupwithaboardtouseasthesolutionstate. 2.Designatesomesubsetoftheboard’ssquaresastheinitiallyexposed numbers(“givens”).Forexample:1378748592816687128471813756542832615992476134753312946587539459613722369584429691378748592816687128471813759We’regoingtofocusontask#1:HowtochooseagoodSudokuboard?BOARDPUZZLECELLCOLUMNROWBOXSTACKBANDGIVENNotallboardsarecreatedequal.Somemakelousypuzzles:888888888999999999222222222333333333444444444111111111555555555777777777666666666ItwouldbepreferabletogeneraterandomSudokuboardswhendesigningapuzzle.Furthermore,therearemanymathematicalquestionsonecanaskaboutthe“average”Sudokuboardthatrequirethatwebeabletogeneraterandomones.Forexample:1.Howoftenarethe1and2intheupper-left3X3boxinthesamecolumn?3.Whatistheprobabilitythatthepermutationof{1,…,9}thatthefirsttworowsprovideiscyclic?1397874654283261591567923481567923481567923482.Whatistheaveragelengthofthelongestincreasingsequenceofnumbersthatappearinanyrow?Furthermore,therearemanymathematicalquestionsonecanaskaboutthe“average”Sudokuboardthatrequirethatwebeabletogeneraterandomones.Forexample:1.Howoftenarethe1and2intheupper-left3X3boxinthesamecolumn?2.Whatistheaveragelengthofthelongestincreasingsequenceofnumbersthatappearinanyrow?3.Whatistheprobabilitythatthepermutationof{1,…,9}thatthefirsttworowsprovideiscyclic?4.Whataboutthe“generalizedSudokuboard”?Forexample,16X16:Furthermore,therearemanymathematicalquestionsonecanaskaboutthe“average”Sudokuboardthatrequirethatwebeabletogeneraterandomones.Forexample:1.Howoftenarethe1and2intheupper-left3X3boxinthesamecolumn?2.Whatistheaveragelengthofthelongestincreasingsequenceofnumbersthatappearinanyrow?3.Whatistheprobabilitythatthepermutationof{1,…,9}thatthefirsttworowsprovideiscyclic?4.Whataboutthe“generalizedSudokuboard”?Forexample,16X16:Inordertogetanapproximateanswertothesequestions,onecould: a.)Generatelotsofrandomexamples. b.)Computetherelevantstatisticforeachofthem. c.)Averagetheanswers.Thisgeneraltechniqueiscalledthe“MonteCarlo”method.Itisveryusefulformathematicalexperimentation,anditcomesupallthetimeinappliedmathematics(usuallytoapproximatesomesortofintegral).Attempt#1:Fillanemptyboardwithrandomnumbersbetween1and9.IftheresultisnotavalidSudokuboard,discardtheresultandtryagain.Problem#1:ThechancesthatarandomboardisactuallyaSudokuboardisabout3X10-56.Evenifwecouldcheckatrillionexampleseverysecond,itwouldstilltake7X1025timeslongerthantheuniversehasbeenaroundbeforeweexpecttoseeasinglevalidboard.Attempt#1b:Eachrowisactuallyapermutation(i.e.,nonumberoccurstwice),sogenerate9randompermutationsuntilavalidSudokuboardresults.Problem#1:ThechancesthatarandomboardisactuallyaSudokuboardisabout6X10-29.Again,evenifwecouldcheckatrillionexampleseverysecond,itwouldstilltake500billionyearsbeforeweexpecttoseeasinglevalidboard.Attempt#1c:Startwithanemptyboard.Randomlychooseanunoccupiedlocationandfillitwitharandomnumber,chosenfromamongthosethatcanlegallylivethere.Problem#1:Wemayrunoutoflegalmoves!Problem#2:Noteveryboardisequallylikelytoemergefromthisprocess.Attempt#1caddendum:Okay,sojuststartoverifyougetstuck.

Despitethisfact,mostboardgeneratingsoftwareoutthereusesthisstrategy.Attempt#2:GenerateallSudokuboardsandpickoneuniformlyatrandomfromthelistofallofthem.Problem#1:Thereare6,670,903,752,021,072,936,960(~6.7×1021=6.7sextrillion)differentSudokuboards(Felgenhauer-Jarvis2005).Evenat4bitspersymbol,thistranslatestoabout270billionterabytes=approx.$18trillion($68per1TBharddrive,saysGoogle)=approx.130%ofUSannualGDPProblem#2:Thisgeneralizesverypoorlytolargerboards.(Thereareabout6×109816X16boards>>numberofatomsintheknownuniverse.)Attempt#3:GeneratealistofonerepresentativeofeachorbitofSudokuboardsunderthenaturalsymmetries:rotation,transposition,permutingsymbols,permutingrowswithinahorizontalband,permutingcolumnswithinaverticalband,permutinghorizontalbands,andpermutingverticalbands.Attempt#3:GeneratealistofonerepresentativeofeachorbitofSudokuboardsunderthenaturalsymmetries:rotation,transposition,permutingsymbols,permutingrowswithinahorizontalband,permutingcolumnswithinaverticalband,permutinghorizontalbands,andpermutingverticalbands.Theoperations:1.Permutingtherowsandcolumnsofeachband/stack(X3!6)IIIIIIABC2.PermutingbandsI,II,andIII,andandstacksA,B,andC(X3!2)3.Permutingthenumbers/colors(X9!)Attempt#3:GeneratealistofonerepresentativeofeachorbitofSudokuboardsunderthenaturalsymmetries:rotation,transposition,permutingsymbols,permutingrowswithinahorizontalband,permutingcolumnswithinaverticalband,permutinghorizontalbands,andpermutingverticalbands.Theoperations:1.Permutingtherowsandcolumnsofeachband/stack(X3!6)2.PermutingbandsI,II,andIII,andstacksA,B,andC(X3!2)3.Permutingthenumbers/colors(X9!)4.Rotatingtheboard(X2)IIIIIIABCAttempt#3:GeneratealistofonerepresentativeofeachorbitofSudokuboardsunderthenaturalsymmetries:rotation,transposition,permutingsymbols,permutingrowswithinahorizontalband,permutingcolumnswithinaverticalband,permutinghorizontalbands,andpermutingverticalbands.Theoperations:1.Permutingtherowsandcolumnsofeachband/stack(X3!6)2.PermutingbandsI,II,andIII,andstacksA,B,andC(X3!2)3.Permutingthenumbers/colors(X9!)4.Rotatingtheboard(X2)IIIIIIABCgenerateagroupoforder1,218,998,108,160.Thenumberoforbitsofthisgroup(i.e.,thenumberof“trulydistinct”boards)=5,472,706,619.Attempt#3:GeneratealistofonerepresentativeofeachorbitofSudokuboardsunderthenaturalsymmetries:rotation,transposition,permutingsymbols,permutingrowswithinahorizontalband,permutingcolumnswithinaverticalband,permutinghorizontalbands,andpermutingverticalbands.Problem#1:Youcan’tjustpickauniformlyrandomchoiceoforbit:someorbitsarebiggerthanothers.Infact,youhavetochoosethemwithprobabilityproportionaltotheirsizes.Thismeansdoingabigcomputationusing“Burnside’sLemma.”Problem#2:Again,thisscalesverypoorly.Thenumberoforbitsforthe16X16boardisapproximately2.25×1071.Stillridiculouslylarge.Attempt#4:Startwithsome

Sudokuboardandmakesmall,randomchangesforawhile.Theresultshouldbeclosetouniformlyrandom.Thisgeneralstrategyisknownasa“randomwalk”or“Markovchain.”WhenpairedwithMonte-Carlotypecalculations,wehave“MarkovChainMonteCarlo”,orMCMC.Whyisitcalleda“randomwalk”?Whyisitcalleda“randomwalk”?Whyisitcalleda“Markovchain”?AndreyMarkov(АндрейАндреевичМарков)1856–1922Considerthe4X4case(thereare288boards,butonly2essentiallydistinctones!)1234341223414123What“smallchanges”canwemaketogetbetweenthem?1234341221434321Considerthe4X4case(thereare288boards,butonly2essentiallydistinctones!)1234341223414123What“smallchanges”canwemaketogetbetweenthem?123434122341412322134341213414123213434121342422312343412214343211234341223414123221343412134141232134341213424223123434122341412322134341213414123213434121342422321343411134242132134342113424213Allwedidwasrelabeltheboardbyswitching1’sand2’s!It’snothardtoseethateachelementgofGcanbefactoreduniquelyintoaproductofarelabeling

L,acolumnpermutationC,arowpermutationR,and(possibly)aquarter-turnQ:wherej

=

0or1.1234341223414123323434122341412343214112234141233214143223414123Prop.Ifthesequenceofmovesterminatesbeforereachingeveryvertex,theresultisatrulydifferentsudokuboard.Proof.LetGbethegroupofLatinsquareisotopies:thegroupgeneratedbyrelabelings,rotations,andallrowandcolumnpermutations(notjustin-bandorin-stack).Supposej=0.WhetherornotLflipsthecolorsredandblue,someoneofthesecyclesisflipped,whileanotherisnot.SupposethatginG0exchangessomeredsandblues,butnotall–andotherwisefixesthecontentofeverycell.NotethattheSudoku

isotopygroupG0

isasubgroup

of

G.WritegasBypermutingrowsandcolumnstogrouptogethercyclesofredsandblues,wegetthattheactionofglookssomethinglike:gThesequenceofrowandcolumnpermutationsrequiredtoflipthecolorseitherreversesrowsorcolumns.oncbedjfhglimakabdeghijklnocfmbcehinmnldogfoaTherefore,therelabeling

Lmustpermutesymbolsa—o.Butthischangesthecontentsofothercells–acontradiction.It’seasytocheckthej=1caseaswell(anddealwiththecaseswherethecyclesareonly4or6inlength).But,doeseverySudokuboardhaveacyclethatterminates“early”?Torestate:DefineagraphHonthesetofcellswithacompletesubgraphineachrow,column,andbox.Colorverticesaccordingtothecontentsofthecells.DefineHijtobethesubgraphofHinducedbyverticesofcoloriandj.Conjecture:ForanySudokuboard,thereareaniandajsothatHijisdisconnected.But,doeseverySudokuboardhaveacyclethatterminates“early”?Torestate:DefineagraphHonthesetofcellswithacompletesubgraphineachrow,column,andbox.Colorverticesaccordingtothecontentsofthecells.DefineHijtobethesubgraphofHinducedbyverticesofcoloriandj.Question:CanonegetfromanySudokuboardtoanyotherviaasequenceofsuchmoves?(Ifso,thenthisMCMCstrategywillwork!)Conjecture:ForanySudokuboard,thereareaniandajsothatHijisdisconnected.Attempt#5:Relaxalinearprogram.Usetheedgesoftheresultingpolytopeasthe“moves”tomakeintherandomwalk.Writexijkforavariablethatindicateswhetherornotcell(i,

j)isoccupiedbycolork.(Soxijk

=1ifso,xijk=0ifnot.)Then,lettingi,j,andkvaryover{1,…,9}wehavethefollowingconstraintsthatdescribeavalidSudokuboard.Attempt#5:Relaxalinearprogram.Usetheedgesoftheresultingpolytopeasthe“moves”tomakeintherandomwalk.Writexijkforavariablethatindicateswhetherornotcell(i,

j)isoccupiedbycolork.(Soxijk

=1ifso,xijk=0ifnot.)Then,lettingi,j,andkvaryover{1,…,9}wehavethefollowingconstraintsthatdescribeavalidSudokuboard.Attempt#5:Relaxalinearprogram.Usetheedgesoftheresultingpolytopeasthe“moves”tomakeintherandomwalk.Writexijkforavariablethatindicateswhetherornotcell(i,

j)isoccupiedbycolork.(Soxijk

=1ifso,xijk=0ifnot.)Then,lettingi,j,andkvaryover{1,…,9}wehavethefollowingconstraintsthatdescribeavalidSudokuboard.forj,k=1,…,9fori,k=1,…,9fori,

j=1,…,9Attempt#5:Relaxalinearprogram.Usetheedgesoftheresultingpolytopeasthe“moves”tomakeintherandomwalk.Writexijkforavariablethatindicateswhetherornotcell(i,

j)isoccupiedbycolork.(Soxijk

=1ifso,xijk=0ifnot.)Then,lettingi,j,andkvaryover{1,…,9}wehavethefollowingconstraintsthatdescribeavalidSudokuboard.Thesetoftheseequationsdefinesanintegerprogram,thesetofwhosesolutionscorrespondexactlytovalidSudokuboards.form,n=0,1,2;k=1,…,9forj,k=1,…,9fori,k=1,…,9fori,

j=1,…,9Attempt#5:Relaxalinearprogram.Usetheedgesoftheresultingpolytopeasthe“moves”tomakeintherandomwalk.Writexijkforavariablethatindicatesw