Genetic Algorithm Sudoku Solver

by Ariel Isaacson

Update of a sudoku-solving genetic algorithm.

The original:

• SudokuGene.java Gene representing 1 sudoku square.
• SudokuFitnessFunction.java Rules to evaluate fitness of a chromosome of SudokuGenes.
• SudokuSolver.java Main program. Represents puzzle's starting state in chromosomes and evolves them to the end state.

My update:

• SudokuRowGene.java Gene representing 1 row of squares.
• RowGeneFitnessFunction.java Rules to evaluate fitness of a chromosome of SudokuRowGenes.
• SudokuRowGeneSolver.java Main program. Does what you think it does.

Update's Purpose:

The Changes:

• Gene Format
  Originally: Gene is 1 square, mutable or not. Initialized to 0 unless value known.
  Now: Gene is a row of squares, some of which are mutable. Initialized with 1 of each number in random order.
• Fitness
  Originally: Chromosome's "unfitness" is the # of zeroes in each row, column and box.
  Now: Chromosome's "unfitness" is the # of repeats in each column and box. Rows never have repeats.
• Mutation
  Originally: If square is mutable, change its value randomly.
  Now: Pick 2 immutable squares at random, swap them.
• Crossover
  Originally: Swap ends of chromosomes.
  Now: "Swap" ends of chromosomes--or of individual genes: mutable-square values in Chromosome A trade places until A's end looks like B's. (In theory. Mutability constraints usually make a perfect trade impossible.)
• Functionality
  Originally: Didn't work. (Starting state too far from end state?)
  Now: Doesn't work. (Natural selection parameters need tweaked?)