////////////////////////////////////////////////////////////////////////////////
//
//	COMMENTAIRES
  //
  //	Nom					katamino.sce
  //	Auteur				Jérôme LABATUT 
  //	Date de création		2020-01-03
  //
  //	Version Scilab			6.0.1
  //	Module Atoms requis		Aucun
  //
  //	Objectif				Katamino / IQ Puzzle (résolution récursive)
  //	
	funcprot(0)
	clearglobal()
	clear()
	
	xdel(winsid())
	tohome()
	clc()
	
	global JEU
  //
//
////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
//
//	FONCTIONS MODELE
  //
  //	Initialisation des paramètres
  //	Sélection d'une grille dans la base de grilles incomplètes
  //
  //	Conversion d'une grille du format lettres au format matrice d'entiers
  //	Recherche d'une case vide
  //	Tranformations orthogonales
  //	Algorithme récursif de résolution du puzzle
//
////////////////////////////////////////////////////////////////////////////////

function affecterParametresModele()
	global JEU
	
	// Paramètres du jeu
		JEU.Lignes =				5
		JEU.Colonnes =				11
		JEU.TAILLE =				max(JEU.Lignes, JEU.Colonnes)
	
	// Catalogue des pièces disponibles
		JEU.Pieces(1).Code =		1
		JEU.Pieces(1).CouleurCode =	color('blue')
		JEU.Pieces(1).Lettre =		'A'
		JEU.Pieces(1).Grille =		['A_';	...
								 'A_';	...
								 'AA'	]
		JEU.Pieces(1).Translations =	[0, 0; 0, 1; 0, 2; 1, 0]
		JEU.Pieces(1).Jouable =		%T
			
		JEU.Pieces(2).Code =		2
		JEU.Pieces(2).CouleurCode =	color('cyan')
		JEU.Pieces(2).Lettre =		'B'
		JEU.Pieces(2).Grille = 		['B_';	...
								 'BB';	...
								 'BB'	]
		JEU.Pieces(2).Translations =	[0, 0; 0, 1; 0, 2; 1, 0; 1, 1]
		JEU.Pieces(2).Jouable =		%T
		
		JEU.Pieces(3).Code =		3
		JEU.Pieces(3).CouleurCode =	color('red')
		JEU.Pieces(3).Lettre =		'C'
		JEU.Pieces(3).Grille =		['C_';	...
								 'C_';	...
								 'C_';	...
								 'CC'	]
		JEU.Pieces(3).Translations =	[0, 0; 0, 1; 0, 2; 0, 3; 1, 0]
		JEU.Pieces(3).Jouable =		%T
		
		JEU.Pieces(4).Code =		4
		JEU.Pieces(4).CouleurCode =	color('dodgerblue')
		JEU.Pieces(4).Lettre =		'D'
		JEU.Pieces(4).Grille =		['_D__';	...
								 'DDDD'	]
		JEU.Pieces(4).Translations = [0, 0; 0, 1; 1, 1; 0, 2; 0, 3]
		JEU.Pieces(4).Jouable =		%T
		
		JEU.Pieces(5).Code =		5
		JEU.Pieces(6).CouleurCode =	color('deeppink')
		JEU.Pieces(5).Lettre =		'E'
		JEU.Pieces(5).Grille =		['_E';	...
								 '_E';	...
								 'EE';	...
								 'E_'	]
		JEU.Pieces(5).Translations = [0, 0; 1, 0; 1, 1; 2, 1; 3, 1]
		JEU.Pieces(5).Jouable =		%T
		
		JEU.Pieces(6).Code =		6
		JEU.Pieces(6).CouleurCode =	color('cyan')
		JEU.Pieces(6).Lettre =		'F'
		JEU.Pieces(6).Grille =		['F_';	...
								 'FF'	]
		JEU.Pieces(6).Translations = [0, 0; 0, 1; 1, 0]
		JEU.Pieces(6).Jouable =		%T
		
		JEU.Pieces(7).Code =		7
		JEU.Pieces(7).CouleurCode =	color('deepskyblue')
		JEU.Pieces(7).Lettre =		'G'
		JEU.Pieces(7).Grille =		['G__';	...
								 'G__';	...
								 'GGG'	]
		JEU.Pieces(7).Translations = [0, 0; 0, 1; 0, 2; 1, 0; 2, 0]
		JEU.Pieces(7).Jouable =		%T
		
		JEU.Pieces(8).Code =		8
		JEU.Pieces(8).CouleurCode =	color('darkviolet')
		JEU.Pieces(8).Lettre =		'H'
		JEU.Pieces(8).Grille =		['__H';	...
								 '_HH';	...
								 'HH_'	]
		JEU.Pieces(8).Translations =	[0, 0; 1, 0; 1, 1; 2, 1; 2, 2]
		JEU.Pieces(8).Jouable =		%T
		
		JEU.Pieces(9).Code =		9
		JEU.Pieces(9).CouleurCode =	color('lawngreen')
		JEU.Pieces(9).Lettre =		'I'
		JEU.Pieces(9).Grille =		['I_I';	...
								 'III'	]
		JEU.Pieces(9).Translations =	[0, 0; 1, 0; 2, 0; 0, 1; 2, 1]
		JEU.Pieces(9).Jouable =		%T
		
		JEU.Pieces(10).Code =		10
		JEU.Pieces(10).CouleurCode =	color('orange')
		JEU.Pieces(10).Lettre =		'J'
		JEU.Pieces(10).Grille = 		['J';	...
								 'J';	...
								 'J';	...
								 'J'		]
		JEU.Pieces(10).Translations = [0, 0; 1, 0; 2, 0; 3, 0]	
		JEU.Pieces(10).Jouable =		%T
		
		JEU.Pieces(11).Code = 		11
		JEU.Pieces(11).CouleurCode =	color('yellow')
		JEU.Pieces(11).Lettre =		'K'
		JEU.Pieces(11).Grille =		['KK';	...
								 'KK'	]
		JEU.Pieces(11).Translations = [0, 0; 1, 0; 0, 1; 1, 1]
		JEU.Pieces(11).Jouable =		%T
		
		JEU.Pieces(12).Code =		12
		JEU.Pieces(12).CouleurCode =	color('darkgreen')
		JEU.Pieces(12).Lettre =		'L'
		JEU.Pieces(12).Grille =		['_L_';	...
								 'LLL';	...
								 '_L_'	]
		JEU.Pieces(12).Translations = [1, 0; 0, 1; 1, 1; 2, 1; 1, 2]
		JEU.Pieces(12).Jouable =		%T
		
		JEU.NombrePieces =			size(JEU.Pieces, 1)
		
		for p = 1:JEU.NombrePieces
			JEU.Pieces(p).Taille =	size(JEU.Pieces(p).Translations, 1)
		end
	
	// Calcul pour chaque pièce de toutes ses positions non superposables
		JEU.Pieces(1).ListeTransformations = [0, 0; 0, 1; 0, 2; 0, 3; 1, 0; 1, 1; 1, 2; 1, 3]
		JEU.Pieces(2).ListeTransformations = [0, 0; 0, 1; 0, 2; 0, 3; 1, 0; 1, 1; 1, 2; 1, 3]
		JEU.Pieces(3).ListeTransformations = [0, 0; 0, 1; 0, 2; 0, 3; 1, 0; 1, 1; 1, 2; 1, 3]
		JEU.Pieces(4).ListeTransformations = [0, 0; 0, 1; 0, 2; 0, 3; 1, 0; 1, 1; 1, 2; 1, 3]
		JEU.Pieces(5).ListeTransformations = [0, 0; 0, 1; 0, 2; 0, 3; 1, 0; 1, 1; 1, 2; 1, 3]
		
		JEU.Pieces(6).ListeTransformations = [0, 0; 0, 1; 0, 2; 0, 3]
		JEU.Pieces(7).ListeTransformations = [0, 0; 0, 1; 0, 2; 0, 3]
		JEU.Pieces(8).ListeTransformations = [0, 0; 0, 1; 0, 2; 0, 3]
		JEU.Pieces(9).ListeTransformations = [0, 0; 0, 1; 0, 2; 0, 3]
		
		JEU.Pieces(10).ListeTransformations = [0, 0; 0, 1]
		JEU.Pieces(11).ListeTransformations = [0, 0; 0, 1]
		
		JEU.Pieces(12).ListeTransformations = [0, 0]
		
		for p = 1:JEU.NombrePieces
			JEU.Pieces(p).NombrePositions = size(JEU.Pieces(p).ListeTransformations, 1)
			
			JEU.Pieces(p).Positions = zeros(JEU.Pieces(p).Taille, 2, JEU.Pieces(p).NombrePositions)
		
			for t = 1:JEU.Pieces(p).NombrePositions
				s =				JEU.Pieces(p).ListeTransformations(t, 1)
				r =				JEU.Pieces(p).ListeTransformations(t, 2)
				JEU.Pieces(p).Positions(:, :, t) = transformation(s, r, JEU.Pieces(p).Translations)
			end		
		end
	
	// Tri des pièces par taille décroissante
		JEU.PiecesDesordre =		JEU.Pieces
		
		JEU.Pieces( 1) =			JEU.PiecesDesordre( 2)	// 5 cases
		JEU.Pieces( 2) =			JEU.PiecesDesordre( 3)	// 5 cases
		JEU.Pieces( 3) =			JEU.PiecesDesordre( 5)	// 5 cases
		JEU.Pieces( 4) =			JEU.PiecesDesordre( 7)	// 5 cases
		JEU.Pieces( 5) =			JEU.PiecesDesordre( 8)	// 5 cases
		JEU.Pieces( 6) =			JEU.PiecesDesordre( 9)	// 5 cases
		JEU.Pieces( 7) =			JEU.PiecesDesordre(12)	// 5 cases
		JEU.Pieces( 8) =			JEU.PiecesDesordre( 1)	// 4 cases
		JEU.Pieces( 9) =			JEU.PiecesDesordre( 4)	// 4 cases
		JEU.Pieces(10) =			JEU.PiecesDesordre(10)	// 4 cases
		JEU.Pieces(11) =			JEU.PiecesDesordre(11)	// 4 cases
		JEU.Pieces(12) =			JEU.PiecesDesordre( 6)	// 3 cases
		
		for p = 1:JEU.NombrePieces
			Codes(p, 1) =			JEU.Pieces(p).Code
		end
		
		[CodesOrdonnes, JEU.Numeros] = gsort(Codes, 'r', 'i')
	end

function parametre = donnerNiveau(numero, nomParametre)
	select numero
		case 33 then
			nomNiveau =			'Problème 33'
			GrilleLettres =		['FFDDDDEEE__';	...
								 'FKKDLEE____';	...
								 'GKKLLL_____';	...
								 'GAAAL______';	...
								 'GGGA_______'		]
			nombreSolutions =		  1
		case 34 then
			nomNiveau =			'Problème 34'
			GrilleLettres =		['FDDDDE_____';	...
								 'FFDCCE_____';	...
								 'GKKCEE_____';	...
								 'GKKCE______';	...
								 'GGGCJJJJ___'		]
			nombreSolutions =		  2
		case 35 then
			nomNiveau =			'Problème 35'
			GrilleLettres =		['FFKKBB_____';	...
								 'FCKKBBB____';	...
								 'GCCCCL_____';	...
								 'GEEELLL____';	...
								 'GGGEEL_____'		]
			nombreSolutions =		  2
		case 36 then
			nomNiveau =			'Problème 36'
			GrilleLettres =		['FJJJJEE____';	...
								 'FFHEEE_____';	...
								 'KKHHII_____';	...
								 'KKDHHI_____';	...
								 'DDDDII_____'		]
			nombreSolutions =		  2
		case 37 then
			nomNiveau =			'Problème 37'
			GrilleLettres =		['FCCCCGGG___';	...
								 'FFBBCG_____';	...
								 'KKBBLG_____';	...
								 'KKBLLL_____';	...
								 'JJJJL______'		]
			nombreSolutions =		  1
		case 38 then
			nomNiveau =			'Problème 38'
			GrilleLettres =		['FFJJJJ_____';	...
								 'FDDDD______';	...
								 'KKGDA______';	...
								 'KKGCAAA____';	...
								 'GGGCCCC____'		]
			nombreSolutions =		  1
		case 39 then
			nomNiveau =			'Problème 39'
			GrilleLettres =		['FFKKIII____';	...
								 'CFKKIGI____';	...
								 'CJJJJG_____';	...
								 'CEEGGG_____';	...
								 'CCEEE______'		]
			nombreSolutions =		  1
		case 40 then
			nomNiveau =			'Problème 40'
			GrilleLettres =		['FFDDDD_____'; ...
								 'FKKDHH_____'; ...
								 'AKKHHL_____'; ...
								 'AEEHLLL____'; ...
								 'AAEEEL_____']
			nombreSolutions =		  1
		case 41 then
			nomNiveau =			'Problème 41'
			GrilleLettres =		['IIIDDDD____'; ...
								 'IEIFD______'; ...
								 'EEFF_______'; ...
								 'EAAA_______'; ...
								 'EAJJJJ_____']
			nombreSolutions =		  1
		case 42 then
			nomNiveau =			'Problème 42'
			GrilleLettres =		['IIIAD______'; ...
								 'IBIADD_____'; ...
								 'BBAAD______'; ...
								 'BBEED______'; ...
								 'EEEJJJJ____']
			nombreSolutions =		  2
		case 43 then
			nomNiveau =			'Problème 43'
			GrilleLettres = 		['IIJJJJ_____'; ...
								 'IDDDD______'; ...
								 'IIADG______'; ...
								 'AAACG______'; ...
								 'CCCCGGG____']
			nombreSolutions =		  2
		case 44 then
			nomNiveau =			'Problème 44'
			GrilleLettres = 		['IIDDDD_____'; ...
								 'IEEED______'; ...
								 'IIFEE______'; ...
								 'AFFKK______'; ...
								 'AAAKK______']
			nombreSolutions =		  1
		case 45 then
			nomNiveau =			'Problème 45'
			GrilleLettres =		['IIIABBB____'; ...
								 'IEIABB_____'; ...
								 'EEAAC______'; ...
								 'ECCCC______'; ...
								 'EJJJJ______']
			nombreSolutions =		  1
		case 46 then
			nomNiveau =			'Problème 46'
			GrilleLettres =		 ['IIDDDD_____'; ...
								   'IAAAD______'; ...
				 				  'IIFAL______'; ...
								  'CFFLLL_____'; ...
								  'CCCCL______'] 
			nombreSolutions =		  1
		case 47 then
			nomNiveau =			'Problème 47'
			GrilleLettres =		['IIBBJ______'; ...
								 'IBBBJ______'; ...
								 'IIAGJ______'; ...
								 'FFAGJ______'; ...
								 'FAAGGG_____']
			nombreSolutions =		  1
		case 48 then
			nomNiveau =			'Problème 48'
			GrilleLettres =		['IIIJJJJ____'; ...
								 'IFIBB______'; ...
								 'FFABB______'; ...
								 'AAACB______'; ...
								 'CCCC_______']
			nombreSolutions =		  1
		case 49 then
			nomNiveau =			'Problème 49'
			GrilleLettres = 		['DDDDHH_____'; ...
								 'GFDHH______'; ...
								 'GFFH_______'; ...
								 'GGGC_______'; ...
								 'CCCC_______']
			nombreSolutions =		 40
		case 50 then
			nomNiveau =			'Problème 50'
			GrilleLettres =		['JJJJ_______'; ...
								 'CGGG_______'; ...
								 'CGIIL______'; ...
								 'CGILLL_____'; ...
								 'CCIIL______']
			nombreSolutions =		101
		case 51 then
			nomNiveau =			'Problème 51'
			GrilleLettres =		['CCCC_______'; ...
								 'CJJJJ______'; ...
								 'GGGII______'; ...
								 'KKGI_______'; ...
								 'KKGII______']
			nombreSolutions =		 32
		case 52 then
			nomNiveau =			'Problème 52'
			GrilleLettres =		['BBAAA______'; ...
								 'BBBDA______'; ...
								 'GGGD_______'; ...
								 'GKKDD______'; ...
								 'GKKD_______'] 
			nombreSolutions =		  4
		case 53 then
			nomNiveau =			'Problème 53'
			GrilleLettres =		['FFKK_______'; ...
								 'FAKK_______'; ...
								 'GA_________'; ...
								 'GAA___C____'; ...
								 'GGGCCCC____']
			nombreSolutions =		  2
		case 54 then
			nomNiveau =			'Problème 54'
			GrilleLettres =		['DDDDEE_____'; ...
								 'JDEEE______'; ...
								 'JGGG_______'; ...
								 'JKKG_______'; ...
								 'JKKG_______']
			nombreSolutions =		105
		case 55 then
			nomNiveau =			'Problème 55'
			GrilleLettres =		['HHJJJJ_____'; ...
								 'FHHG_______'; ...
								 'FFHG_______'; ...
								 'CGGG_______'; ...
								 'CCCC_______']
			nombreSolutions =		 20
		case 56 then
			nomNiveau =			'Problème 56'
			GrilleLettres =		['GGG________'; ...
								 'GECC_______'; ...
								 'GEEC_______'; ...
								 'KKECI_I____'; ...
								 'KKECIII____']
			nombreSolutions =		 27
		case 57 then
			nomNiveau =			'Problème 57'
			GrilleLettres =		['KK_________'; ...
								 'KKHH_______'; ...
								 'GHHL_______'; ...
								 'GHLLL______'; ...
								 'GGGL_______']
			nombreSolutions =		140
		case 58 then
			nomNiveau =			'Problème 58'
			GrilleLettres =		['BBBEEE_____'; ...
								 'BBEE_______'; ...
								 'GGG________'; ...
								 'GKK________'; ...
								 'GKK________']
			nombreSolutions =		115
		case 59 then
			nomNiveau =			'Problème 59'
			GrilleLettres =		['CCCCD______'; ...
								 'CLDDDD_____'; ...
								 'LLL________'; ...
								 'ILI________'; ...
								 'III________']
			nombreSolutions =		314
		case 60 then
			nomNiveau =			'Problème 60'
			GrilleLettres =		['BBB________'; ...
								 'BB_________'; ...
								 'EEE________'; ...
								 'KKEED______'; ...
								 'KKDDDD_____']
			nombreSolutions =		 17
		case 61 then
			nomNiveau =			'Problème 61'
			GrilleLettres =		['KKCCCC_____'; ...
								 'KKC________'; ...
								 'BFF________'; ...
								 'BBF________'; ...
								 'BB_________']
			nombreSolutions =		  3
		case 62 then
			nomNiveau =			'Problème 62'
			GrilleLettres =		['CCCCEE_____'; ...
								 'CLEEE______'; ...
								 'LLL________'; ...
								 'ILI________'; ...
								 'III________']
			nombreSolutions =		925
		case 63 then
			nomNiveau =			'Problème 63'
			GrilleLettres =		['III________'; ...
								 'IFI________'; ...
								 'FF_________'; ...
								 'AAA_C______'; ...
								 'ACCCC______']
			nombreSolutions =		 28
		case 64 then
			nomNiveau =			'Problème 64'
			GrilleLettres =		['AACCCC_____'; ...
								 'GAC________'; ...
								 'GA_________'; ...
								 'GGG________'; ...
								 'JJJJ_______']
			nombreSolutions =		 85
		case 65 then
			nomNiveau =			'Problème 65'
			GrilleLettres =		['FF_________'; ...
								 'CF_________'; ...
								 'CAAA_______'; ...
								 'CA_________'; ...
								 'CC_________']
			nombreSolutions =		  2
		case 66 then
			nomNiveau =			'Problème 66'
			GrilleLettres =		['II_________'; ...
								 'I__________'; ...
								 'IIL________'; ...
								 'FLLL_______'; ...
								 'FFL________']
			nombreSolutions =		496 
		case 67 then
			nomNiveau =			'Problème 67'
			GrilleLettres =		['FF_________'; ...
								 'GF_________'; ...
								 'G__________'; ...
								 'GGGC_______'; ...
								 'CCCC_______'] 
			nombreSolutions =		 29
		case 68 then
			nomNiveau =			'Problème 68'
			GrilleLettres =		['IIJJJJ_____'; ...
								 'I__________'; ...
								 'II_________'; ...
								 'FF_________'; ...
								 'F__________']
			nombreSolutions =		 12
		case 69 then
			nomNiveau =			'Problème 69'
			GrilleLettres =		['DDDDBBBCCCC'; ...
								 '__D_BB_C___'; ...
								 '___________'; ...
								 '___________'; ...
								 '___________']
			nombreSolutions =		  1
		case 70 then
			nomNiveau =			'Problème 70'
			GrilleLettres =		['DDDDCCCCBBB'; ...
								 '_D_____C_BB'; ...
								 '___________'; ...
								 '___________'; ...
								 '___________']
			nombreSolutions =		  1
		case 71 then
			nomNiveau =			'Problème 71'
			GrilleLettres =		['DDDDAAACCCC'; ...
								 '_D__A__C___'; ...
								 '___________'; ...
								 '___________'; ...
								 '___________']
			nombreSolutions =		  1
		case 72 then
			nomNiveau =			'Problème 72'
			GrilleLettres =		['AAAJJJJDDDD'; ...
								 '__A______D_'; ...
								 '___________'; ...
								 '___________'; ...
								 '___________']
			nombreSolutions =		  1	
	end
	
	select nomParametre
		case 'numeroMin'			then parametre = 33
		case 'numeroMax'			then parametre = 72
		case 'Nom'				then parametre = nomNiveau
		case 'Valeur'				then parametre = GrilleLettres
		case 'Solutions'			then parametre = nombreSolutions
	end
end
function GrilleNombres = convertirGrille(GrilleLettres)
	global JEU
	
	GrilleNombres =				zeros(JEU.Lignes, JEU.Colonnes)
	
	for l = 1:JEU.Lignes
		Chaine =					GrilleLettres(l, 1)
		for c = 1:JEU.Colonnes
			Lettre =				part(Chaine, c)
			select Lettre
			case '_' then 
				GrilleNombres(l, c) = 0
			else 
				numero =			JEU.Numeros(asciimat(Lettre) - asciimat('A') + 1, 1)
				GrilleNombres(l, c) = JEU.Pieces(numero).Code
			end
		end
	end
end

function chercherPiecesJouables(Grille)
	global JEU
	
	JEU.Pieces(:).Jouable =			%T
	
	for l = 1:JEU.Lignes
	for c = 1:JEU.Colonnes
		for numero = 1:JEU.NombrePieces
			if (Grille(l, c) == JEU.Pieces(numero).Code)
				JEU.Pieces(numero).Jouable = %F
			end
		end	
	end
	end
end

function [lVide, cVide] = chercherCaseVide(Grille)
	global JEU
	
	[cVides, lVides] =				find(Grille' == 0)
	
	if isempty(cVides)
		lVide =					0
		cVide =					0
	else
		lVide =					lVides(1)
		cVide =					cVides(1)	
	end
end
function GrilleT = transformation(reflexion, rotations90, Grille)
	DX =							Grille(:, 1)
	DY =							Grille(:, 2)
	
	select rotations90
	case 0 then					GrilleT = [  DX,   DY]
	case 1 then					GrilleT = [- DY,   DX]
	case 2 then					GrilleT = [- DX, - DY]
	case 3 then					GrilleT = [  DY, - DX]
	end
	
	select reflexion
	case 1 then					GrilleT = [- GrilleT(:, 1), GrilleT(:, 2)]
	end
end
function GrilleS = resoudreRecursivement(Grille)	// RESOLUTION RECURSIVE
	global JEU
	
	if (JEU.ProfondeurRecursive == 0)
		tic
	end
	JEU.ProfondeurRecursive =		JEU.ProfondeurRecursive + 1
	
	[lVide, cVide] =				chercherCaseVide(Grille)
	if (lVide == 0)&(cVide == 0)
		GrilleS =					Grille
		JEU.SOLUTIONS =			cat(3, JEU.SOLUTIONS, GrilleS)
		mettreAJourDamier(Grille)
		//mettreAJourConsole(JEU.ETAT.RESOLU, Grille, toc())
		sleep(JEU.Pause)
	else	
		for p = 1:JEU.NombrePieces
		if (JEU.Pieces(p).Jouable)&(JEU.Evaluations <= JEU.MaximumEvaluations)
			for pp = 1:JEU.Pieces(p).NombrePositions
			for ppp = 1:JEU.Pieces(p).Taille
				CasesOccupees =	  JEU.Pieces(p).Positions(:, :, pp) 							...
								- ones(JEU.Pieces(p).Taille, 1)*JEU.Pieces(p).Positions(ppp, :, pp)	...
								+ ones(JEU.Pieces(p).Taille, 1)*[lVide, cVide]
				
				PASDebordement =	 (min(CasesOccupees(:, 1)) >= 1)&(max(CasesOccupees(:, 1)) <= JEU.Lignes)	...
								&(min(CasesOccupees(:, 2)) >= 1)&(max(CasesOccupees(:, 2)) <= JEU.Colonnes)
				
				if ( PASDebordement )
					PASChevauchement =	%T
					
					for ppp = 1:JEU.Pieces(p).Taille
						PASChevauchement = PASChevauchement*(Grille(CasesOccupees(ppp, 1), CasesOccupees(ppp, 2)) == 0)
					end
				end	
				if ( PASDebordement & PASChevauchement )
					GrilleS =		Grille
					
					for ppp = 1:JEU.Pieces(p).Taille
						GrilleS(CasesOccupees(ppp, 1), CasesOccupees(ppp, 2)) = JEU.Pieces(p).Code
					end
					JEU.Pieces(p).Jouable = %F
						
					JEU.Evaluations = JEU.Evaluations + 1
					if (modulo(JEU.Evaluations, JEU.PeriodeAffichage) == 1)
						mettreAJourDamier(GrilleS)
						//mettreAJourConsole(JEU.ETAT.RECHERCHE, GrilleS, lVide, cVide, p, pp)
					end
					
					GrilleS =		resoudreRecursivement(GrilleS)
					
					GrilleS =		Grille
					JEU.Pieces(p).Jouable = %T
				end
			end
			end
		end
		end
		
		JEU.ProfondeurRecursive =	JEU.ProfondeurRecursive - 1
	end
	return
end

////////////////////////////////////////////////////////////////////////////////
//
//	FONCTIONS VUES
  //
  //	Interface utilisateur
  //	Console simplifiée
  //
  //	Affichage d'une grille dans la console
  //	Affichage de deux grilles dans la console
//
////////////////////////////////////////////////////////////////////////////////

function affecterParametresVues()
	global JEU
	
	// Interface
		JEU.INTERFACE.Etiquette =	'Interface'
		JEU.INTERFACE.Position =		[0, 0]
		JEU.INTERFACE.Taille =		[700, 700]
		JEU.INTERFACE.CouleurRVB =	[0.8, 0.8, 0.8]
		JEU.INTERFACE.Titre =		'KATAMINO ' + string(JEU.Lignes) + ' lignes x ' + string(JEU.Colonnes) + ' colonnes'
		
	// Boutons de contrôle
		JEU.BOUTONS.Nombre =		5
		JEU.BOUTONS.Unites =		'normalized'
		JEU.BOUTONS.CouleurRVB =		[0.9 0.9 0.9]
		JEU.BOUTONS.TaillePolice =	15
	
	// Damier ( Axes )
		TailleDamier =				(JEU.BOUTONS.Nombre - 1)/JEU.BOUTONS.Nombre
		
		JEU.DAMIER.Etiquette =		'Damier'
		JEU.DAMIER.Position =		[0, 0, TailleDamier, TailleDamier]
		JEU.DAMIER.Marges =			[0, 0, 0, 0]
	
	// Case
		JEU.CASE.Angle =			2*%pi*linspace(0, 1, 60)
		JEU.CASE.X =				1/2 + 1/2*cos(JEU.CASE.Angle - %pi/2)
		JEU.CASE.Y =				1/2 + 1/2*sin(JEU.CASE.Angle - %pi/2)
		JEU.CASE.CouleurCode =		color('grey')
	
	// Console
		JEU.CONSOLE.PasDeLettre =	'_'
		JEU.CONSOLE.Marge =			'\t'
		JEU.CONSOLE.Intervalle =		'   '
		JEU.CONSOLE.Saut1Ligne =		'\n'
		JEU.CONSOLE.Saut2Lignes =	'\n\n'
end

function creerInterface()
	global JEU
	
	// Création de l'interface
		interface1 =				figure('figure_position', JEU.INTERFACE.Position)
		interface1.tag =			JEU.INTERFACE.Etiquette
		
		interface1.figure_size =		JEU.INTERFACE.Taille
		interface1.auto_resize =		'on'
		interface1.figure_name =		JEU.INTERFACE.Titre
		interface1.backgroundcolor =	JEU.INTERFACE.CouleurRVB
		
		delmenu(interface1.figure_id, gettext('File'))
		delmenu(interface1.figure_id, gettext('Tools'))
		delmenu(interface1.figure_id, gettext('Edit'))
		delmenu(interface1.figure_id, gettext('?'))
		toolbar(interface1.figure_id, 'off')
		
	// Création du damier
		creerDamier(JEU.Lignes, JEU.Colonnes)
	
	// Création des commandes de jeu
		for bb = [1, 2, 5]
			select bb
			case 1 then BOUTON =	JEU.BOUTON1 // Résolution de la grille ( sélectionnée )
			case 2 then BOUTON =	JEU.BOUTON2 // Affichage de la base de problèmes
			case 3 then BOUTON =	JEU.BOUTON3 // Entrée manuelle d'une nouvelle grille
			case 5 then BOUTON =	JEU.BOUTON5 // Sortie
			end
			
			bouton =				uicontrol(get(JEU.INTERFACE.Etiquette), 'style', 'pushbutton')
			bouton.Tag =			BOUTON.Etiquette
			bouton.Units =			BOUTON.Unites
			bouton.Position =		BOUTON.Position
			bouton.BackgroundColor =	BOUTON.CouleurRVB
			bouton.FontSize =		BOUTON.TaillePolice
			bouton.Relief =		BOUTON.Relief
			bouton.String =		BOUTON.Titre
			bouton.Callback =		BOUTON.Action
		end
	
	// Création des menus de sélection
		for mm = 1:3
			select mm
			case 1 then MENU =		JEU.MENU1 // Sélection de la grille à complèter
			case 2 then MENU =		JEU.MENU2 // Sélection de la grille à complèter SUITE
			case 3 then MENU =		JEU.MENU3 // Sélection du nombre maximum d'itérations
			end
			menu =				 uimenu(get(JEU.INTERFACE.Etiquette), 'Tag', MENU.Etiquette, 'Label', MENU.Nom)
			
			for m = 1:1:size(MENU.Choix, 1)
				nom =			MENU.Choix(m, 1)
				action =			MENU.Choix(m, 2)
								uimenu(menu, 'Label', nom, 'Callback', action)
				// uimenu(menu ... plus rapide que uimenu(get(JEU.MENU.Etiquette) ..?
			end
		end
		
		MENU =					JEU.MENU4 // Menu des solutions trouvées ! DE HAUTEUR VARIABLE !
		menu =					uimenu(get(JEU.INTERFACE.Etiquette), 'Tag', MENU.Etiquette, 'Label', MENU.Nom)
		menu.Enable =				'off'
		menu.Visible =				'off'
end
function creerDamier(Lignes, Colonnes)
	global JEU
	
	damier =						newaxes(get(JEU.INTERFACE.Etiquette))
	damier.tag = 					JEU.DAMIER.Etiquette
	
	damier.axes_bounds =			JEU.DAMIER.Position
	damier.margins =				JEU.DAMIER.Marges
		
	damier.axes_visible =			"off"
	damier.x_location =				"top"
	damier.y_location =				"left"
	damier.box =					"off"
	damier.isoview =				"on"
	damier.data_bounds =			[0, 0; Colonnes, Lignes]
		
	for l = 1:JEU.Lignes
	for c = 1:JEU.Colonnes
		etiquette =				'Case' + 'L' + string(l) + 'C' + string(c)
		xPolygone =				              c - 1  + JEU.CASE.X               
		yPolygone =				JEU.TAILLE - (l - 1) + JEU.CASE.Y 
		couleur =					JEU.CASE.CouleurCode
			
		xfpoly(xPolygone, yPolygone, couleur)
		set(gce(), 'Tag', etiquette)
		JEU.CASE.Etiquettes(l, c) =	etiquette
	end
	end
	
	drawnow()
end

function mettreAJourMenu(Etat)
	global JEU
	
	menuSolutions =				get(JEU.MENU4.Etiquette)
	
	select Etat
	case JEU.ETAT.RECHERCHE then
		set(menuSolutions, 'Enable', 'off')
		set(menuSolutions, 'Visible', 'off')
		
		delete(menuSolutions.children)
	case JEU.ETAT.RESOLU then
		NombreSolutions =			size(JEU.SOLUTIONS, 3)
		
		if ( NombreSolutions ~= 0 )
			for m = 1:1:NombreSolutions
				nom =			'Solution ' + string(m)
				action =			'choisirSolution(' + string(m) + ')'
				uimenu(menuSolutions, 'Label', nom, 'Callback', action)
			end
			
			set(menuSolutions, 'Enable', 'on')
			set(menuSolutions, 'Visible', 'on')
		end
	end
end
function mettreAJourDamier(Grille)
	global JEU
		
	for l = 1:JEU.Lignes
	for c = 1:JEU.Colonnes
		if (Grille(l, c) ~=0)
			couleur = 			JEU.Pieces(Grille(l, c)).CouleurCode
		else
			couleur =				JEU.CASE.CouleurCode
		end
		set(get(JEU.CASE.Etiquettes(l, c)), 'Background', couleur)
	end
	end
	
	drawnow()
end
function mettreAJourConsole(Etat, varargin)
	global JEU
	
	tohome
	clc
	
	message =						'KATAMINO'
	message =						message + JEU.CONSOLE.Saut1Ligne
	message =						message + JEU.CONSOLE.Saut1Ligne
	
	message =						donnerNiveau(JEU.NumeroNiveau, 'Nom')
	message =						message + JEU.CONSOLE.Saut1Ligne
		
	select Etat
	case JEU.ETAT.SELECTION then
		Grille =					varargin(1)		// grille incomplète à résoudre
		
		message =					message + typographierGrille(JEU.GrilleIncomplete)
	case JEU.ETAT.CONTRADICTOIRE then
		message =					message + typographierGrille(JEU.GrilleIncomplete)
		message =					message + JEU.CONSOLE.Saut1Ligne
		message =					message + JEU.CONSOLE.Saut1Ligne

		message =					message + 'Cette grille n''a pas de solution'
	case JEU.ETAT.RECHERCHE then
		Grille =					varargin(1)		// grille en cours de résolution
		l =						varargin(2)		// ligne de la case vide en cours
		c =						varargin(3)		// colonne de la case vide en cours
		p =						varargin(4)		// pièce en cours d'essai
		position =				varargin(5)		// position de la pièce
		
		message =					message + typographier2Grilles(JEU.GrilleIncomplete, Grille)
		message =					message + JEU.CONSOLE.Saut1Ligne
		message =					message + JEU.CONSOLE.Saut1Ligne
		
		message =					message + string(JEU.Evaluations) + ' évaluations sur '
		message =					message + string(JEU.MaximumEvaluations) + ' autorisées'
		message =					message + JEU.CONSOLE.Saut1Ligne
		message =					message + JEU.CONSOLE.Saut1Ligne
		
		if (l ~= 0)&(c ~= 0)&(p ~= 0)
			message =				message + 'Profondeur récursive '    + string(JEU.ProfondeurRecursive)
			message =				message + JEU.CONSOLE.Marge + 'Case libre (' + string(l) + ',' + string(c) + ')'
			message =				message + JEU.CONSOLE.Marge + 'Pièce '       + string(JEU.Pieces(p).Lettre)
			message =				message + JEU.CONSOLE.Marge + 'Position '    + string(position)
		end
		if (l == 0)&(c == 0)
			message =				message + JEU.CONSOLE.Marge + 'Plus de case libre !'
		end	
	case JEU.ETAT.RESOLU then
		Grille =					varargin(1)		// grille solution
		tempsEcoule =				varargin(2)		// durée mesurée de la résolution
		
		message =					message + typographier2Grilles(Grille, JEU.GrilleIncomplete)
		message =					message + JEU.CONSOLE.Saut1Ligne
		message =					message + JEU.CONSOLE.Saut1Ligne
		
		message =					message + JEU.CONSOLE.Marge
		message =					message + 'Solution trouvée en : ' + string(tempsEcoule) + ' ms'
	end
	
	mprintf(message)
end
function Texte = typographierGrille(Grille)
	global JEU
	
	Texte =						''
	
	for l = 1:JEU.Lignes
		for c = 1:JEU.Colonnes
			if (Grille(l, c) ~= 0)
				Texte =			Texte + JEU.Pieces(JEU.Numeros(Grille(l, c), 1)).Lettre
			else
				Texte =			Texte + JEU.CONSOLE.PasDeLettre
			end
		end
		
		Texte =					Texte + JEU.CONSOLE.Saut1Ligne
	end
end
function Texte = typographier2Grilles(Grille1, Grille2)
	global JEU
	
	Texte =						''
	
	for l = 1:JEU.Lignes
		for c = 1:JEU.Colonnes
			if (Grille1(l, c) ~= 0)
				Texte =			Texte + JEU.Pieces(JEU.Numeros(Grille1(l, c), 1)).Lettre
			else
				Texte =			Texte + JEU.CONSOLE.PasDeLettre
			end
		end
		
		Texte =					Texte + JEU.CONSOLE.Intervalle
		
		for c = 1:JEU.Colonnes
			if (Grille2(l, c) ~= 0)
				Texte =			Texte + JEU.Pieces(JEU.Numeros(Grille2(l, c), 1)).Lettre
			else
				Texte =			Texte + JEU.CONSOLE.PasDeLettre
			end
		end
		
		Texte =					Texte + JEU.CONSOLE.Saut1Ligne
	end
end

////////////////////////////////////////////////////////////////////////////////
//
//	FONCTIONS CONTROLEURS
  //
  //	Initialisation des paramètres
//
////////////////////////////////////////////////////////////////////////////////

function affecterParametresControleurs()
	global JEU
	
	// Menus de sélection
		JEU.MENU1.Etiquette =		'SélectionGrilles'
		JEU.MENU1.Nom =			'Niveaux faciles'
		JEU.MENU1.Numeros =			[        33; 34; 35; 36; 37; 38; 39; 40; ...
								 41; 42; 43; 44; 45; 46; 47; 48; 49; 50; ...
								 51; 52]
		
		JEU.MENU1.Choix =			[]
		for m = 1:1:size(JEU.MENU1.Numeros, 1)
			numero =				JEU.MENU1.Numeros(m, 1)
			nom =				donnerNiveau(numero, 'Nom')
			action =				'choisirGrille(' + string(numero) + ')'
			
			JEU.MENU1.Choix =		[JEU.MENU1.Choix; [nom, action]]
		end
		
		JEU.MENU2.Etiquette =		'SélectionGrillesB'
		JEU.MENU2.Nom =			'Niveaux difficiles'
		JEU.MENU2.Numeros =			[        53; 54; 55; 56; 57; 58; 59; 60; ...
								 61; 62; 63; 64; 65; 66; 67; 68; 69; 70; ...
								 71; 72                                  ]
		
		JEU.MENU2.Choix =			[]
		for m = 1:1:size(JEU.MENU2.Numeros, 1)
			numero =				JEU.MENU2.Numeros(m, 1)
			nom =				donnerNiveau(numero, 'Nom')
			action =				'choisirGrille(' + string(numero) + ')'
			
			JEU.MENU2.Choix =		[JEU.MENU2.Choix; [nom, action]]
		end
		
		JEU.MENU3.Etiquette =		'SélectionNombreIterations'
		JEU.MENU3.Nom =			'Maximum d''itérations'
		JEU.MENU3.Choix =			[' 1000',  'choisirMaximumIterations(1000)';	...
								 ' 5000',  'choisirMaximumIterations(5000)';	...
								 '10000', 'choisirMaximumIterations(10000)';	...
								 '50000', 'choisirMaximumIterations(50000)'	]
		
		JEU.MENU4.Etiquette =		'SélectionSolution'
		JEU.MENU4.Nom =			'Solutions trouvées'
	
	// Boutons de contrôle
		largeurEspace =			1/JEU.BOUTONS.Nombre
		hauteurEspace =			1/JEU.BOUTONS.Nombre	
		xEspace =					((1:JEU.BOUTONS.Nombre) - 1)*largeurEspace
		yEspace =					((1:JEU.BOUTONS.Nombre) - 1)*hauteurEspace
		
		coeffMarge =				1/10
		
		xBouton =					xEspace + coeffMarge*largeurEspace
		yBouton =					yEspace + coeffMarge*hauteurEspace
		largeurBouton =			(1 - 2*coeffMarge)*largeurEspace
		hauteurBouton =			(1 - 2*coeffMarge)*hauteurEspace
		
		JEU.BOUTON1.Etiquette =		'ControleurResolution'
		JEU.BOUTON1.Unites =		JEU.BOUTONS.Unites
		JEU.BOUTON1.Position =		[xBouton(5), yBouton(5), largeurBouton, hauteurBouton]
		JEU.BOUTON1.CouleurRVB =		JEU.BOUTONS.CouleurRVB
		JEU.BOUTON1.TaillePolice =	JEU.BOUTONS.TaillePolice
		JEU.BOUTON1.Titre =			'Recherche'
		JEU.BOUTON1.Relief =		'raised'
		JEU.BOUTON1.Action =		'resoudreGrille()'
		
		JEU.BOUTON2.Etiquette =		'ControleurAffichageBase'
		JEU.BOUTON2.Unites =		JEU.BOUTONS.Unites
		JEU.BOUTON2.Position =		[xBouton(5), yBouton(4), largeurBouton, hauteurBouton]
		JEU.BOUTON2.CouleurRVB =		JEU.BOUTONS.CouleurRVB
		JEU.BOUTON2.TaillePolice =	JEU.BOUTONS.TaillePolice
		JEU.BOUTON2.Titre =			'Problèmes'
		JEU.BOUTON2.Relief =		'raised'
		JEU.BOUTON2.Action =		'afficherBaseGrilles()'
		
		JEU.BOUTON3.Etiquette =		'ControleurEdition'
		JEU.BOUTON3.Unites =		JEU.BOUTONS.Unites
		JEU.BOUTON3.Position =		[xBouton(5), yBouton(3), largeurBouton, hauteurBouton]
		JEU.BOUTON3.CouleurRVB =		JEU.BOUTONS.CouleurRVB
		JEU.BOUTON3.TaillePolice =	JEU.BOUTONS.TaillePolice
		JEU.BOUTON3.Titre =			'Edition'
		JEU.BOUTON3.Relief =		'flat'
		JEU.BOUTON3.Action =		''
		
		JEU.BOUTON5.Etiquette =		'ControleurSortie'
		JEU.BOUTON5.Unites =		JEU.BOUTONS.Unites
		JEU.BOUTON5.Position =		[xBouton(5), yBouton(1), largeurBouton, hauteurBouton]
		JEU.BOUTON5.CouleurRVB =		JEU.BOUTONS.CouleurRVB
		JEU.BOUTON5.TaillePolice =	JEU.BOUTONS.TaillePolice
		JEU.BOUTON5.Titre =			'Sortie'
		JEU.BOUTON5.Relief =		'raised'
		JEU.BOUTON5.Action =		'sortir()'
	
	// États
		JEU.ETAT.SELECTION =		10 // grille incomplète sélectionnée
		JEU.ETAT.CONTRADICTOIRE =	11
		JEU.ETAT.RECHERCHE =		20 // résolution en cours
		JEU.ETAT.BLOQUE =			21 // pas de progrès dans la levée d'incertitude entre deux itérations
		JEU.ETAT.RESOLU =			22
	
	// Paramètres de la partie
		JEU.NumeroNiveauDefaut =		46
		JEU.NumeroNiveau =			JEU.NumeroNiveauDefaut
		JEU.GrilleIncomplete =		convertirGrille(donnerNiveau(JEU.NumeroNiveau, 'Valeur'))
		
		JEU.MaximumEvaluationsDefaut = 5000
		JEU.MaximumEvaluations =		JEU.MaximumEvaluationsDefaut
		
		JEU.PeriodeAffichage =		10
		JEU.PeriodeAffichage =		1
		
		JEU.Pause =				1000
		JEU.PauseCourte =			100	
end

function choisirGrille(numero)
	global JEU
	
	JEU.NumeroNiveau =				numero
	JEU.GrilleIncomplete =			convertirGrille(donnerNiveau(numero, 'Valeur'))
	
	mettreAJourDamier(JEU.GrilleIncomplete)
	//mettreAJourConsole(JEU.ETAT.SELECTION, JEU.GrilleIncomplete)
end
function choisirMaximumIterations(maximumIterations)
	global JEU
	
	JEU.MaximumEvaluations =			maximumIterations
end
function choisirSolution(numeroSolution)
	global JEU
	
	grille =						JEU.SOLUTIONS(:, :, numeroSolution)
	
	mettreAJourDamier(grille)
end

function resoudreGrille()
	global JEU
	
	mettreAJourMenu(JEU.ETAT.RECHERCHE)
	
	JEU.SOLUTIONS =				[]
	JEU.Evaluations =				0
	JEU.ProfondeurRecursive =		0
	
	chercherPiecesJouables(JEU.GrilleIncomplete)
	JEU.GrilleResolue =				resoudreRecursivement(JEU.GrilleIncomplete)
	
	mettreAJourMenu(JEU.ETAT.RESOLU)
end
function afficherBaseGrilles()
	global JEU
	
	numeroMin =					donnerNiveau(0, 'numeroMin')
	numeroMax =					donnerNiveau(0, 'numeroMax')
	
	for numero = numeroMin:1:numeroMax
		JEU.GrilleSolution =		convertirGrille(donnerNiveau(numero, 'Valeur'))
		mettreAJourDamier(JEU.GrilleSolution)
		sleep(JEU.Pause)
	end
end
function sortir()
	xdel(winsid())
end

////////////////////////////////////////////////////////////////////////////////
//
//	LANCEMENT
//
////////////////////////////////////////////////////////////////////////////////

affecterParametresModele()
affecterParametresVues()
affecterParametresControleurs()

creerInterface()