Un problème avec combien de solutions? - Page 1

Je sais pas s'ils y en a beaucoup qui connaissent ce problème:
on dispose d'un carré 10x10 et il faut placer les chiffres de 1 à 100 dedans, sachant que le mouvements entre deux nombres consécutifs se fait soit en diagonal de 2x2 cases, soit suivant le quadrillage en se déplaçant de 4 cases.
J'ai écrit un algo en CaML et en C pour résoudre ce problème, mais en 12h il ne trouve pas de solution...
Sauriez vous écrire un meilleur algo?

Code C:

#include <stdio.h>

//Tableau des valeurs
int t[10][10];

//Mouvements possibles
int mvt[8][2];

//affiche le tableau

void init_mvt()
{
  mvt[0][0] = 2;
  mvt[0][1] = 2;

  mvt[1][0] = 2;
  mvt[1][1] = -2;

  mvt[2][0] = -2;
  mvt[2][1] = -2;

  mvt[3][0] = -2;
  mvt[3][1] = 2;

  mvt[4][0] = 3;
  mvt[4][1] = 0;

  mvt[5][0] = -3;
  mvt[5][1] = 0;

  mvt[6][0] = 0;
  mvt[6][1] = 3;

  mvt[7][0] = 0;
  mvt[7][1] = -3;
}


void aff_tab()
{
 int I,J;
 for (I=0; I<10; I++)
   {
    for (J=0; J<10; J++) printf("%2d", t[I][J]);
    printf("n")
   }
 scanf("d",&I);
}


int est_libre(int a, int b)
{
 return (a>=0 && b>=0 && a<10 && b<10 && t[a][b] == 0);
}

int get_next(int a,int b,int k)
{
  int i,x,y,res;
  res=0;
  if(k==101) return 1;
  for(i=0; i<8 && !res; i++)
  {
    x = mvt[i][0];
    y = mvt[i][1];
    if(est_libre(a+x,b+y))
      { t[a+x][b+y] = k;
        if(get_next(a+x,b+y,k+1)) {res=1;}
        else t[a+x][b+y] = 0;
      }
  }
  return res;
}


int main(int argc, char *argv[])
{
  int n,i,j;
  for(i=0; i<10; i++) for(j=0; j<10; j++) t[i][j] = 0;
  t[0][0] = 1;
  init_mvt();
  get_next(0,0,2);
   aff_tab();
  return 0;
}

et le code en CaML:

let libre = 0;;
let mvt = [2,2;-2,2;2,-2;-2,-2;0,3;0,-3;3,0;-3,0];;

let nouveau n t =
	let u = make_matrix n n 0 in
	for i = 0 to n-1 do
		for j = 0 to n-1 do
		u.(i) <- t.(i)
		done;
	done;
u;;

let est_libre n t a b = ( a >= 0 && b>= 0 && a < n && b < n && t.(a).(b) = 0 );;

let rec get_next n t a b k =
	if k = n*n+1
	then (true,t)
	else aux t k mvt
where rec aux t k = function
	|[] -> (false,t)
	|(x,y)::v ->	if est_libre n t (a+x) (b+y)
			then (
				t.(a+x).(b+y) <- k;
				let (res,tab) = get_next n t (a+x) (b+y) (k+1) in
				if res then (res,tab)
				else	(
					t.(a+x).(b+y) <- 0;
					aux t k v
					)
			      )
			else aux t k v;;

let solve_pb n = let tab0 = make_matrix n n 0 in
	tab0.(0).(0) <- 1;
	(get_next n tab0 0 0 2);;

solve_pb 10;;

Tu peux expliquer mieux le pb, pour ceux qui ne connaissent pas c'est incompréhensible.

Merci

surtout cette partie là:
"sachant que le mouvements entre deux nombres consécutifs se fait soit en diagonal de 2x2 cases, soit suivant le quadrillage en se déplaçant de 4 cases"

OK:

On a un carré de coté 10, soit 100 cases en tout.
On place le n°1 où on veut (en général à la case en haut à gauche).
On remplit ensuite le cadrillage avec les autres nombres, mais pas où on veut! La position d'un autre dépend de la position du précédent. à partir d'un nombre, soit on se déplace de 3 cases dans les directions Haut, Bas, Gauche, Droite, soit de deux cases e, diagonal, c'est à dire { 2 cases en haut, deux cases à droite; 2 cases en haut, de cases à gauche; ... }
Donc si on à le nombre 12 plcé en cases (5,6), le nombre 13 est pacé:
- soit en (8,6)
- soit en (2,6)
- soit en (5,9)
- soit en (5,3)
- soit en (7,8)
- soit en (7,4)
- soit en (3,8)
- soit en (3,4)

Bien sur, si une case est déjà occupée par un nombre, on a pas le droit de se positionner dessus.

Erf moi sur le papier quand on ma demander une solution pour un 10², j'ai d'abord trouve un solution particuliere pour le 5² qui permettait de faire 4 de 5 dans 1 de 10...

En récursif, c'est peut-être là que ça plante : tu dois tester un nombre incroyable de solutions comme ça. Essaie de limiter ce nombre en utilisant une fonction qui te calcule une probabilité de trouver un résultat positif rapidement.

J'en ai trouvé un hyper-rapide mais il échoue à la 76ème case

C'est pas évident à trouver...

je vais peut etre pas apporter grd chose, masi ce genre de "combinatoire" est typiquemetn le genre de pb où une interprétation mathématique (du genre permutations) simplifie les choses

ce que j'ai cité ne sont que des exemples, mais c'est l'esprit de ce que je viens de dire qu'il faut comprendre

(du genre pour démontrer le ptit théoreme de fermat, andrew wise a fait une démo sur des courbes archicompliquées)

alpha-bêta search ?