Nyolckirálynő-probléma

A Wikipédiából, a szabad enciklopédiából

A nyolckirálynő-probléma egy sakkfeladvány, lényege a következő: hogyan illetve hányféleképpen lehet 8 királynőt úgy elhelyezni egy 8×8-as sakktáblán, hogy a sakk szabályai szerint ne üssék egymást. Ehhez a királynő/vezér lépési lehetőségeinek ismeretében az kell, hogy ne legyen két bábu azonos sorban, oszlopban vagy átlóban.

A nyolckirálynő-probléma egy példa az ennél általánosabb „n királynő problémára”, ami azt a kérdést veti fel, hányféleképpen lehet lerakni n darab királynőt egy n×n-es táblán.

Történet[szerkesztés | forrásszöveg szerkesztése]

A kérdést először Max Bezzel vetette fel 1848-ban. Az évek során sok matematikus – többek között Gauss és Georg Cantor – foglalkozott vele, és az általánosított n-királynő-problémával.

Az első megoldást Franz Nauck adta 1850-ben.

1874-ben S. Gunther determinánsok használatával adott egy eljárást, amivel lerakhatóak a bábuk. Később ezt J. W. L. Glaisher finomította.

Edsger Dijkstra 1972-ben arra használta ezt a problémát, hogy bemutassa a strukturált programozás előnyeit, erejét. Publikált egy részletes leírást a backtrack algoritmusról.

Megoldás[szerkesztés | forrásszöveg szerkesztése]

A megoldás nehezen számítható ki, mivel a bábuknak összesen \binom{64}{8}=4426165368 különböző lerakása létezik, de ebből csak 92 felel meg a nyolckirálynő-probléma szabályainak. Ez igen nagy számítási időt jelent. Az összes lehetséges lerakások száma, és ezáltal a számításhoz szükséges idő csökkenthető azáltal, hogy bevezetünk egy olyan szabályt, miszerint minden sorban (vagy oszlopban) csak egy-egy bábu állhat. Így a vizsgálandó lerakások száma csupán 8^8=16777216 (16884-szer kevesebb). Ez n=8-ra kezelhető, de megengedhetetlenül nagy például n=1 000 000-ra már nem.

Algoritmizálási szempontból a bábuk helyét érdemes tömbként kezelni: mivel minden sorban csak egyetlen bábu állhat, ezért elég a sorokat megszámozni (1-től n-ig), majd n darab számot lejegyezni aszerint, hogy az n-edik sorban hányadik helyen áll bábu.

Itt egy algoritmus, ami egy - a probléma szabályainak megfelelő - tömböt ad eredményül (n≥4 és n=1 esetekre):

  • Osszuk el n-et 12-vel. Jegyezzük le a maradékot.
  • Írjuk le egy listába 2-től n-ig a páros számokat növekvő sorrendben.
  • Ha a maradék 3 vagy 9, akkor a 2-es számot vigyük át a lista végére.
  • Írjuk a lista végére 1-től n-ig a páratlan számokat növekvő sorrendben, de ha a maradék 8, akkor páronként cseréljük fel őket (például 3, 1, 7, 5, 11, 9, …).
  • Ha a maradék 2, akkor cseréljük ki az 1-et és 3-at, valamint tegyük az 5-öt a lista végére.
  • Ha a maradék 3 vagy 9, akkor tegyük az 1-et és 3-at a lista végére (ebben a sorrendben).

Végül tegyük le a bábukat a sakktáblára: az első sorba oda, ahova a lista első száma mutatja; a második sorba oda, ahová a lista második száma mutatja…

Néhány példa:

  • 14 királynő: 2, 4, 6, 8, 10, 12, 14, 3, 1, 7, 9, 11, 13, 5
  • 15 királynő: 4, 6, 8, 10, 12, 14, 2, 5, 7, 9, 11, 13, 15, 1, 3
  • 20 királynő: 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 3, 1, 7, 5, 11, 9, 15, 13, 19, 17

A probléma megoldásainak száma (n≤26)[szerkesztés | forrásszöveg szerkesztése]

Az alábbi táblázat tartalmazza a lerakások számát. A lényegesen különböző oszlopban jegyzett értékeket úgy kaptuk, hogy az elforgatással vagy tükrözéssel egymásba vihető lerakásokat csak egyszer számoltuk meg.

n különböző lényegesen különböző
1 1 1
2 0 0
3 0 0
4 2 1
5 10 2
6 4 1
7 40 6
8 92 12
9 352 46
10 724 92
11 2680 341
12 14 200 1787
13 73 712 9233
14 365 596 45.752
15 2 279 184 285 053
16 14 772 512 1 846 955
17 95 815 104 11 977 939
18 666 090 624 83 263 591
19 4 968 057 848 621 012 754
20 39 029 188 884 4 878 666 808
21 314 666 222 712 39 333 324 973
22 2 691 008 701 644 336 376 244 042
23 24 233 937 684 440 3 029 242 658 210
24 227 514 171 973 736 n/a
25 2 207 893 435 808 352 n/a
26 22 317 699 616 364 044 n/a

A probléma megoldásai n=8 esetben[szerkesztés | forrásszöveg szerkesztése]

Mint a fenti táblázat mutatja, egy szabványos, 8×8-as táblán 92 olyan lerakási mód van, amikor a királynők nem ütik egymást. Az elforgatással nem egymásba vihetőek alább láthatóak:

Chess zhor 26.svg
Chess zver 26.svg
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 26.svg
Chess zhor 26.svg
Chess zhor 26.svg
Chess zver 26.svg
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 26.svg
Chess zhor 26.svg
Chess zhor 26.svg
Chess zver 26.svg
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 26.svg
Chess zhor 26.svg
Chess zhor 26.svg
Chess zver 26.svg
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 26.svg
Chess zhor 26.svg
Chess zhor 26.svg
Chess zver 26.svg
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 26.svg
Chess zhor 26.svg
Chess zhor 26.svg
Chess zver 26.svg
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 26.svg
Chess zhor 26.svg
Chess zhor 26.svg
Chess zver 26.svg
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 26.svg
Chess zhor 26.svg
Chess zhor 26.svg
Chess zver 26.svg
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 26.svg
Chess zhor 26.svg
Chess zhor 26.svg
Chess zver 26.svg
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 26.svg
Chess zhor 26.svg
Chess zhor 26.svg
Chess zver 26.svg
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 26.svg
Chess zhor 26.svg
Chess zhor 26.svg
Chess zver 26.svg
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 26.svg
Chess zhor 26.svg
Chess zhor 26.svg
Chess zver 26.svg
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 26.svg
Chess zhor 26.svg

Hasonló problémák[szerkesztés | forrásszöveg szerkesztése]

N-szuperkirálynő-probléma[szerkesztés | forrásszöveg szerkesztése]

Hasonló az n-királynő-problémához, csak itt úgynevezett „szuperkirálynőket” kell a táblára rakni. A szuperkirálynő léphet úgy, mint egy klasszikus sakkbeli királynő (vízszintes, függőleges, átlós), és tud ugrani, mint a huszár.

n szuperkirálynők lerakásainak száma
1 1
2 1110
3 0
4 0
5 0
6 0
7 0
8 0
9 0
10 4
11 44
12 156
13 1876
14 5180
15 32 516
16 202 900
17 1 330 622
18 8 924 976
19 64 492 432
20 495 864 256
21 3 977 841 852
22 34 092 182 276
23 306 819 842 212


Példakód[szerkesztés | forrásszöveg szerkesztése]

A következőkben látható egy egyszerű C nyelven írt, backtrackingre alapuló algoritmus.

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define cps CLOCKS_PER_SEC
 
int **ct = NULL;    //Sakktábla
int cr = 0;         //Sorok száma
int cc = 0;         //Oszlopok száma
int qn = 0;         //Lerakni kívánt vezérek száma
int q = 0;          //Vezérek számlálásához
int z = 0;          //Lehetőségek számolásához
int m = 0;          //Mód, 1: mindet kiírja, 0: csak egyet
 
 
int isHitting(int row, int col);
void prct(void);
int put(int col);
 
 
/*
Megállapítja, hogy az adott helyen a vezér ütés alatt van-e
visszatérés:
nulla: nincs ütés alatt
egy: ütés alatt
*/
int isHitting(int row, int col){
    int i = 0, j = 0;
    for(i = 0; i < cc; i++){
        if(ct[row][i] == 1){
            return 1;
            break;
        }
    }
    for(i = 0; i < cr; i++){
        if(ct[i][col] == 1){
            return 1;
            break;
 
        }
    }
 
    i = 0, j = 0;
 
    i = row;
    j = col;
 
    while(i < cr && j < cc){
        if(ct[i][j] == 1){
            return 1;
            break;
        }
        i++;
        j++;
    }
 
    i = row;
    j = col;
 
    while(i >= 0 && j >= 0){
        if(ct[i][j] == 1){
            return 1;
            break;
        }
        i--;
        j--;
    }
 
    i = row;
    j = col;
 
    while (i < cr && j >= 0){
        if(ct[i][j] == 1){
            return 1;
            break;
        }
 
        i++;
        j--;
    }
 
    i = row;
    j = col;
 
    while (j < cc && i >= 0){
        if(ct[i][j] == 1){
            return 1;
            break;
        }
 
        i--;
        j++;
    }
 
 
 
    return 0;
}
 
/*
Megpróbál lerakni egy vezért a megadott oszlopba
visszatérés:
nulla: nem sikerült
egy: sikerült
*/
 
int put(int col){
    int i = 0, d = 0;
    if(q>=qn){
        if(m == 0)
            return 1;
 
        z++;
        prct();
        printf("\n\n");
 
        return 0;
    }
    while(i < cr && col < cc){
        if (isHitting(i, col) == 0){
            ct[i][col] = 1;
            q++;
            d = put(col+1);
            if ( d == 1 )
                return 1;
            else{
                ct[i][col] = 0;
                q--;
            }
        }
        i++;
 
    }
    if (i >= cr)
        return 0;
 
    return 0;
 
 
}
 
 
/*
Kiírja a sakktáblát, "X" jelöli a vezérek helyét
*/
void prct(void){
    int i = 0, j = 0;
 
    for(i = 0; i < cc; i++){
        for(j = 0; j < cr; j++){
            if(ct[i][j])
                printf("X ");
            else
                printf("O ");
        }
        printf("\n");
    }
 
}
 
int main(void){
    int n = 0, i = 0, j = 0;
    scanf("%d %d %d",&n, &qn, &m);
 
    ct = (int**)malloc(sizeof(int*)*n);
 
    for(i = 0; i<n; i++){
        ct[i] = (int*)malloc(sizeof(int)*n);
        for(j = 0; j < n; j++){
            ct[i][j] = 0;
        }
    }
 
    cr = cc = n;
 
    clock_t c1 = clock();
    if(m == 0){
        printf("%d\n", put(0));
        prct();
    }else if(m == 1){
        put(0);
        printf("%d variation(s)\n", z);
    }
    clock_t c2 = clock();
 
 
 
    printf("Time: %f sec(s)\n",(double)(c2-c1)/cps);
 
    for(i = 0; i < n; i++)
        free(ct[i]);
    free(ct);
 
    return 0;
}

A program egy sorba bekérdezi először a négyzet alakú tábla oldalának hosszát, másodjára pedig az arra lerakni kívánt királynők számát, a harmadik bementi adat pedig a mód, ha ez a szám "0", akkor csak egyféle lerakást ír ki, ha "1", akkor pedig az összeset. Ezek után kirajzolja a táblát (táblákat). Végül pedig kiírja az ehhez szükséges időt.

Lásd még[szerkesztés | forrásszöveg szerkesztése]

Külső hivatkozások[szerkesztés | forrásszöveg szerkesztése]