slitherlink.pdf

(1116 KB) Pobierz
435831961 UNPDF
TheSlitherlinkPuzzle
TonyH¨urlimann
tony.huerlimann@unifr.ch
March31,2008
TheSlitherlinkPuzzle( slitherlink )
Slitherlink(alsoknownasFences,Takegaki,LooptheLoop,Loopy,Ouroboros,
SurizaandDottyDilemma)isalogicpuzzlepublishedbyNikoli 1 ,oneofthe
wellknownpuzzleproducerinJapan.Thepuzzleisnotyetsopopularas
Sudoku,but2dozensofbooksalreadyexistthatareentirelydedicatedto
SlitherlinkandplentyofonlinepuzzlescanbefoundontheInternet.Solving
thepuzzleisaninterestingpasstime,someofthemarequiteeasyhowever
manyareverydicultandmanyhoursarerequiredtosolvethemmanuallly.
Ourmaininterest,however,istopresentmethodsfromMathematicsand
fromComputerSciencetosolvethepuzzleusingsystematicalmethods.We
presenttwodierentmethodstoapproachthesolutionofthispuzzle.The
firstisthroughamathematicalmodelformulation,thesecondisadepthfirst
searchmethod.Bothmethodsstandfortwoparadigmsthatareextremely
usefulforsolvingmanyproblems–notonlypuzzles.Hence,byshowing
thetwoapproaches,webringthesegeneralmethodstotheattentionofthe
readerbyusingthisinnocentlookingproblemexample.
Slitherlinkisplayedonarectangularlattice(grid)ofdots.Someofthecells Problem
(squares)formedbyfourdotshavenumbersinsidethem.Theobjectiveis
toconnecthorizontallyandverticallyadjacentdotssothatthelinesform
asingleloopwithnolooseends.Inaddition,thenumberinsideasquare
(cell)representshowmanyofitsfoursidesmustbesegmentsintheloop.
Thisnumbercanbe0,1,2,or3.Ifthesquareisempty,anynumberoflines
segments(0to3)canbesegmentsoftheloop.
1 http://www.nikoli.co.jp/en/
1
Figure1:ASlitherlinkPuzzleanditsSolution
AnsmallexampleisgiveninFigure 1 .Thispuzzlecontainsa3inthe
square(1,1)(squareonthefirst(top-most)rowandthefirst(left-most)
column),forexample,hencetheloopmustincludethreeofthefourlineseg-
mentsofthissquare(1,1).Wecaneasyverifythateachsquareissurrounded
bytheappropriatenumberoflinesegments.
MatematicalModellingApproach
Wefirstpresenttheapproachthatformulatesthepuzzleasamathematical
model.Thisapproachisveryappealing,becausethemodelissoconcise
andunderstandable.However,ithassomedrapdoorswhichcanbecircum-
navigatedinanelegantway.Weshowthisbypresentingmethodsthatare
extremelycommonandusefultosolvelargemathematicaldiscreteproblems,
calledcutgenerationsinOperationsResearch.
ModelingSteps
Howcanwemodelthispuzzleasamathematicalmodel?First,wedefine
thedimensionsofthepuzzleassets.
1.Vertically,wehavensquares(cells),andhorizontally,wehavem
squares(cells).Wedefinethesetsi={1...n+1}ofverticaldots
andthesetj={1...m+1}ofhorizontaldotswithinthegrid.
2.Eachdotsisadjacenttoatmostfourlinesegmentsconnectingthe
neighboringdotsattheright,atthebottom,attheleft,andatthe
top.Wedefinethesetofthefoursides{right,bottom,left,top}by
2
435831961.001.png
k={1,2,3,4},where1means’rightside’,2means’bottomside’,3
means’leftside’,and4means’topoftheside’.
3.Aboutthepositionofadotoracell,wemakeaconvention.Wesay
that(i 1 ,j 1 )isthei 1 -thdotfromthetopandthej 1 -thdotfromtheleft,
fori 1 2iandj 1 2j.Thepositionofacellisindicatedinasimilarway:
thecell(i 1 ,j 1 )isthethei 1 -thcellfromthetopandthej 1 -thcellfrom
theleft,fori 1 2{1...n}andj 1 2{1...m}.Hence,the(i 1 ,j 1 )dotis
theleft-topcornerofthecell(i 1 ,j 1 ).Notethatthereisoneadditional
dotineachdirectioncomparedtothenumberofcells.
4.Wedefinethelinesegment(i,j,k)astheedgelinkingthedot(i,j)
withdot(i,j+1)(ifk=1),withdot(i+1,j)(ifk=2),withdot
(i,j−1)(ifk=3),andwithdot(i−1,j)(ifk=4).
5.Theuniquedataisamatrixa i,j whichdefinesthenumberinsidethe
square(cell)(i,j)foreachi2{1...n}andj2{1...m}.Wedefine
a i,j 2{−1,0,1,2,3}.Ifa i,j is0,1,2,or3,thenthismeansthatthe
squaremustbesurroundedby0,1,2,or3linesegments.Ifa i,j is
−1,wemaketheconventionthatthesquarecanbesurroundedbyany
numberoflinesegments(upto3).
6.Weintroduceabinaryvariablex i,j,k ,oneforeachlinesegment(i,j,k).
Itisdefinedtoby1,ifthelinesegmentk2Kofthedot(i,j)isin
thesolutionloop,and0otherwise(thesegmentisnotintheloop).For
example,x 2,2,4 =1meansthatthelinesegmentfromdot(2,2)tothe
dot(1,2)(whichisjustabove)isintheloop.Ofcourse,thesevariable
isonlydefined,if(i>1ork6=4)and(j>1ork6=3)and(inor
k6=2)and(jmork6=1).
7.Now,therightlinesegmentofanydot(i,j)istheleftlinesegmentof
thedot(i,j+1)foralli2{1...n}andj2{1...m−1}.Thismeans
thatx i,j,1 =x i,j+1,3 foralli2{1...n}andj2{1...m−1}.This
definestheconstraint A inthemodel.
8.Inthesameway,thebottomlinesegmentofadot(i,j)isthetop
linesegmentofthedot(i+1,j)foralli2{1...n−1}andj2
{1...m}.Thatmeansthatx i,j,2 =x i+1,j,4 foralli2{1...n−1}and
j2{1...m}.Thisdefinestheconstraint B inthemodel.
9.Iftheentrya i,j ofacell(i,j)is−1,thentherecanatmostbethreeline
segmentssurroundingthecell(i,j)intheloop,Thefourlinesegments
surroundingacell(i,j)are:(i,j,1),(i,j,2),(i+1,j+1,3),and(i+
3
1,j+1,4).Thatmeansthatthesumofthecorrespondingfourvariables
x i,j,1 +x i,j,2 +x i+1,j+1,3 +x i+1,j+1,4 mustnotbegreaterthan3.Thisis
definedbyconstraint C .
10.Forallothersquares(i,j)wehavea i,j 6=−1.Forthemweimpose
thatthenumberofsurroundinglinesegmentsisexactlythenumber
a i,j .Hence,thesumofthecorrespondingfourvariablesx i,j,1 +x i,j,2 +
x i+1,j+1,3 +x i+1,j+1,4 mustbea i,j .Thisisspecifiedbyconstraint D .
11.Furthermore,foreachdot(i,j)thenumberofthefourlinesegments
(i,j,k)mustbeeitherzeroor2–eitherthedotisnotpartoftheloop,
thenallfourlinesegmentsadjacenttothedotarenotintheloop,or
thedotispartoftheloop,thenthereareexactlytwolinesegments
passingthroughthedot.Thisfactisexpressedbytheconstraint E .
12.Weshallminimizethenumberoflinesegmentsintheloop.Hencethe
objectivefunctionis: P i,j,k x i,j,k .
ThemodelsofarcanbecodedinLPLasfollows:
modelslitherlink"TheSlitherlinkPuzzle";
parametern"Verticalnumberofcells";
m"Horizontalnumberofcells";
seti:1..n+1;j:1..m+1;
k:=1..4"Foursidesateachdot";
parametera{i,j}default-1"Numberinsidecell(’-1’fornone)";
parameterT:=[1];
readfrom’slitherlink.txt’’%T:table’:n,m,row{i}(col{j}a);
binaryvariableX{i,j,k|(i>1ork<>4)and(j>1ork<>3)and
(i<#iork<>2)and(j<#jork<>1)};
constraint
A{i,j|j<#j}:X[i,j,1]=X[i,j+1,3];
B{i,j|i<#i}:X[i,j,2]=X[i+1,j,4];
C{i,j|i<#iandj<#janda=-1}:
X[i,j,1]+X[i,j,2]+X[i+1,j+1,3]+X[i+1,j+1,4]<=3;
D{i,j|i<#iandj<#janda<>-1}:
X[i,j,1]+X[i,j,2]+X[i+1,j+1,3]+X[i+1,j+1,4]=a;
E{i,j}:sum{k}X=2orsum{k}X=0;
minimizeobj:sum{i,j,k}X;
end
4
 
ThemodeldefinedsofarsolvesentirelytheproblemshowninFigure 1 .So Solution
letussolveanotherpuzzleusingthesamemathematicalformulationgiven
byFigure 2 .
Figure2:AnotherSlitherlinkPuzzleandits“Solution”
Surprise!Thepuzzleisnotsolvedcorrectly.ThesolutioninFigure 2 isnot
validbecauseitgivesustwoseparatedloops.Nevertheless,wecanverify
thatallconstraintsdefinedsofarofourmodelarefulfilled.Thismeansthat
constraintsthatforceasolutionwithonesinglelooparestillmissing.How
canweaddthem?Onanad-hocbase,letustrytosolvetheproblemof
Figure 2 .Lookingatthesolution,weseethatnosegmentofthesquares
inthethirdrowisinaloop.Thiscannotnobe.Ifweforceasingleloop
thenatleasttwosegmentsinthethirdrowshouldbeintheloop.Why?
Becausethesetofthesesegmentsseparatesthetwoloops.Thisisnotbe
possible.Nosubsetofsegmentsshouldexistinsuchawaythattheyseparate
twoloops!Hence,letusaddaconstraint–inourexample–thatforcesat
leasttwosegmentsinthethirdrowtobeintheloop.Thisconstraintcanbe
formulatedasfollows: X
x 3,j,2 2
j
InaLPLformulationweaddthefollowinglinetotheLPLcode:
constraintF:sum{j}X[3,j,2]>=2;
Weaddthisconstrainttotheinstanceandsolvethemodeldefinedsofar
again.Now,wegetacorrectsolutionasshowninFigure 3 ,sinceitcontains
asingleloop.
5
435831961.002.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin