title: Genetic Algorithm for Sudoku
body: <p>can anyone please teach me how to use Genetic Algorithm to solve the sudoku generated by the source code below? The newly created Genetic Algorithm solver for the sudoku should use back the instances in the source code below. </p>
  
  <pre><code>import java.util.Random;
  //Generates a Sudoku puzzle through brute-force
  
  public class SudokuPuzzle
  {
      public int[][] puzzle = new int[9][9];        // Generated puzzle.
      public int[][] solved_puzzle = new int[9][9]; // The solved puzzle.
  
  private int[][] _tmp_grid = new int[9][9]; // For the solver
  private Random rand = new Random();
  private short solution_count; // Should be 1
  
  /**
   * Constructor generates a new puzzle, and its solution
   */
  public SudokuPuzzle()
  {
      generateSolvedPuzzle(0);
      generatePuzzle();
  }
  
  /**
   * Finds a solved puzzle through depth-first search
   */
  private boolean generateSolvedPuzzle(int cur_cell)
  {
      if (cur_cell &gt; 80)
          return true;
  
      int col = cur_cell % 9;
      int row = cur_cell / 9;
  
      // create a sequence of the integers {1,...,9} of random order
      int [] numbers = new int[9];
      for (int i=0; i &lt; 9; i++)
          numbers[i] = 1+i;
      shuffle_array(numbers);
  
      for (int i=0; i &lt; 9; i++)
      {
          int n = numbers[i]; // for the next number in the array
          // if number is acceptable by Sudoku rules
          if (!existsInColumn(solved_puzzle, n, col)
                  &amp;&amp; !existsInRow(solved_puzzle, n, row)
                  &amp;&amp; !existsInSubGrid(solved_puzzle, n, row, col))
          {
              // attempt to fill in the next cell with the current cell set to number
              solved_puzzle[row][col] = n;
              if (generateSolvedPuzzle(cur_cell + 1))
                  return true;
              solved_puzzle[row][col] = 0; // didn't work, reset cell and try the next number in sequence
          }
      }
      return false; // unreachable (since search is exhaustive and a solved puzzle must exist)
  }
  
  /**
   * Solves the Sudoku puzzle through depth-first, exhaustive search, and store the number of
   * solutions in solution_count. Currently, we want to use this only to detect if two solutions
   * exist. Hence, we stop the search as soon as two solutions have been found.
   *
   *
   */
  private boolean _solvePuzzle(int cur_cell)
  {
      if (cur_cell &gt; 80)
      {
          solution_count++;
          if (solution_count &gt; 1) // two solutions detected. notify caller to abort search
              return true;
          return false;
      }
  
      int col = cur_cell % 9;
      int row = cur_cell / 9;
  
      if (_tmp_grid[row][col] == 0) // if cell is unfilled
      {
          for (int n=1; n &lt;= 9; n++) // for each number
          {
              // if number is acceptable by Sudoku rules
              if (!existsInColumn(_tmp_grid, n, col)
                      &amp;&amp; !existsInRow(_tmp_grid, n, row)
                      &amp;&amp; !existsInSubGrid(_tmp_grid, n, row, col))
              {
                  // attempt to fill in the next cell with the current cell set to number
                  _tmp_grid[row][col] = n;
                  if (_solvePuzzle(cur_cell + 1)) // notified of two solutions being detected
                      return true; // notify caller to abort search
                  _tmp_grid[row][col] = 0; // try with other numbers
              }
          }
      }
      else
          if (_solvePuzzle(cur_cell + 1)) // notified of two solutions being detected
              return true; // notify caller to abort search
  
      return false;
  }
  
  private void shuffle_array(int array[])
  {
      // swap the first size elements with other elements from the whole array
      for (int i = 0; i &lt; array.length; i++)
      {
          // find an index j (i&lt;j&lt;=array_length) to swap with the element i
          int j = i + rand.nextInt(array.length - i);
          int t = array[j];
          array[j] = array[i];
          array[i] = t;
      }
  }
  
  /**
   * Returns whether a given number exists in a given column.
   *
   * @param col    column to check.
   * @param number number to check.
   * @return       true iff number exists in row.
   */
  private boolean existsInColumn(int[][] puzzle, int number, int col)
  {
      for (int row = 0; row &lt; 9; row++)
          if (puzzle[row][col] == number)
              return true;
      return false;
  }
  
  /**
   * Returns whether a given number exists in a given row.
   *
   * @param row    row to check.
   * @param number number to check.
   * @return       true iff number exists in row.
   */
  private boolean existsInRow(int[][] puzzle, int number, int row)
  {
      for (int col = 0; col &lt; 9; col++)
          if (puzzle[row][col] == number)
              return true;
      return false;
  }
  
  /**
   * Returns whether if the 3x3 sub-grid which includes (row, col) contains a
   * cell with the given number.
   *
   * @param row    a row in the sub-grid.
   * @param col    a col in the sub-grid.
   * @param number number to check.
   * @return       true iff sub-grid contains number.
   */
  private boolean existsInSubGrid(int[][] puzzle, int number, int row, int col)
  {
      int sub_grid_start_row = (row / 3)*3;
      int sub_grid_start_col = (col / 3)*3;
      for (int _row = sub_grid_start_row; _row &lt; sub_grid_start_row + 3; _row++)
          for (int _col = sub_grid_start_col; _col &lt; sub_grid_start_col + 3; _col++)
              if (puzzle[_row][_col] == number)
                  return true;
      return false;
  }
  
  /**
   * Generates a Sudoku puzzle from a solved puzzle by setting up to 64 cells to 0.
   * (We cannot set more than 64 cells to 0. See http://www.math.ie/McGuire_V1.pdf)
   */
  private void generatePuzzle()
  {
      // copy solved_puzzle to puzzle
      for (int row = 0; row &lt; 9; row++)
          for (int col = 0; col &lt; 9; col++)
              puzzle[row][col] = solved_puzzle[row][col];
  
      // create a sequence of the integers {0,...,80} of random order
      int [] cell_sequence = new int[81];
      for (int i=0; i &lt; 81; i++)
          cell_sequence[i] = i;
      shuffle_array(cell_sequence);
  
      // attempt to set each cell in the sequence to 0
      int count_set_to_zero = 0;
      for (int i=0; i &lt; 81 &amp;&amp; count_set_to_zero &lt; 64; i++)
      {
          int cur_cell = cell_sequence[i];
          int col = cur_cell % 9;
          int row = cur_cell / 9;
          int sav = puzzle[row][col];
          puzzle[row][col] = 0;
          solution_count = 0;
  
          // copy puzzle to _tmp_grid for the solver to work on
          for (int r = 0; r &lt; 9; r++)
              for (int c = 0; c &lt; 9; c++)
                  _tmp_grid[r][c] = puzzle[r][c];
  
          if (_solvePuzzle(0)) // Puzzle allows more than 1 solution
              puzzle[row][col] = sav; // Revert to original puzzle
          else
              count_set_to_zero++;
      }
  }
  
  public void showSolution()
  {
      for (int row = 0; row &lt; 9; row++)
      {
          System.out.print("  ");
          for (int col = 0; col &lt; 9; col++)
              System.out.print(" " + solved_puzzle[row][col]);
          System.out.println();
      }
  }
  
  public void show()
  {
      for (int row = 0; row &lt; 9; row++)
      {
          System.out.print("  ");
          for (int col = 0; col &lt; 9; col++)
              System.out.print(" " + puzzle[row][col]);
          System.out.println();
      }
  }
  
  public static void main(String[] args)
  {
      SudokuPuzzle sudoku_puzzle = new SudokuPuzzle();
      System.out.println("Puzzle:");
      sudoku_puzzle.show();
      System.out.println();
      System.out.println("Solution:");
      sudoku_puzzle.showSolution();
  }
  </code></pre>
  
  <p>}</p>