/*
 * This file is part of JGAP.
 *
 * JGAP offers a dual license model containing the LGPL as well as the MPL.
 *
 * For licencing information please see the file license.txt included with JGAP
 * or have a look at the top of class org.jgap.Chromosome which representatively
 * includes the JGAP license policy applicable for any file delivered with JGAP.
 */
//package examples;

import java.io.*;

import java.awt.image.*;

import org.jgap.*;
import org.jgap.data.*;
import org.jgap.impl.*;
import org.jgap.xml.*;
import org.w3c.dom.*;
import java.util.*;

/**
 * This class provides an implementation of the Sudoku problem
 * using a genetic algorithm. The goal of the problem is to solve a
 * Sudoku puzzle. 
 * <p>
 * Sudoku appears to be a classic constraint satisfaction problem
 * that should appropriate for a genetic algorithm.  The strategy is
 * to allow input of the Sudoku puzzle and then to randomly assign
 * values to the unfilled squares until the puzzle is solved.
 *
 * @author Ralph Morelli
 * @since 1.0
 */
public class SudokuRowGeneSolver {
  /** String containing the CVS revision. Read out via reflection!*/
  private final static String CVS_REVISION = "$Revision: 1.0 $";

  /**
   * The total number of times we'll let the population evolve.
   */
    private static final int MAX_ALLOWED_EVOLUTIONS = 10000; //60
    private static final int MAX_POPULATION = 100; //100

  /**
   * Executes the genetic algorithm to determine the minimum number of
   * coins necessary to make up the given target amount of change. The
   * solution will then be written to System.out.
   *
   * @param a_squareSize The size of the Sudoku square.
   * @throws Exception
   *
   * @author R. Morelli (original method)
   * @author Ariel Isaacson (SudokuRowGene modifications)
   * @since 1.0
   */
  public static void solveSudoku(int a_squareSize, String initsqrs) throws Exception {
      // Extract the initial square assignments
    System.out.println("Square size = " + a_squareSize + " Squares + " + initsqrs);

    // Start with a DefaultConfiguration, which comes setup with the
    // most common settings.
    // -------------------------------------------------------------
    Configuration conf = new DefaultConfiguration();

    // Set the fitness function we want to use, which is our
    // SudokuFitnessFunction. We construct it with
    // the square size.
    // ---------------------------------------------------------
    //FitnessFunction myFunc = new SudokuFitnessFunction(a_squareSize);
    FitnessFunction myFunc = new RowGeneFitnessFunction(a_squareSize);
    conf.setFitnessFunction(myFunc);
    //Let crossover between individual genes happen.
    conf.addGeneticOperator(SudokuRowGene.getInternalCrossoverOperator());
    //Don't let the natural selector cull redundant chromosomes, that feature screws up.
    ((org.jgap.impl.BestChromosomesSelector) conf.getNaturalSelectors(true).get(0)).setDoubletteChromosomesAllowed(true);
    // Now we need to tell the Configuration object how we want our
    // Chromosomes to be setup. We do that by actually creating a
    // sample Chromosome and then setting it on the Configuration
    // object. Each chromosome has an array of Integer genes 
    // corresponding to the Sudoku square.
    // --------------------------------------------------------------
    /*Gene[] sampleGenes = new Gene[a_squareSize * a_squareSize];
    for (int k = 0; k < sampleGenes.length; k++) {
	sampleGenes[k] = new SudokuGene(1, a_squareSize);
	}*/
    int[][] sampleAlleles = new int[a_squareSize][a_squareSize];

    StringTokenizer st = new StringTokenizer(initsqrs, ",");
    while (st.hasMoreTokens()) {
	String token = st.nextToken();
	int sqr = Integer.parseInt(token.substring(0,token.indexOf("=")));
	int val = Integer.parseInt(token.substring(token.indexOf("=")+1));
	System.out.println("sqr= " + sqr + " val= " + val);
	//((SudokuGene)sampleGenes[sqr]).setImmutableValue(val);
	sampleAlleles[sqr / a_squareSize][sqr % a_squareSize] = val;
    }
    
    //    for (int k = 0; k < sampleGenes.length; k++) {
    //	System.out.println(k + " " + sampleGenes[k].getPersistentRepresentation());
    //    }
    Gene[] sampleGenes = new SudokuRowGene[a_squareSize];
    //**/System.out.println("Making genes...");
    for (int index = 0; index < a_squareSize; index++) {
	sampleGenes[index] = new SudokuRowGene(sampleAlleles[index]);
	//**/System.out.println(sampleGenes[index]);
	if (index > 0)
	    System.out.println("Gene #" + index + " is" + (sampleGenes[index].equals(sampleGenes[index-1])?
							    "": " not") + " the same as Gene #" + (index-1));
    }
    Chromosome sampleChromosome = new Chromosome(sampleGenes);
    conf.setSampleChromosome(sampleChromosome);

    // Finally, we need to tell the Configuration object how many
    // Chromosomes we want in our population. The more Chromosomes,
    // the larger number of potential solutions (which is good for
    // finding the answer), but the longer it will take to evolve
    // the population (which could be seen as bad).
    // ------------------------------------------------------------
    conf.setPopulationSize(MAX_POPULATION);

    // Create random initial population of Chromosomes.
    // Here we try to read in a previous run via XMLManager.readFile(..)
    // for demonstration purpose!
    // ------------------------------------------------
    Genotype population;
    try {
      Document doc = XMLManager.readFile(new File("testJGAP.xml"));
      population = XMLManager.getGenotypeFromDocument(conf, doc);
    }
    catch (FileNotFoundException fex) {
      population = Genotype.randomInitialGenotype(conf);
    }

    population = Genotype.randomInitialGenotype(conf);

    // Evolve the population. Since we don't know what the best answer
    // is going to be, we just evolve the max number of times.
    // ---------------------------------------------------------------
    System.out.print("Starting to evolve ");
    for (int i = 0; i < MAX_ALLOWED_EVOLUTIONS; i++) {
	conf.setKeepPopulationSizeConstant(true);
	//**/System.out.println("Population before evolving: " + population.getPopulation().size());
	try {
	    population = new DebugGenotype(conf, population.getPopulation());
	} catch (InvalidConfigurationException e) {
	    System.err.println("Can't use DebugGenotype, proceeding with ordinary one.");
	    }
	population.evolve();
	//**/System.out.println("Population after evolving: " + population.getPopulation().size());
	System.out.print(population.getFittestChromosome().getFitnessValue() + " ");
    }
    System.out.println();

    /****
    // Save progress to file. A new run of this example will then be able to
    // resume where it stopped before!

    // represent Genotype as tree with elements Chromomes and Genes
    DataTreeBuilder builder = DataTreeBuilder.getInstance();
    IDataCreators doc2 = builder.representGenotypeAsDocument(population);

    // create XML document from generated tree
    XMLDocumentBuilder docbuilder = new XMLDocumentBuilder();
    Document xmlDoc = (Document) docbuilder.buildDocument(doc2);
    XMLManager.writeFile(xmlDoc, new File("testJGAP.xml"));
    ****/


    // Display the best solution we found.
    // -----------------------------------
    Chromosome bestSolutionSoFar = population.getFittestChromosome();
    System.out.println("The best solution has a fitness value of " +
                       bestSolutionSoFar.getFitnessValue());
    System.out.println("Here's the completed Sudoku: ");
    Gene[] genes = bestSolutionSoFar.getGenes();
    for (int k = 0; k < genes.length; k++) {
	//String repr = genes[k].getPersistentRepresentation();
	//System.out.print(repr.substring(0,repr.indexOf(":")) + "\t");
	//if ((k+1) % a_squareSize == 0)
	//System.out.println();
	SudokuRowGene.Square[] squares = (SudokuRowGene.Square[]) genes[k].getAllele();
	for (int i = 0; i < squares.length; i++)
	    System.out.print(squares[i].getValue() + " ");
	System.out.println();
    }
  }

  /**
   * Main method. A single command-line argument is expected, which is the
   * amount of change to create (in other words, 75 would be equal to 75
   * cents).
   *
   * @param args the command-line arguments.
   *
   * @author Neil Rotstan
   * @since 1.0
   */
  public static void main(String[] args) {
    if (args.length != 1) {
      System.out.println("Syntax: SudokuRowGeneSolver <squareSize:sqr0=val0,sqr1=val1,...,sqrN=valN>");
    }
    else {
      try {
        StringTokenizer st  = new StringTokenizer(args[0],":");
	int sqrSize = Integer.parseInt(st.nextToken());
	String initSquares = st.nextToken();
        if (sqrSize < 4 || sqrSize > 9) {
	    System.out.println("The <squareSize> argument must be between 4 and 9.");
        }
        else {
          try {
            solveSudoku(sqrSize, initSquares);
          }
          catch (Exception e) {
            e.printStackTrace();
          }
        }
      }
      catch (Exception e) {
        System.out.println(
           "Format: SudokuRowGeneSolver squareSize:sqr0=val0,sqr1=val1,...,sqrN=valN");
      }
    }
  }

    private static void testGeneticOperators(Configuration c, Genotype g) {
	//Try the genetic operators one at a time & see what happens to the population.
	List L = c.getGeneticOperators();
	for (int index = 0; index < L.size(); index++) {
	    Population p = g.getPopulation();
	    ArrayList a = new ArrayList(p.getChromosomes());
	    System.out.println("Trying " + L.get(index).getClass().getName());
	    System.out.println("Population before it: " + a.size());
	    ((GeneticOperator) L.get(index)).operate(p, a);
	    System.out.println("Population after it: " + a.size());
	}
    }
}

class DebugGenotype extends Genotype {
    DebugGenotype(Configuration c, Population p) throws InvalidConfigurationException {
	    super(c, p);
    }

      protected void applyNaturalSelectors(boolean a_processBeforeGeneticOperators) {
    // Process all natural selectors applicable before executing the
    // genetic operators (reproduction, crossing over, mutation...).
    // -------------------------------------------------------------
    int selectorSize = m_activeConfiguration.getNaturalSelectorsSize(
        a_processBeforeGeneticOperators);
    if (selectorSize > 0) {
      int m_population_size = m_activeConfiguration.getPopulationSize();
      int m_single_selection_size = m_population_size / selectorSize;
      Population m_new_population;
      m_new_population = new Population(m_population_size);
      NaturalSelector selector;
      // Repopulate the population of chromosomes with those selected
      // by the natural selector. Iterate over all natural selectors.
      // ------------------------------------------------------------
      for (int i = 0; i < selectorSize; i++) {
        selector = m_activeConfiguration.getNaturalSelector(
            a_processBeforeGeneticOperators, i);
        if (i == selectorSize - 1 && i > 0) {
          // Ensure the last NaturalSelector adds the remaining Chromosomes.
          // ---------------------------------------------------------------
          m_single_selection_size = m_population_size - getPopulation().size();
        }
        else {
          m_single_selection_size = m_population_size;
        }
	//**/System.out.println("Selecting " + m_single_selection_size);
        // Do selection of Chromosomes.
        // ----------------------------
        selector.select(m_single_selection_size, getPopulation(),
                        m_new_population);
	//**/System.out.println("Selected (real selector): " + m_new_population.size());
	///**/org.jgap.impl.BestChromosomesSelector s = new org.jgap.impl.BestChromosomesSelector();
	///**/Population p = new Population();
	///**/s.setDoubletteChromosomesAllowed(true);
	///**/s.select(17, getPopulation(), p);
	///**/System.out.println("Selected (fake selector): " + p.size());
        // Clean up the natural selector.
        // ------------------------------
        selector.empty();
      }
      setPopulation(new Population());
      //**/System.out.println("Replaced population.  Size: " + getPopulation().size());
      getPopulation().addChromosomes(m_new_population);
      //**/System.out.println("Put selected chromosomes in new population.  Size: " + getPopulation().size());
    }
  }
}