Am primit o singură soluţie complet corectă, de la Zoltan Szabo. Cu un algoritm greedy (verificat cu un backtracking până la cazul n=5) a obtinut soluţiile:

Rezultatele algoritmului greedy

n=3   Maximul de hiper-regine;:max=4

O pozitie posibilă (data într-un sistem de coordinate în spaţiu):
(1 1 1), (1 2 3), (2 3 1), (3 1 2)

n=4   Maximul de hiper-regine: max=7
(1 1 1), (1 2 3), (1 4 2), (2 4 4), (3 1 2), (4 3 1), (4 4 3).

n=5    Maximul de hiper-regine: max=13
(1 1 1), (1 2 3), (1 3 5), (1 4 2), (1 5 4), (2 1 5), (3 1 2), (3 5 1), (4 2 5),  (4 3 1), (5 1 3), (5 4 4), (5 5 2)

n=6    Maximul de hiper-regine: max=18
(1 1 2), (1 2 4), (1 3 6), (1 4 3), (2 1 6), (2 3 1), (2 5 5), (2 6 2), (3 3 5), (4 2 2), (4 5 6), (4 6 1), (5 1 4), (5 2 6), (5 4 2), (5 6 3), (6 2 1), (6 4 5)

n=7    Maximul de hiper-regine: max=25
(1 1 2), (1 2 4), (1 3 6), (1 4 3), (1 7 5), (2 1 6), (2 3 1), (2 5 5), (2 6 2), (3 3 5), (3 4 7), (3 7 6), (4 1 7), (4 2 2), (4 6 1), (4 7 4), (5 1 4), (5 4 2), (5 6 6), (6 2 1), (6 3 4), (7 1 3), (7 2 6), (7 5 1),

(7 6 5)

n=8    Maximul de hiper-regine: max=33
(1 1 2), (1 2 4), (1 3 6), (1 4 3), (1 7 5), (2 1 6), (2 2 8), (2 3 1), (2 5 7), (2 6 2), (2 8 3), (3 3 5), (3 6 4), (3 7 6), (3 8 1), (4 1 7), (4 2 2), (4 5 6), (4 6 8), (5 1 4), (5 3 8), (5 7 3), (5 8 5), (6 1 8),

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

n=9    Maximul de hiper-regine: max=42
(1 1 3), (1 2 5), (1 3 7), (1 4 9), (1 5 4), (1 8 6), (2 1 7), (2 2 9), (2 3 1), (2 5 2), (2 6 6), (2 7 3), (2 9 4), (3 2 4), (3 4 8), (3 7 1), (3 8 7), (3 9 2), (4 1 8), (4 2 6), (4 6 5), (4 9 9), (5 2 3), (5 3 8),

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

n=10    Maximul de hiper-regine: max=58
(1 1 1), (1 2 3), (1 3 5), (1 4 2), (1 5 4), (1 6 9), (1 10 6), (2 1 5), (2 2 7), (2 3 9), (2 5 6), (2 6 1), (2 7 3), (2 8 8), (2 10 4), (3 1 2), (3 5 8), (3 6 10), (3 7 5), (3 8 1), (3 9 6), (3 10 9), (4 1 6),

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

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

n=11    Maximul de hiper-regine: max=67
(1 1 3), (1 2 5), (1 3 7), (1 4 9), (1 5 4), (1 8 6), (1 11 8), (2 1 7), (2 2 9), (2 3 1), (2 5 2), (2 6 6), (2 7 3), (2 8 10), (2 9 4), (2 10 11), (2 11 5), (3 1 11), (3 2 4), (3 4 10), (3 5 8), (3 7 1), (3 8 7),
(3 9 2), (3 11 9), (4 1 8), (4 2 6), (4 6 5), (4 7 10), (4 9 9), (4 10 4), (4 11 1), (5 2 3), (5 4 11), (5 6 2), (5 8 1), (5 11 6), (6 1 5), (6 3 9), (6 6 4), (6 7 6), (7 1 10), (7 2 2), (7 3 4), (7 5 1),

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

Algoritmul greedy, pentru fiecare camp prima data va incerca sa plaseze hiper-regina in conditii valide; in caz contrar lasa campul liber.

Astfel fiecare camp este verificat o singura data la o parcurgere.

Insa luand in calcul ca prima hiper-regina nu neaparat tebuie sa fie pe prima pozitie valida (1,1,1), am repornit algoritmul incercand prima pozitie a hiper-reginei in orice camp al tablei de sah. Dintre toate solutiile am ales solutia cea mai buna.

 #include <fstream>

#include <iostream>

using namespace std;

int a[20][20][20],n,i,j,k,maxdama,vf,st[8000][3],maxsol[8000][3];

int d[26][3];

ifstream fin("dama.in");

ofstream fout("dama.out");

int valid (int x, int y, int z)

{

    int i,xx,yy,zz;

    for (i=0;i<26;++i)

    {

        xx=x;yy=y;zz=z;

        while (1<=xx and xx<=n and 1<=yy and yy<=n and 1<=zz and zz<=n and a[xx][yy][zz]==0)

        {

            xx+=d[i][0];

            yy+=d[i][1];

            zz+=d[i][2];

        }

        if (a[xx][yy][zz]==1)

            return 0;

    }

    return 1;

}

void rec(int x,int y,int z)

{   int x1,y1,z1;

    if (x==n+1)

    {

        if (vf>=maxdama)

        {

            maxdama=vf;

            for (int i=1;i<=vf;++i)

            {

                maxsol[i][0]=st[i][0];

                maxsol[i][1]=st[i][1];

                maxsol[i][2]=st[i][2];

            }

        }

    }

    else

    {

        x1=x;

        y1=y;

        z1=z;

        z++;

        if(z>n)

        {

            y++;

            z=1;

            if(y>n)

            {

    &nbs