스도쿠 솔버의 코드 설명

Question

다음 코드 스 니펫에 대한 질문이 있습니다. 빈 셀을 채워 스도쿠 퍼즐을 해결하는 스도쿠 솔버입니다. 솔버 메서드 뒤에 로직을 적용 할 수 없습니다. 왜 k = 1-9를 시도한 후 false를 반환하고 모든 셀을 루핑 한 후 true를 반환합니다. 필자가 우리가 재귀 적으로 solver() 메소드에 들어가고 스도쿠가 완료되면 true를 호출 순서로 반환하고 마지막으로 호출 된 첫 번째 solver()가 true를 반환 할 것이라고 생각했습니다. 나는 두 가지 이상의 "반환"이 일어나는 몇 가지 시나리오를 생략해야한다고 생각한다. 누군가 "돌아 오는"것이 존재해야하는 이유를 설명해 줄 수 있습니까?

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

각 재귀 호출은 첫 번째 '.' 여전히 처리됩니다. 잠정적으로 숫자로 대체됩니다. 변경이 성공하면 (보드를 무효로하지는 않습니다) 재발합니다 (다음 번에 시도합니다.). 이 검색 브랜치에서 시도한 숫자가 유효하지 않기 때문에 실패하면 로컬에서 수행 된 변경 사항을 실행 취소하고 false를 반환합니다. 이것은 호출자 (루트까지)가 다음 선택을 시도하도록 강제하는 것을 의미합니다.

Answer 2

이것은 간단한 무력의 해결사입니다. 모든 열린 공간에서 모든 숫자를 시도합니다. 주어진 공간에 숫자를 채운 후 보드가 '규칙'(게임 규칙을 따르는 경우) 인 경우, 다른 반점을 채우는 동일한 솔버 기능을 재귀 적으로 호출하고 보드가 여전히 유효한지 테스트합니다 에.

매우 비효율적 인 솔버이지만 코드 작성이 쉽습니다.

Answer 3

이 코드 스도쿠를 확인하십시오. 올바른 경우 check_sudoku() 메소드는 잘못된 요소가있는 행과 열 번호를 잘못 표시하면 true를 반환합니다.

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

}