2016-04-09 80 views
-3

我想寫一個數獨求解器,使用後向跟蹤廣告遞歸,當我完成每件事情時,我的輸出結果只是「[]」,沒有任何內容。 和我的預期輸出應該是我的測試儀中的3解決方案。Sudoku方法和求解器

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 

}

以下是我的測試

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

}

+0

也許它會更好,如果你有實際的代碼而不是'// TODO自動生成的構造函數存根?或者那裏真的有一些你忘記與我們分享的代碼? – ajb

+0

正如@ user6179968所說:「如果你希望StackOverflow做你的[作業],也許你不應該在聖何塞州立大學攻讀CS46B(https://drive.google.com/file/d/0B7QJIi-5wncoOHp2NXA5WW5zdVk/view ) 爲你 ;)」 –

回答

1

你有沒有試着調試程序? 您收到空解決方案的原因在於isLegal方法: 您初始化num爲0,然後檢查其中一個單元是否等於0.當然,初始板包含零,因此isLegal始終返回false,因此您的程序立即終止。 正如您在上面的註釋isLegal中指出的那樣,您應該檢查該板在其中一個行/列/多維數據集中沒有重複。 在這裏,我給你的最簡單的方法我能想到的檢查每一行有沒有重複:

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

祝您好運!