sudoku solver bằng cách sử dụng backtracking

Question

Gần đây tôi đã làm việc trên một thuật toán giải thuật sudoku backtracking và hiện tại tôi muốn hỏi về cách tôi nên thay đổi phương thức resolve() của tôi từ void thành boolean.

Tôi đang sử dụng một thuật toán quay lui rất đơn giản, và nó hiện đang làm việc tốt, nhưng tôi muốn có một boolean thay vì một khoảng trống, bởi vì có một printstack không phải là rất tốt đẹp ...

Cảm ơn !

public class Backtracking{ 


static int backtrack = 0; 


//check if valid in row 
protected static boolean validInRow(int row, int value) 
{ 
    for(int col = 0; col < 9; col++) 
    if(board[row][col] == value) 
     return false ; 

    return true ; 
} 

    //check if valid in column 
protected static boolean validInCol(int col, int value) 
{ 
    for(int row = 0; row < 9; row++) 
    if(board[row][col] == value) 
     return false ; 

    return true ; 
} 

//check if valid in 3*3 
protected static boolean validInBlock(int row, int col, int value) 
{ 
    row = (row/3) * 3 ; 
    col = (col/3) * 3 ; 

    for(int r = 0; r < 3; r++) 
     for(int c = 0; c < 3; c++) 
     if(board[row+r][col+c] == value) 
     return false ; 

    return true ; 
} 




     //call other methods 
public void solve(int row, int col) throws Exception 
{ 

    if(row > 8) 
    throw new Exception("Solution found") ; 
    else 
    { 

    while(board[row][col] != 0) 
    { 
     if(++col > 8) 
     { 
      col = 0 ; 
      row++ ; 


      if(row > 8) 
       throw new Exception("Solution found") ; 
     } 
    } 


    for(int value = 1; value < 10; value++) 
    { 
     if(validInRow(row,value) && validInCol(col,value) && validInBlock(row,col,value)) 
     { 
      board[row][col] = value; 
      new PrintEvent(board); 



      if(col < 8) 
       solve(row, col + 1); 
      else 
       solve(row + 1, 0); 

      backtrack++; 
     } 
     } 


     board[row][col] = 0; 

     } 
    } 
} 

Answer 1

Vâng, bạn có thể catch ngoại lệ để tránh theo dõi ngăn xếp, nhưng điều đó vẫn không đẹp lắm. Những gì bạn có thể làm sau khi thay đổi kiểu trả về để boolean là:

 if(col < 8) { 
      if (solve(row, col + 1)) { 
       return true; 
      } 
     } else { 
      if (solve(row + 1, 0)) { 
       return true; 
      } 
     } 

và sau đó tất nhiên, thay đổi throw báo cáo để return true;.

Answer 2

public boolean solve(int row, int col) throws Exception 
{ 
    { 

    while(board[row][col] != 0) 
    { 
     if(++col > 8) 
     { 
      col = 0 ; 
      row++ ; 


      if(row > 8) 
      return true 
     } 
    } 


    for(int value = 1; value < 10; value++) 
    { 
     if(validInRow(row,value) && validInCol(col,value) && validInBlock(row,col,value)) 
     { 
      board[row][col] = value; 
      new PrintEvent(board); 



      if(col < 8) 
       solve(row, col + 1); 
      else 
       solve(row + 1, 0); 

      backtrack++; 
     } 
     } 


     board[row][col] = 0; 

     } 
    } 
return false; 
}