using System;
using System.Collections.Generic;
using System.Text;

namespace SudokuProc
{
	class Program
	{
		private static Random randomG = new Random();
		static int[,] Grille = new int[9, 9];
		static bool[,] Verrou = new bool[9, 9];
		static bool[,] verrouUtilisateur = new bool[9, 9];
		static bool GameStarted = false;
		static bool modeFacile;
		static bool[,] Suggested = new bool[9,9];
		static int[,] Suggestion = new int[9,9];
		static int[,] Historique = new int[500,3];	//Historique de toutes les actions durant la partie
													//[x,0]=ligne [x,1]=colonne [x,2]=chiffre
		static int nbActions;					//nombre d'actions totales de l'utilisateur durant la partie
		static bool[,] Change = new bool[9, 9];			//Cases qui ont changé après résolution de l'impasse

		static void Main(string[] args)
		{
			//Initialisation de la fenêtre
			Console.Clear();
			Console.Title = "TP1 - Sudoku!";
			Console.SetWindowSize(120, 50);

			//intro
			Console.WriteLine("*********************TP1 - Sudoku!*********************\n");
			while (true)
			{
				AfficherMenu();
				if (GameStarted)
				{
					switch (EntreeChoix(1, 7))
					{
						case 1: //Continuer la partie
							Jouer();
							break;
						case 2: //Ecrire une solution
							GenererGrille(0, verrouUtilisateur);
							AfficherGrille();
							NettoyerGrille(verrouUtilisateur);
							Console.WriteLine("Appuyez sur une touche pour continuer...");
							Console.ReadLine();
							Jouer();
							break;
						case 3:	//reset la grille
							ResetGrille();
							Jouer();
							break;
						case 4: //Voir l'historique des coups joués
							VoirHistorique();
							Jouer();
							break;
						case 5: //Nouvelle partie, Jeu normal
							InitialiserGrille();
							modeFacile = false;
							Jouer();
							break;
						case 6: //Nouvelle partie, Jeu facile
							InitialiserGrille();
							modeFacile = true;
							Jouer();
							break;
						case 7: //Quitter
							Console.WriteLine("Merci d'avoir jouer à TP1 - Sudoku!");
							return;
					}
				}
				else
				{
					switch (EntreeChoix(1, 3))
					{
						case 1: //Jeu normal
							InitialiserGrille();
							modeFacile = false;
							Jouer();
							break;
						case 2: //Jeu facile
							InitialiserGrille();
							modeFacile = true;
							Jouer();
							break;
						case 3: //Quitter
							Console.WriteLine("Merci d'avoir jouer à TP1 - Sudoku!");
							return;
					}
				}
				//### Ajouter une exception ici
			}

		}


		/// <summary>
		/// Affiche un menu
		/// </summary>
		static void AfficherMenu()
		{
			if (GameStarted)
			{
				Console.WriteLine("1) Continuer la partie");
				Console.WriteLine("2) Écrire une solution à la partie en cours");
				Console.WriteLine("3) Reset la grille");
				Console.WriteLine("4) Voir l'historique des coups joués");
				Console.WriteLine("5) Démarrer une nouvelle partie");
				Console.WriteLine("6) Démarrer une nouvelle partie en mode facile");
				Console.WriteLine("7) Quitter");
			}
			else
			{
				Console.WriteLine("1) Démarrer une nouvelle partie");
				Console.WriteLine("2) Démarrer une nouvelle partie en mode facile");
				Console.WriteLine("3) Quitter");
			}
			Console.Write("Votre choix : ");
		}
		/// <summary>
		/// Lis un chiffre entré par l'utilisateur
		/// </summary>
		/// <param name="p_Min">Borne inférieur, inclusive, 1+</param>
		/// <param name="p_Max">Borne supérieure, inclusive</param>
		/// <returns>La valeur entrée</returns>
		static int EntreeChoix(int p_Min, int p_Max)
		{
			int chiffre;
			
			while (true)
			{
				chiffre = Convert.ToInt32(Console.ReadLine(),10);

				if (chiffre == 0)
				{
					//Entrée invalide
					Console.WriteLine("Vous devez entrer un chiffre entre {0} et {1}.", p_Min, p_Max);
				}
				else 
				{
					if ((chiffre >= p_Min) && (chiffre <= p_Max))
					{
						return chiffre;
					}
					else
					{
						//Chiffre hors limites
						Console.WriteLine("La valeur entrée doit être entre {0} et {1}.", p_Min, p_Max);
					}
					
				}

			}
		}
		/// <summary>
		/// Génère un grille de départ puis cacher des cases. 
		/// </summary>
		static void InitialiserGrille()
		{
			//Initialisation des tables
			for (int i = 0; i < 9; i++)
			{
				for (int j = 0; j < 9; j++)
				{
					Grille[i, j] = 0;
					Verrou[i, j] = false; //Dévérouiller toutes les cases. Nécessaire pour la génération de grille.
					verrouUtilisateur[i, j] = false;
				}
			}
			GenererGrille(0,Verrou);
			CacherCases();
			
			//verrouUtilisateur doit correspondre au Verrou en debut de partie
			for (int i = 0; i < 9; i++)
			{
				for (int j = 0; j < 9; j++)
				{
					verrouUtilisateur[i, j] = Verrou[i, j];
				}
			}

			//Remettre l'historique a 0
			for (int i = 0; i < 500; i++)
			{
				Historique[i, 0] = 0;
				Historique[i, 1] = 0;
				Historique[i, 2] = 0;
			}
			nbActions = 0;

		}
		/// <summary>
		/// Fonction récursive. Place des numeros dans la grille 
		/// pour obtenir une grille de sudoku valide.
		/// </summary>
		/// <param name="p_compteur">Itérateur pour indiquer la case où l'on est rendu. Mettre 
		/// a 0 pour commencer du début.</param>
		/// <param name="p_verrou">Tableau indiquant les cases à ne pas modifier</param>
		/// <returns>TRUE une valeur à été placée avec succès. FALSE si les posibilités sont épuisées sans succès.</returns>
		static bool GenererGrille(int p_compteur, bool[,] p_verrou)
		{
			//Condition de sortie
			if (p_compteur == 81)
			{
				return true;
			}

			int rangee = p_compteur / 9;
			int col = p_compteur % 9;
			int numChoisi;
			bool[] utilise = new bool[9];
			int essais = 0;

			do
			{
				while (true)
				{
					if (essais == 9) //Tout les nombre ont été essayé
					{
						if (!p_verrou[rangee, col])
						{
							Grille[rangee, col] = 0;
						}
						return false;
					}
					if (p_verrou[rangee, col])
					{
						//Si la case est vérouillée, on enregistre le nombre d'essai à 9. 
						//Tout les nombres ont été essayé. Le programme considère alors 
						//qu'il n'y a pas de modification possible.
					    essais = 9;
					    break;
					}
					else
					{
						do
						{
							numChoisi = randomG.Next(1, 10);
						} while (utilise[numChoisi - 1]);
						utilise[numChoisi - 1] = true; //vérouille le nombre selectionner pour qu'il ne soit pas réutilisé.
						essais++;
						if (Check(rangee, col, numChoisi) == 0)
						{
							Grille[rangee, col] = numChoisi;
							break;
						}
					}
				}
			} while (!GenererGrille(p_compteur + 1, p_verrou));
			return true;
		}

		/// <summary>
		/// 
		/// </summary>
		/// <param name="position"></param>
		/// <returns></returns>
		static bool GenGrid(int position)
		{
			Random NumRand = new Random();

			int num;
			int line = position / 9;
			int col = position % 9;

			num = NumRand.Next(1, 10);
			for (int i = 0; i < 9; ++i)
			{
				/* Si le nombre est valide pour la grille, l'inscrire dans la
				 * grille et appeler GenGrille de nouveau en incrementant la 
				 * position. Sinon, essayer un autre chiffre. */
				if (Check(line, col, num) == 0)
				{
					if (position == 80)
					{
						Grille[line, col] = num;
						return true;
					}
					else
					{
						Grille[line, col] = num;
						if (GenGrid(position + 1) == true)
						{
							return true;
						}
						else
						{
							Grille[line, col] = 0;
						}
					}
				}
				/* Si le numero est 9, le mettre a 1, sinon l'incrementer pour le prochain essai */
				if (num == 9)
				{
					num = 1;
				}
				else
				{
					++num;
				}
			}
			return false;	//Tous les chiffres de 1 a 9 ont ete essayes sans succes.
		}

		/// <summary>
		/// Cache des cases au hasard dans la grille et vérouille le reste.
		/// </summary>
		static void CacherCases()
		{
			int casesCache = 0;
			int casesACacher;
			int line;
			int col;

			//On vérouille toutes les case, on va ensuite dévérouiller les cases où on cache des chiffres.
			for (int i = 0; i < 9; i++)
			{
				for (int j = 0; j < 9; j++)
				{
					Verrou[i, j] = true;
				}
			}

			for (int regionH = 0; regionH < 9; regionH = regionH + 3) //Bloc de 3 ligne
			{
				for (int regionV = 0; regionV < 9; regionV = regionV + 3) //Bloc de 3 colonnes
				{
					casesCache = 0;
					casesACacher = randomG.Next(4, 8);
					while (casesCache != casesACacher)
					{
						line = randomG.Next(0, 3) + regionH;
						col = randomG.Next(0, 3) + regionV;
						if (Verrou[line, col]) //Ignorer si la case est dévérouillée, donc déja cachée
						{
							Grille[line, col] = 0;
							casesCache++;
							Verrou[line, col] = false;
						}
					}
				}
			}
		}	
		/// <summary>
		/// Vérifie si un chiffre peut être placer dans une certaine case selon les règles du Sudoku
		/// </summary>
		/// <param name="p_Ligne">Ligne de la case</param>
		/// <param name="p_Col">Colonne de la case</param>
		/// <param name="p_Nombre">Valeur à vérifier</param>
		/// <returns>0 si possible, 1 si erreur dans la région, 2 si erreur dans la ligne, 3 si erreur dans la colonne</returns>
		static int Check(int p_Ligne, int p_Col, int p_Nombre)
		{
			//check la region 3x3
			int regionV = (p_Ligne - (p_Ligne % 3));
			int regionH = (p_Col - (p_Col % 3));
			for (int i = regionV; i < regionV + 3; i++)
			{
				for (int j = regionH; j < regionH + 3; j++)
				{
					if (Grille[i, j] == p_Nombre)
						return 1;
				}
			}

			//check ligne
			for (int i = 0; i < 9; i++)
			{
				if (Grille[p_Ligne, i] == p_Nombre)
					return 2;
			}

			//check colonne
			for (int i = 0; i < 9; i++)
			{
				if (Grille[i, p_Col] == p_Nombre)
					return 3;
			}

			//Réussi
			return 0;
		}
		/// <summary>
		/// Lit et enregistre les modification à la grille de jeu.
		/// </summary>
		/// <param name="facile">TRUE pour le mode facile</param>
		static void Jouer()
		{
			int line;
			int col;
			int valeurEntre;			
			char[] delimiterChars = { ' ', ',', '.', ':', '\t', ';' };
			string[] Valeurs;
			bool gridFull = false;	//flag qui indique que toutes les cases sont occupees, partie terminee

			GameStarted = true;	//partie en cours
			Console.WriteLine("\nVoici votre grille : \n");

			//Boucler jusqu'a ce que toutes les cases soient occupees
			while (!gridFull)
			{
				AfficherGrille();
				Console.WriteLine("Que voulez-vous modifier? (ligne, colonne, valeur) \"Enter\" pour retourner au menu, \"s\" pour suggerer une action, \"d\" pour défaire la dernière action");
				Valeurs = Console.ReadLine().Split(delimiterChars);

				//L'utilisateur a appuye sur "Enter", retourner au menu
				if (Valeurs[0] == "")
				{
					return;
				}
				////L'utilisateur desire retourner au menu
				//if((Valeurs[0] == "m")||(Valeurs[0] == "M"))
				//{
				//    return;
				//}

				//L'utilisateur veut defaire la derniere action
				else if((Valeurs[0] == "d") || (Valeurs[0] == "D"))
				{
					undo();
					continue;
				}
				//L'utilisateur desire une suggestion pour sa prochaine action
				else if ((Valeurs[0] == "s") || (Valeurs[0] == "S"))
				{
				    SuggestMove();
					continue;
				}

				line = Convert.ToInt32(Valeurs[0])-1;
				col = Convert.ToInt32(Valeurs[1])-1;
				valeurEntre = Convert.ToInt32(Valeurs[2]);

				//verifier si les chiffres entres sont corrects
				if ((line < 0) || (line > 8) || (col < 0) || (col > 8) || (valeurEntre < 0) || (valeurEntre > 9))
				{
					Console.ForegroundColor = ConsoleColor.Red;
					Console.WriteLine("\n-- Une des valeurs entrees est incorrecte\n");
					Console.ResetColor();
					continue;
				}

				EnregistrerNombre(line, col, valeurEntre);

				//Verifier si toutes les cases sont remplies
				gridFull = true;
				for (int i = 0; i < 9; ++i)
				{
					for (int j = 0; j < 9; ++j)
					{
						if (Grille[i, j] == 0)
						{
							gridFull = false;
						}
					}
				}
			}
			//Cases toutes occupees, fin de la partie
			AfficherGrille();
			Console.WriteLine("Bravo! Vous avez completé la grille!");
		}

		/// <summary>
		/// Vérifie si une case est disponible et y enregistre la valeur spécifiée.
		/// </summary>
		/// <param name="line">Ligne de la case</param>
		/// <param name="col">Colonne de la case</param>
		/// <param name="valeurEntre">Valeur à entrer</param>
		static void EnregistrerNombre(int line, int col, int valeurEntre)
		{
			int resultatCheck;
			int temp;

			//Si la case ne contient pas une variable de départ (verrouillée)
			if (!Verrou[line, col])
			{
				resultatCheck = Check(line, col, valeurEntre); //Verifier si la valeur est valide pour cette case

				//Retirer la valeur dans la case si l'utilisateur a entré comme valeur '0'
				if (valeurEntre == 0)
				{
					//enregistrer l'etat de la case dans l'historique avant de la modifier
					Historique[nbActions, 0] = line;
					Historique[nbActions, 1] = col;
					Historique[nbActions, 2] = Grille[line, col];
					++nbActions;

					Grille[line, col] = valeurEntre;
					verrouUtilisateur[line, col] = false;
				}
				//Si la valeur est valide pour cette case
				else if (resultatCheck == 0)
				{
					temp = Grille[line, col];

					//enregistrer l'etat de la case dans l'historique avant de la modifier
					Historique[nbActions, 0] = line;
					Historique[nbActions, 1] = col;
					Historique[nbActions, 2] = Grille[line, col];
					++nbActions;

					Grille[line, col] = valeurEntre;
					verrouUtilisateur[line, col] = true;

					if (modeFacile)
					{
						//Verifier s'il est possible de completer la grille avec la valeur entree
						//Si non, remettre l'ancienne valeur (temp), deverouiller la case, decrementer
						// le nombre de cases occupees et afficher une erreur
						if (!GenererGrille(0, verrouUtilisateur))
						{
							Grille[line, col] = temp;
							verrouUtilisateur[line, col] = false;
							AfficherErreur(5);

							//decrementer le nombre d'actions
							--nbActions;
						}

						//Enlever les valeurs ajoutees a Grille[,] par la fonction GenererGrille()
						//Toutes les cases non verrouillees sont remises a 0
						NettoyerGrille(verrouUtilisateur);
					}
				}
				//Valeur invalide pour la case (meme valeur sur la ligne, colonne ou region
				else
				{
					AfficherErreur(resultatCheck);
				}
			}
			else
			{
				AfficherErreur(4);	//Erreur, case verrouillée (case de départ)
			}
		}
		/// <summary>
		/// Affiche la grille de jeu
		/// </summary>
		static void AfficherGrille()
		{
			//En-tête
			Console.WriteLine("      1     2     3     4     5     6     7     8     9   ");
			Console.WriteLine("   -------------------------------------------------------");

			//Lignes
			for (int i = 0; i < 9; i++)
			{
				Console.Write("   |");
				for (int j = 0; j < 9; j++)
				{
					EcrireCaseLigneVide(i,j);					
				}
				Console.WriteLine();
				
				Console.Write(" {0} |", i + 1);
				for (int j = 0; j < 9; j++)
				{					
					if ((j == 2) || (j == 5)) //Case adjacente à un séparateur vertical
					{
						EcrireCaseAdj(i, j);
					}
					else //Autre case
					{
						EcrireCaseAutre(i, j);
					}
				}
				Console.WriteLine();

				Console.Write("   |");
				for (int j = 0; j < 9; j++)
				{
					EcrireCaseLigneVide(i, j);
				}
				Console.WriteLine();

				//Séparateur de bloc horizontal
				if ((i == 2) || (i == 5))
				{
					Console.WriteLine("   *******************************************************");
				}
				else
				{
					if (i == 8) //Dernière ligne
					{
						Console.WriteLine("   -------------------------------------------------------");
					}
					else
					{
						Console.WriteLine("   ------------------#-----------------#------------------");
					}
				}
			}
		}

		/// <summary>
		/// Afficher une partie de case sur une ligne sans chiffres
		/// </summary>
		/// <param name="i">le numéro de la ligne</param>
		/// <param name="j">le numéro de la colonne</param>
		private static void EcrireCaseLigneVide(int i, int j)
		{
			if (Change[i, j])
			{
				Console.ForegroundColor = ConsoleColor.Yellow;
				Console.Write("-----");
				Console.ResetColor();
				if ((j == 2) || (j == 5))
				{
					Console.Write("#");
				}
				else
				{
					Console.Write("|");
				}

			}
			else
			{
				if ((j == 2) || (j == 5))
				{
					Console.Write("     #");
				}
				else
				{
					Console.Write("     |");
				}
			}
		}
		/// <summary>
		/// Écrit une case adjacente à un séparateur vertical
		/// </summary>
		/// <param name="i">le numéro de la ligne</param>
		/// <param name="j">le numéro de la colonne</param>
		static void EcrireCaseAdj(int i, int j)
		{
			if (Grille[i, j] == 0) //Case non modifiée
			{
				if (Change[i, j]) //Case a changer pour resoudre une impasse
				{
					Console.ForegroundColor = ConsoleColor.Yellow;
					Console.Write("|   |");
					Console.ResetColor();
					Console.Write("#");
				}
				else  //Laisser la case blanche
				{
					Console.Write("     #", Grille[i, j]);
				}
			}
			else //Une valeur y est entrée
			{
				if (Verrou[i, j]) //Valeur de départ vérouillée
				{
					Console.ForegroundColor = ConsoleColor.Green;
					Console.Write(" [{0}] ", Grille[i, j]);
					Console.ResetColor();
					Console.Write("#");
				}
				else if (Suggested[i, j]) //Valeur suggérée (Rouge)
				{
					Console.ForegroundColor = ConsoleColor.Red;
					Console.Write(" ({0}) ", Suggestion[i, j]);
					//Console.Write(" ({0}) ", Grille[i, j]);
					Console.ResetColor();
					Console.Write("#");
				} 
				else if (Change[i, j])
				{
					Console.ForegroundColor = ConsoleColor.Yellow;
					Console.Write("| {0} |", Grille[i, j]);
					Console.ResetColor();
					Console.Write("#");
				}
				else //Valeur entrée par l'utilisateur
				{
					Console.ForegroundColor = ConsoleColor.Cyan;
					Console.Write("  {0}  ", Grille[i, j]);
					Console.ResetColor();
					Console.Write("#");
				}
			}
		}
		/// <summary>
		/// Écrit une case qui n'est pas adjacente à un séparateur
		/// </summary>
		/// <param name="i">le numéro de la ligne</param>
		/// <param name="j">le numéro de la colonne</param>
		static void EcrireCaseAutre(int i, int j)
		{
			if (Grille[i, j] == 0) //Case non modifiée
			{				
				if (Change[i, j]) //Case a changer pour resoudre une impasse
				{
					Console.ForegroundColor = ConsoleColor.Yellow;
					Console.Write("|   |");
					Console.ResetColor();
					Console.Write("|");
				}
				else //Laisser la case blanche
				{
					Console.Write("     |", Grille[i, j]);
				}
			}
			else //Une valeur y est entrée
			{
				if (Verrou[i, j]) //Valeur de départ vérouillée
				{
					Console.ForegroundColor = ConsoleColor.Green;
					Console.Write(" [{0}] ", Grille[i, j]);
					Console.ResetColor();
					Console.Write("|");
				}
				else if (Suggested[i, j]) //Valeur suggérée (Rouge)
				{
					Console.ForegroundColor = ConsoleColor.Red;
					Console.Write(" ({0}) ", Suggestion[i, j]);
					//Console.Write(" ({0}) ", Grille[i, j]);
					Console.ResetColor();
					Console.Write("|");
				}
				else if (Change[i, j]) //Case a changer pour resoudre une impasse
				{
					Console.ForegroundColor = ConsoleColor.Yellow;
					Console.Write("| {0} |", Grille[i, j]);
					Console.ResetColor();
					Console.Write("|");
				}
				else //Valeur entrée par l'utilisateur
				{
					Console.ForegroundColor = ConsoleColor.Cyan;
					Console.Write("  {0}  ", Grille[i, j]);
					Console.ResetColor();
					Console.Write("|");
				}
			}
		}
		/// <summary>
		/// Affiche des message d'erreurs au hasard
		/// </summary>
		/// <param name="type">Type d'erreur: 1. Région 2.Ligne 3.Colonne 4.Case vérouill 5.Impossible de completer</param>
		static void AfficherErreur(int type)
		{
			//Message en rouge
			Console.ForegroundColor = ConsoleColor.Red;

			if (type == 1) //Valeur déja dans la région
			{
				switch (randomG.Next(1, 5))
				{
					case 1:
						Console.WriteLine("\n-- Cette valeur est déja dans la région!\n");
						break;
					case 2:
						Console.WriteLine("\n-- Attention! Vous ne pouvez pas placer cette valeur ici! Vérifiez la région.\n");
						break;
					case 3:
						Console.WriteLine("\n-- Ce chiffre ne peut pas être placé ici! Il est déja dans la région.\n");
						break;
					case 4:
						Console.WriteLine("\n-- Ce chiffre est déja placé dans la région.\n");
						break;
				}
			}
			if (type == 2) //Valeur déja dans la ligne
			{
				switch (randomG.Next(1, 5))
				{
					case 1:
						Console.WriteLine("\n-- Vérifier la ligne, cette valeur y est déja.\n");
						break;
					case 2:
						Console.WriteLine("\n-- Ce chiffre est déja sur cette ligne.\n");
						break;
					case 3:
						Console.WriteLine("\n-- Attention, vous ne pouvez pas placer deux fois le même chiffre sur la même ligne.\n");
						break;
					case 4:
						Console.WriteLine("\n-- Vous ne pouvez pas écrire ce chiffre ici, il est déja dans la ligne.\n");
						break;
				}
			}
			if (type == 3) //Valeur déja dans la colonne
			{
				switch (randomG.Next(1, 5))
				{
					case 1:
						Console.WriteLine("\n-- Cette valeur est déja dans la colonne.\n");
						break;
					case 2:
						Console.WriteLine("\n-- Vous ne pouvez pas placer deux fois le même chiffre dans la même colonne.\n");
						break;
					case 3:
						Console.WriteLine("\n-- Ce chiffre ne peut pas être écrit ici, il est déja dans la colonne.\n");
						break;
					case 4:
						Console.WriteLine("\n-- Ce chiffre est déja placé dans la colonne.\n");
						break;
				}
			}
			if (type == 4) //Case vérouillée
			{
				switch (randomG.Next(1, 6))
				{
					case 1:
						Console.WriteLine("\n-- Vous ne pouvez pas modifier cette case!\n");
						break;
					case 2:
						Console.Write("\n-- Vous ne pouvez pas modifier les cases avec des ");
						Console.ForegroundColor = ConsoleColor.Green;
						Console.Write("[ ]");
						Console.ForegroundColor = ConsoleColor.Red;
						Console.WriteLine(".\n");
						break;
					case 3:
						Console.WriteLine("\n-- Cette case à été verouillée pour votre sécurité.\n");
						break;
					case 4:
						Console.WriteLine("\n-- Cette case est vérouillée!\n");
						break;
					case 5:
						Console.WriteLine("\n-- Vous ne pouvez pas modifier les cases de départ.\n");
						break;
					default:
						break;
				}
			} 
			if (type == 5) //Pas de solution possible (Mode facile)
			{
				switch (randomG.Next(1, 4))
				{
					case 1:
						Console.WriteLine("\n-- Aucune solution possible avec cette valeur!\n");
						break;
					case 2:
						Console.WriteLine("\n-- Cette valeur vous empecherais de completer la grille.\n");
						break;
					case 3:
						Console.WriteLine("\n-- Vous ne pouvez pas placer ce chiffre ici, il n'y a aucune solution possible.\n");
						break;
				}
			}

			Console.ResetColor();
		}

		static void undo()
		{
			if (nbActions == 0)
			{
				Console.ForegroundColor = ConsoleColor.Red;
				Console.WriteLine("\n-- Aucune action n'as encore été prise !\n");
				Console.ResetColor();
				return;
			}
			--nbActions;
			int line = Historique[nbActions,0];
			int col = Historique[nbActions,1];

			Grille[line, col] = Historique[nbActions, 2];
			if (Grille[line, col] == 0)
			{
				verrouUtilisateur[line, col] = false;
			}
			else
			{
				verrouUtilisateur[line, col] = true;
			}
		}

		/// <summary>
		/// Suggere une action a l'utilisateur
		/// </summary>
		static void SuggestMove()
		{
			int[] positions= new int[81];	//Positions dans la Grille qui sont vides
			int count=0;					//nombre de positions trouvees
			int randPosition;				//Position au hasard dans une des positions vides trouvees
			int caseVideChoisie;
			bool[,] verrouSugg = new bool[9, 9];
			
			//Obtenir les positions
			for (int i = 0; i < 9; ++i)
			{
				for (int j = 0; j < 9; ++j)
				{
					if (Grille[i, j] == 0)
					{
						positions[count] = i * 9 + j;
						++count;
					}
					//initialiser le verrou de suggestions
					verrouSugg[i, j] = verrouUtilisateur[i, j];
				}
			}

			while (true)
			{
				if(!GenererGrille(0, verrouSugg))
				{
					Console.ForegroundColor = ConsoleColor.Red;
					Console.WriteLine("\n-- Il est impossible de completer la grille avec les valeurs entrees presentement\n");
					Console.ResetColor();
					NettoyerGrille(verrouUtilisateur);
					ResoudreImpasse();
					return;
				}
				else
				{
					//AfficherGrille();
					//GenererGrille(0, verrouUtilisateur);
					randPosition = randomG.Next(0, count);		//position random dans positions[]
					caseVideChoisie = positions[randPosition];	//Case vide choisie
					Suggestion[caseVideChoisie / 9, caseVideChoisie % 9] = Grille[caseVideChoisie / 9, caseVideChoisie % 9];
					Suggested[caseVideChoisie / 9, caseVideChoisie % 9] = true;
					verrouSugg[caseVideChoisie / 9, caseVideChoisie % 9] = true;

					//On retire la valeur utilisée
					positions[randPosition] = positions[count-1];
					--count;

					NettoyerGrille(verrouSugg);
					AfficherGrille();

					if (count == 0) //Toute la grille est suggérée
					{
						Console.WriteLine("La grille est pleine!");
						Console.WriteLine("Appuyer sur une touche pour continuer...");
						Console.ReadLine();
						EnregistrerSug();
						return;
					}

					while (true)
					{
						Console.WriteLine("Suggerer une autre action ? (y/n)");
						string reponse = Console.ReadLine();
						if (reponse == "y")
						{
							break;
						}
						else if (reponse == "n")
						{
							EnregistrerSug();						
							return;
						}
						else
						{
							Console.WriteLine("Reponse incorrecte");
						}
					}
				}
			}
		}

		/// <summary>
		/// Enregistre les suggestion et initialise le tableau de suggestion
		/// </summary>
		static void EnregistrerSug()
		{
			while (true)
			{
				Console.WriteLine("Voulez-vous conserver les suggestions? (y/n)");
				string reponse = Console.ReadLine();
				if (reponse == "y")
				{
					for (int i = 0; i < 9; ++i)
					{
						for (int j = 0; j < 9; ++j)
						{
							if (Suggested[i, j])
							{
								//enregistrer l'etat de la case dans l'historique avant de la modifier
								Historique[nbActions, 0] = i;
								Historique[nbActions, 1] = j;
								Historique[nbActions, 2] = 0;
								++nbActions;

								verrouUtilisateur[i, j] = true;
								Grille[i, j] = Suggestion[i, j];
							}
						}
					}
					break;
				}
				else if (reponse == "n")
				{
					break;
				}
				else
				{
					Console.WriteLine("Reponse incorrecte");
				}
			}

			//Remettre toutes les cases de Suggested[] a false
			for (int i = 0; i < 9; ++i)
			{
				for (int j = 0; j < 9; ++j)
				{
					Suggested[i, j] = false;
				}
			}
		}
		
		static void ResoudreImpasse()
		{
			int[,] backupGrille = new int[9, 9];			//Backup de la grille
			bool[,] backupVerrou = new bool[9, 9];		//Backup de verrouUtilisateur
			//int[,] bufferResolution = new int[9, 9];	//Grille resolue
			string reponse;								//reponse aux questions
			int nbActionsDefaites = 0;					//Nombre de fois qu'on retourne en arriere
														//pour corriger l'impasse
			while (true)
			{
				Console.WriteLine("Voulez-vous retourner en arrière pour voir ce qui a causé l'impasse? (y/n)");
				reponse = Console.ReadLine();
				if (reponse == "n")
				{
					return;
				}
				else if(reponse == "y")
				{
					/* Faire un backup de la grille et du verrou utilisateur */
					for (int i = 0; i < 9; ++i)
					{
						for (int j = 0; j < 9; ++j)
						{
							backupGrille[i, j] = Grille[i, j];
							backupVerrou[i, j] = verrouUtilisateur[i, j];
						}
					}
					/* Aussi longtemps que la grille ne peut etre resolue avec les valeurs
					 * entrees, retourner une action en arriere et essayer encore */
					for (int i = 0; !GenererGrille(0, verrouUtilisateur); ++i)
					{
						int line = Historique[(nbActions-1) - i, 0];
						int col = Historique[(nbActions-1) - i, 1];

						if (Historique[(nbActions-1) - i, 2] == 0)
						{
							Grille[line, col] = Historique[(nbActions-1) - i, 2];
							verrouUtilisateur[line, col] = false;
						}
						else
						{
							Grille[line, col] = Historique[(nbActions-1) - i, 2];
							verrouUtilisateur[line, col] = true;
						}
						++nbActionsDefaites;
					}
					NettoyerGrille(verrouUtilisateur);
					//la Grille[,] peut etre resolue a partir d'ici


					//Determiner quelles cases doivent etre modifiees
					for (int i = 0; i < 9; ++i)
					{
						for (int j = 0; j < 9; ++j)
						{
							if (Grille[i, j] != backupGrille[i, j])
							{
								Change[i, j] = true;
							}
						}
					}

					//Afficher la grille avec les cases qui doivent etre modifiees
					AfficherGrille();

					while (true)
					{
						Console.WriteLine("Voici l'etat du tableau tel qu'il etait la derniere fois qu'il etait resolvable");
						Console.WriteLine("Voulez-vous revenir en appliquant ces modifications? (y/n)");
						Console.WriteLine("Les cases qui seront modifiées apparaissent en jaune");
						reponse = Console.ReadLine();
						if (reponse == "y")
						{
							//Decrementer le nombre d'actions du nombre de fois qu'on retourne en arriere
							nbActions -= nbActionsDefaites;
							for (int i = 0; i < 9; ++i)
							{
								for (int j = 0; j < 9; ++j)
								{
									Change[i, j] = false;
								}
							}
							return;
						}
						else if (reponse == "n")
						{
							for (int i = 0; i < 9; ++i)
							{
								for (int j = 0; j < 9; ++j)
								{
									Grille[i, j] = backupGrille[i, j];
									verrouUtilisateur[i, j] = backupVerrou[i, j];
									Change[i, j] = false;
								}
							}
							return;
						}
						else
						{
							Console.WriteLine("Reponse incorrecte");
						}
					}
				}
				else
				{
					Console.WriteLine("Reponse incorrecte");
				}
			}
		}

		/// <summary>
		/// Remet la grille telle qu'elle etait au debut de la partie
		/// </summary>
		static void ResetGrille()
		{
			nbActions = 0;
			for (int i = 0; i < 9; i++)
			{
				for (int j = 0; j < 9; j++)
				{
					if (!Verrou[i, j])
					{
						Grille[i, j] = 0;
						verrouUtilisateur[i, j] = false;
					}
				}
			}
		}

		/// <summary>
		/// Cache les case qui ne sont pas vérouillées.
		/// (Nettoyage après avoir vérifier une solution possible)
		/// </summary>
		/// <param name="VerrouUtilisateur">Tableau de verrouillage à utiliser</param>
		static void NettoyerGrille(bool[,] Verrou)
		{
			for (int i = 0; i < 9; i++)
			{
				for (int j = 0; j < 9; j++)
				{
					if (!(Verrou[i,j]))
					{
						//Si la case n'est pas vérouillée, effacer la case.
						Grille[i,j] = 0;
					}
				}
			}
		}

		static void VoirHistorique()
		{
			int[,] copyGrille = new int[9, 9];
			int ligneCase;	// ligne de la case apres modification
			int colonneCase; // colonne de la case apres modification

			/* Faire une copie de la grille */
			for (int i = 0; i < 9; ++i)
			{
				for (int j = 0; j < 9; ++j)
				{
					copyGrille[i, j] = Grille[i, j];
				}
			}

			for (int i = 0; i < nbActions; ++i)
			{
				ligneCase = Historique[(nbActions-1)-i,0];
				colonneCase = Historique[(nbActions-1)-i,1];
				Console.WriteLine("{0}) Ligne: {1} Colonne: {2} Valeur: {3}", i+1, Historique[(nbActions-1)-i,0]+1, Historique[(nbActions-1)-i,1]+1, copyGrille[ligneCase,colonneCase]);
				copyGrille[ligneCase, colonneCase] = Historique[(nbActions - 1) - i, 2];
			}
			Console.WriteLine("Appuyez sur une touche pour continuer");
			Console.ReadLine();
		}
	}
}