Имитация отжига для решения судоку - PullRequest
Новая
       40

Имитация отжига для решения судоку

0 голосов
/ 02 мая 2020

Я пытаюсь решить головоломку судоку 9x9 с помощью имитации отжига, но моя реализация, похоже, не работает правильно. Он даже не приближается к более дешевому решению, но вместо этого продолжает вращаться вокруг результатов, которые стоят от 60 до 80.

Моя функция стоимости возвращает сумму трех вещей: количество повторяющихся цифр в каждой строка , столбец и блок (3x3).

И реализованная мной функция преемника (соседа) изменяет две случайно выбранные цифры из сетки 9x9 со случайным значения.

А вот моя функция SA, которая не работает должным образом: 

public static void simulatedAnnealing() {

Sudoku neighbour; // candidate successor object
final Double temperature = 2.0; // initial temperature
final Double coolingFactor = 0.999; // cooling constant
final int maxIterations = 1000; // number of iterations

for(Double t = temperature; t>1; t*=coolingFactor) {

    for(int i = 0; i < maxIterations; i++) {

        neighbour = sudoku.generateSuccessor(); // set random neighbour
        int delta = neighbour.cost() - sudoku.cost(); // calculate delta

        if (delta <= 0) {
            sudoku = neighbour; // always accept good step.
         } else {
               if (Math.exp(-delta / temperature) > Math.random()) { // Simulated annealing
                   sudoku = neighbour;
               } 
         } 
     }

    System.out.println(sudoku.cost());
    if(sudoku.cost() == 0) { break; } // if puzzle is solved

} }

Функция для генерации преемников: 

public Sudoku generateSuccessor() {

int[][] newGrid = new int[9][9];

for(int o = 0; o < 9; o ++) { // cloning current grid array
    for(int g = 0; g < 9; g ++) {
        newGrid[o][g] = grid[o][g];
     }
 }

Sudoku rndm = new Sudoku(newGrid); // random Sudoku object.

for (int i = 0; i < 2; i++) { // will randomize 2 cells in 9x9 grid.

    int rndmCell = rndmValue(); // random digit for randomizing.
    int randomRow = rndm(); // random row that will be randomized
    int randomCol = rndm(); // random column that will be randomized

    // prevent randomizing given cells in sudoku (in problem definition)
    boolean shouldContinue = false;
    for (Coordinate c : SudokuSolver.concreteCoordinates) {
        if (c.row == randomRow && c.col == randomCol) { 
            shouldContinue = true;
            break;
        }
    }
    if (shouldContinue) {
        i--;
        continue;
    }
    // prevention end.

    rndm.grid[randomRow][randomCol] = rndmCell;
}

return rndm;

}

Функция стоимости: 

public int cost() {
    if(hasZeros()) { // if grid is not totally filled with numbers don't calculate its cost.
        return -1;
    }

    int cost = 0;
    for(int i = 0; i< 9; i++) { // find total collusions in rows&columns.
        cost += findNumberOfCollusions(grid[i]); // find collustions at row 'i'.
        cost += findNumberOfCollusions(getColumn(grid,i)); // find collustions at column 'i'.
    }

    for(int r = 0; r < 9; r += 3) { //find total colusions in blocks (3x3).
        for(int c = 0; c < 9; c += 3) {
            int[] block = new int[9];
            int ctr = 0;
            for (int i = r; i < r + 3; i++) {
                for (int y = c; y < c+ 3; y++) {
                    block[ctr] = grid[i][y];
                    ctr++;
                }
            }
            cost += findNumberOfCollusions(block);
        }
    }
    return cost;
}

Когда я запускаю программу, выходные данные стоят от 60 до 80. После этого температура опускается ниже предела, и программа выводит решение, которое стоит примерно в этом интервале. Может кто-нибудь сказать мне, что я делаю не так? Заранее спасибо.

...