Otte dronninger, Eulers springer, det afkortede skakbræt: de store matematiske hjernetræningsopgaver på skakbrættet

Disse opgaver løses med skakbrikkerne eller skakbrættets gitter, men de har intet med en partie at gøre: de er ægte matematikopgaver, som kan løses fra mellemskoleniveau, og nogle af dem har optaget store navne inden for faget. De passer perfekt til en matematikklub, en fremlæggelse eller et emne til en mundtlig eksamen.

Oversigtstabel

Otte dronninger-problemet

Otte dronninger-problemet

At placere otte dronninger på et skakbræt på 8 × 8, så ingen kan slå en anden: aldrig to dronninger på samme række, samme linje eller samme diagonal.

Problemet blev offentliggjort i 1848 af Max Bezzel, en skakproblemkomponist. Franz Nauck offentliggjorde de første løsninger i 1850 og generaliserede det til n dronninger på et bræt med n × n felter. Carl Friedrich Gauss hører til de matematikere, der interesserede sig for det.

Problemets mål: at finde én placering og dernæst alle. Der findes 92. Mange kan udledes af hinanden ved rotation eller spejling af brættet; hvis man samler dem, står der tilbage 12 grundløsninger. Her er en af dem, med dronningerne på d8, g7, c6, h5, b4, e3, a2 og f1:

Man kan let kontrollere, at der er én dronning på hver række og hver linje. For diagonalerne skal man blot kontrollere, at forskellen i kolonner mellem to vilkårlige dronninger aldrig er lig med forskellen i rækker.

Hvordan løser man det?

Den klassiske metode er tilbagesporing (på engelsk backtracking): man placerer en dronning i første kolonne, derefter en dronning i anden kolonne på et felt, der ikke angribes, og så videre; når der ikke er noget felt tilbage, går man tilbage og flytter den foregående dronning. Det er en meget populær øvelse i informatik på gymnasiet. Versionen med n dronninger har løsninger for alle n undtagen 2 og 3: for eksempel 2 løsninger for n = 4, 10 for n = 5, 4 for n = 6 og 40 for n = 7.

Eulers springerproblem

Springerproblemet

Find en række springertræk, der besøger hvert af de 64 felter præcis én gang. Rundturen kaldes lukket, hvis det sidste felt ligger ét springertræk fra det første, så løkken kan gentages.

Problemet er meget gammelt: en rundtur for springeren på en halv skakbræt optræder allerede i en sanskrit-poetikafhandling fra det 9. århundrede, Kavyalankara af Rudrata. Leonhard Euler viede det en afhandling, « Solution d'une question curieuse qui ne paroit soumise à aucune analyse » (Løsning på et nysgerrigt spørgsmål, der ikke synes at kunne behandles analytisk), fremlagt i 1759 og udgivet i 1766 i Det Kongelige Preussiske Videnskabsakademis (Berlin) skrifter. I 1823 foreslog H. C. von Warnsdorff en enkel regel til at finde en rundtur: gå altid til det felt, hvorfra springeren har færrest mulige træk videre.

Der findes et enormt antal lukkede rundrejser på et almindeligt skakbræt: 26 534 728 821 064, når retningen tælles med, altså halvdelen, 13 267 364 410 532, hvis man regner en rundrejse og dens omvendte som det samme.

En rundrejse at tjekke på et bræt med 5 × 5 felter

Til træning kan man starte med noget mindre. Her er en åben rundrejse, der besøger alle 25 felter på et bræt med 5 × 5: følg tallene fra 1 til 25; hvert tal ligger ét springertræk fra det foregående.

Denne rute er fundet med Warnsdorffs regel, og hvert spring er kontrolleret. Udfordring: find en anden, der starter i midten.

Springerproblemet til den mundtlige eksamen

Emnet egner sig godt til den mundtlige prøve i studieretningen matematik eller NSI (informatik): modellering med en graf (felterne er knudepunkterne, de mulige spring er kanterne), søgning efter en vej, der går gennem alle knudepunkter, algoritmen med tilbagesporing, Warnsdorffs regel og dens effektivitet. Man kan også forklare, hvorfor der ikke findes nogen lukket rundrejse på et bræt med 5 × 5 felter: springeren skifter farve ved hvert træk, så en løkke må have et lige antal felter, men 25 er ulige.

Det afkortede skakbræt

Filosoffen Max Black stillede problemet i 1946 i sin bog Critical Thinking. Man fjerner to modsatte hjørner fra et skakbræt (for eksempel a1 og h8). Kan man dække de 62 resterende felter med 31 dominobrikker, hvor hver brik dækker to nabofelter?

Svar: nej. Hver dominobrik dækker nødvendigvis et hvidt og et sort felt. 31 dominobrikker ville derfor dække 31 hvide og 31 sorte felter. Men de to modsatte hjørner har samme farve: der bliver 32 felter i den ene farve og 30 i den anden. Dækningen er umulig, uden at man behøver at prøve en eneste placering. Martin Gardner gjorde problemet kendt for et bredt publikum i 1957 i sin klumme i Scientific American.

Og hvis man fjerner et hvidt og et sort felt? Ralph Gomory har vist (resultat offentliggjort i 1973), at dækningen så altid er mulig, uanset hvilke to felter der fjernes.

Polyominoer og pentominoer

En polyomino er en figur sammensat af ens kvadrater, der hænger sammen via deres sider; dominoen har to, pentominoen fem. Matematikeren Solomon Golomb indførte og undersøgte disse figurer fra 1953. Der findes 12 forskellige pentominoer (når man regner en brik, der vendes eller drejes, som den samme), og de dækker tilsammen 60 felter.

Et skakbræt har 64 felter, altså 60 + 4: man kan derfor forsøge at lægge de 12 pentominoer på skakbrættet og lade et kvadrat på 2 × 2 i midten stå åbent. I 1958 lod Dana Scott en computer løse dette problem, et af de første anvendelser af metoden med tilbagesporing: der findes 65 løsninger. En anden berømt udfordring: et rektangel på 6 × 10 kan dækkes på 2 339 forskellige måder med de 12 pentominoer.

Hvor mange kvadrater er der på et skakbræt?

Svaret »64« er forkert, eller rettere ufuldstændigt: det tæller kun de små kvadrater. Man skal også tælle kvadrater på 2 × 2, 3 × 3 … op til det store kvadrat på 8 × 8.

Summen er kvadratet af de hele tal fra 1 til 8: 1 + 4 + 9 + … + 64 = 204. Og for at gå videre: et skakbræt indeholder 1 296 rektangler (kvadrater medregnet), for et rektangel bestemmes af valget af 2 linjer blandt de 9 linjer i gitteret og 2 kolonner blandt 9, altså 36 × 36.

Læs videre

Disse problemer bygger på præcise begreber: paritet, farvning, optælling, grafer. Vi uddyber dem med øvelser til skole og mellemskole på siden de matematiske begreber på skakbrættet. For andre meget store tal, se Sissas skakbræt. Og for dem, der elsker gåder, tilbyder Le Palais des Échecs' blog Le Palais des Échecs' logikudfordringer, som fornyes regelmæssigt.