/*
	Patrice Torchet
	Le virus informatique
	remplissage d'un carré
	(puissance 4 inversé dans un carré de 9 par 9)

	Borland C++ 3.1
	optimiser le code pour la vitesse (quoi qu'il ne soit pas trés efficace)

	Bug BC 3.1 : mettre l'optimisation 'Register Variable' à 'None' car
	ce con utilise DX et ne voit pas que la division entière baise le registre !
	(les gotoxy et cprintf sont douteux aussi)
*/

#include "conio.h"
#include "dos.h"
#include "stdio.h"

	//************************************************************
	//	pour rechercher toutes les dispositions optimum
#define	CHERCHER_MAX

	//************************************************************
	//	constantes
#define NB_COL		9
#define	NB_LIGNE	9
	//	pas à utiliser pour le calcul du tableau d'ajustement
#define AJ_PAS		1
	//	nombre de cases utiles 9*9
#define NB_CASES	(NB_COL*NB_LIGNE)
/*	pour obtenir un tableau avec les trois premières lignes bidon
	afin de tester les alignements verticaux tout le temps.
	ça coute moins cher de tester les 3 premières lignes pour rien
	plutot que de vérifier tout le temps qu'on a dépassé la troisième ligne.
*/
#define NB_DECAL	(3*NB_COL)

	//************************************************************
	//	Variables Globales
char tab[NB_CASES+NB_DECAL];
char tab_aj[NB_CASES+NB_DECAL];
int score, score_max;

	//************************************************************
	//	Affichage de la solution courante
void afficher_tab (int col)
	//	Afficher le tableau
	{
	int aff;

	for (aff=0; aff<NB_CASES; aff++)
		{
		if (aff%NB_COL==0)
			gotoxy( col+1, aff/NB_COL+1);
		cprintf(" %d", tab[aff+NB_DECAL]);
		}
	gotoxy( col+1,19); cprintf("%d", score);
	}

	//************************************************************
void optimiser (void)
	{
	int ptr, col, espoir;

	// Initialisation tableau et variables
	for(ptr=0; ptr<NB_CASES+NB_DECAL; ptr++) { tab[ptr]=0; }

#ifdef CHERCHER_MAX
	espoir= 1;			// pour aller directement au score maximum
#else
	espoir= NB_CASES;	// aprés le premier remplissage, contient
						// l'amélioration potentielle du score
#endif

	ptr= NB_DECAL;	// pointeur dans le tableau
	col= 0;			// indique la colonne courante dans le tableau

	score= 0;		// score courant pendant l'exploration
	score_max= 0;	// meilleur score obtenu

	// Exploration Descente
	desc_deb:
	//	ajuster le score potentiel en début de ligne
	espoir+=tab_aj[ptr];

#ifndef CHERCHER_MAX
	if(col==0)
		{
#if (NB_COL==9)
		if (ptr <= NB_DECAL+27)
			{
			//	éliminer les calculs symétriques sur la première ligne
			//	Ca élimine 240 cas sur les 512 possibilités
			if (     tab[NB_DECAL+ 0]!=tab[NB_DECAL+ 8]) { if (tab[NB_DECAL+ 0]<tab[NB_DECAL+ 8]) goto 
desc_fin; }
			else if (tab[NB_DECAL+ 1]!=tab[NB_DECAL+ 7]) { if (tab[NB_DECAL+ 1]<tab[NB_DECAL+ 7]) goto 
desc_fin; }
			else if (tab[NB_DECAL+ 2]!=tab[NB_DECAL+ 6]) { if (tab[NB_DECAL+ 2]<tab[NB_DECAL+ 6]) goto 
desc_fin; }
			else if (tab[NB_DECAL+ 3]!=tab[NB_DECAL+ 5]) { if (tab[NB_DECAL+ 3]<tab[NB_DECAL+ 5]) goto 
desc_fin; }
			else if (ptr >= NB_DECAL+18)
				{
				// éliminer les calculs symétriques	sur la seconde ligne
				// si la première est déjà symétrique
				if (     tab[NB_DECAL+ 9]!=tab[NB_DECAL+17]) { if (tab[NB_DECAL+ 9]<tab[NB_DECAL+17]) goto 
desc_fin; }
				else if (tab[NB_DECAL+10]!=tab[NB_DECAL+16]) { if (tab[NB_DECAL+10]<tab[NB_DECAL+16]) goto 
desc_fin; }
				else if (tab[NB_DECAL+11]!=tab[NB_DECAL+15]) { if (tab[NB_DECAL+11]<tab[NB_DECAL+15]) goto 
desc_fin; }
				else if (tab[NB_DECAL+12]!=tab[NB_DECAL+14]) { if (tab[NB_DECAL+12]<tab[NB_DECAL+14]) goto 
desc_fin; }
				else if (ptr==NB_DECAL+27)
					{
					//	éliminer les calculs symétriques	sur la troisième ligne
					// si la première et la seconde sont déjà symétriques
					if (     tab[NB_DECAL+18]!=tab[NB_DECAL+26]) { if 
(tab[NB_DECAL+18]<tab[NB_DECAL+26]) goto desc_fin; }
					else if (tab[NB_DECAL+19]!=tab[NB_DECAL+25]) { if 
(tab[NB_DECAL+19]<tab[NB_DECAL+25]) goto desc_fin; }
					else if (tab[NB_DECAL+20]!=tab[NB_DECAL+24]) { if 
(tab[NB_DECAL+20]<tab[NB_DECAL+24]) goto desc_fin; }
					else if (tab[NB_DECAL+21]!=tab[NB_DECAL+23]) { if 
(tab[NB_DECAL+21]<tab[NB_DECAL+23]) goto desc_fin; }
					}
				}
			}
#endif
		}
#endif

	// élimination des séries de 4
	//	verifier qu'on a dépassé la troisième ligne coute plus cher que de
	//	faire le teste d'alignement pour rien sur les trois premières lignes.
	if (((col > 2)        && tab[ptr- 1]             && tab[ptr- 2]             && tab[ptr- 3]            )  || // test 
pour ---*
		((col > 2)        && tab[ptr-(1*(NB_COL+1))] && tab[ptr-(2*(NB_COL+1))] && tab[ptr-(3*(NB_COL+1))])  || // 
test pour \\\*
		(                    tab[ptr-(1*(NB_COL+0))] && tab[ptr-(2*(NB_COL+0))] && tab[ptr-(3*(NB_COL+0))])  || // 
test pour |||*
		((col < NB_COL-3) && tab[ptr-(1*(NB_COL-1))] && tab[ptr-(2*(NB_COL-1))] && tab[ptr-(3*(NB_COL-1))]))    // 
test pour ///*
		{
		if (ptr==NB_DECAL+NB_CASES-1) goto desc_suiv;
			if (espoir > 1)
				 { espoir--; ptr++;
				 if (col==(NB_COL-1)) col=0; else col++;
				 goto desc_deb; }
		else goto desc_fin;
		}

	// pas d'alignement, armer le drapeau
	tab[ptr]=1; score++;

	//	continuer car score potentiel toujours supérieur
	if (ptr!=NB_DECAL+NB_CASES-1)
		{ ptr++; if (col==(NB_COL-1)) col=0; else col++; goto desc_deb; }

	desc_suiv:
	//	tableau complet
	if (score >= score_max)
		{
		score_max= score;
		//	Afficher le tableau
		afficher_tab (1);
		}

	//	si le dernier drapeau est armé, il sera forcément désarmé
	//	et ne pourra améliorer le score dans l'immédiat.
#ifdef CHERCHER_MAX
	if (tab[ptr]) { tab[ptr]=0; score--; }
#else
	//	caler l'espoir d'aprés le nouveau score.
	if (tab[ptr]) { tab[ptr]=0; score--; espoir=0; }
	else espoir=1;
#endif

	// Remontée
	desc_fin:
	//	tarer espoir car la remontée va générer un zéro
	espoir--;

	desc_fin_2:
	//	ajuster le score potentiel en début de ligne
	espoir-=tab_aj[ptr];

	//	si drapeau armé, désarmer puis on boucle
	if (tab[ptr-1])
		{
		tab[ptr-1]=0; score--;
		if (espoir > 0) { goto desc_deb; }
		}
	else
		espoir++;	//	il était déjà désarmé

	ptr--; if (col==0) col=(NB_COL-1); else col--;
	//	si c'est la case zéro, c'est fini, sinon drapeau précédant
	if (ptr>NB_DECAL) { goto desc_fin_2; }
	}

	//************************************************************
	// Génération de la table d'ajustement
int gen_aj (int ptr_min, int max)
	{
	int ptr, col, espoir;

	// Initialisation tableau et variables
	for(ptr= 0; ptr < NB_CASES+NB_DECAL; ptr++)
		{ tab[ptr]=0; }

	espoir= AJ_PAS;
	ptr= ptr_min;		// pointeur dans le tableau
	col= ptr%NB_COL;	// indique la colonne courante dans le tableau

	score= 0;		// score courant pendant l'exploration
	score_max= max;	// meilleur score obtenu

	// Exploration Descente
	desc_deb:

	//	ajuster le score potentiel en début de ligne
	espoir+=tab_aj[ptr];

	// élimination des séries de 4
	//	verifier qu'on a dépassé la troisième ligne coute plus cher que de
	//	faire le teste d'alignement pour rien sur les trois premières lignes.
	if (((col > 2)        && tab[ptr- 1]             && tab[ptr- 2]             && tab[ptr- 3]            )  || // test 
pour ---*
		((col > 2)        && tab[ptr-(1*(NB_COL+1))] && tab[ptr-(2*(NB_COL+1))] && tab[ptr-(3*(NB_COL+1))])  || // 
test pour \\\*
		(                    tab[ptr-(1*(NB_COL+0))] && tab[ptr-(2*(NB_COL+0))] && tab[ptr-(3*(NB_COL+0))])  || // 
test pour |||*
		((col < NB_COL-3) && tab[ptr-(1*(NB_COL-1))] && tab[ptr-(2*(NB_COL-1))] && tab[ptr-(3*(NB_COL-1))]))    // 
test pour ///*
		{
		if (ptr==NB_DECAL+NB_CASES-1) goto desc_suiv;
		if (espoir > 1)
			 { espoir--; ptr++;
			 if (col==(NB_COL-1)) col=0; else col++;
			 goto desc_deb; }
		else goto desc_fin;
		}

	// pas d'alignement, armer le drapeau
	tab[ptr]=1; score++;

	//	continuer car score potentiel toujours supérieur
	if (ptr!=NB_DECAL+NB_CASES-1)
		{
		ptr++;
		if (col==(NB_COL-1)) col=0; else col++;
		goto desc_deb;
		}

	desc_suiv:
	//	tableau complet
	if (score > score_max)
#if (AJ_PAS==1)
		{ return (score); } //	score amélioré
#else
		{ score_max= score; }
#endif
	//	caler l'espoir d'aprés le nouveau score.
	if (tab[ptr]) { tab[ptr]=0; score--; espoir=0; }
	else espoir=1;

	// Remontée
	desc_fin:
	//	tarer espoir car la remontée va générer un zéro
	espoir--;

	desc_fin_2:
	//	ajuster le score potentiel en début de ligne
	espoir-=tab_aj[ptr];

	//	si drapeau armé, désarmer puis on boucle
	if (tab[ptr-1])
		{
		tab[ptr-1]=0; score--;
		if (espoir > 0) { goto desc_deb; }
		}
	else
		espoir++;	//	il était déjà désarmé

	ptr--; if (col==0) col=(NB_COL-1); else col--;
	//	si c'est la case zéro, c'est fini, sinon drapeau précédant
	if (ptr>ptr_min) { goto desc_fin_2; }

	return (score_max);
	}

	//************************************************************
	//	c'est suposé permettre le CTRL-C pendant l'éxécution
int c_break(void)
	{
	gotoxy(1,20); cprintf("Abandon ...\n");
	return (0);
	}

//************************************************************
void	main ()
	{
	struct  time t_db, t_fn;	// pour le chronométrage
	int	ptr, last_score, new_score;

	ctrlbrk(c_break);

	//	éffacer l'écran
	clrscr();

	// top début
	gettime(&t_db);

	//	Initialisation tableau d'ajustement
	for(ptr= 0; ptr < NB_CASES+NB_DECAL; ptr++) { tab_aj[ptr]=0; }

	//	Afichage du tableau d'ajustement à vide
	for(ptr= 0; ptr < NB_CASES; ptr++)
		{
		if (ptr%NB_COL==0) gotoxy( 41, ptr/NB_COL+1);
		cprintf(" 0");
		}

	//	génération de la table d'ajustement
	last_score= 0;
	for (ptr= NB_CASES+NB_DECAL-AJ_PAS; ptr >= NB_DECAL; ptr-=AJ_PAS)
		{
		//	placer le curseur
		gotoxy( 42+(ptr%NB_COL*2), ptr/NB_COL-2 );

		//	calculer la case
		new_score= gen_aj(ptr, last_score);
		tab_aj[ptr]= AJ_PAS+ last_score- new_score;
		last_score= new_score;

		//	Afficher la valeur
		cprintf("%d", tab_aj[ptr]);
		}

	//	LE calcul du carré
	optimiser ();

	// top fin
	gettime(&t_fn);

	// calcul du temps d'éxécution
	if ( t_fn.ti_hund < t_db.ti_hund ) { t_fn.ti_hund += 100; t_db.ti_sec++; }
	t_fn.ti_hund -= t_db.ti_hund;
	if ( t_fn.ti_sec  < t_db.ti_sec  ) { t_fn.ti_sec  +=  60; t_db.ti_min++; }
	t_fn.ti_sec  -= t_db.ti_sec ;
	if ( t_fn.ti_min  < t_db.ti_min  ) { t_fn.ti_min  +=  60; t_db.ti_hour++; }
	t_fn.ti_min  -= t_db.ti_min ;
	if ( t_fn.ti_hour < t_db.ti_hour ) { t_fn.ti_hour +=  24; }
	t_fn.ti_hour -= t_db.ti_hour;

	gotoxy(1,20);
	cprintf("%2d:%02d:%02d.%02d\n", t_fn.ti_hour, t_fn.ti_min, t_fn.ti_sec, t_fn.ti_hund);
	}