Sudoku Methode und Solver

Question

Ich versuche, einen Sudoku-Solver mit Rückverfolgung Rekursive Rekordsive zu schreiben, wenn ich alles fertig bin, ist meine Ausgabe nur "[]" mit nichts in der Klammer. und meine erwartete Ausgabe sollte die 3 Lösung in meinem Tester sein.

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 

}

folgende ist mein Tester

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

Haben Sie versucht, das Programm zu debuggen? Der Grund dafür, dass Sie eine leere Lösung erhalten, liegt in der isLegal-Methode: initialisieren Sie num auf 0 und überprüfen Sie, ob eine der Zellen gleich 0 ist. Natürlich enthält eine erste Tafel Nullen, daher gibt isLegal immer false zurück und daher Ihre Programm wird sofort beendet. Wie Sie oben im Kommentar zu isLegal angegeben haben, sollten Sie überprüfen, ob die Karte in einer der Zeilen/Spalten/Cubes dupliziert ist. Hier , ich gebe Ihnen die einfachste Art, wie ich denken kann, um zu überprüfen, dass jede Zeile keine Duplizierung hat:

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

Best of luck!