Sudoku Çözücü Kod açıklaması

Question

Aşağıdaki kod parçacığı hakkında soru var: Bu boş hücreleri doldurarak bir Sudoku bulmacasını çözen bir sudoku çözücüdür. Çözücü yönteminin arkasındaki mantığı gerçekten alamıyorum. Neden k = 1-9'u denedikten sonra false değerini döndürür ve tüm hücreler üzerinde döngü yaptıktan sonra true değerini döndürür. Düşündüğüm şey, özyinelemede çözücü() yöntemine giriyor ve sudoku tamamlandıktan sonra, geri alma sırası olarak geri dönecek ve en sonunda ilk çağrılan çözücü() gerçek olarak geri dönecektir. Bence, iki "geri dönüş" ün gerçekleştiği bazı senaryoları çıkarmam gerekiyor. Birisi bana neden "geri dönüş" gerektiğini açıklayabilir mi?

public class Solution { 

public static void main(String[] args) { 
    Solution s = new Solution(); 
    char[][] board = {{'.', '2', '6', '5', '.', '.', '.', '9', '.'}, 
         {'5', '.', '.', '.', '7', '9', '.', '.', '4'}, 
         {'3', '.', '.', '.', '1', '.', '.', '.', '.'}, 
         {'6', '.', '.', '.', '.', '.', '8', '.', '7'}, 
         {'.', '7', '5', '.', '2', '.', '.', '1', '.'}, 
         {'.', '1', '.', '.', '.', '.', '4', '.', '.'}, 
         {'.', '.', '.', '3', '.', '8', '9', '.', '2'}, 
         {'7', '.', '.', '.', '6', '.', '.', '4', '.'}, 
         {'.', '3', '.', '2', '.', '.', '1', '.', '.'}}; 

    s.solver(board); 
} 
public boolean solver(char[][] board) { 
    for (int r = 0; r < board.length; r++) { 
     for (int c = 0; c < board[0].length; c++) { 
      if (board[r][c] == '.') { 
       for (int k = 1; k <= 9; k++) { 
        board[r][c] = (char) ('0' + k); 
        if (isValid(board, r, c) && solver(board)) { 
         return true; 
        } else { 
         board[r][c] = '.'; 
        } 
       } 
       return false; 
      } 
     } 
    } 
    return true; 
} 

public boolean isValid(char[][] board, int r, int c) { 
    //check row 
    boolean[] row = new boolean[9]; 
    for (int i = 0; i < 9; i++) { 
     if (board[r][i] >= '1' && board[r][i] <= '9') { 
      if (row[board[r][i] - '1'] == false) { 
       row[board[r][i] - '1'] = true; 
      } else { 
       return false; 
      } 
     } 
    } 

    //check column 
    boolean[] col = new boolean[9]; 
    for (int i = 0; i < 9; i++) { 
     if (board[i][c] >= '1' && board[i][c] <= '9') { 
      if (col[board[i][c] - '1'] == false) { 
       col[board[i][c] - '1'] = true; 
      } else { 
       return false; 
      } 
     } 
    } 

    //check the 3*3 grid 
    boolean[] grid = new boolean[9]; 
    for (int i = (r/3) * 3; i < (r/3) * 3 + 3; i++) { 
     for (int j = (c/3) * 3; j < (c/3) * 3 + 3; j++) { 
      if (board[i][j] >= '1' && board[i][j] <= '9') { 
       if (grid[board[i][j] - '1'] == false) { 
        grid[board[i][j] - '1'] = true; 
       } else { 
        return false; 
       } 
      } 
     } 
    } 

    return true; 
} 
} 

Answer 1

Her özyinelemeli çağrı, ilk '.' Ile ilgilenir. hala ele alınacak. Bu, bir rakamla geçici olarak değiştirilecektir. Değişiklik başarılı olursa (tahtayı geçersiz kılmaz) yinelemeye devam edin (sonraki '.' 'Ifadesini deneyiniz). Bu, yerel olarak yapılan değişikliği geri alamaz ve yanlış döndürürse, bu arama dalında denenen herhangi bir basamak geçersizdir. Bu, arayanı (root'a kadar) bir sonraki seçimi denemek için zorlamak anlamına gelir.

Answer 2

Bu basit bir kaba kuvvet çözümleyicisidir. Sadece her açık alanda her sayıyı dener. Bir sayı ile verilen bir boşluk doldurulduktan sonra, tahta 'geçerli' ise (oyunun kurallarına uyuyorsa), o zaman tekrar tekrar aynı boş alanı doldurup aynı tahta boşluğunu dolduracak ve tahta hala geçerli olup olmadığını test edecektir. üzerinde.

Çok verimsiz bir çözümdür, ancak kodu kolaydır.

Answer 3

Bu kod Sudoku kontrol edin. Doğru değilse check_sudoku() yöntemi true olursa, yanlış bir satır öğesi ve yinelenen öğeye sahip sütun numarasını gösterir.

public static void main(String[] args) { 
    int array[][]={{9,6,3,1,7,4,2,5,8}, 
        {1,7,8,3,2,5,6,4,9}, 
        {2,5,4,6,8,9,7,3,1}, 
        {8,2,1,4,3,7,5,9,6}, 
        {4,9,6,8,5,2,3,1,7}, 
        {7,3,5,9,6,1,8,2,4}, 
        {5,8,9,7,1,3,4,6,2}, 
        {3,1,7,2,4,6,9,8,5}, 
        {6,4,2,5,9,8,1,7,3}}; 

    Sudoku sudoku=new Sudoku(); 
    if(sudoku.check_sudoku(array)) 
    { 
     System.out.println("You won the game :)"); 
    } 


} 


public class Sudoku { 

private int temp1[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}, temp2[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; 
private int data1, data2; 

public boolean check_sudoku(int array[][]) { 
    for (int i = 0; i < 9; i++) { 
     for (int j = 0; j < 9; j++) { 
      data1 = array[i][j]; 
      data2 = array[j][i]; 
      if (data1 >= 10 || data2 >=10 || data1 <= 0 || data2 <= 0) { 
       System.out.println("Invalid Solution because value must be in between 1 to 9"); 
       return false; 
      } else if (temp1[data1 - 1] == 0 || temp2[data2 - 1] == 0) { 
       System.out.println("Invalid Solution please check " + (i + 1) + " row " + (j + 1) + " column or " + (j + 1) + " row " + (i + 1) + " column"); 
       return false; 
      } else { 
       temp1[data1 - 1] = 0; 
       temp2[data2 - 1] = 0; 
      } 
     } 
     int check1[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; 
     int check2[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; 
     temp1 = check1; 
     temp2 = check2; 
    } 
    return true; 
} 

}