/*
 *
 * sudokuka
 *
 * Copyright (C) 2007 Laurent RICHARD
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; version 2
 * of the Licensen.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
 *
 * Resolution.java
 *
 * Created on 4 juin 2007, 16:49
 *
 */

package sudokuka;

import javax.swing.JFrame;
import javax.swing.JTextField;
import javax.swing.JOptionPane;
import java.util.ArrayList;

public class Resolution 
    {
 
    public int[] values;
    public int[] solution;
    
    public static void main (String[] args)
    {
        Resolution machin = new Resolution();
        machin.afficher(machin.solution);
        machin.solution(machin.values,new javax.swing.JFrame());
        machin.afficher(machin.solution);
        System.out.println("");
        machin.afficher(machin.values);    }
    
    /** Creates a new instance of Resolution */
    public Resolution(/*JTextField[][] grilleTT*/) 
        {
        int grilleTT[][] = new int[9][9];
		grilleTT[0][0] = 3;
		grilleTT[0][1] = 0;
		grilleTT[0][2] = 0;
		grilleTT[0][3] = 1;
		grilleTT[0][4] = 0;
		grilleTT[0][5] = 0;
		grilleTT[0][6] = 0;
		grilleTT[0][7] = 0;
		grilleTT[0][8] = 0;
		grilleTT[1][0] = 0;
		grilleTT[1][1] = 5;
		grilleTT[1][2] = 7;
		grilleTT[1][3] = 0;
		grilleTT[1][4] = 0;
		grilleTT[1][5] = 3;
		grilleTT[1][6] = 1;
		grilleTT[1][7] = 0;
		grilleTT[1][8] = 0;
		grilleTT[2][0] = 9;
		grilleTT[2][1] = 0;
		grilleTT[2][2] = 6;
		grilleTT[2][3] = 0;
		grilleTT[2][4] = 5;
		grilleTT[2][5] = 0;
		grilleTT[2][6] = 0;
		grilleTT[2][7] = 0;
		grilleTT[2][8] = 8;
		grilleTT[3][0] = 4;
		grilleTT[3][1] = 0;
		grilleTT[3][2] = 0;
		grilleTT[3][3] = 6;
		grilleTT[3][4] = 0;
		grilleTT[3][5] = 0;
		grilleTT[3][6] = 9;
		grilleTT[3][7] = 5;
		grilleTT[3][8] = 1;
		grilleTT[4][0] = 0;
		grilleTT[4][1] = 0;
		grilleTT[4][2] = 5;
		grilleTT[4][3] = 8;
		grilleTT[4][4] = 0;
		grilleTT[4][5] = 0;
		grilleTT[4][6] = 0;
		grilleTT[4][7] = 0;
		grilleTT[4][8] = 6;
		grilleTT[5][0] = 0;
		grilleTT[5][1] = 0;
		grilleTT[5][2] = 0;
		grilleTT[5][3] = 0;
		grilleTT[5][4] = 0;
		grilleTT[5][5] = 7;
		grilleTT[5][6] = 0;
		grilleTT[5][7] = 0;
		grilleTT[5][8] = 0;
		grilleTT[6][0] = 8;
		grilleTT[6][1] = 0;
		grilleTT[6][2] = 0;
		grilleTT[6][3] = 0;
		grilleTT[6][4] = 0;
		grilleTT[6][5] = 0;
		grilleTT[6][6] = 0;
		grilleTT[6][7] = 0;
		grilleTT[6][8] = 0;
		grilleTT[7][0] = 0;
		grilleTT[7][1] = 0;
		grilleTT[7][2] = 0;
		grilleTT[7][3] = 0;
		grilleTT[7][4] = 0;
		grilleTT[7][5] = 0;
		grilleTT[7][6] = 0;
		grilleTT[7][7] = 4;
		grilleTT[7][8] = 2;
		grilleTT[8][0] = 0;
		grilleTT[8][1] = 0;
		grilleTT[8][2] = 0;
		grilleTT[8][3] = 0;
		grilleTT[8][4] = 7;
		grilleTT[8][5] = 1;
		grilleTT[8][6] = 0;
		grilleTT[8][7] = 0;
		grilleTT[8][8] = 0;
	values = new int[81];
	solution = new int[81];

        int compteur=0;
        
        for (int i=0;i<9;i++)
            {
            for (int j=0;j<9;j++)
                {
                try
                    {
                    this.values[compteur]=grilleTT[i][j];
                    compteur++;
                    }
                 catch(Exception e)
                    {
                    this.values[compteur] = 0;
                    compteur++;
                    }
                }
            }

        }
    
    
    protected void afficher (int [] vecteur)
    {
    System.out.println("|---|---|---|");
    for (int i=0; i<81; i++)
        {
        if (i % 3 == 0) System.out.print("|");
        if (i % 9 == 0 && i > 0) { System.out.println(); System.out.print("|"); }
        if (i % 27 == 0 && i > 0) { System.out.println("---|---|---|"); System.out.print("|"); }
        System.out.print (vecteur[i]);
        }
    System.out.println("|"); System.out.println("|---|---|---|");
    System.out.println();
    }

    protected int index_debut_ligne (int nombre)
        {
        return (nombre - (nombre%9));
        }

    protected int index_debut_colonne (int nombre)
        {
        return(nombre%9);
        }

    protected int index_debut_bloc (int nombre)
        {
        return((27*(ligne(nombre)/3))+(3*(colonne(nombre)/3)));
        }
    
    protected int ligne (int nombre)
        {
        return (nombre/9);
        }

    protected int colonne (int nombre)
        {
        return(nombre%9);
        }


    protected boolean ok_ligne (int[] grille, int cible, int debut)
        {
        int temp1;
        temp1 = index_debut_ligne(debut);
        for (int i=temp1;i<temp1+9;i++)
            {
            if (grille[i]==cible) 
                {
                return false;
                }
            }
        return true;
        }
    
    protected boolean ok_colonne (int[] grille, int cible, int debut)
        {
        int temp1;
        temp1 = index_debut_colonne(debut);
        for (int i=temp1;i<temp1+81;i=i+9)
            {
            if (grille[i]==cible)
                {
         
                return false;
                }
            
            }
        return true;
        }
    
    protected boolean ok_bloc (int[] grille, int cible, int debut)
        {
        int temp1;
        temp1=index_debut_bloc(debut);
        for (int i=0;i<3;i++)
            {
            for (int j=0;j<3;j++)
                {
                if (grille[temp1+(9*i)+j]==cible) 
                    {
                    return false;
                    }
                }
            }
        return true;
        }

    protected boolean ok (int[] grille, int cible, int debut)
        {
        if (debut==81) return false;
        else return (ok_ligne(grille,cible, debut) && ok_colonne(grille,cible, debut) && ok_bloc(grille,cible, debut)); 
        }
    
    protected int suivant (int[] grille, int cible)
        {
        int temp1;
        temp1=cible;
        while (grille[temp1] != 0)
            {
            if (temp1<80) temp1++;
            else return 81;
            }
        return temp1;
        }
    
    protected ArrayList index_fixes (int[] grille)
        {
        ArrayList monArray = new ArrayList();
        for (int i=0;i<81;i++)
            {
            if (grille[i]>0) monArray.add(i);             
            }
        return (monArray);
        }
    
    protected void solution (int[] grille, JFrame fenetre)
        {
        int index=0;
        int valeur=0;
        ArrayList monArray = new ArrayList();
        monArray = index_fixes(grille);
        
        for (int i=0; i<81;i++)
            {
            this.solution[i]=this.values[i];
            }
        while (index < 81)
            {
            index=suivant(grille,index);
            valeur++;
            
            if (ok(grille,valeur,index))
                {
                grille[index]=valeur;
                valeur=0;
                }
            else
                {
                if (valeur==9)
                    {
                    valeur=0;
                    
                    //
                    while(true)
                    {
	                    
	                    grille[index]=0;
	                    index=index-1;
	                    while (grille[index]==9)
	                        {
	                        valeur=0;
	                        grille[index]=0;
	                        index=index-1;
	                       }
	                    while (valeurDansArray(index,monArray))
	                        {
	                        index=index-1;                        
	                        }
	                    if (index<0)
	                        {
//	                        JOptionPane.showMessageDialog(fenetre, "Aucune solution possible", "Pas de solution", JOptionPane.ERROR_MESSAGE);
				System.out.println("Pas de solution trouvée pour ce sudoku.");
	                        //return;
	                        }
	                    if (grille[index]<9)
	                        {
	                        valeur=grille[index];
	                        grille[index]=0;                          
	                        break;
	                        }
	             }
	             }
                }
            }
        
        }
    
    private boolean valeurDansArray(int valeur, ArrayList aarray)    
        {
        for (int i=0; i<aarray.size();i++)
            {
            if (valeur==aarray.get(i)) return true;
            }
        return false;
        }

}