package projet;
import java.util.Scanner;
public class Sudoku{
	//fonction principale
	public static void main(String args[]){
		int[][] tabInit = new int[9][9], tableauModifie = new int[9][9];
		int[] caseSuivante;	
		int tps,i,j,k;
		String modif2;
		char modif;
		AffichageSudoku AS;
		boolean impossible;
		//initialisation à 0 du tableau initiale et du tableau à modifier
		for (i=0; i<9; i++){
			for (j=0; j<9; j++){
				tabInit[i][j]= 0;
				tableauModifie[i][j]= 0;
			}
		}
		//entrée des coordonnés et de la valeur des cases de la grille
		modif='Y';
		while(modif=='Y'||modif=='y'){
			System.out.println("Voulez vous entrer les coordonees d'une case a modifier?(Y/N) ");
			modif2=new Scanner(System.in).nextLine();
			modif=modif2.charAt(0);
			if(modif=='Y'||modif=='N'||modif=='y'||modif=='n'){
				if(modif=='Y'||modif=='y'){
					impossible = true;
					i=0;j=0;k=0;
					while(i<1||i>10){
						System.out.println("Entrez la ligne de la case a modifier ");
						i=(new Scanner(System.in)).nextInt();
					}
					while(j<1||j>10){
						System.out.println("Entrez la colonne de la case a modifier ");
						j=(new Scanner(System.in)).nextInt();
					}
					while((k<1||k>9)&&impossible){
						System.out.println("Entrez la nouvelle valeur de la case a modifier ");
						k=(new Scanner(System.in)).nextInt();
						if(chiffrePossible(k,i-1,j-1,tableauModifie)){
							impossible=false;
						}					
					}
					tabInit[i-1][j-1]= k;
					tableauModifie[i-1][j-1]= k;
				}
			}
			else{
				modif='Y';
			}
		}
		AS = new AffichageSudoku(tableauModifie,tabInit,1);
		resolution(0,0,tableauModifie,tabInit,AS);
		AS.afficheGagne();
	}
	//fonction de verification de ligne
	public static boolean verifLigne(int i,int[][] tableauModifie){
		int j = 0,un=0,deux=0,trois=0,quatre=0,cinq=0,six=0,sept=0,huit=0,neuf=0;
		for(j=0;j<9;j++){
			if(tableauModifie[i][j]==0){
				return false;
			}
			else{
				if(tableauModifie[i][j]==1){
					un = un + 1;
				}
				else{
					if(tableauModifie[i][j]==2){
						deux = deux + 1;
					}
					else{
						if(tableauModifie[i][j]==3){
							trois = trois + 1;
						}
						else{
							if(tableauModifie[i][j]==4){
								quatre = quatre + 1;
							}
							else{
								if(tableauModifie[i][j]==5){
									cinq = cinq + 1;
								}
								else{
									if(tableauModifie[i][j]==6){
										six = six + 1;
									}
									else{
										if(tableauModifie[i][j]==7){
											sept = sept + 1;
										}
										else{
											if(tableauModifie[i][j]==8){
												huit = huit + 1;
											}
											else{
												if(tableauModifie[i][j]==9){
													neuf = neuf + 1;
												}
											}
										}
									}
								}
							}
						}
					}
				}
			}
		}
		if(un == 1 && deux == 1 && trois == 1 && quatre == 1 && cinq == 1 && six == 1 && sept == 1 && huit == 1 && neuf == 1){
			return true;
		}
		else{
			return false;
		}
	}
	//verification de colonne
	public static boolean verifColonne(int j,int[][] tableauModifie){
		int i = 0,un=0,deux=0,trois=0,quatre=0,cinq=0,six=0,sept=0,huit=0,neuf=0;
		for(i=0;i<9;i++){
			if(tableauModifie[i][j]==0){
				return false;
			}
			else{
				if(tableauModifie[i][j]==1){
					un = un + 1;
				}
				else{
					if(tableauModifie[i][j]==2){
						deux = deux + 1;
					}
					else{
						if(tableauModifie[i][j]==3){
							trois = trois + 1;
						}
						else{
							if(tableauModifie[i][j]==4){
								quatre = quatre + 1;
							}
							else{
								if(tableauModifie[i][j]==5){
									cinq = cinq + 1;
								}
								else{
									if(tableauModifie[i][j]==6){
										six = six + 1;
									}
									else{
										if(tableauModifie[i][j]==7){
											sept = sept + 1;
										}
										else{
											if(tableauModifie[i][j]==8){
												huit = huit + 1;
											}
											else{
												if(tableauModifie[i][j]==9){
													neuf = neuf + 1;
												}
											}
										}
									}
								}
							}
						}
					}
				}
			}
		}
		if(un == 1 && deux == 1 && trois == 1 && quatre == 1 && cinq == 1 && six == 1 && sept == 1 && huit == 1 && neuf == 1){
			return true;
		}
		else{
			return false;
		}
	}
	//verification carré
	public static boolean verifCarre(int i,int j, int[][] tableauModifie){
		int a = 0,b = 0,k,l,un=0,deux=0,trois=0,quatre=0,cinq=0,six=0,sept=0,huit=0,neuf=0;
		if(i==3){
		a = a + 3;
		}
		if(i==6){
		a = a + 6;
		}
		if(j==3){
		b = b + 3;
		}
		if(j==6){
		b = b+ 6;
		}
		for(k=a;k<(a+3);k++){
			for(l=b;l<(b+3);l++){
				if(tableauModifie[k][l]==0){
					return false;
				}
				else{
					if(tableauModifie[k][l]==1){
						un = un + 1;
					}
					else{
						if(tableauModifie[k][l]==2){
							deux = deux + 1;
						}
						else{
							if(tableauModifie[k][l]==3){
								trois = trois + 1;
							}
							else{
								if(tableauModifie[k][l]==4){
									quatre = quatre + 1;
								}
								else{
									if(tableauModifie[k][l]==5){
										cinq = cinq + 1;
									}
									else{
										if(tableauModifie[k][l]==6){
											six = six + 1;
										}
										else{
											if(tableauModifie[k][l]==7){
												sept = sept + 1;
											}
											else{
												if(tableauModifie[k][l]==8){
													huit = huit + 1;
												}
												else{
													if(tableauModifie[k][l]==9){
														neuf = neuf + 1;
													}
												}
											}
										}
									}
								}
							}
						}
					}
				}
				
			}
		}
		if(un == 1 && deux == 1 && trois == 1 && quatre == 1 && cinq == 1 && six == 1 && sept == 1 && huit == 1 && neuf == 1){
			return true;
		}
		else{
			return false;
		}
	}
	//verification tableau
	public static boolean verifTableau(int[][] tableauModifie){
		if(verifLigne(0,tableauModifie)&&verifLigne(1,tableauModifie)&verifLigne(2,tableauModifie)&&verifLigne(3,tableauModifie)&&verifLigne(4,tableauModifie)&&verifLigne(5,tableauModifie)&&verifLigne(6,tableauModifie)&&verifLigne(7,tableauModifie)&&verifLigne(8,tableauModifie)&&verifColonne(0,tableauModifie)&&verifColonne(1,tableauModifie)&&verifColonne(2,tableauModifie)&&verifColonne(3,tableauModifie)&&verifColonne(4,tableauModifie)&&verifColonne(5,tableauModifie)&&verifColonne(6,tableauModifie)&&verifColonne(7,tableauModifie)&&verifColonne(8,tableauModifie)&&verifCarre(0,0,tableauModifie)&&verifCarre(0,3,tableauModifie)&&verifCarre(0,6,tableauModifie)&&verifCarre(3,0,tableauModifie)&&verifCarre(3,3,tableauModifie)&&verifCarre(3,6,tableauModifie)&&verifCarre(6,0,tableauModifie)&&verifCarre(6,3,tableauModifie)&&verifCarre(6,6,tableauModifie)){
		return true;
		}
		else{
		return false;
		}
	}
	//chiffre dans la ligne
	public static boolean chiffreDansLigne(int k,int i,int[][] tableauModifie){
		boolean present=false;
		for(int j=0;j<9 && !present;j++){
			if(tableauModifie[i][j]==k){
			present=true;
			}
		}
		return present;
	}
	//chiffre dans la colonne
	public static boolean chiffreDansColonne(int k,int j,int[][] tableauModifie){
		boolean present=false;
		for(int i=0;i<9;i++){
			if(tableauModifie[i][j]==k){
			present=true;
			}
		}
		return present;
	}
	//chiffre dans le carré
	public static boolean chiffreDansCarre(int k,int i,int j,int[][] tableauModifie){
		int a = 0,b = 0,l,m;
		boolean present = false;
		if(i>=3&&i<6){
		a = a + 3;
		}
		if(i>=6){
		a = a + 6;
		}
		if(j>=3&&j<6){
		b = b + 3;
		}
		if(j>=6){
		b = b+ 6;
		}
		for(l=a;l<a+3;l++){
			for(m=b;m<b+3;m++){
				if(tableauModifie[l][m]==k){
					present = true;
				}
			}
		}
		return present;
	}
	//chiffre possible
	public static boolean chiffrePossible(int k,int i,int j,int[][] tableauModifie){
		boolean possible = false;
		if(!chiffreDansLigne(k,i,tableauModifie)&&!chiffreDansColonne(k,j,tableauModifie)&&!chiffreDansCarre(k,i,j,tableauModifie)){
			possible = true;
		}
		return possible;
	}
	//case vide dans la grille
	public static boolean caseVide(int[][] tableauModifie){
		for(int i=0;i<9;i++){
			for(int j=0;j<9;j++){
				if(tableauModifie[i][j] == 0){
				return true;
				}
			}
		}
		return false;
	}
	//Retour case précédente
	public static int[] caseAvant(int i,int j,int[][] tabInit){
		int[] caseAvant = new int[3];
		for(int l=0;l<3;l++){
			caseAvant[l] = 0;
		}
		
		if(j!=0){
			caseAvant[1] = j - 1;
			caseAvant[0] = i;
		}
		else{
			caseAvant[1] = 8;
			caseAvant[0] = i - 1;		
		}
		if(tabInit[caseAvant[0]][caseAvant[1]] != 0){
			caseAvant[2] = 1;
		}	
		return caseAvant;
	}
	//fonction retour
	public static void backTrack(int[] caseAvant,int[][] tabInit,int[][] tableauModifie,AffichageSudoku AS){
		int i,j,n;
		int[] caseSuivante;
		if(caseAvant[2] == 1){	
			backTrack(caseAvant(caseAvant[0],caseAvant[1],tabInit),tabInit,tableauModifie,AS);
		}
		else{
			i = caseAvant[0];
			j = caseAvant[1];
			caseSuivante = caseSuivante(i,j,tabInit);
			n = tableauModifie[i][j];
			if(n==9){
				tableauModifie[i][j] = 0;
				backTrack(caseAvant(i,j,tabInit),tabInit,tableauModifie,AS);
			}
			else{
				n = n + 1;
				for(int k = n; k < 10; k++){
					if(chiffrePossible(k,i,j,tableauModifie)){
						tableauModifie[i][j] = k;
						AS.refresh(tableauModifie);
						resolution(caseSuivante[0],caseSuivante[1],tableauModifie,tabInit,AS);
					}
					else{
						tableauModifie[i][j] = 0;
					}
				}
				//aucune chiffre n'as pu être utilisé donc on retourne en arrière
				backTrack(caseAvant(i,j,tabInit),tabInit,tableauModifie,AS);
			}
		}
	}
	//case suivante
	public static int[] caseSuivante(int i,int j,int[][] tabInit){
		int[] caseSuivante = new int[3];
		for(int l=0;l<3;l++){
		caseSuivante[l] = 0;
		}
			if(j!=8){
				caseSuivante[0] = i;
				caseSuivante[1] = j + 1;
			}
			else{
				caseSuivante[0] = i + 1;
				caseSuivante[1] = 0;
			}
			if(tabInit[caseSuivante[0]][caseSuivante[1]] != 0){
				caseSuivante[2] = 1;
			}
			if(i == 9 && j == 8){
				caseSuivante[2] = 2;
			}
		return caseSuivante;
	}
	//Fonction de résolution
	public static void resolution(int i,int j,int[][] tableauModifie,int[][] tabInit,AffichageSudoku AS){
		int[] caseSuivante = caseSuivante(i,j,tabInit);
		int k;
			if(tableauModifie[i][j] == 0){
				if(caseSuivante[2] != 2){
					for(k=1;k<10;k++){
						if(chiffrePossible(k,i,j,tableauModifie)){
							tableauModifie[i][j] = k;
							AS.refresh(tableauModifie);
							resolution(caseSuivante[0],caseSuivante[1],tableauModifie,tabInit,AS);
						}
						else{
							tableauModifie[i][j] = 0;
						}
					}
					if(!verifTableau(tableauModifie)&&tableauModifie[i][j] == 0){
						backTrack(caseAvant(i,j,tabInit),tabInit,tableauModifie,AS);
					}
				}
				else{
					for(k=1;k<10;k++){
					if(tableauModifie[i][j] == 0){
						if(chiffrePossible(k,i,j,tableauModifie)){
							tableauModifie[i][j] = k;
							AS.refresh(tableauModifie);
						}
					}
					}
				}
			}			
			else{
				resolution(caseSuivante[0],caseSuivante[1],tableauModifie,tabInit,AS);
			}
	}
}