您的当前位置：首页 Computational methods and new results for chessboard problems, Australas

Computational methods and new results for chessboard problems, Australas

来源：筏尚旅游网

CDMTCSResearchReportSeries

ComputationalMethodsandNewResultsforChessboardProblems

MatthewD.KearsePeterB.Gibbons

DepartmentofComputerScienceUniveristyofAuckland,AucklandNZ

CDMTCS-133May2000

CentreforDiscreteMathematicsandTheoreticalComputerScience

ComputationalMethodsandNewResultsfor

ChessboardProblems

MatthewD.KearsePeterB.Gibbons

DepartmentofComputerScience

UniversityofAucklandPrivateBag92019

AucklandNewZealand

email:p.gibbons@auckland.ac.nz

Keywords:chessboard,queens’graph,kings’graph,dominationnumber,irredundance

number,backtracking,localsearch,reduction.

Abstract

Wedescribevariouscomputingtechniquesfortacklingchessboarddominationprob-lemsandapplythesetothedeterminationofdominationandirredundancenumbersforqueens’andkings’graphs.Inparticularweshowthatγ(Q15)=γ(Q16)=,conﬁrmthatγ(Q17)=γ(Q18)=9,showthatγ(Q19)=10,showthati(Q18)=10,improvetheboundfori(Q19)to10≤i(Q19)≤11,showthatir(Qn)=γ(Qn)for1≤n≤13,showthatIR(Q9)=Γ(Q9)=13andthatIR(Q10)=Γ(Q10)=15,showthatγ(Q4k+1)=2k+1for16≤k≤21,improvetheboundfori(Q22)toi(Q22)≤12,andshowthatIR(K8)=17,IR(K9)=25,IR(K10)=27,andIR(K11)=36.

1Introduction

Combinatorialproblemsonchessboardshavebeenstudiedbycombinatorialistsandpuzzle-solversforover250years.Investigationscentreontheplacementofthevarioustypesofchesspieces,viz.kings,queens,bishops,rooks,knightsandpawns,ongeneralizedn×nchessboards.Forexcellentsurveysofworkandresultsinthisareathereaderisreferredto[10,14].

GivenagraphG=(V,E),asetofverticesDinVisadominatingsetifeveryvertexinV\\DisadjacenttoatleastonevertexinD.ThedominationnumberofG,denotedγ(G),istheminimumcardinalityofadominatingsetinG.AsetofverticesSinVisindependentifnotwoverticesinSareadjacent.ThevertexindependencenumberofG,denotedβ(G),isthemaximumcardinalityofanindependentsetofverticesinG.Theindependentdomination

numberofG,denotedi(G),istheminimumcardinalityofanindependentdominatingsetinG.TheupperdominationnumberofG,denotedΓ(G),isthemaximumcardinalityofaminimaldominatingsetofverticesinG.TheclosedneighbourhoodofasetofverticesS,denotedN(S),isthesetofvertices,includingS,thatareadjacenttoavertexinS.AsetofverticesSinVisirredundantif,foreveryvertexuinS,thesetN(u)\\N(S\\{u})=∅.TheirredundancenumberofG,denotedir(G),istheminimumcardinalityofamaximalirredundantsetofverticesinG.TheupperirredundancenumberofG,denotedIR(G),isthemaximumcardinalityofanirredundantsetinG.

These6domination,independenceandirredundancenumbersarerelatedasfollows(see[5]):

ir(G)≤γ(G)≤i(G)≤β(G)≤Γ(G)≤IR(G).

Associatedwitheachofthe6chesspiecesonecandeﬁneaclassofgraphs.Forexamplethequeens’graphQnhasasetofn2verticescorrespondingtothesquaresofann×nchessboardwithtwoverticesadjacentifandonlyifaqueenplacedononesquarecanattacktheothersquareinonemove.Notethatonachessboardaqueenattacksallsquaresonthesamerow,columnanddiagonal.Inasimilarmanneronecandeﬁnethekings’graphKn,andgraphsfortheotherchesspieces.Duetothecomplexitiesofallowablepawnmoves,thegridgraphGn(inwhichtwosquaresareadjacentiftheyareadjacentonthesameroworcolumn)isnormallystudiedinpreferencetothepawns’graph.

Determinationofthe6numbersdeﬁnedaboveforthe6classesofgraphsgivesriseto36fundamentalproblemsonchessboarddomination.Inworktodatemanyofthenumbershavebeencompletelydeterminedforallvaluesofn.Forexampleall6valueshavebeendeterminedfortherooks’graph.Inothercases,valueshavebeendetermined,generallybycomputersearch,foronlysmallvaluesofn,withboundsestablishedforothervalues.Thedevelopmentofimprovedsearchtechniquesisimportantinenablingustoextendthesetofknowndomination,independenceandirredundancenumbers,therebyprovidingopportuni-tiesforfurtherinsightintothecompletespectrumofthesevalues.

Inthispaperwedescribeprobabilisticandexhaustivesearchtechniquesfortacklingchessboarddominationproblems,andapplythesetothedeterminationofdominationandirredundancenumbersforthequeens’andkings’graphs.InparticularwedescribepreviousworkontheseproblemsinSection2.InSection3wedescribethebacktrackingmethodandvariousreﬁnementsthathaveallowedustoshowthatγ(Q15)=γ(Q16)=9,toconﬁrmthatγ(Q17)=γ(Q18)=9,toshowthatγ(Q19)=10,toshowthati(Q18)=10,andtoimprovetheboundfori(Q19)to10≤i(Q19)≤11.Insection4wedescribetheapplicationofreductiontechniqueschessboardproblems,anduseittoshowthatir(Qn)=γ(Qn)for1≤n≤13,toshowthatIR(K8)=17,IR(K9)=25,IR(K10)=27,andIR(K11)=36,andtoshowthatIR(Q9)=Γ(Q9)=13andthatIR(Q10)=Γ(Q10)=15.Section5appliesalocalsearchmethodtogeneratedominatingsetsofsize2k+1inQ4k+1andtotherebyconﬁrmthatγ(Q4k+1)=2k+1for1≤k≤15,andtoextendtheresulttok≤21.Inadditionweestablishthati(Q22)≤12.SomeconcludingremarksarepresentedinSection6.ThroughoutthepaperquotedrunningtimesareforalgorithmsimplementedinthelanguageConanAlphaServer2100Model4/275runningat275MhzunderDigitalUNIXV4.0D.

2.1

Background

QueensDominationProblems

Theﬁrsteightvaluesofγ(Qn)weregivenbyBall[1]in12.Sincethentherehasbeenmuchworkondeterminingvaluesforγ(Qn)forlargern.Manyboundshavebeendiscoveredforγ(Qn),themostwellknownbeingthelowerboundduetoSpencer(privatecommunication

toCockayne[7])ofγ(Qn)≥n−.Sincethen,Weakley[22]hasobtainedtheimprovedbound2

fornoftheform4k+1ofγ(Q4k+1)≥2k+1forallk.Infactithasbeensuggestedbutnotproventhatγ(Q4k+1)=2k+1forallk,andthishasbeenveriﬁedfork≤15.Therehavealsobeenmanyupperboundsdevelopedforγ(Qn).Burger,CockayneandMynhardt[4]haveshownthatγ(Qn)≤31n+O(1).Obviously,anylowerboundforγ(Qn)isalsoalower

boundfori(Qn).However,upperboundsforγ(Qn)donotholdfori(Qn).Thebestknown

upperboundofi(Qn)≤12n+O(1)wasdiscoveredbyEisenstein,Grinstead,HahneandVanStone[9].RecentlyWeakley[23]hasshownthatifn≡1(mod4)andDisad-element

d+3

dominatingsetofQnofaparticular,commonlyusedkind,thenγ(Qk)≤nk+O(1).Also+2

d+6

ifDisindependent,theni(Qk)≤nk+O(1).+2

Alistofknownvaluesforγ(Qn)andi(Qn)forsmallnaregiveninTable1.

n1234567101112131415γ(Qn)11123345555678≤9i(Qn)1113344555577n16171819202122232425γ(Qn)≤999≤10≤1111≤12≤12≤1313i(Qn)99≤10≤11≤1111≤13≤13≤1313

Table1:Knownvaluesforγ(Qn)andi(Qn).

2.2QueensLowerIrredundance

Verylittleisknownaboutthequeenslowerirredundancenumberir(Qn).Infactnocase

isknownwhereir(Qn)<γ(Qn)althoughFrickeetal[10]suspectthatthevalueofγ(Qn)−ir(Qn)canbearbitrarilylarge.Kearse[15]hasproducedtheonlypublishedboundof√

ir(Qn)≥4−67n.Valuesofir(Qn)forsmalln(see[14])are:ir(Q1)=ir(Q2)=ir(Q3)=1,ir(Q4)=2.

2.3QueensUpperIrredundanceandDomination

ThequeensupperdominationnumberΓ(Qn)andupperirredundancenumberIR(Qn)havehadrelativelylittlestudyuntilrecently.Weakley[22]wasoneoftheﬁrsttoinvestigateΓ(Qn)andtodiscoverthatΓ(Qn)>β(Qn)waspossible.HealsoprovedthatΓ(Qn)≥2n−5.ThisboundwaslaterimprovedbyBurger,CockayneandMynhardt[4]toΓ(Qn)≥5n−O(1).2

Kearse([15])hasfurtherimprovedthisboundtoIR(Qn)≥6n−O(n3).

√

ThebestupperboundofIR(Qn)≤󰀎6n+6−8n+n+1󰀏forn≥6isduetoBurger,CockayneandMynhardt[4],andis√aslightimprovementontheboundoriginallygivenbyCockayneofIR(Qn)≤󰀎6n+6−8n+3󰀏forn≥6.ThereisnoknownupperboundforΓ(Qn)otherthanthatofIR(Qn).AlistofknownvaluesforΓ(Qn)andIR(Qn)isgiveninTable2.

n123456710Γ(Qn)112457911IR(Qn)112457911

Table2:Theknownupperirredundanceanddominationnumbersforthequeens’graph.

󰀁

2.4TheKings’Graph

Inthekings’graphtwosquaresareadjacentiftheylieonthesameoradjacentcolumnsaswellasthesameoradjacentrows.Unlikethequeens’graph,manyproblemsinvolvingthekings’graphhavebeensolved,inthatoptimalsolutionstoarbitrarysizedboardscanbeconstructed.Inparticular,in19AkivaandIsaakYaglom[24]provedamongother

resultsthatγ(Kn)=i(Kn)=󰀎n−󰀏,andthatβ(Kn)=󰀎n+1󰀏2.However,littleisknown32

aboutsolutionstotheotherthreeproblems.Itisknownthanthatir(Kn)<γ(Kn)ispossible,andthatβ(Kn)<Γ(Kn)ispossible.Anotherresultofinterestisthatforn>1,(n−1)2n2

≤IR(K)≤(duetoFricke(unpublished)).n33

Alistofknownvaluesofirredundance,dominationandpackingnumbersforthekings’graphisgiveninTable3.

ir(Kn)γ(Kn)i(Kn)β(Kn)Γ(Kn)IR(Kn)

1111111

23456711344911444999114449991449916162514499161449916

10161625

Table3:Theknownirredundance,dominationandpackingnumbersforthekings’graph.

2.5Terminology

Inreferringtothepositionsonachessboardweoftenidentifythesquaresusingxandycoordinateswhichstartfrom0andincreaseacrossanddownthepagerespectively.Insomecasesitisdesirabletoorderthesquaresandtoidentifythemwithasingleinteger.Inthiscase,webeginwiththetopleftsquareandproceedtoorderthesquarescolumn-wise.RefertoFigure1foranexampleofthesenumberingsona4×4board.

(0,0)(1,0)(2,0)(3,0)15913(0,1)(1,1)(2,1)(3,1)261014(0,2)(1,2)(2,2)(3,2)371115(0,3)(1,3)(2,3)(3,3)481216

Figure1:Thechessboardsquarenumberingconventionusedinthispaper.

Therearetwomainwaysofidentifyingdiagonalsintheliterature.Diagonalsthatmove

downandtotherightarecalleddownorpositivediagonals,andsimilarlydiagonalsmovingupandtotherightareupornegativediagonals.

3.1

Backtrackingandreﬁnements

TheBasicBacktrackingAlgorithm

Backtrackingisawellknownexhaustivesearchmethodthatinvolvessystematicallygen-eratingpartialsolutions,andtryingtoextendeachtoafullsolution.Ifanextensionisnotpossiblethenthealgorithmbacktrackstoconsiderthenextpartialsolutioninorder.Thetechniquedatesbackforatleast100years(see[16]forexample)andhassincebeensuccessfulinitsapplicationtoavastarrayofproblems(see[2]).

In[12]GibbonsandWebbdescribedtheapplicationofbacktrackingtotheindependentqueensdominationproblem,andwereabletodeterminethevaluesofi(Q14),i(Q15)andi(Q16).Thisalgorithmbacktracksontheplacementofqueensonthechessboardandusesthedihedralgroupofchessboardsymmetriestorejectpartialsolutionsthathavealreadybeenconsideredearlierinthesearch.Thisalgorithmcanbeadaptedtosolvethequeensdominationproblem.

3.2BacktrackingBasedonUnattackedSquares

Ratherthanbacktrackingonqueenplacements,animprovementistosystematicallyidentifyundominatedsquaresandtotryplacingpiecesinallpositionsthatattackthesesquares.ForexampleinFigure2twoqueenshavealreadybeenplaced,andtheplacementofathirdisbeingconsidered.AnundominatedsquarehasbeenlocatedatXandsquaresadjacenttoXhavebeenmarkedwithano.ThethirdqueenwillnowbetriedsystematicallyinallosquaresaswellastheXsquare.

Ateachstageduringtheexecutionofthealgorithm,wemustdecideonwhichofthemanyundominatedsquarestofocusthesearch.Thenaivemethodoftakingtheﬁrstsuchsquareinorderperformsquitewell.However,thebreadthofthesearchtreeismoreconstrainedif

QoooQoo

ooooooo

ooo

Figure2:TheundominatedsquareXhasbeenselected,andthethirdqueenwillbetriedineachofthelocationsmarkedo,whichareadjacenttoX.

wetakethatsquarewiththeleastnumberofoptionsavailabletoplacetheattackingpiece.Thereisatradeoﬀinvolvingthecostofﬁndingthissquare.Inpracticeitisbesttothesearchforthebestsquareearlyoninthesearch,buttosimplytaketheﬁrstuncoveredsquareinthelatterpartofthesearch.Theperformanceofthismethodisbetterthanthatoftheﬁrstmethod,butnottotheextentthatanynewresultswereabletobefound.However,itformsthebasisforanimprovedmethodwhichisdescribednow.

3.3BacktrackingBasedonIntersectingSetsofSquares

Insteadofbacktrackingbasedonthepositionsofthequeens,thismethodbacktracksbasedonthesetofqueensattackingagivenposition.Considerﬁrstthecaseofplacingtheﬁrstqueen.WeselecttheﬁrstuncoveredsquarexandassigntothisqueenthelistN(x)ofsquaresthatattackthisposition.Wenowselectthenextuncoveredsquareyandinvestigateseparatelywhetherthisistobecoveredbytheﬁrstqueenorasecond(asyetunused)queen.Weﬁrstinvestigatethecasewheretheﬁrstqueenistocovery.InthiscaseitsassociatedlistofsquaresmustbereducedtoN(x)∩N(y).InthecasethatN(x)∩N(y)=∅wecannotcovertheﬁrstandsecondsquaressimultaneouslyusingtheﬁrstqueen,andthereforemustusethesecond.Otherwisetheﬁrstqueencancoverbothsquares,andtheprocedureisrecursivelycalledtoinvestigatecoverageofthenextuncoveredsquare.Inthecasethat|N(x)∩N(y)|=1,theﬁrstqueenisﬁxedandallsquaresinitsneighbourhoodarerecordedasbeingcovered.Notethatsquaresarenotconsideredcovereduntiltheyareattackedbyaﬁxedqueen.

Moregenerally,ateachlevelofthebacktrackingsearch,thefollowingstepsmustbetaken.First,thenextuncoveredsquaremustbefound.Theneachunﬁxedqueenisconsideredinturnwithitsassociatedlistofpositionsreducedsothatitcoversthisnewsquareaswellaspreviouslyassignedones.Ifitslistbecomesempty,thenweceaseconsiderationofthisqueenandmoveontothenext.Otherwisewerecursivelycalltheproceduretoinvestigatecoverageofthenextuncoveredsquare.Againwerecordsquaresattackedbythisqueenifitbecomesﬁxed.Afterallpieceshavebeenconsidered,wethentrydominatingthelatest

squarewithanasyetunusedqueen.

Thisisalldemonstratedinmoredetailinthefollowingalgorithmdescription.IntersectingSquaresAlgorithmDataStructuresattackCounti:positionsi:k:N(X):

thethethethe

numberofqueensattackingsquareisetofpositionsassignedtoqueeni

numberofqueensavailabletocovertheboardneighbourhoodofsquareX

ofpieces)

procedureDominationBacktrack(p,attackCount1..numberofsquares,positions1..number

whileattackCountp>0do

{Findthenextundominatedsquare}p=p+1

ifp>numberofsquaresthen

{Anycombinationoftheelementsof}{positions1..numberofpiecesisasolution}return

fori=1tokdo

if|positionsi|>1then

{Foreachpiecealreadydominatingatleastonesquare}newPositions=positionsi∩N(p)if|newPositions|>0then

if|newPositions|=1then

foreachx∈N(newPositions)do

attackCountx=attackCountx+1

DominationBacktrack(p+1,attackCount,

(positions1..i−1,newpositions,positionsi+1..numberofpieces))if|newPositions|=1then

foreachx∈N(newPositions)do

attackCountx=attackCountx−1

i=1

while|positionsi|>0do{Findtheﬁrstunusedpiece}

i=i+1

ifi≤numberofpieces

newPositions=N(p)

if|newPositions|=1then

foreachx∈N(newPositions)do

attackCountx=attackCountx+1

DominationBacktrack(p+1,attackCount,

positions1..i−1,newpositions,positionsi+1..numberofpieces)if|newPositions|=1then

foreachx∈N(newPositions)do

endProcedure

attackCountx=attackCountx−1

DominationBacktrack(1,(0,0,...,0),({},{},...,{}))

Applyingthisalgorithmyieldedsomealreadyknownsolutions,butwithsigniﬁcantlylongertimesthanthoseofeitherofthetwopreviousalgorithmswhensolvingthequeensdominationproblem.However,applyingthemethodonlyfortheplacementofthelastpiecealwaysgaveasigniﬁcantimproventintheexecutiontime.Wenowdiscussanumberofenhancementsthatcanbeappliedtoanyofthethreealgorithmsandﬁnallyacombinedmethodthatproducessigniﬁcantspeedimprovements.

3.4Enhancements

Twosimplemethodsweredevelopedforquicklydecidingwhethertoextendfromthecurrentpartialsolution.Theﬁrstcheckisforaqueenthatcoversnosquaresnotcoveredbyanotherqueen.Ifsuchaqueenexists,andwearesearchingforonlyasolutionwithaminimalnumberofqueens,thenthispartialsolutionwillobviouslynotleadtoit,andthealgorithmcanbacktrack.

Forexample,inFigure3thefourthplacedqueen,Q4,hascreatedaconﬁgurationwheretheﬁrstqueen(Q1)nolongerattacksauniquesquareandisthereforeredundant.Thealgorithmcanimmediatelyconsiderthenextplacementofthefourthqueen.

Q1Q3Q2

Figure3:TheplacementofQ4causesQ1tonolongerbenecessary.

Thenextcheckiswhetherthereareenoughremainingqueenstocovertheremaininguncoveredsquares.Forann×nchessboardaqueencanattackatmost4n−3diﬀerentsquaresincludingtheoneitisplacedon.Asecondqueencanattackfewernewsquaresthanthisasmanyofthesquaresattackedbyitarealreadyattackedbytheﬁrstqueen.Byusingthebacktrackingmethodsalreadypresented,wecanbuildatablewiththemaximumnumberofnewsquaresthatcanbeattackedforanygivennumberofqueensforaﬁxedsizeboard.Ifthenumberofremainingsquarestobecoveredisgreaterthanthemaximumthancanbecoveredbytheremainingnumberofqueens,thenwecanbacktrack.

Notethatactuallybuildingupalistofthemaximumnumberofsquaresthatcanbedominatedforanynumberofpiecesuptothedominationnumberwouldrequireasmuch

workassolvingtheproblemitself.Thereforeinpracticethenumberofsquaresdominatedbyuptohalfthisnumberisinitiallycomputed,withthisinformationbeingusedforplacingthesecondhalfofthepieces.

3.5CombiningtheMethods

Thebestmethodwasobtainedbyapplyingtheenhancementsoftheprevioussectiontoacombinationofthethreebacktrackingmethods.Inparticular,optimalperformancewasachievedbyplacingtheﬁrstqueenusingtheﬁrstalgorithm,placingallbutthelast2or3queensusingthesecondalgorithm,andplacingtheremaining2or3queensusingtheﬁnalmethod.Theoptimalnumberofqueenstoplaceusingthelastmethodincreaseswiththeoverallnumberofqueensbeingplaced.

3.6IsomorphRejection

Isomorphrejectioncannotbeeasilyappliedtotheunattackedsquaresmethod,sooncethealgorithmswitchestothismethod,isomorphrejectionisnolongerapplied.However,acountofthenumberofnon-isomorphicsolutionscanstillbefoundbyrejectingcompletesolutionsfoundthatarenottheﬁrstintheirisomorphismclass.

3.7ResultsObtained

TheresultsofthecombinedmethodsarelistedinTable4(withpreviouslyunknownresultsinbold).Inparticularweshowedthatγ(Q15)=γ(Q16)=9byﬁndingnodominatingsetswith8queens.Additionally,weconﬁrmedthealreadyknownresultsofγ(Q17)=γ(Q18)=9.Thealgorithmcanbeeasilymodiﬁedtohandlethecaseoftheindependentqueensdominationproblembyaddingtherestrictionthataqueencannotbeplacedinalocationthatattacksanotherqueen.Thisrestrictiongreatlyspeedsupthealgorithm,andenabledustoshowthati(Q18)=10.Alsobyﬁndingnoindependentdominatingsetof9queensona19by19boardweimprovedpreviouslyknownboundof9≤i(Q19)≤11to10≤i(Q19)≤11.Thislastresultleadstoonefurtherresultforthequeensdominationproblem.Weakley[22]hasprovedatheoremwhichincludestheresultthatifRisadominatingsetof(n−1)/2

squaresofQn,thenRisindependent.Itfollowsfromthisthatifi(Qn)>n−thenγ(Qn)>2n−1

.Theresultthati(Q19)>9impliesthatγ(Q19)>9.Sinceitisalreadyknownthat2

γ(Q19)≤10itfollowsthatγ(Q19)=10.

4Reductions

Inthissectionwepresentareductionmethodwhichissuitableforsolvingavarietyofconstraintsatisfactionproblems.Themethodisparticularlywellsuitedtothekingsup-perirredundanceproblem.Itisalsoappliedtothequeensupperandlowerirredundanceproblemstoproducesomenewresults.

Supposewehaveapartialconﬁgurationandareconsideringallpossibleextensionstoseewhetheranyofthemformacompletesolution.Inadditionsupposethatforanysuch

Boardsize3456710111213141515161718

QueensDomination

NumberofQueensNumberofNon-IsomorphicSolutions1123337314135638521515161741858880925872808080IndependentQueensDominationNumberofQueensNumberofNon-IsomorphicSolutions113232417415915151517105748559131491692901020

Time-----1.1secs

0.4secs0.7secs1.2secs34secs18mins11hours21hours230hours31hours30hours43hours

Boardsize345671011121314151617181819

Time--------0.2secs34secs45secs9.4mins110mins5hours11hours28hours120hours62hours

Table4:Runningtimesfortheenhancedbacktrackingalgorithmsolvingthequeensandindependentqueensdominationproblems.

extensionthatformsacompletesolution,oneofthepiecesinthepartialsolutioncanbemovedtoanotherlocationandthesolutionpreserved.Thenthereisnopointincontinuingthesearchfromthispartialconﬁgurationiftheotherpartialconﬁgurationfoundbymovingthepiecehasalreadybeenorwillbesearched.

Speciﬁcally,assumeapartialsolution(x1,x2,...,.xk)toaproblemwithsolutionspace(X1,X2,...,Xn)withk10

4.1Examples

Wedemonstratethetechniquewithasimpleexampleforthekingsupperirredundanceproblem.Thisprobleminvolvesproducingaconﬁgurationofasmanykingsaspossiblesuchthateverykinghasatleastoneprivateneighbour.Aprivateneighbourisasquareattackedbyauniqueking,andcanincludethesquarethekingisonitself.

Figure4:Thekingatposition(1,1)couldmovetoposition(0,0).

ConsidertheexampleinFigure4.Hereakingisbeingconsideredforplacementnear

thetop-leftcorner.ThreeothersquaresaremarkedwithanXbecauseifakingwereplacedinanyofthesethreesquaresthenitwouldhavenoprivateneighbour.Becauseoftheserestrictions,nomatterhowthesolutionisextended,thekingalreadyplacedisguaranteedtohaveaprivateneighbourinthetop-leftcorner.Nowobservethatiftherewereasolutioninvolvingakinginthisposition,thenitcouldbemovedtothetop-leftsquareandthiswouldstillbeasolution.Thatis,thepartialsolutionwithakinginposition(1,1)reducestothepartialsolutionwithakinginposition(0,0).Infactitismorelikelythatasolutionwouldbefoundifthekingwereposition(0,0)sinceitwouldattackfeweradditionalsquaresfromthatposition,therebyleavingthosesquarestobeprivateneighboursofotherkings.Aconsequenceofthisisthatthereisreallynoneedtoeversearchforamaximalirredundantconﬁgurationofkingswithoneintheoriginalposition,sobeforebeginningsuchasearch,thissquarecanbeimmediatelyruledoutfromcontainingaking.

Wecanexpressthissequenceoflogicalconclusionsinthefollowingway.Theboardisinitially:

Ifakingwereatposition(1,1)

thenthefollowingpositionswouldbeprohibited:(0,0),(0,1),(1,0)andtheboardbecomes:

XXX

andthekingat(1,1)couldbemovedto(0,0).

Soakingshouldnotbeatposition(1,1)andtheboardbecomes:

Thisdemonstratesthatstartingfromaboardaboutwhichnodecisionshavesofarbeenmadewecanconcludethatthereshouldbenopieceinposition(1,1).Notethatwheneverasquareislistedasbeingprohibited,itisdoneeitherbecauseakingplacedinitwouldhavenoprivateneighbours,orbecauseakinginthatsquarewouldcausesomealreadyplacedkingtohavenoprivateneighbours.

Considerthelogicofanotherexample.Theboardisinitially:

Thefollowingpositionswouldbeprohibited:(0,0),(1,1)

andtheboardbecomes:

Ifposition(1,0)wereprohibited

thentheboardbecomes:

andthekingat(0,1)couldbemovedto(0,0).

Soposition(1,0)shouldcontainakingandtheboardbecomes:

Thefollowingpositionsareprohibitedbecauseeitherofthealreadyplacedkingswouldhavenoprivateneighbour:

(2,0),(2,1),(3,0),(3,1),(0,2),(0,3),(1,2),(1,3)andtheboardbecomes:

XXX

XXXX

Ifakingwereatposition(4,1)

thenthefollowingpositionwouldbeprohibited(4,0)

Andtheboardbecomes:

XXX

XXXX

andthekingat(4,1)couldbemovedto(4,0)

Sotherecanbenokingatposition(4,1).

Bysymmetrytherecanbenokingatposition(1,4)andtheboardbecomes:

XXXX

Thusbyplacingakingatposition(0,1),wecanconcludethattheremustalsobeakingat(1,0)andthat12othersquarescannotcontainkings.

Inasimilarway,itcanbeshownthatastartingconﬁgurationof

mustbeextendedto

XXX

Asaﬁnalexamplewecanshow,usingsimilarlogic,thatthereisnopointinextendingthefollowingpartialsolution:

XXX

¿Fromtheabovefourexampleswecanconcludethatinasearchforamaximalirredun-dantconﬁgurationofkings,weonlyneedtoconsiderthefollowingthreepossibilitiesinthetopleftcorner:

•Thereisakinginposition(0,0)

•Thereisapairofkingsatpositions(0,1)and(1,0)•Thereisapairofkingsatpositions(0,2)and(2,0)

Ofcourseasimilarsituationarisesinallfourcornersoftheboardifitislargeenough,andsuchinformationwouldgreatlyspeedupanybacktrackingsearchforasolutiontotheproblem.

4.2TheReductionAlgorithm

Thelogicdescribedbywayofexamplesintheprevioussectioncanbeappliedsystematicallyduringthesearch.Theproceduresapplyingthechecksusethefollowingdatastructures:•ThenumberofprivateneighboursofeachpiecedenotedbyprivateNs1..number

ofpieces.

•ThecurrentusageofeachsquareisrecordedinthearraysquareUsage1..numberofsquares.

Eachsquarecanbeunused(UNUSED),occupied(USED)orprohibited(PROHIBITED).Atcertainpointsduringthealgorithm,thevariableoldSquareUsageisused.Thisisalocalvariabletoeachprocedure,andisusedtobackupthecurrentusagesforthesquaressothatitcanberestoredatalaterpoint.

•ThecurrentstatusofeachsquareisrecordedinthearraysquareStatus1..numberofsquares.Inadditiontoknowingthenumberofpiecesattackingeachsquare,itisusefultoknowifthiscanpossiblychangedeeperwithinthesearch.Forexampleasquarecouldbeunattacked(UNATTACKED)orifalladjacentsquaresareprohibitedthenitisguaranteedtobeunattacked(GUNATTACKED).Similarlyasquarecanbeapri-vateneighbourofsomepiece(PNEIGHBOUR)oraguaranteedprivateneighbour(GPNEIGHBOUR).Ifthesquareisnotanyofthesestates,thenitisattackedbyatleast2pieces(ATTACKED).

PiecesareplacedusingtheprocedurePutPiece(pieceNum,p,ok)whichplacespiecepieceNumatpositionponlyifitandallexistingpiecesstillhaveatleastoneprivateneigh-bour.Theﬂagokissettotrueifthepiecewasplaced.ProcedureRemovePiece(pieceNum)removesthepieceandrestoresthedatastructures.

Wenowconsidertheconditionsthatmustholdforapiecetoallowedtomovefromonesquaretoanother.Firstly,itmusteitherstillattackaguaranteedprivateneighbourfromthenewposition,oralternativelystillattackalltheoriginalprivateneighbours.Secondly,itcannotattackanyadditionalsquaresthatcouldbeprivateneighboursofsomeotherpieceeithernowordeeperinthesearch,unlesstheotherpieceisguaranteedtohaveaprivateneighbourelsewhere.TheseadditionalsquarescanbeidentiﬁedasthoseforwhichthestatusisUNATTACKED,PNEIGHBOURorGPNEIGHBOUR,andarereferredtoasdisallowedsquares.Weneedtobesurethat,ifwehaveruledoutanextensionbasedonmovingapiecetoanotherlocation,thenalatersolutionwiththepieceatthisnewlocationwillnotberejectedbecauseitcouldmovebacktotheoldposition.Thisisensuredby

checkingthatthenumberofdisallowedsquareswhichareattackedissmallerinthepositionmovedto.Ifthisistrueatsomepointwithinthesearch,thendeeperwithinthesearchitwillnotbepossibletomoveapiecebackbecausenosquareseverchangestatefrombeingallowedtodisallowedfurtherdownthebacktrackingtree.

TheprocedureDisallowedSquares(p)returnsalistofsquaresadjacenttopthatmaynotbeattacked.TheprocedureComputeSquareStatus()computesthestatusofeachsquarexandstorestheresultinsquareStatusx

Thealgorithmthatanalysesthecurrentstateoftheboardtodetermineifamoveforanypieceispossibleisgivenbelow.Notethatitalsochecksforcaseswhereanewpiececouldbeaddedtotheboardatnocosttothecurrentpartialconﬁguration.Suchcasesarisewhenthereexistsaprohibitedsquareforwhichalladjacentsquaresareeitherattackedbyatleasttwopiecesorareguaranteedtobeunattackedsothatitwillnotinterferewithanyexistingorfuturepieces.Alsoatleastoneofthesesquaresshouldbeguaranteedtobeunattackedsothatthenewpiecehasatleastoneprivateneighbouritself.

ProcedureMove()

{Returnstrueifanypiececouldmoveorbecreated}{atnocosttothecurrentpartialconﬁguration.}

ComputeSquareStatus()

forallsquaresxdo{Checkifanewpiececouldbecreatedatx}

ifsquareUsagex=PROHIBITEDand|DisallowedSquares(x)|=0then

forally∈N(x)do

ifsquareStatusy=GUNATTACKEDthen

returntrue{Anewpiececouldbecreatedatx}

forallpsuchthatpositionp=NULLdo{Checkifpiecepcanbemoved}

pos=positionp

PN={x:x∈N(pos),|attackListx|=1

{PN=thesetofprivateneighboursofpiecep}

GPN={x:x∈N(pos),squareStatusx=GPNEIGHBOUR}

{GPN=thesetofguaranteedprivateneighboursofpiecep}RemovePiece(p){Temporarilyremovethepiece}ComputeSquareStatus()

oldList=DisallowedSquares(pos)

forallx∈N(N(pos)){Forallpossiblemovesforpiecep}

{N(N(pos))isusedbecauseitcontainsthesetofpossiblesquares}{stillattackingneighboursofp.}newList=DisallowedSquares(x)ifnewList⊂oldListthen

{Nonewsquaresthatarenotallowedareattackedandatleast}{oneoftheseisnolongerattacked}

if(PN\\N(x))=∅or|GPN∩N(x)|>0then

{Eitherallprivateneighboursoratleastoneguaranteed}{privateneighbourisstillattacked}

PutPiece(p,pos,ok){Putthepiecebackinitsoriginalplace}returntrue{Piecepcouldmovefrompostox}

PutPiece(p,pos,ok){Putthepiecebackinitsoriginalplace}returnfalseendProcedure

Inordertobeabletomakethelogicaldeductionspresentedearlier,aformofforwardcheckingisrequired.Asimplecaseinvolvescheckingtoseeifpiecekcanbeplacedineachpossibleposition,andifnotprohibitingthatsquare.ThistaskiscarriedoutbytheprocedureBasicForwardCheck(k).ThefollowingfunctionForwardCheck(k,startSquare)returnstrueifthereisnopointinextendingthecurrentpartialsolution.Otherwiseitreturnsfalseandprohibitsanysquarethatwouldresultinamovebeingpossibleifitcontainedapiece.Additionally,ifitdetectsthatapiecemustbeplacedinacertainsquarethenitcallstherecursivebacktrackproceduretosearchtheremainingsolutionspaceandthenreturnstrue.ProcedureForwardCheck(k,startSquare)

BasicForwardCheck(k)ifMove()then

returntrueok=true

whileokdo{Aslongassomethinghaschanged,keeprepeating}

ok=false

forallsquaresxdo

ifsquareUsagex=UNUSEDthen

oldSquareUsage=squareUsagecanMove=false

ifPutPiece(k,x)then{Checkifapiececouldbeatx}

BasicForwardCheck(k+1)ifMove()then

canMove=trueRemovePiece(k)

squareUsage=oldSquareUsageifcanMove=truethen

squareUsagex=PROHIBITED{Theremustnotbeapieceatx}ok=trueelse

squareUsagex=PROHIBITED

{Checkifthissquarecouldbeprohibited}

ifMove()then{Theremustbeapieceinsquarex}

PutPiece(k,x)

Backtrack(k+1,startSquare)RemovePiece(k)

returntrue{Thiscasehasbeenfullysearchednow}squareUsagex=UNUSED

returnfalseendProcedure

Finallythefundamentalbacktrackingalgorithmis:ProcedureBacktrack(k,startSquare)

ifk>numberofpiecesthen

position1..numberofpiecesisasolutionreturn

oldSquareUsage=squareUsage

abort=ForwardCheck(k,startSquare)i=startSquare

whilei≤numberofsquaresandabort=falsedo

ifPutPiece(k,i)then

Backtrack(k+1,i+1)RemovePiece(k)

squareUsagei=PROHIBITED

abort=ForwardCheck(k,startSquare)i=i+1

squareUsage=oldSquareUsageendProcedure

squareUsage1..numberofsquares=UNUSEDattackList1..numberofsquares=∅position1..numberofpieces=NULLBacktrack(0,0)

4.3IsomorphRejection

Aswiththealgorithmforthequeensdomination,isomorphrejectioniseasilyincorporatedintothisalgorithm.Itisnotincludedinthegivenalgorithmdescriptionstokeepthemassimpleaspossible,butthesamemethodusedbeforeisemployed.Thatis,atanystagewhereasquarexisprohibited,ifthecurrentboardconﬁgurationmapstoitselfundersometransformationT,thenthesquarethatxmapstounderTisalsoprohibited.

4.4Results

Thedescribedalgorithmobtainedthefollowingnewresultsforthekingsupperirredundanceproblem:IR(K8)=17,IR(K9)=25,IR(K10)=27,andIR(K11)=36.Maximalirredundantconﬁgurationsofthegivensizeswerealreadyknowntoexist,butthisprogramdeterminedthatnolargercasesexist.SomeperformanceﬁguresforthealgorithmaregiveninTable5.

4.5QueensLowerIrredundance

Thisprobleminvolvesﬁndingaminimalplacementofqueensonachessboardsothateveryqueenisirredundant,andsothatnomoreirredundantqueenscanbeaddedtotheboardwhilemaintainingthepropertythatallqueensareirredundant.Currentlythereisnoknown

Boardsize6677101011NumberofKings910161717182526272837SolutionFoundYesNoYesNoYesNoYesNoYesNoNoTime0.2secs0.3secs1.6secs2.1secs60secs59secs25mins9mins8.4hours9.2hours140hours

Table5:Runningtimesforbacktrackingalgorithmsolvingthekingsupperirredundanceproblem.

caseforwhichir(Qn)<γ(Qn),andtodateonlytheﬁrstfourvaluesforir(Qn)havebeenpublished.Toﬁndiftheredoesexistaconﬁgurationinwhichir(Qn)<γ(Qn)wemustsearchann×nboardformaximalirredundantsetsofsizesbetween1andγ(Qn)−1.

Thealgorithmwasrunwithanumberofqueensrangingfrom1upto1lessthanthedominationnumberforboardsuptosize13×13.Inallcasesnosolutionwasfound,therebyindicatingthatir(Qn)=γ(Qn)for1≤n≤13.TherunningtimesaregiveninTable6.

Boardsize56710111213

NumberofQueens223444456

SolutionFoundNoNoNoNoNoNoNoNoNo

Time---1sec3secs9secs21secs22mins26hours

Table6:Runningtimesforbacktrackingalgorithmsolvingthequeenslowerirredundanceproblem.

4.6QueensUpperIrredundance

Thereductiontechniquesdevelopedforthekings’graphwerealsoappliedtothequeens’graph.Howeverthealgorithmisfarlesssuitedtothequeensgraphwiththeresultsbeingnotnearlyasgood.Infactthereductionpartofthebacktrackingalgorithmwasfoundtoslowdownthealgorithm,withthebestresultsbeingfoundwiththereductionpartremoved.ThealgorithmdoesrunfastenoughtoﬁndthepreviouslyunknownvaluesofIR(Q9)=13andIR(Q10)=15.TheseareinfactequaltoWeakley’slowerboundofΓ(Qn)≥2n−5.SinceIR(Qn)≥Γ(Qn)thisadditionallyimpliesthatΓ(Q9)=13andΓ(Q10)=15.TherunningtimesfortheseandanumberofothercasesaregiveninTable7.

Boardsize66771010NumberofQueens710111213141516SolutionFoundYesNoYesNoYesNoYesNoYesNoTime0.4secs0.2secs7.3secs2.9secs1sec84secs2hours1hour40hours46hours

Table7:Runningtimesforbacktrackingalgorithmsolvingthequeensupperirredundanceproblem.

5ProbabilisticMethods

Probabilisticmethodshavetheadvantageofbeingabletogeneratechessboardconﬁgurationsofmuchgreatersizesthancanbegeneratedbyexhaustivesearch.Ontheotherhandtheycannotestablishnonexistenceofaconﬁgurationwiththerequiredproperties,ortoenumerateallsuchconﬁgurations.Inthissectionwedescribetheuseofasimplelocalsearchtechniquewhichwasusedtoestablishthenewresultthati(Q22)≤12byﬁndinganindependentdominatingconﬁgurationof12queensona22by22board.Previouslyithasbeenproventhatγ(Q4k+1)=2k+1forallk≤15byexhibitingdominatingsetsofthissize.Thisisextendedheretoprovethattheresultholdsfork≤21.

5.1Localsearch

LocalsearchtechniquesoperatewithinasetΣoffeasiblesolutions.Associatedwitheachi∈Σisacostc(i),andthetaskistoﬁndanoptimalsolutionwithoverallminimumcost.Intheproblemsofthissectionanoptimalsolutionhascost0.Foreachi∈ΣwedeﬁneasetTioftransformationseachofwhichcanbeusedtochangeiintoacloselyrelatedfeasiblesolutionj.ThesetofsolutionsthatcanbereachedfromibyapplyingatransformationfromTiiscalledtheneighbourhoodD(i)ofi.

Thesimplestlocalsearchissimplyarandomwalk,startingwithanarbitarystartingfeasiblesolutionandsuccessivelymovingtoaneighbouringfeasiblesolution.Thechosenneigbouringsolutionisselectedfromasmallsetofneighbours,andistheonewiththelowestcost.Thewalkﬁnishessuccessfullywhenanoptimalsolutionisfound,orunsuccessfullywhenanupperlimitoftransformationsisreached.Thealgorithmisasfollows:ProcedureRandomSearch(x,searchSize,stopThreshold){xarandomstartingconﬁguration.}

{searchSizeisthenumberofneighboursgeneratedfromthecurrentsolution.}

repeatstopThresholdtimes

bestCost=∞

repeatsearchSizetimes

y=transform(x){GeneratearandomelementinD(x)}ifCost(y)=0then

returny{yisasolution}ifCost(y)bestCost=Cost(y)bestSolution=y

x=bestSolution

endProcedure

ThisalgorithmwasadaptedtothequeensdominationproblemusingthefollowingTrans-formprocedure:

ProcedureTransform(x)

{Returnsarandomtransformationfromxtoanewconﬁguration.}

{xisasetoforderedpairs(i,j)whichindicatesthatqueeniisplacedinsquarej}

Selectarandompair(i,j)∈xy=x\\{(i,j)}

SelectarandomundominatedsquareafromySelectarandomsquareb∈D(a)returny∪{(i,b)}endProcedure

Despiteitssimplicity,thismethod,usingsearchSize=20,quicklyfoundsolutionsofsizeγ(Qn)foralln≤18.Wenotedthatthemajorityofsolutionsfoundinthiswayhadqueensonlyoneven-evensquares(i.e.squares(i,j)wherei,j≡0(mod2)).Modifyingthepreviousalgorithmtosearchonlyforsolutionswithqueensoneven-evensquareswewereabletoﬁndoptimalsolutionsforboardsfromsizes12to25,includingJohannesWaldmann’sdominatingconﬁguration([20])of12queensona23×23board(seeFigure5).TheaveragerunningtimesofthisalgorithmoveranumberoftrialsaregiveninTable8.

Boardsize1213141516171819202122232425

QueensDomination

NumberofQueensSearchSize6107108119119129139141017111911201220122013201320

AverageTime

0.01secs0.07secs0.05secs0.03secs0.16secs1.1secs9.4secs12secs2.7secs35secs22secs28mins99secs27mins

Table8:Runningtimesfortheprobabilisticalgorithmsolvingthequeensdominationprob-lem.

Asimilartransformationwasusedforthequeensindependentdominationproblem,butsincemostsolutionstothisproblemdonothavequeensononlyeven-evensquares,thisrestrictionwasdropped.Thisalgorithmgeneratedthenewresultofanindependentdom-inatingconﬁgurationof12queensona22×22board(seeFigure5).Thealgorithmwastestedonboardsupto22by22,andtheresultsofthisaregiveninTable9.

Figure5:Adominatingconﬁgurationof12queensona23by23boardandanindependentdominatingconﬁgurationof12queensona22by22board.

Boardsize1213141516171819202122

QueensIndependentDominationNumberofQueensSearchSize71171281491792292210221122112211221222

AverageTime

0.3secs11secs5secs2secs17secs56mins27mins101secs16mins7hours4hours

Table9:Runningtimesfortheprobabilisticalgorithmsolvingtheindependentqueensdom-inationproblem.

5.2

DominationinQ4k+1

Weakley[22]hasshownthatγ(Q4k+1)≥2k+1forallintegersk,andhasconjecturedthatγ(Q4k+1)=2k+1forallintegersk.Thisconjecturehasbeenconﬁrmedforallk≤15bygeneratingdominatingsetsofsize2k+1(seeWeakley[22]fork≤6andk=8,Burger,CockayneandMynhardt[3]fork=9,12,13,15,GibbonsandWebb[12]k=7,10,11,14.Inthissectionweadapttheabovelocalsearchalgorithmtoﬁndindependentdominatingsetsofsize2k+1fork≤21.

Themethodusedin[12]togeneratedominatingsetsofsize2k+1wasthatofsimulatedannealing.Inthispaperitwasnotedthatmanydominatingsetscontainqueensonlyoneven-evensquares.Forexampleseethedominatingsetfork=3inFigure6.Inordertocheckwhethersuchaconﬁgurationisdominating,itisnecessarytoonlycheckthattheodd-oddsquaresareattackedsinceallothersareattackedbyaqueenineitherthesameroworcolumn.Thisleadstoacompressedrepresentationoftheboardwhereevenrowsandcolumnsarerepresentedaslinesandodd-oddsquaresformthesquaresinthecompressedrepresentation.Queensarenowplacedontheintersectionsofthelines,withonequeenperline.Figure7showsthecompressedboardofFigure6.Inthisrepresentationallsquaresmustbedominateddiagonallybysomequeen.

001234567101112

101112

Figure6:A13x13board(k=3)dominatedby7queens.Odd-oddsquaresareshaded.Aninitialconﬁgurationforthesimulatedannealingalgorithmwasgeneratedbyrandomly

00123456

3456

Figure7:AcompressedrepresentationofFigure6.

placingthe2k+1queenswithoneperrowandcolumnofthecompressedboard.Thecostofaconﬁgurationofqueenswasthenumberofundominatedsquares.Thetransformationmethodwastochoosetworandomqueensatpositions(x1,y1)and(x2,y2)andmovethemtopositions(x1,y2)and(x2,y1).Thispreservestheonequeenperrowandcolumnconstraint,andallowsforthenewconﬁgurationtopossiblydominatediﬀerentsquaresalongthediagonals.

Byobservingthedominatingconﬁgurationsfoundonboardsofsize4k+1interestingpatternsemerge.Whenlookingatthecompressedboardrepresentationforlargeboards,itwasnotedthatapartfromtheedgesandthecentreoftheboard,onlyeveryseconddiagonalwasoccupiedinmostcases.InfacttheboardcouldbedominatedifonlyeveryseconddiagonalwereoccupiedasillustratedinFigure8(a)forthecaseofk=4.Theboardcouldalsobedominatedbyomittingsomenumberofcornerdiagonalsandincludingmorecentrediagonals.IngeneralthisisdenotedasanX/Ysetofdiagonals,whereX(resp.Y)down(resp.up)diagonalshavebeenremovedfromeachofthetwoappropriatecornersandX(resp.Y)pairsofup(resp.down)diagonalsaddedtothecentre.Figure8givesexamplesof0/0,0/1,1/1,and1/2setsofdiagonalsfork=4.

Thesediagonalscanbespeciﬁedformallybyﬁrstnumberingthediagonals.Letthesquaresbenumberedfrom0to2k−1acrossanddowntheboard.Thenthedowndiagonalpassingthroughsquare(x,y)isnumbered2k+x−yandtheupdiagonalisnumberedx+y+1.

AnX/Ydominatingsetofdiagonalsthenconsistsof•DownDiagonals

(2+2X),(2+2X)+2,...,(4k−2−2X)−2,(4k−2−2X)

(2k+1−2Y),(2k+1−2Y)+2,...,(2k−1+2Y)−2,(2k−1+2Y)•UpDiagonals

(2+2Y),(2+2Y)+2,...,(4k−2−2Y)−2,(4k−2−2Y)

(2k+1−2X),(2k+1−2X)+2,...,(2k−1+2X)−2,(2k−1+2X)

Thesecasesallusemostlyevennumbereddiagonalsandarereferredtoasanevendiagonalset.Itisalsopossibletodominatetheboardwithanodddiagonalset,whichconsistsmostlyoddnumbereddiagonals.Theseare•DownDiagonals

(1+2X),(1+2X)+2,...,(4k−1−2X)−2,(4k−1−2X)

(2k+2−2Y),(2k+2−2Y)+2,...,(2k−2+2Y)−2,(2k−2+2Y)•UpDiagonals

(1+2Y),(1+2Y)+2,...,(4k−1−2Y)−2,(4k−1−2Y)

(2k+2−2X),(2k+2−2X)+2,...,(2k−2+2X)−2,(2k−2+2X)

Inorderfortheboardtobedominated,theremuststillbeonequeenoneachverticalandhorizontallineandatleastonequeenoccupyingeachofthespeciﬁeddiagonals.IfevencasesarerestrictedtoXandYbeinglessthank,andoddcasesarerestrictedtoXandYbeinglessthank+1andnotequalto0,thenthereareatotalof2k−1−2X+2Ydowndiagonalsand2k−1−2Y+2Xupdiagonals.Thereareatmost2k+1queens,soatmost2k+1diagonalsofeachtypecanbeoccupied,whichleadstotheconstraintthat|X−Y|≤1.Furthermore,thetotalnumberofdiagonalsrequiredoverallis4k−2whichis4lessthanthemaximumthatcouldbeattackedby2k+1queens,soinanysolutiontherewillbe4sparediagonals.Thesecouldtaketheformofmultiplequeensattackingthesamediagonal,orredundantdiagonalsbeingattacked.AlsonotethatanevenX/Yconﬁgurationisthesameasanodd(k−Y)/(k−X)conﬁguration,henceonlycaseswhereeitherXorY

needbeconsidered.≤k2

Solutionstotheproblemcanthenbefoundthroughalocalsearchforconﬁgurationscontainingaqueenineachrowanddiagonalsuchthatoneofthesediagonalconﬁgurationsisdominated.Aprescribedsetofdiagonalsisinitiallychosen,andthetransformationofGibbonsandWebb’ssimulatedannealingalgorithmisused.Thecostofaconﬁgurationismuchmoreeasilycomputedasthenumberofspeciﬁeddiagonalsthatarenotoccupied,ratherthanthenumberofundominatedsquares.

Botheven-diagonalandodd-diagonalsetsforarangeofX/Yvaluesweretestedforallvaluesofkupto23.Forallcaseswithk≤20atleastoneevensolution,andwithk≤21atleastoneoddsolutionwasfound.

ThetypesofsolutionsfoundaregiveninTable11intheAppendix.SamplesolutionsforevencasescanbefoundinTable12andoddcasesinTable13,wherethenthelementinasolutionistherowinwhichthequeeninthenthcolumnisplaced.Animageofthecompressedboardforasolutionwithk=20canbeseeninFigure9.

(a)A0/0setofdominatingdiagonals.

(b)A1/0setofdominatingdiagonals.

(c)A1/1setofdominatingdiagonals.

(d)A2/1setofdominatingdiagonals.

Figure8:Thesecompressedrepresentationsof17×17boards(k=4)aredominatedbyfourdiﬀerentsetsofnumbereddiagonals.

Figure9:Aneven3/4dominatingsetfork=20.Thiscorrespondstoasetof41queens

dominatingan81x81board,provingthatγ(Q81)=41.Notethepairofqueensondowndiagonals22and30,andalsocoverageoftheredundantdowndiagonals51and57.

5.3FurtherObservations

Forallevencasesuptok=20andoddcasesuptok=21,anX/(X+1)solutionwasalwaysfound.Furthermore,Xincreasedby1forapproximatelyevery4valuesofkoncekbecamelargeenough.Continuingwiththispattern,itwouldbeexpectedthatfork=21to24,even4/5solutionswouldexist,andfork=22to25,odd5/6solutionswouldexist.Thealgorithmwasrunextensivelyontheseandothercaseswithrunningtimestotallingseveralweeks,butnofurtherresultsemergedforoddcaseshigherthank=21orevencaseshigherthank=20.ThiscouldbeduetothegeneralincreasedrunningtimethealgorithmrequireswithmovingtohigherX/(X+1)solutions.

ItisalsoseenthatforevenX/(X+1)conﬁgurations,allbut2X+2queenslieoneven/evenorodd/oddsquares.Furthermore,2Xofthesemustliewithinthecentralrectanglethatoccupiestheintersectioncentralodddiagonals.Similarly,foroddX/(X+1)conﬁgurations,allbut2X+1queenslieoneven/oddorodd/evensquares,and2X−1ofthesemustlieinthecentralevendiagonalintersectionregion.Thisinformationcouldbemadeuseofintheformofamorerestrictedsearchspace,butattemptstodosohavesofarbeenunsuccessful.

6ConcludingRemarks

Wehavepresentedanumberofcomputationalsearchtechniquesthathavebeenappliedtovariouschessboarddominationproblems.Thesehavebeensuccessfulingeneratingnewdominatingconﬁgurationsonn×nchessboards,forsmallvaluesofn.Forexample,newoptimaldominatingandindependentdominatingsetsofqueenshavebeenfoundtoproduceanupdatedsetofknownvaluesforγ(Qn)andi(Qn)inTable10.

n1234567101112131415γ(Qn)1112334555567i(Qn)1113344555577n161718192021γ(Qn)99910≤1111i(Qn)9910≤11≤1111

22232425≤12≤12≤1313≤12≤13≤1313

Table10:Knownvaluesforγ(Qn)andi(Qn).Boldvaluesarenewresultsfromthispaper.Webelievethatmethodssuchasthereductiontechniquecouldbesuccessfullyappliedtootherchessboardandcombinatorialproblems.

Wehaveshownthatir(Qn)=γ(Qn)forn≤13.Althoughitispossibleforsomenthatir(Qn)<γ(Qn)nosuchcasehasyetbeenfound.Byexaminingthediﬀerencebetweenthe

theoreticallowerboundofγ(Qn)≥n−andtheactualvalueofγ(Qn)itisfoundthatfor2

knownvaluesthisismaximalatn=15,wherethediﬀerenceis2.ThisindicatesthatQ15couldbealikelycandidateforasituationwhereir(Qn)<γ(Qn)istrue.Improvementstothealgorithmusedinthispapermayallowasearchforsuchacase.

Theprobabilisticalgorithmdevelopedheretoestablishthatγ(Q4k+1)=2k+1for16≤k≤21wasverysuccessful.Howeverthetransformationmethodusedwasrather

simplisticandifimproveduponfurthersolutionsmaybefound.Therearealsoadditionalpatternsofsolutionsthatwerenottakenadvantageofduringthesearch.

Inconclusionwebelievethatcomputationaltechniquessuchastheonesdescribedcanhelpshedlightonmanyoftheremainingopenchessboardproblemslistedin[10]and[14].

AAppendix

k1234567101112131415161718192021

SolutionTypesFoundEven0/1;Odd0/1Even0/1;Odd0/1

Even0/0,0/1,1/2;OddEven0/0,0/1,1/2;OddEven0/1,1/1,1/2;OddEven0/1,1/1;Odd1/1,Even1/2;Odd1/2Even1/2;Odd1/2Even1/2;Odd1/2Even1/2Odd2/3Even1/2Even2/3Odd2/3Even2/3Odd2/3Even2/3Odd2/3Odd3/3Even2/3Odd3/4Even2/3Odd3/3Odd3/4Even2/3Odd3/4Even3/4Odd3/4Even3/4Odd4/5Even3/4Odd4/5Even3/4Odd4/5Odd4/5

AverageTime------0.3secs2secs4secs3secs13secs9secs35secs35secs150secs12secs60secs80secs110secs60secs240secs5mins20mins24mins3hours10mins3hours1hour7hours28hours1hour6hours4hours50hours30hours

1/1,0/1,1/1,1/2,1/21/11/22/3

Table11:Solutiontypesfoundforγ(Q4k+1)=2k+1.

k12345671011121314151617181920

SolutionTypeEven0/1Even0/1Even0/1Even0/1Even0/1Even0/1Even1/2Even1/2Even1/2Even1/2Even1/2Even2/3Even2/3Even2/3Even2/3Even2/3Even3/4Even3/4Even3/4Even3/4

SampleSolution(0,2,1)(1,3,0,2,4)(2,5,1,4,0,3,6)(1,7,2,5,8,4,0,3,6)

(8,7,2,4,3,9,0,5,10,1,6)

(10,5,2,11,3,6,12,9,0,7,4,1,8)

(6,3,10,1,14,9,2,8,5,12,0,11,4,7,13)

(12,7,3,11,2,1,16,10,8,6,0,15,14,5,13,9,4)

(8,15,12,6,3,1,18,11,2,10,7,17,0,13,16,5,14,9,4)

(10,15,8,3,20,17,7,5,0,12,9,19,16,1,4,11,18,14,2,13,6)

(16,19,6,3,18,13,7,17,2,12,22,1,11,10,0,21,14,9,20,15,8,5,4)(18,11,6,19,0,5,8,4,20,12,24,16,13,21,9,1,22,15,2,7,10,3,14,17,23)

(12,7,22,4,18,15,6,25,2,5,26,14,17,10,13,1,24,21,0,11,8,23,20,3,19,9,16)

(8,19,12,17,26,21,3,5,28,9,0,14,4,18,15,27,11,23,20,13,2,25,6,1,10,24,22,7,16)

(12,15,20,7,26,29,2,27,11,19,4,8,17,14,30,3,24,16,13,1,6,21,28,25,0,23,10,5,18,9,22)

(8,21,24,27,20,15,32,7,4,23,0,16,6,31,17,1,13,18,30,14,19,25,28,3,12,9,2,29,26,11,22,5,10)

(2,23,28,15,8,5,14,31,6,25,11,29,4,33,21,18,13,27,32,12,19,16,0,3,30,7,10,1,22,34,26,17,20,9,24)

(7,21,28,25,14,9,20,35,2,11,34,29,0,12,17,1,32,22,19,16,13,3,30,18,36,31,6,23,26,5,8,15,4,33,24,27,10)

(26,13,32,10,14,5,24,15,28,37,2,9,36,3,30,20,38,16,19,33,23,18,6,1,17,7,21,29,0,35,34,11,8,27,4,31,22,25,12)

(28,9,22,13,8,29,32,39,14,5,40,33,30,7,4,20,15,24,21,11,36,16,23,37,2,18,38,27,12,3,6,1,0,35,31,17,34,25,10,19,26)

Table12:Evensolutionsfoundforγ(Q4k+1)=2k+1.

k1234567101112131415161718192021

SolutionTypeOdd0/1Odd0/1Odd1/2Odd0/1Odd1/2Odd1/2Odd1/2Odd1/2Odd1/2Odd2/3Odd2/3Odd2/3Odd2/3Odd3/4Odd3/4Odd3/4Odd3/4Odd4/5Odd4/5Odd4/5Odd4/5

SampleSolution(1,0,2)(3,0,2,4,1)(2,0,5,3,1,6,4)(7,6,3,0,4,8,5,2,1)

(7,3,1,6,9,0,4,8,5,2,10)

(9,0,3,10,6,2,11,5,8,12,1,4,7)

(7,12,3,8,4,14,1,9,6,0,13,10,5,2,11)

(9,4,13,16,3,12,7,5,8,2,15,0,14,10,1,6,11)

(15,4,7,16,13,6,17,0,10,9,8,18,1,12,5,2,11,14,3)

(0,10,13,16,5,20,1,14,12,6,8,2,17,9,3,18,15,19,11,4,7)

(11,5,17,20,13,2,6,14,1,22,12,9,3,0,10,18,21,16,19,8,15,4,7)(7,14,11,22,5,9,23,4,19,24,12,16,1,13,10,6,3,0,21,18,15,2,20,8,17)

(7,20,11,8,5,26,23,18,10,24,14,4,25,13,3,2,12,15,21,0,17,6,1,22,19,16,9)

(19,8,13,5,21,18,1,28,23,2,14,17,9,0,3,11,16,26,12,22,25,6,20,24,15,4,7,10,27)

(3,22,25,12,9,24,19,4,1,13,27,26,18,15,5,2,10,17,14,30,21,0,29,8,23,20,7,16,11,6,28)

(13,18,25,8,19,24,31,28,1,4,11,7,16,2,20,17,14,0,29,26,5,15,21,32,27,12,23,6,3,10,30,22,9)

(9,24,13,10,31,7,27,22,33,2,11,16,18,30,3,34,20,15,1,32,14,17,25,0,21,12,5,8,28,4,29,26,23,6,19)

(7,12,19,30,27,10,31,1,11,2,25,6,18,34,22,17,35,21,5,15,33,4,20,32,16,24,3,0,29,14,9,28,13,8,23,26,36)

(27,12,21,28,6,10,35,4,11,16,33,0,5,19,22,32,29,38,3,23,18,13,37,17,20,34,9,26,1,8,31,2,7,24,15,30,36,14,25)

(27,16,13,3,29,36,7,30,37,12,1,28,17,34,9,23,18,2,22,25,39,4,14,19,33,6,20,40,35,26,5,0,21,32,11,8,15,24,31,10,38)

(13,28,19,26,37,12,9,18,3,34,41,17,11,42,35,4,31,25,20,38,24,15,7,23,16,2,22,6,33,10,39,0,5,30,1,36,29,8,21,14,27,32,40)

Table13:Oddsolutionsfoundforγ(Q4k+1)=2k+1.

References

[1]W.W.RouseBall,MathematicalRecreationandProblemsofPastandPresentTimes,

MacMillan,London(12).[2]J.R.BitnerandE.M.Reingold,BacktrackProgrammingTechniques,Comm.ACM,18

(1975),651-656.[3]A.P.Burger,E.J.Cockayne,andC.M.Mynhardt,DominationnumbersfortheQueens’

graph,Bull.Inst.Combin.Appl.10(1994)73-82.[4]A.P.Burger,E.J.Cockayne,andC.M.Mynhardt,DominationandIrredundancein

theQueens’graph,DiscreteMathematics163(1997)47-66.[5]E.J.Cockayne,S.T.Hedetniemi,andD.J.Miller,Propertiesofhereditaryhypergraphs

andmiddlegraphs.Canad.Math.Bull.,21(4),461-468,1978.[6]E.J.Cockayne,IrredundanceintheQueens’Graph,submitted.

[7]E.J.Cockayne,ChessboardDominationProblems,DiscreteMathematics86(1990)13-20.[8]E.J.CockayneandP.H.Spencer,OntheIndependentQueensCoveringProblem,Graphs

andCombinatorics4(1988)101-110.[9]M.Eisenstein,C.M.Grinstead,B.Hahne,D.VanStoneTheQueenDominationProblem

Congr.Numer.91(1992)1-193.[10]G.H.Fricke,S.M.Hedetniemi,S.T.Hedetniemi,A.A.McRae,C.K.Wallis,M.S.

Jacobson,H.W.Martin,andW.D.Weakley,CombinatorialProblemsonChessboards:aBriefSurvey,in:AlaviandSchwenkeds.,GraphTheory,CombinatoricsandApplications,vol.1,Proc.eventhQuadrennialConf.ontheTheoryandApplicationsofGraphs,WesternMichiganUniversity(Wiley,1995).[11]P.B.Gibbons,ComputationalMethodsinDesignTheory,inTheCRCHandbookof

CombinatorialDesigns,C.J.ColbournandJ.H.Dinitz(eds.),CRCPress(1996)Chapter9,SectionVI.[12]P.B.GibbonsandJ.A.Webb,SomeNewResultsfortheQueensDominationProblem,

AustralasianJournalofCombinatorics15(1997)145-160.[13]C.M.Grinstead,B.Hahne,D.VanStone,OntheQueenDominationProblem,Discrete

Mathematics86(1991)21-26.[14]SandraM.Hedetniemi,StephenT.Hedetniemi,andRobertReynolds,Combinatorial

ProblemsonChessboards:II,in:DominationinGraphs,AdvancedTopics(1997)Chap-ter6.[15]MatthewD.Kearse,LowerBoundsonIredundanceintheQueens’Graph,toappear.

[16]E.Lucas,R´ecr´eationsMath´ematiques,Gauthier-Villars,Paris(11).

[17]BrendanD.McKay,Isomorph-FreeExhaustiveGeneration,JournalofAlgorithms26

(1998)306-324.[18]PatrickProsser,HybridAlgorithmsfortheConstraintSatisfactionProblem,Computa-tionalIntelligence9(1993)268-299.[19]J.D.Swift,IsomorphRejectioninExhaustiveSearchTechniques,Proc.A.M.S.Symp.

Apple.Math.10(1958),195-200.[20]JohannesWaldmann,Privatecorrespondence(1998).

[21]R.J.Walker,AnenumerativeTechniqueforaClassofCombinatorialProblems,inCom-binatorialAnalysis(ProceedingsofSymposiainAppliedMathematics,Vol.X),AmericanMathematicalSociety,Providence,R.I.(1960).[22]W.D.Weakley,DominationintheQueen’sGraph,GraphTheory,Combinatorics,and

Applications2(1995)1223-1232.[23]W.D.Weakley,UpperBoundsforDominationNumbersoftheQueensGraph,preprint.[24]A.M.YaglomandI.M.Yaglom,ChallengingMathematicalProblemswithElementary

Solutions,volume1:CombinatorialAnalysisandProbabilityTheory.Holden-Day,SanFrancisco.(19).

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文