Hopperproblem

Det springer Problemet (eller til og med polygraphy eller algoritme av den springer eller rider av Euler) er en matematisk-logisk problem basert på bevegelser av den springer av sjakkspill (en kvadratisk deling av en felles side og deretter en diagonal kvadrat i samme retning) . En ridder som er plassert på et hvilket som helst kvadrat på sjakkbrettet, må besøke alle rutene uten å passere to ganger på den samme.

Ulike variasjoner av problemet

Ulike typer bevegelse av deler

Mens målet generelt er å dekke alle rutene på brettet med en ridder, har en variant blitt studert i det middelalderske Midtøsten der stykket veksler mellom en ridderbevegelse og en diagonal bevegelse ( se nedenfor ).

Ulike skuffformer

Problemet gjaldt opprinnelig forløpet til et firkantet sjakkbrett på 64 firkanter eller på et halvt sjakkbrett på 32 firkanter; men det ble senere studert for andre dimensjoner og også for ikke-rektangulære former, inkludert kors.

Ulike typer ruter

Det er forskjellige måter å krysse sjakkbrettet på: banen kan være åpen eller i nærheten av seg selv, i så fall snakker vi om rytterens tur . Vi kan også se etter løsninger med bestemte symmetrier eller til og med de lengste løsningene uten å krysse.

Krets av hopperen på et sjakkbrett i størrelsen 24 × 24 oppnådd av et nevralt nettverk .
Kurs åpnet på et sjakkbrett på størrelse 130 x 130, oppnådd ved bruk av heuristikken til Warnsdorf.
Åpne kurs på et sjakkbrett på 5 x 5 størrelse.
Rytterens tårn på et kryssformet brett.
Lukket krets uten maksimal kryssing på kort 49; lengden er 24 hopp.
Åpen bane uten maks kryss på sjakkbrett størrelse 64; lengden er 35 hopp.

Historie

I India

Den første forekomsten finnes i en avhandling om indisk poetisk ornament, Kavyalankara av dikteren Rudrata.

En løsning på problemet i løpet av et helt halvt sjakkbrett på 32 firkanter ble funnet i et manuskript fra begynnelsen av X - tallet ; denne løsningen kan enkelt tilpasses for å oppnå hele sidelinjen til et sjakkbrett på 64 firkanter. Denne løsningen er ikke en krets fordi den ikke lar deg gå tilbake til startpunktet.

Et indisk leksikon fra XVII - tallet illustrerer lukket sti på et brett på 64 firkanter. Charles Monneron rapporterer fra India om en annen løsning på problemet, som vil bli skrevet ut senere i Encyclopedia .

Løsning av kurset på et halvt sjakkbrett (900 e.Kr.).
1	30	9	20	3	24	11	26
16	19	2	29	10	27	4	23
31	8	17	14	21	6	25	12
18	15	32	7	28	1. 3	22	5

Indisk sti stengte XVII - tallet.
2	51	6	15	64	25	28	23
7	14	1	50	5	22	43	26
52	3	8	63	16	27	24	29
9	62	1. 3	4	49	42	21	44
12	53	10	17	36	45	30	41
61	56	59	48	31	40	35	20
58	11	54	37	18	33	46	39
55	60	57	32	47	38	19	34

Åpent kurs med sammenhengende ender rapportert av Monneron.
17	20	39	4	37	22	49	6
40	53	18	21	8	5	36	23
19	16	3	38	61	50	7	48
54	41	52	1	64	9	24	35
15	2	1. 3	60	51	62	47	10
42	55	30	63	12	59	34	25
29	14	57	44	27	32	11	46
56	43	28	31	58	45	26	33

Raja Krishna Wadiyar III (i) ble interessert i faget i første halvdel av XIX th århundre , skylder vi ham til den første av et kurs kjent rytter hvis blokk tall danner et magisk kvadrat.

I den arabiske verden

Lukket krets

Den rytteren Euler har vært kjent i lang tid. Rundt 840 ga den arabiske sjakkspilleren og teoretikeren al-Adli ar-Rumi allerede en løsning.

Midler mnemoniske for å holde en løsning på skjøteledningen kretsen er dokumentert i et manuskript kopiert på 1,141 , som inneholder tekster i tillegg til den X- th -tallet ; dette er dikt på 64 vers , som hver er knyttet til koordinatene til en firkant på sjakkbrettet. Fire slike dikt er kjent, noe som fører til den konklusjonen at problemet med rytterkretsen var populært i den arabisk-muslimske verden, og at ingen generell metode for å konstruere en slik kurs var kjent.

Andre kursregler

Arabiske lærde har også studert et beslektet problem der stykket som skal flyttes, vedtar vekselvis bevegelsen til rytteren og den til en annen brikke, rådgiver eller elefant, i chatrang (versjonen av sjakk praktisert i den middelalderske arabiske verdenen). Rådgiveren ( damens forfader ) og elefanten (forfedren til den galne ) som beveger seg henholdsvis ett kvadrat diagonalt og to kvadrater diagonalt. Dikt ble også komponert for å huske løsninger.

Arabisk lukket kurs av en elefantrytter.
49	42	40	51	9	34	36	11
47	52	54	45	39	12	14	33
41	50	48	43	37	10	8	35
55	44	46	53	15	32	38	1. 3
61	22	16	63	5	26	28	7
19	56	58	21	31	64	2	25
17	62	60	23	29	6	4	27
59	20	18	57	3	24	30	1

Arabisk lukket kurs for en rytter-rådgiver.
37	14	16	35	33	18	24	31
15	36	34	17	19	32	30	25
1. 3	38	48	11	21	26	28	23
39	12	10	49	27	20	22	29
9	42	40	47	61	50	52	63
43	8	46	41	51	60	62	53
45	6	4	59	57	2	64	55
7	44	58	5	3	56	54	1

I Occident

I middelalderen og renessansen

Det finnes i et manuskript Anglo-Norman fra XIV - tallet en farled som tar sikte på å bringe rytteren fra et hjørne til et annet. Flere andre senere manuskripter gir også åpne kurs på sjakkbrett eller halvpensjon.

Løsning datert XIV th århundre.
23	26	11	4	49	52	45	40
10	3	22	25	46	41	48	51
27	24	5	12	53	50	39	44
2	9	28	21	42	47	54	59
29	20	1. 3	6	61	58	43	38
8	1	16	19	32	35	60	55
17	30	7	14	57	62	37	34
.	15	18	31	36	33	56	63

I begynnelsen av XVIII th århundre

Pierre Rémond de Montmort studerte dette problemet, og gir en løsning sitert av Martin Grandin . Sistnevnte bruker også to andre løsninger innhentet av Abraham de Moivre og av de Mairan .

Rémond de Montmorts løsning
58	23	62	15	64	21	54	1. 3
61	16	59	22	55	14	51	20
24	57	10	63	18	49	12	53
9	60	17	56	11	52	19	50
34	25	36	7	40	27	48	5
37	8	33	26	45	6	41	28
32	35	2	39	30	43	4	47
1	38	31	44	3	46	29	42

Løsning av de Moivre der det sentrale torget besøkes etter grensen.
34	49	22	11	36	39	24	1
21	10	35	50	23	12	37	40
48	33	62	57	38	25	2	1. 3
9	20	51	54	63	60	41	26
32	47	58	61	56	53	14	3
19	8	55	52	59	64	27	42
46	31	6	17	44	29	4	15
7	18	45	30	5	16	43	28

Mairans lukkede løsning.
56	9	26	43	54	7	32	29
25	44	55	8	27	30	53	6
10	57	24	39	42	33	28	31
23	40	45	36	1	52	5	34
46	11	58	41	38	35	64	51
59	22	37	48	19	2	15	4
12	47	20	61	14	17	50	63
21	60	1. 3	18	49	62	3	16

Eulers arbeid

Matematikeren Leonhard Euler gjenopptok den vitenskapelige studien i 1759 . "Løsningen på et nysgjerrig spørsmål som ikke synes å være gjenstand for noen analyse" ble imidlertid ikke publisert før i 1766 . Côme Alexandre Collini publiserte en i Encyclopedic Journal i 1773.

Euler viser der løsningen på flere problemer:

hvordan få en komplett tur fra en delvis tur;
hvordan man forvandler en åpen sti til en lukket sti;
hvordan få en symmetrisk sti;
å få kurs på firkantede eller rektangulære sjakkbrett av varierende størrelse;
skaffe seg fullstendige kurs på sjakkbrett i form av et kors eller rombkors .

En løsning publisert av Euler.
En løsning foreslått av Euler. Dette er symmetrisk i forhold til sentrum av sjakkbrettet, og går først gjennom den nedre halvdelen av sistnevnte, deretter den øvre delen.
Løsning av trikset på et 10x10 sjakkbrett, foreslått av Euler.

Euler gjorde også feil, han bekreftet dermed at ingen lukket sti er mulig på et sjakkbrett med bredde 3; et moteksempel ble gitt i 1917 på et sjakkbrett i størrelse 3 × 10.

Stengt kurs på et sjakkbrett i størrelse 3 × 10.
1	28	25	6	19	4	21	10	1. 3	16
26	7	30	3	24	9	18	15	22	11
29	2	27	8	5	20	23	12	17	14

Videre studier

Gjennom århundrene har matematikere studert dette temaet ved å variere:

dimensjonene til sjakkbrettet,
antall spillere,
egenskapene til ruten,
måten en rytter beveger seg på.

Det ble foreslått å studere rytterkursene der summen av antall passasjer i en boks er konstant i henhold til radene og kolonnene. I 1888 ble 83 slike kurs (inkludert 27 stengt) deponert ved National Conservatory of Arts and Crafts ; ingen av disse banene gir en magisk firkant fordi summen ikke er den samme etter diagonalene. En 84 th ruten ble oppdaget i 1970 Omfattende forskning etablert i 2003 som et sjakkbrett det er totalt 108 ulike kurs som danner magisk kvadrat verken som har lik diagonal

Lukket kurs som også er et magisk torg. (Med unntak av diagonalene)
42	59	2	17	40	15	22	63
3	18	41	60	21	64	39	14
58	43	20	1	16	23	62	37
19	4	57	44	61	38	1. 3	24
56	45	6	29	12	25	36	51
5	30	55	48	33	52	11	26
46	7	32	53	28	9	50	35
31	54	47	8	49	34	27	10

Det skal bemerkes at det arbeides noe med emnet golfkjørere XXI th century .

Matematisk analyse

Kobling med grafteori

Jakten på en rytters tur er et spesielt tilfelle av Hamiltoniske grafer i grafteorien . Dessuten, siden en ridder alltid går fra en svart boks til en hvit boks og omvendt , følger det at grafen for ridderens bevegelser er en todelt graf .

Eksistens av et åpent kurs på et rektangulært sjakkbrett

Når det gjelder et søk etter et kurs som ikke nødvendigvis løper på seg selv, er det bevist at det er en løsning for ethvert rektangulært sjakkbrett med lengde og bredde som er større enn eller lik 5.

Eksistensen av en lukket krets på et rektangulært sjakkbrett

Triksene til ryttere kan gjøres på brikker av forskjellig størrelse og i forskjellige former (rektangel, terning, belegningsstein, uendelig spiral osv.), Men antall firkanter må være jevnt. Når det gjelder et rektangulært sjakkbrett, har vi følgende eksistensresultat:

Schwenks setning - For ethvert m × n sjakkbrett slik at m er mindre enn eller lik n , er det en ridderes tur, med mindre en eller flere av følgende forhold er oppfylt:

m og n er rare; n er forskjellig fra 1.
m = 1, 2 eller 4; n er forskjellig fra 1.
m = 3 og n = 4, 6 eller 8.

Tilstand 1

Betingelse 1 forhindrer eksistensen av en lukket sving, av enkle grunner til paritet og farging. På et standard sjakkbrett i svart og hvitt beveger en ridder seg fra hvitt til svart eller omvendt. Så en lukket sving må besøke samme antall sorte og hvite firkanter, og antall besøkte torg må være jevnt. Nå hvis m og n er merkelige, er antall kvadrater merkelig så det er ingen lukket sving. Imidlertid kan det være åpne tårn.

Tilstand 2

I henhold til denne tilstanden er det ingen lukket sving hvis den minste siden er 1, 2 eller 4.

Hvis m = 1 eller 2, kan ikke ridderen nå alle rutene (unntatt i trivielt tilfelle 1 × 1 ). Vi kan også vise fraværet av en lukket sving i 4 × n-saken ved et fargeleggingsargument.

Anta at det er et lukket tårn på et 4 × n sjakkbrett . La oss kalle settet med svarte firkanter og settet med hvite firkanter besøkt av svingen, på et standard sjakkbrett. La oss se på figuren til høyre. La oss kalle settet med grønne bokser og settet med røde bokser. De er like mange. Merk at ridderen må gå fra et kvadrat til et kvadrat på . Siden han må besøke hvert kvadrat, må han også gå fra et kvadrat til et kvadrat av (ellers måtte han reise to eller flere ruter etterpå, noe som er umulig). $A_1$ $A_ {2}$ $B_ {1}$ $B_ {2}$ $B_ {1}$ $B_ {2}$ $B_ {2}$ $B_ {1}$ $B_ {1}$

Undersøkelse av dette hypotetiske trikset gir en motsetning:

Den første firkanten av svingen vil være i og . Ellers er det tilstrekkelig å invertere definisjonene av og . $A_ {1}$ $B_ {1}$ $B_ {1}$ $B_ {2}$
Den andre boksen må være i og . $A_ {2}$ $B_ {2}$
Den tredje boksen må være i og . $A_ {1}$ $B_ {1}$
Den fjerde boksen må være i og . $A_ {2}$ $B_ {2}$
Og så videre.

Det følger at settene og er forvirrede, akkurat som settene og . Dette er absurd, så det er ingen tur i 4 × n-saken , uavhengig av n . $A_ {1}$ $B_ {1}$ $A_ {2}$ $B_ {2}$

Tilstand 3

Vi kan bevise tilstand 3 fra sak til sak. Å lete etter en lukket sving i 3 × 4 , 3 × 6 , 3 × 8 tilfeller mislykkes raskt. For 3 × n tilfeller , med n jevn og større enn 8, konstruerer vi de lukkede svingene ved induksjon, og gjentar bevegelsene.

Andre tilfeller

Vi har bevist at et lukket tårn ikke eksisterer under de tre nevnte forholdene. Å bevise eksistensen av et slikt triks i andre tilfeller er mer komplisert.

Effektiv oppnåelse av et rytterkurs

For å lykkes i et kurs er det tilstrekkelig å velge for hvert nytt hopp en ledig plass blant den som gir færrest mulig påfølgende hopp, selv om det betyr å avbryte de siste trekkene i tilfelle en blindgate: dette er en klassisk programmeringsøvelse.

Selv om det generelle problemet med å finne en Hamilton-krets i en graf er NP-komplett , kan det spesielle tilfellet med rytterens tur løses på lineær tid .

Oppregning av løsninger

Det er 26.534.728.821.064 forskjellige lukkede kretser på et firkantet sjakkbrett med 64 firkanter, og det er 9.862 av dem på et firkantet sjakkbrett på 36 firkanter.

Antall åpne baner for et firkantet sjakkbrett er gitt av A165134 fra OEIS :

Sjakkbrett dimensjon:	1	2	3	4	5	6	7	8
Antall åpne kurs:	1	0	0	0	1.728	6,637,920	165 575 218 320	19 591 828 170 979 904

applikasjoner

Kryptografi

Jumperproblemet er blitt foreslått for å designe krypteringsskjemaer i visuell kryptografi ;
Problemet har også blitt foreslått for generering av pseudo - tilfeldige tall med kryptografisk kvalitet.

I litteratur

Rudrata , en dikter av Kashmir fra slutten av IX - tallet (rundt 825-850), tilbyr et problem Euler skrevet i vers: "Poesi av poesi" skrevet på sanskrit , som inkluderer et sett med vers basert på stavelserier i forhold til rytterkurset.
Georges Perec distribuerer i romanen La Vie mode emploi kapitlene i boken i henhold til løpet av en rytter av Euler.
Mikhaïl W. Ramseier , i sin roman Nigrida , tilbyr et plot som dreier seg om et kryptogram basert på en Vigenère-kryptering skjult i et problem for Eulers rytter.
I XX th århundre, forfattere gruppe Oulipo bruker dette. Det mest bemerkelsesverdige eksemplet er 10 × 10-turen som bestemmer rekkefølgen på kapitlene i boken av Georges Perec : La Vie manual . Den samme forfatteren brukte også en 9 × 9 i Two Hundred og Forty-Three True Color Postkort .

Merknader og referanser

Merknader

Schwenks setning ( se nedenfor ) lar oss faktisk si at de eneste sjakkbrettene med bredde 3 som det ikke er noen lukket krets for, har en lengde på 2, 4, 6, 8 eller et oddetall.
Den oppnådde da beløpet er en åttendedel av den totale sum av 64 tall : . ${\ displaystyle {\ frac {64 \ times 65} {2}} \ times {\ frac {1} {8}} = 260}$
Andre kilder nevner andre funn mellom 1888 og 1970, det ser ut til at spill og strategi ble feilinformert
Noen baner kan nummereres fra flere startruter, med tanke på at det er totalt 140 baner, med nær symmetri.

Referanser

(fr) Denne artikkelen er delvis eller helt hentet fra Wikipedia-artikkelen på engelsk med tittelen " Knight's tour " ( se listen over forfattere ) .

Maksimal lengde på et åpent kurs er gitt i følgende A003192 av OEIS , og det av et lukket kurs etterpå A157416 av OEIS .
C. Rajendran, "bevegelser Chaturanga Beskrevet i Rudrata's Kavyalankara" i Working-Papers "Indian Views", Förderkreis Scach-Geschichtsforschung eV november 2001.
Sesiano 2015 , s. 163
Sesiano 2015 , s. 162
Sesiano 2015 , s. 161
(no) " History of Magic Knight's Tour " , om mayhematics ,2004
Sesiano 2015 , s. 157
Sesiano 2015 , s. 159
Sesiano 2015 , s. 160
Sesiano 2015 , s. 165-167
Sesiano 2015 , s. 168
Sesiano 2015 , s. 169
Euler, Løsning av et nysgjerrig spørsmål som ikke synes å være gjenstand for noen analyse , Mémoires de l'Académie Royale des Sciences et Belles Lettres, År 1759, bind 15, s. 310-337, Berlin 1766
Sesiano 2015
Jean-Paul Delahaye , " Du uklarhet Det falske i matematikk " Pour la Science , n o 516,oktober 2020.
Pierre Berloquin , " Manøver av kavaleri ", Jeux et Stratégie , nr . 18,November-desember 1982, s. 24-26.
(i) Eric W. Weisstein , " Det er ingen magiske ridderturer på sjakkbrettet " på MathWorld ,6. august 2003.
(in) P. og J. Cull De Curtins, " Knight's Tour Revisited " , Fibonacci Quarterly , vol. 16,1978, s. 276–285 ( les online )
(in) A. Conrad, T. Hindrichs, H. Morsy og I. Wegener, " Solution of the Hamiltonian Path Problem Knight's one Chessboards " , Discrete Applied Mathematics , vol. 50, n o to1994, s. 125–134 ( DOI 10.1016 / 0166-218X (92) 00170-Q )
(i) Allen J. Schwenk, " Hvilke rektangulære sjakkbrett har en ridderturné? " , Mathematics Magazine ,1991, s. 325–332
(in) John J. Watkins, Over the Board: the Mathematics of Chessboard Problems , Princeton University Press ,2004, 257 s. ( ISBN 978-0-691-11503-0 , les online )
(i) Brendan McKay, " Knight's Tours is an 8 × 8 Chessboard " , teknisk rapport TR-CS-97-03 , Institutt for informatikk, Australian National University,1997( les online )
(in) Eric W. Weisstein , " Knight's Tour " på MathWorld
(i) Manpreet Singha, Ajay Kakkarb og Manjinder Singhc, " Bilde kryptering Basert på Ridder Tour Problem " , Procedia Computer Science ,2015( les online ).
(in) Ali Shakir Mahmood og Mohd Rahim Mohd Shafry, " Generating and Expanding of year Encryption Key Based on the Knight's Tour Problem " , Journal of Theoretical and Applied Information Technology , Vol. 95, n o 7,15. april 2017( les online ).

Bibliografi

[Sesiano15] Jacques Sesiano, Euler og rytterens reise: Med et vedlegg om teoremet til polyhedra , Lausanne, Presses polytechniques et universitaire romandes ,2015, 272 s. ( ISBN 978-2-88074-857-9 , online presentasjon , les online ).

Relaterte artikler

Twixt

Eksterne linker

(no) George Jelliss, “ Knight's Tour Notes ” , på mayhematics.com , 2000 - 2017 (åpnet 3. november 2017 ) : samling av ruter fra forskjellige epoker, med forskjellige regler og forskjellige brettformer.
Beskrivelsen av problemet og noen referanser av Georges Perec hentet fra anmeldelsen l'Arc , nr. 78.
Et Flash-program for å spille rytterproblemet på procrastin.fr
(no) program for å løse problemet med rytteren på bloggen Dmitry Brant