Qhuszár

// Definiálok egy figurát, legyen a neve ideiglenesen Qhuszár, amely szintén L alakban léphet:
// függőlegesen 3-t és vízszintesen egyet, vagy fordítva.
// Ennek a figurának a különleges lépését "nagy lóugrásnak" neveztem el és nem az ellenkező színű
// mezőre érkezik meg az eredeti helyzetéhez viszonyítva. Tehát azonos színű mezőkön ugrálhat.
// Helyezzük el a Qhuszárt a sakktábla bal alsó a1-es sötét mezejére. A kérdés az, hogy ezzel a
// figurával és hozzárendelt lépésével bejárható-e a sakktábla összes sötét mezője (összesen
// 31 lépéssel) úgy, hogy minden mezőt csak egyszer érinthet?

#include <stdio.h>
#include <string.h>

// A tabla (...) korul "senki foldje" terulet (XXX) is van, hogy egyszerubb legyen
// a lougras, ne kelljen ellenorizni, hogy kiugrik-e a huszar a tablabol.
// Az XXX-eket eleve feltoltom majd, mintha ott mar jart volna a huszar, igy oda nem fog lepni.
//
// Az igy kibovitett sakktabla ilyen lesz: (Lentebb a tabla nevu egydimenzios tomb tarolja sorfolytonosan)
//
// X X X X X X X X X X X X
//   X X X X X X X X X X X
//   X X X X X X X X X X X
//   : . . . . . . . X X X
//   . . . . . . . . X X X
//   . . . . . . . . X X X
//   . . . . . . . . X X X
//   . . . . . . . . X X X
//   . . . . . . . . X X X
//   . . . . . . . . X X X
//   * . . . . . . . X X X:
//   X X X X X X X X X X X
//   X X X X X X X X X X X
//   X X X X X X X X X
//
#define s_x (8+3)           // egy sor ilyen szeles
#define s_y1 (3*s_x + 1)    // elso pozicio ':' elott ennyi van
#define s_y2 (3*s_x - 2)    // utolso pozicio 'X:' utan ennyi van

#define POS(x,y) (s_y1 + (x) + s_x*(y)) // bal felso = ':' = (0,0)
#define KEZD POS(0, 7)      // A1 = '*'

#define UTLEPES 32

char tabla[s_y1 + 8*s_x + s_y2];

int lep[] = {
     3 + s_x*(1),
     3 + s_x*(-1),
     1 + s_x*(3),
    -1 + s_x*(3),
    -3 + s_x*(1),
    -3 + s_x*(-1),
     1 + s_x*(-3),
    -1 + s_x*(-3)
};

bool printall = false;
int megoldasok = 0;

void kiir()
{
    printf("Solution #%d\n", ++megoldasok);
    for (int y=0; y<8; y++) {
        for (int x=0; x<8; x++) {
            int n = tabla[POS(x,y)];
            if (n)
                printf(" %02d", n);
            else
                printf(" --");
        }
        printf("\n");
    }
    printf("\n");
}

void kovlep(int pos, int xy, char n)
{
    int ujpos = pos + xy;
    if (tabla[ujpos]) {
        if (n == UTLEPES+1 && tabla[ujpos] == 1)
            kiir();
        return;             // backtrack
    }
    tabla[ujpos] = n;
    if (printall && n == UTLEPES) {
        kiir();
    } else {
        for (int i=0; i<8; i++)
            kovlep(ujpos, lep[i], n+1);
    }
    tabla[ujpos] = 0;
}

int main()
{
    memset(tabla, 0, sizeof(tabla));
    memset(tabla, -1, s_y1);
    for (int y=0; y<8; y++)
        for (int x=8; x<=10; x++)
            tabla[POS(x,y)] = -1;
    memset(tabla+POS(0,8), -1, s_y2);

    kovlep(KEZD, 0, 1);

    return 0;
}