谁能教我如何使用遗传算法解决下面源代码生成的数独？新创建的数独遗传算法求解器应该使用下面源代码中的实例。
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 > 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 < 9; i++)
numbers[i] = 1+i;
shuffle_array(numbers);
for (int i=0; i < 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)
&& !existsInRow(solved_puzzle, n, row)
&& !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 > 80)
{
solution_count++;
if (solution_count > 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 <= 9; n++) // for each number
{
// if number is acceptable by Sudoku rules
if (!existsInColumn(_tmp_grid, n, col)
&& !existsInRow(_tmp_grid, n, row)
&& !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 < array.length; i++)
{
// find an index j (i<j<=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 < 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 < 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 < sub_grid_start_row + 3; _row++)
for (int _col = sub_grid_start_col; _col < 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 < 9; row++)
for (int col = 0; col < 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 < 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 < 81 && count_set_to_zero < 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 < 9; r++)
for (int c = 0; c < 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 < 9; row++)
{
System.out.print(" ");
for (int col = 0; col < 9; col++)
System.out.print(" " + solved_puzzle[row][col]);
System.out.println();
}
}
public void show()
{
for (int row = 0; row < 9; row++)
{
System.out.print(" ");
for (int col = 0; col < 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();
}
}