Скорость генерации Судоку

Question

Я написал алгоритм обратного отслеживания для генерации судокуса с произвольным размером. Моя проблема заключается в изменении скорости алгоритма генерации.

Я добавил несколько консольных выходов, чтобы увидеть результаты. Я создал ~ 20 Sudokus размером 16x16, каждый из которых имел время генерации от 1 мс до 150 мс. Следующее заняло 10 минут, и это даже не закончилось. (Я остановил программу). Учитывая это, я думаю, что я ошибся в реализации backtracking, которая препятствует продвижению алгоритма.

Вот код:

public class Generator { 
    public static NormalSudoku generateNormal(int size) { 
    NormalSudoku ns = new NormalSudoku(size); 
    boolean[][][] track = new boolean[size][size][size]; 
    ArrayList<Integer> vals = new ArrayList<Integer>(); 
    fill(vals, size); 

    int row = 0; 
    int col = 0; 
    int val = 0; 

    int count = 0; 
    while (row < size) { 
     boolean found = false; 
     while (!vals.isEmpty() && !found) { 
      val = vals.get((int) (Math.random() * vals.size())); 
      track[row][col][val - 1] = true; 
      if (ns.checkValue(row, col, val)) { 
       ns.setValue(row, col, val); 
       fill(vals, size); 
       col++; 
       found = true; 
      } else { 
       vals.remove(Integer.valueOf(val)); 
      } 

      if (col >= size) { 
       row++; 
       col = 0; 
      } 
     } 
     if (vals.isEmpty()) { 
     ns.setValue(row, col, 0); 
     for (int i = 0; i < size; i++) { 
      track[row][col][i] = false; 
     } 
     col--; 
     if (col < 0) { 
      row--; 
      col = size - 1; 
     } 
     ns.setValue(row, col, 0); 
     fill(vals, track, row, col); 
     } 
    } 
    return ns; 
    } 

    private static void fill(ArrayList<Integer> vals, int size) { 
    vals.clear(); 
    for (int i = 1; i <= size; i++) { 
     vals.add(i); 
    } 
    } 

    private static void fill(ArrayList<Integer> vals, boolean[][][] track, 
     int row, int col) { 
    vals.clear(); 
    for (int i = 0; i < track[row][col].length; i++) { 
     if (!track[row][col][i]) { 
     vals.add(Integer.valueOf(i + 1)); 
     } 
    } 
    } 
} 

Объяснение кода:

логический [] [] [] трек:

своего рода контрольный список для значений, которые уже пробовали (чтобы уменьшить накладные расходы при попытке повторить одно и то же случайное значение несколько раз). Я положил трек [row] [col] [val] в true, если я уже попытался поместить val в это поле. Если я вернусь, я должен очистить метки для этой ячейки, чтобы снова сделать значения.

ns.checkValue:

Устанавливает значение в ячейке, проверяет, является ли судоку по-прежнему верна, устанавливает старое значение снова и возвращает истина/ложь.

ns.setValue:

Просто устанавливает значение в ячейке.

Vals:

список массив, содержащий значения, которые еще не пробовали для этой ячейки. Если я продвигаюсь вперед, список, очевидно, должен содержать все возможные числа. Если я вернусь, список должен содержать только числа, которые еще не были проверены. (Я использую массив треков, чтобы понять это).

Что я делаю неправильно?

Greets

Answer 1

Ok первое по какой-то причине вы выбрали случайное число из списка Vals, который большая часть времени полон с 10+ чисел, так что вы потеряете довольно много времени там. Я проверил ваш код, и на самом деле это довольно случайный вопрос о продолжительности решения. Например, на этом временном решении

[12, 9, 14, 7, 5, 13, 8, 2, 15, 3, 4, 6, 16, 1, 10, 11] 
[1, 2, 13, 15, 12, 16, 14, 4, 11, 8, 10, 9, 5, 6, 0, 0] 
.... 

Это займет слишком много времени, чтобы заполнить клетки (2,15) и (2,16) becouse он выбирает случайным образом из списка вальса 10 значений, доступных для какой-либо причине, кроме возможными значениями являются числа 3 и 7.

В списке vals вы должны исключать числа из текущей строки и текущего столбца и региона.

Однако это не улучшает алгоритм.

Вашего Алгоритм Построения является:

1. For current cell try all values until you find one that fits. 
2. If it fits track it and move on to next cell. 
3. If no value fits take step back, try value on the previous cell that was not used yet. 

Becouse из случайности, что Вы нашли слишком много времени на пункте 3, если некоторое значение не находится на хорошем месте, в некоторых первых позициях.