遞歸數獨求解器在Java中不起作用

Question

我已經在C語言中編寫了包含解算器的Sudoku遊戲，並且希望用Java進行試驗，以便人們可以更輕鬆地使用它（便攜性）。我認爲由於語言之間存在巨大的相似性，端口將非常簡單，但看起來似乎有些痛苦。

我的求解器遞歸無限，它從來沒有發生過C.這裏是解決難題我原來的C函數：

int sudoku_solve(struct sudoku* sudoku) 
{ 
    if(!sudoku) return 0; 

    int mask = 0x1ff; 
    int best_x = 0, best_y = 0; 
    int best_mask = 0x2ff; 


    for(int y = 0; y < 9; ++y){ 
     for(int x = 0; x < 9; ++x){ 
      if(sudoku->grid[y][x] != 0) continue; 
      mask = sudoku_get_mask(sudoku, x, y); 
      if(mask < best_mask){ 
       best_mask = mask; 
       best_x = x; 
       best_y = y; 
      } 
     } 
    } 

    if(best_mask == 0x2ff) return 1; // this puzzle is already solved! 

    if(best_mask == 0x000) return 0; // this puzzle can't be solved! 

    int start_c = rand() % 9; 
    int c = start_c; 
    do{ 
     if((best_mask & (1<<c))){ 
      sudoku->grid[best_y][best_x] = c+1; 
      if(sudoku_solve(sudoku)) return 1; 
     } 
     c = (c+1) % 9; 
    } while(c != start_c); 

    sudoku->grid[best_y][best_x] = 0; 


    return 0; 
} 

我知道這不一定是最快或最好寫的求解器，但它工作。它只是發現具有最小可能值的瓦片，然後從隨機值開始，嘗試所有可能的值，直到獲得可解的難題（使用遞歸）。 sudoku_get_mask返回一個整數，前9位設置爲相應的值。它檢查已經使用的值的水平，垂直和子平方，並將其從掩模中移除。

現在，這裏是Java端口：

public int Solve() 
{ 
    int mask = 0x2FF; 
    int bmask = 0x2FF, bx = 0, by = 0; 

    for(int y = 0; y < 9; ++y){ 
     for(int x = 0; x < 9; ++x){ 
      if(grid[y][x] != 0) continue; // ignore spaces with values already set 
      mask = GetMask(x, y); 
      if(mask < bmask) // less bits set == less possible choices 
      { 
       bmask = mask; 
       bx = x; 
       by = y; 
      } 
     } 
    } 

    if(bmask == 0x2FF) // the puzzle had no good slots, it must be solved 
     return 1; 

    if(bmask == 0) // the puzzle is unsolvable 
     return -1; 

    int start_c = rand() % 9; 
    int c = start_c; 
    do{ 
     if((bmask & (1<<c)) != 0){ 
      grid[by][bx] = (char) (c+1); 
      if(Solve() == 1) return 1; 
     } 
     c = (c+1)%9; 
    }while(c != start_c); 

    grid[by][bx] = 0; // restore old value 

    return 0; 
} 

他們幾乎是相同的，所以我不明白，爲什麼在Java端口無限遞歸！求解器應該總是1.找到一個解決方案或2.找到沒有解決方案。按照我的邏輯，我看不出它應該無限遞增的方式。

這裏是GetMask Java代碼：

protected int GetMask(int x, int y) 
{ 
    int mask = 0x1FF; 
    for(int cx = 0; cx < 9; ++cx){ 
     mask &= (grid[y][cx] == 0 ? mask : ~(1 << (grid[y][cx]-1))); 
    } 
    for(int cy = 0; cy < 9; ++cy){ 
     mask &= (grid[cy][x] == 0 ? mask : ~(1 << (grid[cy][x]-1))); 
    } 
    int idx = squareIndex[y][x]; 
    int[] pt = null; 
    for(int c = 0; c < 9; ++c){ 
     pt = squarePoint[idx][c]; 
     mask &= (grid[pt[1]][pt[0]] == 0 ? mask : ~(1 << (grid[pt[1]][pt[0]]-1))); 
    } 
    return mask; 
} 

這裏是squareIndex和squarePoint（只針對查找分平方表）：

static int squareIndex[][] = { 
    {0,0,0,1,1,1,2,2,2}, 
    {0,0,0,1,1,1,2,2,2}, 
    {0,0,0,1,1,1,2,2,2}, 
    {3,3,3,4,4,4,5,5,5}, 
    {3,3,3,4,4,4,5,5,5}, 
    {3,3,3,4,4,4,5,5,5}, 
    {6,6,6,7,7,7,8,8,8}, 
    {6,6,6,7,7,7,8,8,8}, 
    {6,6,6,7,7,7,8,8,8} 
}; 

static int[] squarePoint[][] = { 
    { {0,0}, {1,0}, {2,0}, {0,1}, {1,1}, {2,1}, {0,2}, {1,2}, {2,2} }, 
    { {3,0}, {4,0}, {5,0}, {3,1}, {4,1}, {5,1}, {3,2}, {4,2}, {5,2} }, 
    { {6,0}, {7,0}, {8,0}, {6,1}, {7,1}, {8,1}, {6,2}, {7,2}, {8,2} }, 
    { {0,3}, {1,3}, {2,3}, {0,4}, {1,4}, {2,4}, {0,5}, {1,5}, {2,5} }, 
    { {3,3}, {4,3}, {5,3}, {3,4}, {4,4}, {5,4}, {3,5}, {4,5}, {5,5} }, 
    { {6,3}, {7,3}, {8,3}, {6,4}, {7,4}, {8,4}, {6,5}, {7,5}, {8,5} }, 
    { {0,6}, {1,6}, {2,6}, {0,7}, {1,7}, {2,7}, {0,8}, {1,8}, {2,8} }, 
    { {3,6}, {4,6}, {5,6}, {3,7}, {4,7}, {5,7}, {3,8}, {4,8}, {5,8} }, 
    { {6,6}, {7,6}, {8,6}, {6,7}, {7,7}, {8,7}, {6,8}, {7,8}, {8,8} } 
}; 

Answer 1

我猜Smith先生是不會提交正式答案（我想我會讓他的點）。

問題是std C函數rand（）返回範圍[0，INT_MAX]中的整數，Java函數Randomizer.nextInt（）在[INT_MIN，INT_MAX]範圍內。我不得不用「generator.randInt（9）」替換「generator.nextInt（）％9」，它工作。