數獨生成速度

Question

我寫了一個回溯算法來生成任意大小的數獨。我的問題是這一代算法的變化速度。

我添加了一些控制檯輸出來查看結果。我生成了大小爲16x16的〜20 Sudokus，每個生成時間爲1ms到150ms。下一個花了10多分鐘，甚至沒有完成。 （我停止了該程序）。考慮到這一點，我認爲我在回溯實現中犯了一個錯誤，這妨礙了算法的發展。

下面是代碼：

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)); 
     } 
    } 
    } 
} 

的代碼的說明：

布爾[] [] []磁道：

某種清單爲它們已經嘗試過的值（以減少多次嘗試相同的隨機值的開銷）。如果我已經嘗試將val放在這個字段上，我將track [row] [col] [val]設置爲true。如果我回去，我必須清除那個單元格的標記，以使這些值再次可能。

ns.checkValue：

設置在單元格的值，會檢查數獨仍然是正確的，再次將舊的值，並返回真/假。

ns.setValue：

只需設置單元格上的值。

瓦爾斯：

含有不用於該小區還嘗試過的值的數組列表。如果我繼續前進，那麼列表顯然必須包含每個可能的數字。 如果我回溯，列表只需包含尚未嘗試的數字。 （我使用軌道陣列來實現這一點）。

我在做什麼錯？

電賀

Answer 1

好吧，第一件事就是某種原因，你選擇從瓦爾斯列表，它的大部分時間是滿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] 
.... 

這需要becouse它選擇從列表瓦爾斯隨機可用10個值由於某種原因，但太多的時間來填補細胞（2,15）和（2,16）可能的值是數字3和7.

在vals列表中，您應該排除當前行和當前列和區域中的數字。

但是，這並沒有改善很多算法。

你algorith是：

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，如果某個值是不是好地方，在一些非常的第一位置。