Bonjour,

Pour ce petit exercice nous allons travailler le Sudoku et la méthode pour générer des grilles fonctionnelles aléatoirement.

Tout d'abord le résultat :

Les sources sont disponibles en fin d'exercice.

Tout d'abord le SUDOKU c'est quoi ? (merci Wikipedia)

Le sudoku (prononcé “soudokou” en français), est un jeu en forme de grille défini en 1979 par l’Américain Howard Garns, mais inspiré du carré latin, ainsi que du problème des 36 officiers du mathématicien suisse Leonhard Euler.

Le but du jeu est de remplir la grille avec une série de chiffres (ou de lettres ou de symboles) tous différents, qui ne se trouvent jamais plus d’une fois sur une même ligne, dans une même colonne ou dans une même sous-grille. La plupart du temps, les symboles sont des chiffres allant de 1 à 9, les sous-grilles étant alors des carrés de 3 × 3. Quelques symboles sont déjà disposés dans la grille, ce qui autorise une résolution progressive du problème complet.

La règle du jeu générique, se traduit ici simplement : chaque ligne, colonne et région ne doit contenir qu’une seule fois tous les chiffres de un à neuf. Formulé autrement, chacun de ces ensembles doit contenir tous les chiffres de un à neuf.

Une règle non écrite mais communément admise veut également qu’une bonne grille de sudoku, une grille valide, ne doit présenter qu’une et une seule solution. Ce n’est pas toujours le cas…

Les chiffres ne sont utilisés que par convention, les relations arithmétiques entre eux ne servant pas (sauf dans la variante Killer Su Doku). N’importe quel ensemble de signes distincts — lettres, formes, couleurs, symboles — peut être utilisé sans changer les règles du jeu.

L’intérêt du jeu réside dans la simplicité de ses règles, et dans la complexité de ses solutions. Les grilles publiées ont souvent un niveau de difficulté indicatif. L’éditeur peut aussi indiquer un temps de résolution probable. Quoiqu’en général les grilles contenant le plus de chiffres pré-remplis soient les plus simples, l’inverse n’est pas systématiquement vrai. La véritable difficulté du jeu réside plutôt dans la difficulté de trouver la suite exacte des chiffres à ajouter.

Ce jeu a déjà inspiré plusieurs versions électroniques qui apportent un intérêt différent à la résolution des grilles de sudoku. Sa forme en grille et son utilisation ludique le rapprochent d’autres casse-tête publiés dans les journaux, tels les mots croisés et les problèmes d’échecs. Le niveau de difficulté peut être adapté, et des grilles sont publiées dans des journaux, mais peuvent aussi être générées à la demande sur Internet.

Nous allons en rester là pour les règles de base, je vous encourage néanmoins à aller faire un tour sur la page de Wikipédia traitant du Sudoku, les règles et algorithmes de résolutions y sont détaillés, et force est de constater qu'ils sont complexes… Fort heureusement nous allons nous limiter à des systèmes simples qui demandent finalement plus de logique que de mathématiques pour résoudre les grilles, car oui, comme nous allons créer un générateur de grille il faut également s'assurer que les grilles soient valides, donc les résoudre avant de les proposer au joueur, c'est là toute la difficulté de l'exercice. Rassurez-vous si je vous propose cet exercice c'est qu'en fin de compte on peut le traiter de façon logique et simple.

Je vous recommande fortement d'avoir au moins lu les exercices suivants : DEMINEUR, PONG, SNAKE, TAQUIN
Les exercices sont courts mais de nombreuses astuces y sont proposées, je ne les expliquerai pas à chaque nouvel exercice.

Pour ce programme vous devez connaître :

Si vous souhaitez plus de précisions sur ces points, je vous encourage à parcourir le Wiki de Mediabox où vous trouverez de nombreux tutoriaux détaillés.

Voyons d'abord tout le code d'un coup.

var i:int;
var j:int;
var k:int;
var d:int;
var X:int;
var Y:int;
var c:Case;
var vide:int = 40;
var index:int = 0;
var possible:int;
var aVider:Array = [];
var grille:Array = [];
var lignes:Array = [];
var colonnes:Array = [];
var possibilites:Array;
var grilleFinale:Array;
var grilleJouable:Array;
var complet:Boolean;
var carres:Array = [];
var T:int = 40;
var C:int = 9;
var decal:int = 30;
var id:*;
var deco:Grille = new Grille();
var fond:Fond = new Fond();
var stock:Array;
 
var panneaux:Panneaux = new Panneaux();
panneaux.addEventListener(MouseEvent.MOUSE_DOWN, generateur);
panneaux.buttonMode = true;
addChild(panneaux);
 
function generateur(e:MouseEvent):void{
 
	while(numChildren>0) removeChildAt(0);
 
	grilleFinale = [];
	grilleJouable = [];
	complet = false;
 
	debut:
	while (!complet){
		for (i = 1; i <= C; i++){
			grille[i] = [];
			lignes[i] = [];
			colonnes[i] = [];
			for (j = 1; j <= C; j++) {
				grille[i][j] = 0;
				lignes[i][j] = j;
				colonnes[i][j] = j;
			}
		}
 
		for (i = 1; i <= 3; i++) {
			carres[i] = [];
			for (j = 1; j <= 3; j++){
				carres[i][j] = [];
				for (k = 1; k <= C; k++) {
					carres[i][j][k] = k;
				}
			}
		}
 
		for (i = 1; i <= C; i++) {
			for (j = 1; j <= C; j++) {
				possibilites = [];
				index = 0;
				for (k = 1; k <= C; k++) {
					if (! lignes[i][k]) continue;
					if (! colonnes[j][k]) continue;
					if (! carres[Math.ceil(i/3)][Math.ceil(j/3)][k]) continue;
					possibilites[index] = k;
					index++;
				}
 
				if (possibilites.length == 0) continue debut;
 
				possible = possibilites[Math.floor((Math.random() * possibilites.length))];
				grille[i][j] = possible;
				lignes[i][possible] = 0;
				colonnes[j][possible] = 0;
				carres[Math.ceil(i/3)][Math.ceil(j/3)][possible] = 0;
			}
		}
		complet = true;
	}
 
	for (i=1; i<=C; i++) {
		for (j=1; j<=C; j++) {
			if (grille[i][j]) grilleFinale.push(grille[i][j]);
		}
	}
 
	aVider = [];
	for (i = 0; i < C*C; i++) {
		if (i <= vide) aVider[i] = true	else aVider[i] = false; 
	}
 
	aVider = shuffle(aVider);
 
	for (i = 0; i < grilleFinale.length; i++) {
		if (aVider[i] == true) grilleJouable[i] = 0	else grilleJouable[i] = grilleFinale[i];
	}
 
	trace(grilleFinale);
	trace(grilleJouable);
	init();
}
 
function shuffle(A:Array):Array{
	for (i = A.length; i>0; i--){
		j = Math.random() * i, 
		k = A[i], 
		A[i] = A[j], 
		A[j] = k;
	}
	return A;
}
 
function init():void {
	stock = [];
	fond.x = decal;
	fond.y = decal;
	addChild(fond);
	for (i = 0; i < C*C; i++) {
		d = grilleFinale[i];
		c = new Case();
		addChild(c);
		c.chiffre.text = d.toString();
		c.num = d;
		if (grilleJouable[i] > 0) {
			stock[i] = c;
			c.x =(i%C)*T+decal;
			c.y = int(i/C)*T+decal;
		} else {
			stock[i] = "";
			c.x = 410;
			c.y = c.num*T-10;
			c.addEventListener(MouseEvent.MOUSE_DOWN, presser);
			c.addEventListener(MouseEvent.MOUSE_UP, relacher);
			c.buttonMode = true;
			c.mouseChildren = false;
		}
	}
	deco.x = decal;
	deco.y = decal;
	addChild(deco);
};
 
function presser(e:MouseEvent) {
	var p:Case = Case(e.target);
	p.startDrag();
	deco.infos.text = "";
	setChildIndex(p, numChildren-1);
	if(p.x!=410) stock[int((p.x-decal)/T)+int((p.y-decal)/T)*C] = "";
};
 
 
function relacher(e:MouseEvent) {
	stopDrag();
 
	var p:Case = Case(e.target);
	X = int((mouseX-decal)/T);
	Y = int((mouseY-decal)/T);
 
	if (p.x<decal || p.x>T*10-decal || p.y<decal || p.y>T*10-decal) {
		replace(p,"Vous êtes en dehors de la grille !", p);
		return;
	}
 
	if(stock[X+Y*C]) {
		replace(p,"Cette case est déjà occupée !", stock[X+Y*C]);
		return;
	}
 
	for (i = 0; i < C; i++) {
		// ligne
		id = stock[i+Y*C];
		if (id && id.num == p.num) {
			replace(p,"Il y a deja un " + p.num + " dans cette ligne !", id);
			return;
		}
		// colonne
		id = stock[X+i*C];
		if (id && id.num == p.num) {
			replace(p,"Il y a deja un " + p.num + " dans cette colonne !", id);
			return;
		}
	}
 
	for (var j = 0; j < 3; j++) {
		for (i = 0; i < 3; i++) {
			id = stock[3*int(X/3)+i+(3*int(Y/3)+j)*C];
			if (id && id.num == p.num){
				replace(p,"Il y a deja un " + p.num + " dans ce carre !", id);
				return;
			}
		}
	}
 
	p.x = X*T+decal;
	p.y = Y*T+decal;
	stock[X+Y*C] = p;
	setChildIndex(deco, numChildren-1);
 
	for each(var g in stock){
		if(!g) return;
	}
	deco.infos.text = "Bravo la grille est remplie, c'est gagné !";
	addChild(panneaux);
	panneaux.gotoAndStop(3);
};
 
function replace(p:Case,t:String,fx:Case):void{
	deco.infos.text = t;
	p.x = 410;
	p.y = p.num*T-10;
	fx.fond_chiffre.play();
	setChildIndex(deco, numChildren-1);
}

Comme d'habitude j'utilise la bibliothèque de Flash pour gérer les graphismes, ce qui me permet d'alléger le code et de ne conserver que ce qui est utile pour l'exercice, si vous n'utilisez pas Flash voici les modifications à faire dans le programme :

Panneaux :

• un clip qui regroupe tous les panneaux d'interface
• un panneau différent par frame

Cases :

• un clip avec un fond animé et un champ texte dynamique

Grille :

• un clip avec le tracé des différentes zones et un champ texte dynamique pour les infos

Fond :

• le fond des éléments graphiques

Avant de se lancer sur l'étude du programme je dois vous parler de la méthode, ici je vais utiliser deux techniques, la première utilise des tableaux à multiples dimensions (deux et trois) pour le tirage et les tests de la grille de chiffre, la seconde va utiliser une liste simple pour le jeu et la grille affichée. J'ai préféré conserver ces deux méthodes plutôt que celle que j'utilise habituellement (la liste) car il me semble important que vous visualisiez bien ce que je fais pour générer et tester la grille avant qu'on puisse jouer, vous êtes libres d'optimiser par la suite si vous le souhaitez.

Allez c'est parti pour l'étude pas à pas :

var i:int;
var j:int;
var k:int;
var d:int;
var X:int;
var Y:int;
var c:Case;
var vide:int = 40;
var index:int = 0;
var possible:int;
var aVider:Array = [];
var grille:Array = [];
var lignes:Array = [];
var colonnes:Array = [];
var possibilites:Array;
var grilleFinale:Array;
var grilleJouable:Array;
var complet:Boolean;
var carres:Array = [];
var T:int = 40;
var C:int = 9;
var decal:int = 30;
var id:*;
var deco:Grille = new Grille();
var fond:Fond = new Fond();
var stock:Array;
 
var panneaux:Panneaux = new Panneaux();
panneaux.addEventListener(MouseEvent.MOUSE_DOWN, generateur);
panneaux.buttonMode = true;
addChild(panneaux);

Il y a beaucoup de variables de déclarées ici, pas de panique on va commencer par les pointeurs :

i, j , k, d sont de simples variables génériques qui servent dans les boucles, elles sont réutilisées souvent.

X et Y sont des positions des cases dans la grille, on les distingues de x et y (les positions sur la scène) car elles sont en majuscule.

Le reste vous apparaîtra clairement lorsqu'on commencera à étudier le programme, notez simplement une variable un peu particulière : id.

“id” pourra représenter différents types d'objets (displayObject, int, array, …) c'est pourquoi elle est de type générique noté par une étoile.

Une fois toutes les variables, tableaux et objets créés j'ajoute le panneau d'interface qui, au clic, lance la génération de la grille.

function generateur(e:MouseEvent):void{
 
	while(numChildren>0) removeChildAt(0);
 
	grilleFinale = [];
	grilleJouable = [];
	complet = false;
 
	debut:
	while (!complet){
		for (i = 1; i <= C; i++){
			grille[i] = [];
			lignes[i] = [];
			colonnes[i] = [];
			for (j = 1; j <= C; j++) {
				grille[i][j] = 0;
				lignes[i][j] = j;
				colonnes[i][j] = j;
			}
		}
 
		for (i = 1; i <= 3; i++) {
			carres[i] = [];
			for (j = 1; j <= 3; j++){
				carres[i][j] = [];
				for (k = 1; k <= C; k++) {
					carres[i][j][k] = k;
				}
			}
		}
 
		for (i = 1; i <= C; i++) {
			for (j = 1; j <= C; j++) {
				possibilites = [];
				index = 0;
				for (k = 1; k <= C; k++) {
					if (! lignes[i][k]) continue;
					if (! colonnes[j][k]) continue;
					if (! carres[Math.ceil(i/3)][Math.ceil(j/3)][k]) continue;
					possibilites[index] = k;
					index++;
				}
 
				if (possibilites.length == 0) continue debut;
 
				possible = possibilites[Math.floor((Math.random() * possibilites.length))];
				grille[i][j] = possible;
				lignes[i][possible] = 0;
				colonnes[j][possible] = 0;
				carres[Math.ceil(i/3)][Math.ceil(j/3)][possible] = 0;
			}
		}
		complet = true;
	}
 
	for (i=1; i<=C; i++) {
		for (j=1; j<=C; j++) {
			if (grille[i][j]) grilleFinale.push(grille[i][j]);
		}
	}
 
	aVider = [];
	for (i = 0; i < C*C; i++) {
		if (i <= vide) aVider[i] = true	else aVider[i] = false; 
	}
 
	aVider = shuffle(aVider);
 
	for (i = 0; i < grilleFinale.length; i++) {
		if (aVider[i] == true) grilleJouable[i] = 0	else grilleJouable[i] = grilleFinale[i];
	}
 
	trace(grilleFinale);
	trace(grilleJouable);
	init();
}

Bien, le programme est composé de deux parties principales, le générateur et le jeu en lui même. Le code présenté ci-dessus est le générateur, son but est de créer une grille de 81 cases (9*9) composée de lignes, colonnes et carrés (3*3). Chaque ligne, colonne, carré doit contenir uniquement une série de chiffres allant de 1 à 9 et placés dans un ordre aléatoire et sans répétition, c'est seulement à cette condition que le Sudoku sera réalisable, il faut donc se débrouiller pour créer cette grille et s'assurer qu'elle fonctionne avant de permettre au joueur de jouer. Une fois la grille créée il faut également retirer des cases afin de permettre au joueur de placer des chiffres pour résoudre la grille, plus le nombre de cases retirées est important et plus le Sudoku est difficile à résoudre.

Au final nous allons donc avoir deux grilles, la grille finale et complète (grilleFinale) et la même grille à laquelle on a retiré des cases (grilleJouable). Lorsque l'on dispose de ces deux grilles on peut passer à la deuxième partie du programme, le jeu en lui même.

Voilà pour le postulat de départ, voyons à présent comment fonctionne la première partie, le générateur dont je viens de vous donner le code. Pour simplifier la création j'ai fait exprès d'utiliser des tableaux à multiples dimensions, c'est plus pratique que des listes simples que j'utilises d'habitude et qu'on utilisera d'ailleurs dans la seconde partie du code, mais qui rendraient la structure plus difficile à comprendre. On va y aller pas à pas :

while(numChildren>0) removeChildAt(0);
grilleFinale = [];
grilleJouable = [];
complet = false;

Je commence par supprimer de l'affichage tout ce qui est visible, réinitialiser les deux grilles et signaler que la grille finale n'est pas complète, pour le cas où le joueur relancerait une partie.

debut:
while (!complet){
// ...
}

Cela peut vous paraître étrange comme écriture, ce “debut:” placé en vrac comme ça en début de boucle sans déclaration préalable et avec deux points, il s'agit en fait d'un point de repère utilisé par la suite avec l'instruction “continue”, je vais détailler ça dans quelques instants, sachez simplement qu'à un moment précis je vais demander au programme de revenir à ce point de référence, cette écriture ne fonctionne qu'avec un “continue” n'essayez pas de l'utiliser autrement. Juste après le point de référence je lance une boucle “while” avec pour paramètre ”!complet”, donc “tant que la grilleFinale n'est pas complète on boucle.

for (i = 1; i <= C; i++){
	grille[i] = [];
	lignes[i] = [];
	colonnes[i] = [];
	for (j = 1; j <= C; j++) {
		grille[i][j] = 0;
		lignes[i][j] = j;
		colonnes[i][j] = j;
	}
}

Ce bloc sert à initialiser tous les tableaux qui vont nous être utiles. La “grille” temporaire que nous allons définir contient un tableau pour chaque ligne, 9 en tout, notez que pour une fois la boucle ne commence pas à 0 mais à 1, elle va donc de 1 à 9 compris. Indépendamment je crée un nouveau tableau “lignes” qui lui aussi va contenir un nouveau tableau vide par ligne, et également un autre tableau “colonnes” qui contient également un tableau par colonnes. Pour résumer nous avons trois tableaux indépendants à deux dimensions, un pour la grille, un pour les lignes et un pour les colonnes, chacun comprenant 10 index, le premier étant vide et les 9 autres contenant un tableau.

Immédiatement après je crée une seconde boucle, elle aussi allant de 1 à 9 compris, elle permet de remplir les sous tableaux de chaque tableau principal, toutes les cases de la grille sont pour le moment initialisées à 0, toutes les cases des lignes comprennent 9 chiffes allant de 1 à 9, et pareil pour les colonnes. Ce qui nous donne :

grille = [
"",
["",0,0,0,0,0,0,0,0,0],
["",0,0,0,0,0,0,0,0,0],
["",0,0,0,0,0,0,0,0,0],
["",0,0,0,0,0,0,0,0,0],
["",0,0,0,0,0,0,0,0,0],
["",0,0,0,0,0,0,0,0,0],
["",0,0,0,0,0,0,0,0,0],
["",0,0,0,0,0,0,0,0,0],
["",0,0,0,0,0,0,0,0,0]
]
 
lignes = [
"",
["",1,2,3,4,5,6,7,8,9],
["",1,2,3,4,5,6,7,8,9],
["",1,2,3,4,5,6,7,8,9],
["",1,2,3,4,5,6,7,8,9],
["",1,2,3,4,5,6,7,8,9],
["",1,2,3,4,5,6,7,8,9],
["",1,2,3,4,5,6,7,8,9],
["",1,2,3,4,5,6,7,8,9],
["",1,2,3,4,5,6,7,8,9],
["",1,2,3,4,5,6,7,8,9],
]
 
colonnes = [
"",
["",1,2,3,4,5,6,7,8,9],
["",1,2,3,4,5,6,7,8,9],
["",1,2,3,4,5,6,7,8,9],
["",1,2,3,4,5,6,7,8,9],
["",1,2,3,4,5,6,7,8,9],
["",1,2,3,4,5,6,7,8,9],
["",1,2,3,4,5,6,7,8,9],
["",1,2,3,4,5,6,7,8,9],
["",1,2,3,4,5,6,7,8,9],
["",1,2,3,4,5,6,7,8,9],
]

On sort de la première boucle et on s'attaque à présent aux carrés :

for (i = 1; i <= 3; i++) {
	carres[i] = [];
	for (j = 1; j <= 3; j++){
		carres[i][j] = [];
		for (k = 1; k <= C; k++) {
			carres[i][j][k] = k;
		}
	}
}

Cette fois on crée une première boucle allant de 1 à 3 compris. Pour chaque pas de la boucle on crée un nouveau tableau de lignes pour les carrés, puis on refait tout de suite une boucle de 1 à 3 compris pour créer les colonnes, et enfin une troisième boucle de 1 à 9 compris pour remplir chaque case, ce qui nous donne :

carres = [
"",
[["",1,2,3,4,5,6,7,8,9],[ "",1,2,3,4,5,6,7,8,9],[ "",1,2,3,4,5,6,7,8,9]],
[["",1,2,3,4,5,6,7,8,9],[ "",1,2,3,4,5,6,7,8,9],[ "",1,2,3,4,5,6,7,8,9]],
[["",1,2,3,4,5,6,7,8,9],[ "",1,2,3,4,5,6,7,8,9],[ "",1,2,3,4,5,6,7,8,9]]
]

Vous saisissez pourquoi cette fois je préfère vous expliquer ça avec des tableaux à multiples dimensions plutôt qu'avec des listes simples ?

Bien nos tableaux de références sont remplis, reste à présent à effectuer le tirage de la grille finale et la mélanger correctement :

for (i = 1; i <= C; i++) {
	for (j = 1; j <= C; j++) {
		possibilites = [];
		index = 0;
		for (k = 1; k <= C; k++) {
			if (! lignes[i][k]) continue;
			if (! colonnes[j][k]) continue;
			if (! carres[Math.ceil(i/3)][Math.ceil(j/3)][k]) continue;
			possibilites[index] = k;
			index++;
		}
 
		if (possibilites.length == 0) continue debut;
		possible = possibilites[Math.floor((Math.random() * possibilites.length))];
		grille[i][j] = possible;
		lignes[i][possible] = 0;
		colonnes[j][possible] = 0;
		carres[Math.ceil(i/3)][Math.ceil(j/3)][possible] = 0;
	}
}

Nous avons deux boucles imbriquées allant chacune de 1 à 9 compris, elles vont nous permettre de retrouver nos lignes et nos colonnes, donc nos 81 cases. Je commence par vider le tableau des possibilités, il représente les solutions de mélange possibles à tester, et je met l'index de référence à 0.

Comme nous l'avons vu plus haut chaque case de notre grille temporaire comporte 9 chiffres (et un index vide au départ). Je vais donc faire une boucle sur chaque index qui m'intéresse dans un case, donc de 1 à 9 compris.

Si je tombe sur un 0 ou du vide ou rien (vide n'est pas forcément rien), je signale au programme d'ignorer le reste des instructions de la boucle et je repart au prochain index (instruction “continue” utilisée sans label), et ce pour les cases des lignes, des colonnes et des carrés. Si je tombe sur un chiffre qui m'intéresse alors je l'ajoute dans le tableau des possibilités et j'incrémente l'index. Si pour le moment nous ignorons le reste du code notre tableau de possibilités se remplis de la manière suivante à chaque itération des deux premières boucles :

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

En sortie de boucle nous avons le code suivant :

if (possibilites.length == 0) continue debut;

Ok nous revoici avec notre fameux point de référence, en gros si le tableau des possibilités est vide on sort de toutes les boucles en cours, y compris le “while” et on reprend au point de référence, c'est à dire juste avant le “while”. Donc si le tableau des possibilités est vide c'est que la grille n'est pas jouable et qu'il faut tout recommencer, c'est à ça que sert le point de référence utilisé avec une instruction “continue”, il permet d'ignorer tout le reste de toutes les boucles en cours et non plus simplement celle en cours et de recommencer depuis ce point.

Tout ceci est bien joli mais pour le moment notre tableau des possibilités est bien rempli à chaque itération de mes boucles, donc ça ne sert pas à grand chose, de plus pour le moment on a rien mélangé ou trié, donc on ne vois pas bien où tout cela nous mène, pas de panique c'est justement la suite du code qui va se charger de tout ça. Nous sommes d'accord que pour le moment aucune instruction “continue” ne s'est déclenchée, donc le reste du code est lu, et que trouve t'on dans ce code ?

possible = possibilites[Math.floor((Math.random() * possibilites.length))];
grille[i][j] = possible;
lignes[i][possible] = 0;
colonnes[j][possible] = 0;
carres[Math.ceil(i/3)][Math.ceil(j/3)][possible] = 0;

“possible” qu'il ne faut pas confondre avec “possibilites” est une simple variable qui va stocker un chiffre possible pour une case. La première chose à faire est donc d'enregistrer ce chiffre, et pour cela on va le tirer aléatoirement dans le tableau des possibilités qui va de 1 à 9 compris. “possible” est donc égal à un chiffre situé entre 1 et 9 compris. On la l'enregistrer tout de suite dans une case de la grille temporaire,si on suit l'ordre des boucles ce sera donc la première case de la grille qui va enregistrer le premier chiffre. Immédiatement après on va vider la case correspondante à ce chiffre dans le tableau des lignes, dans le tableau des colonnes et dans le tableau des carrés, ha ……. revenons quelques secondes sur les boucles qui nous avons vues juste au dessus et leurs instructions “continue”. A présent nous allons avoir des cases dont le chiffre est zéro, ce qui va déclencher les instructions “continue” et nous empêcher de retirer un chiffre pour cette case qui est déjà prise et c'est là que la magie opère puisqu'il ne nous est pas possible pour une même ligne, colonne et carré de tirer deux fois le même chiffre, nous remplissons ainsi notre grille temporaire de manière aléatoire sans jamais répéter le même chiffre dans chaque ligne, colonne, carré.

J'avoue, c'est un peu tordu et on pourrait faire plus court comme algorithme, mais il a le mérite d'être assez abordable et compréhensible, si vous vous sentez perdu isolez cette partie du reste du programme et placez des trace un peu partout, vous verrez alors ce qu'il se passe pas à pas.

Si tout s'est bien passé nous sortons des différentes boucles et on tombe sur :

complet = true;

Notre grille est bien complète et on peut à présent travailler avec, on sort donc de la boucle “while” et s'occupe de notre grille temporaire :

for (i=1; i<=C; i++) {
	for (j=1; j<=C; j++) {
		if (grille[i][j]) grilleFinale.push(grille[i][j]);
	}
}

Rien de bien compliqué, le but ici est de remplir la grille finale qui est une simple liste, avec les chiffres trouvés pour chaque case de la grille temporaire, je crée donc deux boucles pour parcourir le tableau à deux dimensions, et pour chaque case dans l'ordre je remplis la grille finale, j'obtiens au final une simple liste de chiffres, un pour chaque case de ma grille.

Vous vous demandez peut-être pourquoi convertir notre grille temporaire à deux dimensions en une liste, tout simplement parce que travailler avec une liste est plus rapide et plus simple et que je n'ai utilisé les tableaux à multiples dimensions que pour vous expliquer en détail le générateur, maintenant que cette partie est réglée on va revenir à nos bases c'est à dire travailler des grilles avec des listes, comme je le fais depuis le début des exercices. Si vous préférez vous pouvez continuer avec la grille temporaire mais vous allez devoir faire de nombreuses boucles pour rien.

aVider = [];
for (i = 0; i < C*C; i++) {
	if (i <= vide) aVider[i] = true else aVider[i] = false; 
}

Il nous reste encore un peu de travail pour commencer à jouer, on va devoir notamment supprimer quelques cases de la grille finale pour laisser la possibilité au joueur de les remplir et donc de jouer.

Pour faire ça je vais utiliser un nouveau tableau temporaire “aVider” qui va réunir toutes les cases à vider et une variable “vide”, rappelez-vous que j'ai 81 cases dans ma liste et je veux en retirer 40, “vide” est donc égal à 40. Je crée une boucle de 81 itérations et je remplis les 40 premières entrées avec “true” et les 41 suivantes avec “false”, j'obtient un tableau “aVider” composé de 40 index à “true” et 41 à “false”.

function shuffle(A:Array):Array{
	for (i = A.length; i>0; i--){
		j = Math.random() * i, 
		k = A[i], 
		A[i] = A[j], 
		A[j] = k;
	}
	return A;
}

C'est très simple, pour mélanger un tableau on boucle sur tous ses index, on en dire un aléatoirement, on enregistre sa référence et on l'interverti avec l'index de la boucle en cours. Au final on obtient un tableau mélangé aléatoirement, nos 40 “true” sont donc à présent répartis aléatoirement dans les 81 index du tableau.

Revenons à notre code principal car nous n'avons pas encore fini.

for (i = 0; i < grilleFinale.length; i++) {
	if (aVider[i] == true) grilleJouable[i] = 0	else grilleJouable[i] = grilleFinale[i];
}

Je souhaite conserver ma grille finale au cas ou j'en aurait besoin par la suite, je vais donc créer une nouvelle grille qui elle sera jouable, pour la remplir je vais prendre pour référence ma liste “aVider”, pour chaque index quand je tombe sur “true” je met un 0, donc une case vide et quand je tombe sur “false” je met le chiffre correspondant de ma grille finale, et le tour est joué, j'ai à présent une grille jouable composée de 81 index dont 40 sont vides.

trace(grilleFinale);
trace(grilleJouable);
init();

Afin de m'assurer que les deux grilles correspondent bien je les traces, puis si tout va bien j'initialise le jeu et le joueur peut commencer à jouer.

Faites une pause, respirez, et on attaque la seconde partie, le jeu proprement dit.

function init():void {
	stock = [];
	fond.x = decal;
	fond.y = decal;
	addChild(fond);
	for (i = 0; i < C*C; i++) {
		d = grilleFinale[i];
		c = new Case();
		addChild(c);
		c.chiffre.text = d.toString();
		c.num = d;
		if (grilleJouable[i] > 0) {
			stock[i] = c;
			c.x =(i%C)*T+decal;
			c.y = int(i/C)*T+decal;
		} else {
			stock[i] = "";
			c.x = 410;
			c.y = c.num*T-10;
			c.addEventListener(MouseEvent.MOUSE_DOWN, presser);
			c.addEventListener(MouseEvent.MOUSE_UP, relacher);
			c.buttonMode = true;
			c.mouseChildren = false;
		}
	}
	deco.x = decal;
	deco.y = decal;
	addChild(deco);
};

A l'initialisation du jeu on commence par vider le stock (notez qu'on aurait pu le faire à l'initialisation du générateur, mais comme cela concerne surtout le jeu autant le mettre ici cela revient au même), je place le fond du jeu, ça c'est juste de la déco, mais notez la variable “decal” utilisée, elle va servir un peu partout comme référence pour placer les éléments et faire les calculs, toute notre grille n'est pas affichée en haut à gauche de la scène mais un peu décalée pour se retrouver au centre de l'écran, il faut donc le prendre en compte.

On attaque une première boucle sur 81 index, elle sert à créer les différentes pièces utiles, “d” est le chiffre correspondant à l'index de la boucle dans la grille finale (c'est pour ça que je l'ai conservée), “c” est la nouvelle pièce à créer, il y a 81 pièces à créer indépendamment de leur position. Dans chaque pièce on renseigne le champ texte avec le chiffre correspondant et on enregistre également ce chiffre dans une petite variable “num”.

Reste à présent à savoir où placer chaque pièce, certaines sont dans la grille, mais celles correspondant à des cases vides se trouvent en dehors dans un endroit où le joueur peut les piocher pour les placer sur la grille. On regarde donc si la pièce se trouve dans la grille jouable, si c'est le cas on la place dans la grille et on l'ajoute au stock. Si ce n'est pas le cas, alors on va placer la pièce sur le côté de la grille à une position x qui est fixe et à une position y qui correspond à la valeur du chiffre qu'elle contient, on obtient donc une liste ordonnée de 1 à 9 contenant toutes les pièces à placer. Reste enfin à placer sur chacune de ces pièces externes à la grille des écouteurs qui vont permettre au joueur de les manipuler, un qui écoute la pression sur la pièce et l'autre le relâchement de la pièce. Pensez à annuler l'interactivité du contenu des pièces pour que le champ texte ne gêne pas le joueur pour attraper sa pièce.

Au final il ne reste plus qu'à placer la grille de décor par dessus les pièces.

Le jeu est initialisé, mais pas encore prêt.

function presser(e:MouseEvent) {
	var p:Case = Case(e.target);
	p.startDrag();
	deco.infos.text = "";
	setChildIndex(p, numChildren-1);
	if(p.x!=410) stock[int((p.x-decal)/T)+int((p.y-decal)/T)*C] = "";
};

Quand le joueur attrape une pièce dans la pioche, on la drag avec la souris, on vide le champ texte de la grille de décor (vous verrez pourquoi ensuite) et on place la pièce attrapée par dessus tout le reste, c'est à dire par dessus les autres pièces et par dessus la grille de décor. Enfin, il faut vérifier si la pièce qu'on vient de prendre se trouve dans la pioche ou dans la grille, car le joueur peut s'être trompé et souhaiter retirer ou déplacer une pièce de la grille, auquel cas, si la pièce est dans la grille il faut vider la référence dans la liste afin de libérer la case précédemment occupée.

Ok, maintenant il reste à voir ce qu'il se passe quand le joueur va poser une pièce dans la grille.

function relacher(e:MouseEvent) {
	stopDrag();
 
	var p:Case = Case(e.target);
	X = int((mouseX-decal)/T);
	Y = int((mouseY-decal)/T);
 
	if (p.x<decal || p.x>T*10-decal || p.y<decal || p.y>T*10-decal) {
		replace(p,"Vous êtes en dehors de la grille !", p);
		return;
	}
 
	if(stock[X+Y*C]) {
		replace(p,"Cette case est déjà occupée !", stock[X+Y*C]);
		return;
	}
 
	for (i = 0; i < C; i++) {
		// ligne
		id = stock[i+Y*C];
		if (id && id.num == p.num) {
			replace(p,"Il y a deja un " + p.num + " dans cette ligne !", id);
			return;
		}
		// colonne
		id = stock[X+i*C];
		if (id && id.num == p.num) {
			replace(p,"Il y a deja un " + p.num + " dans cette colonne !", id);
			return;
		}
	}
 
	for (var j = 0; j < 3; j++) {
		for (i = 0; i < 3; i++) {
			id = stock[3*int(X/3)+i+(3*int(Y/3)+j)*C];
			if (id && id.num == p.num){
				replace(p,"Il y a deja un " + p.num + " dans ce carre !", id);
				return;
			}
		}
	}
 
	p.x = X*T+decal;
	p.y = Y*T+decal;
	stock[X+Y*C] = p;
	setChildIndex(deco, numChildren-1);
 
	for each(var g in stock){
		if(!g) return;
	}
	deco.infos.text = "Bravo la grille est remplie, c'est gagné !";
	addChild(panneaux);
	panneaux.gotoAndStop(3);
};

On commence par arrêter le drag, ça c'est logique, puis on va lancer une série de tests.

var p:Case = Case(e.target);
X = int((mouseX-decal)/T);
Y = int((mouseY-decal)/T);

On récupère la pièce qu'on vient de lâcher et on enregistre sa position dans la grille, notez que j'utilise la position de la souris et non de la pièce pour détecter la case où on lâche la pièce, c'est une question de maniabilité pour le joueur.

if (p.x<decal || p.x>T*10-decal || p.y<decal || p.y>T*10-decal) {
	replace(p,"Vous êtes en dehors de la grille !", p);
	return;
}

Premier test, on vérifie si la pièce est bien relâchée à l'intérieur de la grille, si ce n'est pas le cas on signale au joueur qu'il a lâché la pièce en dehors et on replace la pièce puis on stoppe les tests. Puisque la fonction “replace” va être utilisée pour tous les tests on va l'étudier tout de suite.

function replace(p:Case,t:String,fx:Case):void{
	deco.infos.text = t;
	p.x = 410;
	p.y = p.num*T-10;
	fx.fond_chiffre.play();
	setChildIndex(deco, numChildren-1);
}

On met à jour le champ texte qui donne les infos au joueur (c'est pour ça qu'on le vide quand le joueur attrape une pièce), on replace la pièce dans la pioche, on demande à la pièce concernée (soit celle qu'on a posé au mauvais endroit, soit celle qui empêche de poser la pièce en cours) de se signaler (on joue l'animation de la pièce) et on repasse la grille de décor par dessus tout le reste.

Passons au deuxième test.

if(stock[X+Y*C]) {
	replace(p,"Cette case est déjà occupée !", stock[X+Y*C]);
	return;
}
 
On regarde si la case est déjà occupée dans la grille, si c'est le cas.... on replace la pièce et on stoppe les tests.
 
for (i = 0; i < C; i++) {
	// ligne
	id = stock[i+Y*C];
	if (id && id.num == p.num) {
		replace(p,"Il y a deja un " + p.num + " dans cette ligne !", id);
		return;
	}
	// colonne
	id = stock[X+i*C];
	if (id && id.num == p.num) {
		replace(p,"Il y a deja un " + p.num + " dans cette colonne !", id);
		return;
	}
}

A présent on va vérifier chaque pièce de la ligne et de la colonne où le joueur souhaite poser sa pièce. Si on tombe sur un chiffre identique à la pièce que le joueur souhaite poser, on replace la pièce dans la pioche et on stoppe les tests.

for (var j = 0; j < 3; j++) {
	for (i = 0; i < 3; i++) {
		id = stock[3*int(X/3)+i+(3*int(Y/3)+j)*C];
		if (id && id.num == p.num){
			replace(p,"Il y a deja un " + p.num + " dans ce carre !", id);
			return;
		}
	}
}

Même manipulation avec le carré dans lequel la pièce est posée, on fait deux boucles pour une grille de 3*3 correspondante au carré, et on vérifie si le chiffre d'une des pièces présentes dans ce carré correspond au chiffre le pièce qu'on veut poser, si c'est le cas…… on replace et on stoppe les tests.

p.x = X*T+decal;
p.y = Y*T+decal;
stock[X+Y*C] = p;
setChildIndex(deco, numChildren-1);

Tous les tests ont été passés avec succès, le joueur peut donc poser sa pièce, on place la pièce au bon endroit dans la grille (en tenant compte du décalage) et on renseigne le stock, puis on replace la grille de décor au dessus de tout le reste.

for each(var g in stock){
	if(!g) return;
}
deco.infos.text = "Bravo la grille est remplie, c'est gagné !";
addChild(panneaux);
panneaux.gotoAndStop(3);

Et enfin pour terminer, à chaque fois que le joueur pose une pièce on vérifie si la grille est correctement remplie auquel cas la partie est gagnée, on le signale au joueur et on le félicite, puis on affiche le panneau de victoire proposant au joueur de refaire une partie, ce qui relance le générateur qui va créer une nouvelle grille.

Et c'est terminé !

Plus que le jeu en lui même, c'est surtout le générateur qui est intéressant ici, il vous assure que votre jeu est jouable et ne proposera pas deux fois la même grille, vous avez donc là un jeu réellement complet, a vous de proposer des options supplémentaire comme augmenter ou réduire la difficulté en modifiant le nombre de cases vides. Il n'y a rien de bien complexe ici, pas de grosses formules, pas de collisions, pas de maths poussées, juste de la logique et de la manipulation de tableau, c'est le thème principal de cet exercice, vous apprendre à gérer des listes et des tableaux complexes et effectuer des tests dessus.