Sudoku metodu ve çözücü

Question

Her şeyi bitirdiğimde, çıkışım yalnızca parantez içinde "[]" ile geri izleme reklamını tekrar tekrar kullanarak bir Sudoku çözücü yazmaya çalışıyorum. ve beklenen çıkışım test cihazımdaki 3 çözüme sahip olmalıdır.

package sudoku; 
    import java.util.*; 
    public class Grid 
    { 
    private int[][] values; 


    // Dots in input strings become 0s in values[][]. 
    // 
public Grid(String []rows) 
{ 
    values = new int[9][9]; 
    for (int j=0; j<9; j++) 
    { 
     String row = rows[j]; 
     char[] charray = row.toCharArray(); 
     for (int i=0; i<9; i++) 
     { 
      char ch = charray[i]; 
      if (ch != '.') 
       values[j][i] = ch - '0'; 
     } 
    } 
} 


public Grid(Grid grid) { 
    this.grid = grid; 
} 

public String toString() 
{ 
    String s = ""; 
    for (int j=0; j<9; j++) 
    { 
     for (int i=0; i<9; i++) 
     { 
      int n = values[j][i]; 
      if (n == 0) 
       s += '.'; 
      else 
       s += (char)('0' + n); 
     } 
     s += "\n"; 
    } 
    return s; 
} 



// 
// Finds an empty member of values[][]. Returns an array list of 9 grids that look like the current grid, 
// except the empty member contains 1, 2, 3 .... 9. Returns null if the current grid is full. 

// 
public ArrayList<Grid> next9Grids(){ 
    if(this.isFull()) 
    { 
     return null; 
    } 
    else 
    { 
    ArrayList<Grid> grids = new ArrayList<>(); 
    for(int i = 0; i < 9;i++) 
    { 
     for(int j = 0; j< 9 ;j++) 
     { 
      if(values[i][j] == 0) 
      { 
       for(int k = 1; k<=9;k++) 
       { 
        Grid theGrid = new Grid(this); 
        theGrid.values[i][j] = k; 
        grids.add(theGrid); 
       } 
      } 
     } 
    } 
    return grids; 
    } 
    } 


// Returns true if this grid is legal. A grid is legal if no row, column, or zone contains 
// a repeated 1, 2, 3, 4, 5, 6, 7, 8, or 9. 
// 
public boolean isLegal() 
{ 
    int row = 0; 
    int col = 0; 
    int num =0; 
    for( col = 0; col < 9; col++) 
     if(values[row][col] == num) 
      return false ; 
    for( row = 0; row < 9; row++) 
     if(values[row][col] == num) 
      return false ; 
    row = (row/3) * 3 ; 
     col = (col/3) * 3 ; 

     for(int r = 0; r < 3; r++) 
     for(int c = 0; c < 3; c++) 
     if(values[row+r][col+c] == num) 
      return false ; 
     return true; 
} 

// Returns true if every cell member of values[][] is a digit from 1-9. 
// 
public boolean isFull() 

{ 
    int min = 1; 
    int max = 9; 
    for (int i = 0; i < values.length; i++) 
    { 
     for (int j = 0; j < values[0].length; j++) 
     { 
     if (values[i][j] < min || values[i][j] > max) 
     { 
      return false; 
     } 
     } 
    } 
    return true; 
    }  

// Returns true if x is a Grid and, for every (i,j), 
// x.values[i][j] == this.values[i][j]. 
// 
public boolean equals(Grid that) 
{ 
    Grid x = (Grid)that; 
    if (x.equals(this)) 
    { 
     for (int i = 0; i < 9; i++) 
     { 
      for (int j = 0; j < 9; j++) 
      { 
       if (that.values[i][j] == this.values[i][j]) 
       { 
        return true; 
       } 
      } 
     } 
    } 
    return false; 
} 

}

package sudoku; 

import java.util.*; 


public class Solver 
{ 
    private Grid      problem; 
    private ArrayList<Grid>    solutions; 



public Solver(Grid problem) 
{ 
    this.problem = problem; 
    solutions = new ArrayList<Grid>(); 
} 


public ArrayList<Grid> solve() 
{ 
    solutions = new ArrayList<>(); 
    solveRecurse(problem); 
    return solutions; 
} 


// Standard backtracking recursive solver. 
// 
private void solveRecurse(Grid grid) 
{  
    Evaluation eval = evaluate(grid); 

    if (eval == Evaluation.ABANDON) 
    { 
     return; 
    } 
    else if (eval == Evaluation.ACCEPT) 
    { 
     solutions.add(grid); 
    } 
    else 
    { 
     ArrayList<Grid> array = grid.next9Grids(); 
     for (Grid i: array) 
     { 
     solveRecurse(i); 
     // Here if eval == Evaluation.CONTINUE. 
     } 
    } 
} 

// Returns Evaluation.ABANDON if the grid is illegal. 
// Returns ACCEPT if the grid is legal and complete. 
// Returns CONTINUE if the grid is legal and incomplete. 
// 
public Evaluation evaluate(Grid grid) 
{ 
    if(!grid.isLegal()) 
    { 
     return Evaluation.ABANDON; 
    } 
    else if(grid.isLegal() && grid.isFull()) 
    { 
     return Evaluation.ACCEPT; 
    } 
    else 
     return Evaluation.CONTINUE; 

} 


public ArrayList<Grid> getSolutions() 
{ 
    return solutions; 
} 


public static void main(String[] args) 
{ 
    Grid g = TestGridSupplier.getPuzzle1();  // or any other puzzle 
    Solver solver = new Solver(g); 
    solver.solve(); 
    System.out.println(solver.getSolutions()); 

    // Print out the solution 

}

aşağıdaki benim test cihazıdır

package sudoku; 

    public class TestGridSupplier 
    { 

    private final static String[]  PUZZLE_1 = 
    { 
     "..3.1.5..", 
     "8..395..1", 
     "15.....27", 
     ".8..7..5.", 
     "62.9.4.13", 
     ".9..2..7.", 
     "91.....34", 
     "2..748..9", 
     "..6.3.2.."  
    };  


    private final static String[]  SOLUTION_1 = 
    { 
     "463217598", 
     "872395641", 
     "159486327", 
     "384671952", 
     "627954813", 
     "591823476", 
     "918562734", 
     "235748169", 
     "746139285" 
}; 


static Grid getPuzzle1()  { return new Grid(PUZZLE_1); } 
static Grid getSolution1()  { return new Grid(SOLUTION_1); } 



private final static String[]  PUZZLE_2 = 
{ 
    ".........", 
    "8.1...9.7", 
    "..75493..", 
    "7..9.2..8", 
    "....1....", 
    "1..3.8..5", 
    "..84312..", 
    "2.5...1.9", 
    "........." 
};  


private final static String[]  SOLUTION_2 = 
{ 
    "439187562", 
    "851623947", 
    "627549381", 
    "763952418", 
    "582714693", 
    "194368725", 
    "978431256", 
    "245876139", 
    "316295874" 
}; 

static Grid getPuzzle2()  { return new Grid(PUZZLE_2); } 
static Grid getSolution2()  { return new Grid(SOLUTION_2); } 




private final static String[]  PUZZLE_3 = 
{ 
    ".97..1.6.", 
    "2....7..5", 
    "....9...3", 
    "85.......", 
    "..9...5..", 
    ".......32", 
    "3...7....", 
    "5..6....1", 
    ".4.1..37." 
}; 


private final static String[]  SOLUTION_3 = 
{ 
    "497351268", 
    "236847195", 
    "185296743", 
    "853924617", 
    "629713584", 
    "714568932", 
    "361472859", 
    "578639421", 
    "942185376" 
}; 


static Grid getPuzzle3()  { return new Grid(PUZZLE_3); } 
static Grid getSolution3()  { return new Grid(SOLUTION_3); } 


// 
// You can use these to test your Grid's evaluate() method. 
// 
private final static String[]  REJECT_1 = 
{ 
    "11.......", 
    ".........", 
    ".........", 
    ".........", 
    ".........", 
    ".........", 
    ".........", 
    ".........", 
    "........." 
}; 

private final static String[]  REJECT_2 = 
{ 
    "2........", 
    "2........", 
    ".........", 
    ".........", 
    ".........", 
    ".........", 
    ".........", 
    ".........", 
    "........." 
}; 

private final static String[]  REJECT_3 = 
{ 
    "3........", 
    "..3......", 
    ".........", 
    ".........", 
    ".........", 
    ".........", 
    ".........", 
    ".........", 
    "........." 
}; 

private final static String[]  REJECT_4 = 
{ 
    ".........", 
    ".........", 
    ".........", 
    "....4....", 
    ".....4...", 
    ".........", 
    ".........", 
    ".........", 
    "........." 
}; 

private final static String[]  CONTINUE = 
{ 
    "123456789", 
    ".........", 
    ".........", 
    ".........", 
    ".........", 
    ".........", 
    ".........", 
    ".........", 
    "........." 
}; 

static Grid getReject1()  { return new Grid(REJECT_1); } 
static Grid getReject2()  { return new Grid(REJECT_2); } 
static Grid getReject3()  { return new Grid(REJECT_3); } 
static Grid getReject4()  { return new Grid(REJECT_4); } 
static Grid getContinue()  { return new Grid(CONTINUE); } 
static Grid getAccept()   { return getSolution1(); } 

}

Answer 1

programı hata ayıklama denediniz mi? Boş bir çözüm almanızın sebebi, deLegal yöntemidir: , num'i 0 olarak başlatırsınız ve sonra, hücrelerden birinin 0'a eşit olup olmadığını kontrol edin. Tabii ki, bir ilk kart sıfırlar içerir, bu nedenle isLegal her zaman false değerini döndürür. program hemen sonlandırır. Yukarıdaki yorumda belirtildiği gibi, Legal, satırın/cols/küplerden birinde çoğaltmanın olmadığını kontrol etmelisiniz. İşte , ben her satırında hiç tekrarını olup olmadığını kontrol etmek size düşünebildiğim Could en basit yolu vereceğiz:

boolean[] rowAppearances; 
    for(row = 0; row < 9; row++) 
    { 
     rowAppearances = new boolean[9]; 
     for(col = 0; col < 9; col++) 
     { 
      if (values[row][col] != 0) 
      { 
       if(rowAppearances[values[row][col] - 1]) 
        return false; 
       else 
        rowAppearances[values[row][col] - 1] = true; 
      } 
     } 
    } 

İyi şanslar!