@** R\'esolution du probl\`eme des pentominos par force brute.

L'objet de ce programme est de placer les 12 pentominos dans un boite
donn\'ee de taille $a \times b \times c$.

@c

#include <sys/time.h>
#include <sys/resource.h>
#include <stdio.h>

int Backtracks, Solution;
@<Variables globales@>		@/
@<Fonctions@>


@ Mesures de temps.



@<Fonc...@>=
struct rusage       t1, t2;

long cputime()
{
    getrusage(RUSAGE_SELF, &t2);
    return (long) 1000*(t2.ru_utime.tv_sec - t1.ru_utime.tv_sec)
      + (t2.ru_utime.tv_usec - t1.ru_utime.tv_usec)/1000;
}

void initcputime()
{
    getrusage(RUSAGE_SELF, &t1);
}


@ Les pentominos.

Les pentominos sont des pi\`eces connexes form\'ees de cubes
assembl\'ees dans le plan, \`a une sym\'etrie pr\`es, il en existe 12
diff\'erentes, not\'ees $F, I, L, P, N, T, U, V, W, X, Y$ et $Z$ en
raison de leur forme.

Le tableau |int Pentomino[12][5]| est initialis\'e avec la forme de
chacun des 12 pentominos~: |Pentomino[i][j]| est un entier
repr\'esantant la position du j\`eme cube du i\`eme pentomino dans un
de ses placements, le chiffre des unit\'es repr\'esente la
coordonn\'ee sur l'axe des $x$, celui des dizaines la coordonn\'ee sur
l'axe des $y$.

La chaine |char Lettre[]| contient chacun des caract\`eres \`a
afficher suivant le placement que l'on aura trouv\'e.

@<Vari...@>=
int Pentomino[12][5] = {			@/
	{ 1, 10, 11, 12, 22},	/* Le $F$ */	@/
	{ 0,  1,  2,  3,  4},	/* Le $I$ */	@/
	{ 0,  1,  2,  3, 13},	/* Le $L$ */	@/
	{ 0,  1,  2, 11, 12},	/* Le $P$ */	@/
	{ 0,  1,  2, 12, 13},	/* Le $N$ */	@/
	{ 2, 10, 11, 12, 22},	/* Le $T$ */	@/
	{ 0,  1, 10, 20, 21},	/* Le $U$ */	@/
	{ 0,  1,  2, 10, 20},	/* Le $V$ */	@/
	{ 1,  2, 10, 11, 20},	/* Le $W$ */	@/
	{ 1, 10, 11, 12, 21},	/* Le $X$ */	@/
	{ 0,  1,  2,  3, 12},	/* Le $Y$ */	@/
	{ 0,  1, 11, 21, 22}	/* Le $Z$ */	@/
};

char Lettre[] = "# FILPNTUVWXYZ";

@ Le volume.

La taille du volume o\`u l'on placera les pentominos sera un pav\'e de
dimensions $a \times b \times c$.  Ce volume sera mis en bijection
avec le tableau d'entiers |int Volume[1000]| (pourquoi une taille de
$1000$ ? Pour ne pas se casser le choux \`a essayer de calculer la
taille maxi qui devrait \^etre inf\'erieure \`a 600 avec du pot).

@<Vari...@>=
int	Volume[1000];
int	a, b, c;


@ Les orientations.

La forme des pentominos a \'et\'e cod\'ee plus haut, 
manque de bol, on peut les tourner dans tous les sens possibles 
et inimaginables~: en trois dimension, il existe 24 orientations
possibles pour un seul pentomino, soit 288 pour les 12.
Toutes ces orientation seront stock\'ees dans le tableau
|int Orientation[288][6]|.

@<Vari...@>=
int
Orientation[288][6];

int
IndexO[15];


@ L'ordre de placement des pentominos.

Les pentominos seront plac\'es de fa\c con b\^ete et m\'echante~:
on place le 1er le plus en bas \`a gauche possible, le second
le plus en bas \`a gauche possible... Puis on backtraque et change
de pentomino d\`es qu'il y a impossibilit\'e.

Le tableau |int Ordre[12]| contiendra l'ordre de placement des pentominos.

@<Vari...@>=
int
Ordre[14];


@ Orientations initiales des pentominos.

Il faudrait \^etre compl\`etement chtarb\'e pour pr\'ecoder \`a la main
les 24 orientations de chacun des 12 pentominos,
laissons l'ordinateur faire le boulot \`a notre place
et allons prendre un caf\'e.

@<Orie...@>=
{
    for (i = 0; i < 12; i++) {

	for (j = 0; j < 24; j++)
	    Orientation[i * 24 + j][0] = i + 1;

	for (j = 0; j < 5; j++) {

	    u = Pentomino[i][j] % 10;
	    v = Pentomino[i][j] / 10;

	    Orientation[i * 24][j + 1] = u + (a + 1) * v;
	    Orientation[i * 24 + 1][j + 1] = v + (a + 1) * u;
	    Orientation[i * 24 + 2][j + 1] = u + 2 * (a + 1) * b * v;
	    Orientation[i * 24 + 3][j + 1] = v + 2 * (a + 1) * b * u;
	    Orientation[i * 24 + 4][j + 1] = (a + 1) * v + 2 * (a + 1) * b * u;
	    Orientation[i * 24 + 5][j + 1] = (a + 1) * u + 2 * (a + 1) * b * v;

	    if (i != 0) {
/* Elimination de sym\'etries de solution avec le F en 2 dimensions */
	    	Orientation[i * 24 + 6][j + 1] = u - (a + 1) * v;
	    	Orientation[i * 24 + 7][j + 1] = -u + (a + 1) * v;
	    	Orientation[i * 24 + 8][j + 1] = -u - (a + 1) * v;
	
		Orientation[i * 24 + 9][j + 1] = v - (a + 1) * u;
		Orientation[i * 24 + 10][j + 1] = -v + (a + 1) * u;
		Orientation[i * 24 + 11][j + 1] = -v - (a + 1) * u;
	
		Orientation[i * 24 + 12][j + 1] = u - 2 * (a + 1) * b * v;
		Orientation[i * 24 + 13][j + 1] = -u + 2 * (a + 1) * b * v;
		Orientation[i * 24 + 14][j + 1] = -u - 2 * (a + 1) * b * v;
	
		Orientation[i * 24 + 15][j + 1] = v - 2 * (a + 1) * b * u;
		Orientation[i * 24 + 16][j + 1] = -v + 2 * (a + 1) * b * u;
		Orientation[i * 24 + 17][j + 1] = -v - 2 * (a + 1) * b * u;

	    	Orientation[i * 24 + 18][j + 1] = (a + 1) * u - 2 * (a + 1) * b * v;
	    	Orientation[i * 24 + 19][j + 1] = -(a + 1) * u + 2 * (a + 1) * b * v;
	    	Orientation[i * 24 + 20][j + 1] = -(a + 1) * u - 2 * (a + 1) * b * v;

	    	Orientation[i * 24 + 21][j + 1] = (a + 1) * v - 2 * (a + 1) * b * u;
	    	Orientation[i * 24 + 22][j + 1] = -(a + 1) * v + 2 * (a + 1) * b * u;
	    	Orientation[i * 24 + 23][j + 1] = -(a + 1) * v - 2 * (a + 1) * b * u;
	    }
	    else {
		for (k = 6; k < 24; k++)
		    Orientation[i * 24 + k][j + 1] = u + (a + 1) * v;
	    }
	}
    }
}


@ Ajustement initial des pentominos.

On va un p'tit peu modifier ces orientations pour qu'elles soient
pr\'esentables en calant les cubes sur le 0 et en les triant
par ordre croissant.

@<Ajus...@>=
{
    for (i = 0; i < 288; i++) {
	u = 32000;
	for (j = 1; j < 6; j++)
	    if (Orientation[i][j] < u)
		u = Orientation[i][j];
	for (j = 1; j < 6; j++)
	    Orientation[i][j] -= u;
	for (j = 1; j < 6; j++)
	    for (k = j + 1; k < 6; k++)
		if (Orientation[i][k] < Orientation[i][j]) {
		    u = Orientation[i][j];
		    Orientation[i][j] = Orientation[i][k];
		    Orientation[i][k] = u;
		}
    }
}


@ Elimination des pentominos sym\'etriques.

Parmis les 12 pentominos, y'a des petits malins qui
occupent le m\^eme espace pour plusieurs orientation
(on dit qu'il sont invariants pour une isom\'etrie donn\'ee).
Virons les doublons !

@<Elim...@>=
{
    for (i = 0; i < 288; i++)
	if (Orientation[i][0] != -1)
	    for (k = i + 1; k < 288; k++) {
		u = -1;
		for (j = 0; j < 6 && u; j++)
		    if (Orientation[i][j] != Orientation[k][j])
			u = 0;
		if (u)
		    Orientation[k][0] = -1;
	    }
    k = 0;
    for (i = 0; i < 288; i++)
	if (Orientation[i][0] != -1) {
	    for (j = 0; j < 6; j++)
		Orientation[k][j] = Orientation[i][j];
	    k++;
	}
    Orientation[k][0] = Orientation[k][1] = -1;
}


@ Pr\'eparation du volume.

Il n'y a pas de mots simples pour d\'ecrire cette portion de code,
ex\'ecutez la \`a la main et vous verrez bien.

@<Pr\'e...@>=
{
    u = 0;
    for (k = 0; k < c; k++) {
	for (j = 0; j < b; j++) {
	    for (i = 0; i < a; i++)
		Volume[u++] = 0;
	    Volume[u++] = -1;
	}
	for (j = 0; j < b; j++) {
	    for (i = 0; i <= a; i++)
		Volume[u++] = -1;
	}
    }
    while (u < 1000)
	Volume[u++] = -1;
    Volume[999] = 0;
}


@ Placement des pentominos.

Ceci est une super fonction r\'ecursive.
A chaque appel, on place un nouveau pentomino sur le volume.
Si les 12 pentominos sont d\'ej\`a plac\'es, on les affiche,
sinon on essaie d'en placer un autre.

@<Fonc...@>=

static void affsol() {
	int i, j, k;

	Solution++;
	printf("Solution no %d en %d backtracks, %ld msecs",
	       Solution, Backtracks, cputime());
	if (cputime() / 1000 != 0)
	    printf(" (%f solutions/sec)", 1000.0 * Solution / cputime());
	printf(".\n");

	for (i = 0; i < a; i++) {
	    for (j = 0; j < b; j++) {
		for (k = 0; k < i; k++)
		    printf("  ");
		for (k = 0; k < 2 * c; k += 2)
		    printf("%c",
	Lettre[Volume[i + j * (a + 1) + k * (a + 1) * b] + 1]);
	    printf("\n");
	    }
	    printf("\n");
	}
	Backtracks++;
}


static void
pentominos(int *vol)
{
    static int  i = 0;
    register int         j;
    int		k;
    register int		*ptr;
    int im;

    while (*vol)
	vol++;

   im = i++;
    k = Ordre[im];
    for (j = im; j < 12; ) {
	for (ptr = Orientation[IndexO[k]]; *ptr == k; ptr+= 6)
		    if (!vol[ptr[2]] &&
		        !vol[ptr[3]] &&
		        !vol[ptr[4]] &&
			!vol[ptr[5]]) {
			    vol[ptr[1]] = k;
			    vol[ptr[2]] = k;
			    vol[ptr[3]] = k;
			    vol[ptr[4]] = k;
			    vol[ptr[5]] = k;

				if (i != 12)
					pentominos(vol+1);
				else
					affsol();

			    vol[ptr[1]] = 0;
			    vol[ptr[2]] = 0;
			    vol[ptr[3]] = 0;
			    vol[ptr[4]] = 0;
			    vol[ptr[5]] = 0;
		     }
	k = Ordre[++j];
	Ordre[j] = Ordre[im];
	Ordre[im] = k;
    }
    ptr = Ordre + im;
    switch(12-im) {
	case 12: *(ptr++) = *(ptr+1);
	case 11: *(ptr++) = *(ptr+1);
	case 10: *(ptr++) = *(ptr+1);
	case 9: *(ptr++) = *(ptr+1);
	case 8: *(ptr++) = *(ptr+1);
	case 7: *(ptr++) = *(ptr+1);
	case 6: *(ptr++) = *(ptr+1);
	case 5: *(ptr++) = *(ptr+1);
	case 4: *(ptr++) = *(ptr+1);
	case 3: *(ptr++) = *(ptr+1);
	case 2: *(ptr++) = *(ptr+1);
	case 1: *(ptr++) = *(ptr+1);
    }
    i = im;
    Backtracks++;
}


@ Placement des pentominos.

Pas quoi fouetter un chat ici.

@<Plac...@>=
{
int l;
    for (i = 0; i < 12; i++)
	Ordre[i] = i + 1;
    Ordre[i] = 0;
    Solution = Backtracks = 0;

	for (i = 0; i < 12; i++)
		for (l = 0; Orientation[l][0] != -1; l++)
			if (Orientation[l][0] == i+1) {
				IndexO[i+1]= l;
				break;
			}
			

	initcputime();
    pentominos(Volume);
    
    if (Solution == 0)
	puts("Pas de solution");
    printf("Total : %d backtracks, %ld usecs.\n", Backtracks, cputime());
}


@ La fonction principale.

Et voici l'in\'evitable fonction |int main(void)| utilis\'ee
par tout programme $C$.

@<Fonc...@>=
int
main(void)
{
	int	i, j, k;
	int	u, v;
	
	puts("Les pentominos - algorithme de force brute");
	
	printf("Longueur du volume ? ");
	scanf("%d", &a);
	printf("Largeur du volume ? ");
	scanf("%d", &b);
	if (a > b) {
		i = a; a = b; b = i;
	}
	if (a*b < 60) {
		printf("Hauteur du volume ? ");
		scanf("%d", &c);
	}
	else c = 1;
	if (b > c) {
		i = b; b = c; c = i;
	}
	if (a > b) {
		i = a; a = b; b = i;
	}

	@<Oriente les pentominos@>;
	@<Ajuste les pentominos@>;
	@<Elimine les pentominos sym\'etriques@>;

	@<Pr\'epare le volume@>;

	@<Place les pentominos@>;
	
	return 0;
}