數獨求解器評估函數

所以我試圖寫一個簡單的遺傳算法來解決一個數獨（不是最有效的方法，我知道，但它只是爲了練習演化算法）。我遇到了一些問題，提出了一個有效的評估函數來測試難題是否得到解決，以及有多少錯誤。我的第一本能是檢查矩陣中的每一行和列（以八度爲單位，與matlab類似）是否具有唯一的元素，通過排序來檢查重複項，然後將它們重新放回原來的樣子，這似乎很長糾纏不清。有什麼想法嗎？數獨求解器評估函數

抱歉，如果這已經問...

來源

2010-12-23 Rich

我會使用網格的號碼作爲索引，並遞增的9個元素長度數組的各個元素=> s_array [X] ++其中x是數取自電網。在檢查一行結束時，數組中的每個元素都必須是1。如果0發生在數組中的某個位置，則該行是錯誤的。

但是，這只是一個簡單的完整性檢查，如果沒有問題，線路明智。 PS：如果是10年前，我會建議使用位操作的組合解決方案（值1,2或3的第1位，第2位，第3位等），並檢查結果是否爲2^10-1。

來源

2010-12-23 00:52:28 karatedog

聽起來不錯，除了'把他們放回'部分。您可以將任意行，列或方塊中的數字放入列表中，然後以任何您想要的方式檢查雙打。如果有雙打，則會出現錯誤。如果所有的數字都是唯一的，那就沒有。你不需要把實際的數字從難題中解放出來，所以不需要再把它們放回去。

此外，如果你正在編寫一個解算器，它不應該做任何無效的移動，所以根本不需要這個檢查。

來源

2010-12-23 00:52:35 GolezTrol

加速：
使用按位操作代替排序。

我在c中製作了100行數獨解算器，速度相當快。對於或超級速度，你需要實現DLX算法，在matlab交換中也有一些文件。
http://en.wikipedia.org/wiki/Exact_cover
http://en.wikipedia.org/wiki/Dancing_Links
http://en.wikipedia.org/wiki/Knuth「s_Algorithm_X

#include "stdio.h" 
int rec_sudoku(int (&mat)[9][9],int depth) 
{ 
    int sol[9][9][10]; //for eliminating 
    if(depth == 0) return 1; 
    for(int i=0;i<9;i++) 
    { 
     for(int j=0;j<9;j++) 
     { 
      sol[i][j][9]=9; 
      for(int k=0;k<9;k++) 
      { 
       if(mat[i][j]) sol[i][j][k]=0; 
       else sol[i][j][k]=1; 
      } 
     } 
    } 
    for(int i=0;i<9;i++) 
    { 
     for(int j=0;j<9;j++) 
     { 
      if(mat[i][j] == 0) continue; 
      for(int k=0;k<9;k++) 
      { 
       if(sol[i][k][mat[i][j]-1]) 
       { 
        if(--sol[i][k][9]==0) return 0; 
        sol[i][k][mat[i][j]-1]=0; 
       } 
       if(sol[k][j][mat[i][j]-1]) 
       { 
        if(--sol[k][j][9]==0) return 0; 
        sol[k][j][mat[i][j]-1]=0; 
       } 
      } 
      for(int k=(i/3)*3;k<(i/3+1)*3;k++) 
      { 
       for(int kk=(j/3)*3;kk<(j/3+1)*3;kk++) 
       { 
        if(sol[k][kk][mat[i][j]-1]) 
        { 
         if(--sol[k][kk][9]==0) return 0; 
         sol[k][kk][mat[i][j]-1]=0; 
        } 
       } 
      } 
     } 
    } 
    for(int c=1;c<=9;c++) 
    { 
     for(int i=0;i<9;i++) 
     { 
      for(int j=0;j<9;j++) 
      { 
       if(sol[i][j][9] != c) continue; 
       for(int k=0;k<9;k++) 
       { 
        if(sol[i][j][k] != 1) continue; 
        mat[i][j]=k+1; 
        if(rec_sudoku(mat,depth-1)) return 1; 
        mat[i][j]=0; 
       } 
       return 0; 
      } 
     } 
    } 
    return 0; 
} 
int main(void) 
{ 
    int matrix[9][9] = 
    { 
     {1,0,0,0,0,7,0,9,0}, 
     {0,3,0,0,2,0,0,0,8}, 
     {0,0,9,6,0,0,5,0,0}, 
     {0,0,5,3,0,0,9,0,0}, 
     {0,1,0,0,8,0,0,0,2}, 
     {6,0,0,0,0,4,0,0,0}, 
     {3,0,0,0,0,0,0,1,0}, 
     {0,4,0,0,0,0,0,0,7}, 
     {0,0,7,0,0,0,3,0,0} 
    }; 
    int d=0; 
    for(int i=0;i<9;i++) for(int j=0;j<9;j++) if(matrix[i][j] == 0) d++; 
    if(rec_sudoku(matrix,d)==0) 
    { 
     printf("no solution"); 
     return 0; 
    } 
    for(int i=0;i<9;i++) 
    { 
     for(int j=0;j<9;j++) 
     { 
      printf("%i ",matrix[i][j]); 
     } 
     printf("\n"); 
    } 
    return 1; 
}

來源

2010-12-23 00:59:30

的檢查很容易，你會爲行，列創建套，和3x3的加入了許多，如果它不存在，並相應地改變你的健身，如果它纔不是。

然而，真正的伎倆是「相應地改變你的健康」。有些問題看起來非常適合GA和ES（進化策略），也就是說我們尋找寬容的解決方案，數獨有一個確切的答案......非常棘手。

我的第一個破解可能是創建可變長度染色體的解決方案（以及它們可以是固定長度，但9x9的空白）。健身功能應該能夠確定解決方案的哪一部分是有保證的，哪一部分不是（有時候你必須在一個非常艱難的數獨遊戲中在黑暗中進行猜測，如果不成功則返回），它會爲每個可能的分支創建孩子是一個好主意。

然後這是一個遞歸解決方案。不過，您可以從電路板上的不同位置開始掃描。重組將結合具有重疊解決方案的未驗證部分的解決方案。

只要在這個高水平的隨和時尚中思考一下，我就能看到這個想法是如何實現的！

只有當有多條路徑需要採用時，纔會應用突變，畢竟突變是一種猜測。

來源

2010-12-23 01:01:38 Quaternion

當我解決了這個問題時，我只計算了每行，每列和子網格中的重複次數（事實上，我只需要計算列和子網格中的重複次數，因爲我的進化算子從未設計過重複成行）。我只是使用HashSet來檢測重複項。有更快的方法，但這對我來說足夠快。

您可以在my Java applet中看到這種可視化（如果速度太快，請增加人口數量以減慢速度）。彩色正方形是重複的。黃色正方形與另一個正方形發生衝突，橙色與另外兩個正方形發生衝突，紅色發生三次或更多正方形。

來源

2010-12-27 23:34:02

這是我的解決方案。 Sudoku solving solution in C++

來源

2011-07-18 11:25:30 Avinash

這是我的solution使用集合。如果一條線，塊或一列你得到的一組長度（讓說）7，你的健康將是9 - 7

來源

2013-01-04 07:01:16 trez

如果你是在一個小整數集的排序可以操作使用桶分類在O(n)中完成。
可以使用tmp陣列做這個任務在MATLAB：

函數TF = checkSubSet（板，SEL）％％給出一個9x9的板和選擇（使用邏輯9x9的SEL矩陣）％驗證板（sel）有9個獨特元素％％假設作出：％ - 董事會是9x9與數字1,2，...，9 ％ - sel只有9個「真實」條目：nnz（sel） = 9 ％ tmp =零（1,9）; tmp（board（sel））= 1; ％窮人的桶分類 tf = all（tmp == 1）& & nnz（sel）== 9 & & numel（tmp）== 9; ％檢查有效性

現在我們可以使用checkSubSet驗證板是正確的

function isCorrect = checkSudokuBoard(board) 
% 
% assuming board is 9x9 matrix with entries 1,2,...,9 
% 

isCorrect = true; 
% check rows and columns 
for ii = 1:9 
    sel = false(9); 
    sel(:,ii) = true; 
    isCorrect = checkSubSet(board, sel); 
    if ~isCorrect 
     return; 
    end 
    sel = false(9); 
    sel(ii, :) = true; 
    isCorrect = checkSubSet(board, sel); 
    if ~isCorrect 
     return; 
    end 
end 
% check all 3x3 
for ii=1:3:9 
    for jj=1:3:9 
     sel = false(9); 
     sel(ii + (0:2) , jj + (0:2)) = true; 
     isCorrect = checkSubSet(board, sel); 
     if ~isCorrect 
      return; 
     end 
    end 
end

來源

2013-01-04 12:02:43 Shai

數獨求解器評估函數

回答

相關問題