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