Lỗi giải Sudoku

Question

Tôi không biết mình đang làm gì sai, và tôi đã nhìn chằm chằm vào mã này cả ngày. Đây là một bộ giải Sudoku "tiêu chuẩn" trong Java, có một số int[][] với số 0 trong đó các khoảng trống. Do tôi chỉ đi qua trong một bảng với 35 lỗ, điều này sẽ có thể giải quyết phần lớn các vấn đề, nhưng chỉ có thể giải quyết ~ 66%. Trong những trường hợp khác, có một số ít (thường là 2 hoặc 4) không gian trống còn lại, không thể giải quyết được (nghĩa là một số không chính xác đã được ghi thành board.) Hầu như luôn luôn, nó sẽ là số 9 bị thiếu.

Tôi hiểu rằng giải pháp đơn giản như vậy sẽ không giải quyết được tất cả Sudokus. Tôi cố tình cho nó dễ dàng.

import java.util.ArrayList; 
import java.util.List; 

public class SudokuSolver 
{ 
    public SudokuSolver() 
    { 
     init(); 
    } 

    public boolean solve() 
    { 
     /* Each method checks (in different ways) to see if it can find a new number 
      If said method does find a number, it sets off a chain reaction, starting back at the beginning. 
     */ 
     int countdown = 20; 
     while(!solved() && --countdown > 0) 
     { 
      if(given()) 
       continue; 
      if(findSingletons()) 
       continue; 
      if(zerosLeft() <= 4) 
       justGuess(); 
     } 
     return solved(); 
    } 

    public boolean given() 
    { 
     boolean repeat = false; 
     //Iterate through every given number 
     for(int i=0;i<9;i++) 
     { 
      for(int j=0;j<9;j++) 
      { 
       if(board[i][j] != 0 && !found[i][j]) 
       { 
        repeat = true; 
        foundNum(i, j, board[i][j]); 
       } 
      } 
     } 
     //Call given every time a new number is found 
     return repeat; 
    } 

    public boolean findSingletons() 
    { 
     boolean repeat = false; 
     //LOTS of iteration, but I'm out of ideas. 
     int[] values; 
     ArrayList<Integer> singletons = new ArrayList<Integer>(); 
     for(int i=0;i<9;i++) 
     { 
      values = new int[10]; 
      singletons.clear(); 
      for(int j=0;j<9;j++) 
       for(int k=0;k<possible[i][j].size();k++) 
        values[possible[i][j].get(k)]++; 
      for(int j=1;j<10;j++) 
       if(values[j] == 1) 
        singletons.add(j); 
      for(int j=0;j<9;j++) 
       for(int k=0;k<singletons.size();k++) 
        if(possible[i][j].contains(singletons.get(k))) 
        { 
         foundNum(i, j, singletons.get(k)); 
         repeat = true; 
        } 
     } 

     for(int i=0;i<9;i++) 
     { 
      values = new int[10]; 
      singletons.clear(); 
      for(int j=0;j<9;j++) 
       for(int k=0;k<possible[j][i].size();k++) 
        values[possible[j][i].get(k)]++; 
      for(int j=1;j<10;j++) 
       if(values[j] == 1) 
        singletons.add(j); 
      for(int j=0;j<9;j++) 
       for(int k=0;k<singletons.size();k++) 
        if(possible[j][i].contains(singletons.get(k))) 
        { 
         foundNum(j, i, singletons.get(k)); 
         repeat = true; 
        } 
     } 

     int[] corners = {0,3,6}; 
     for(int a=0;a<3;a++) 
      for(int l=0;l<3;l++) 
       for(int i=corners[a];i<corners[a]+3;i++) 
       { 
        values = new int[10]; 
        singletons.clear(); 
        for(int j=corners[l];j<corners[l]+3;j++) 
         for(int k=0;k<possible[i][j].size();k++) 
          values[possible[i][j].get(k)]++; 
        for(int j=1;j<10;j++) 
         if(values[j] == 1) 
          singletons.add(j); 
        for(int j=0;j<9;j++) 
         for(int k=0;k<singletons.size();k++) 
          if(possible[i][j].contains(singletons.get(k))) 
          { 
           foundNum(i, j, singletons.get(k)); 
           repeat = true; 
          } 
       } 
     return repeat; 
    } 

    public void justGuess() 
    { 
     outer: 
     for(int i=0;i<9;i++) 
      for(int j=0;j<9;j++) 
       if(board[i][j] == 0) 
       { 
        foundNum(i, j, possible[i][j].get(0)); 
        break outer; 
       } 
    } 

    public void foundNum(int x, int y, int numFound) 
    { 

     if(board[x][y] != 0 && board[x][y] != numFound) 
     { 
      throw new RuntimeException("Attempting to place a number where one was already found"); 
     } 

     board[x][y] = numFound; 
     possible[x][y].clear(); 
     possible[x][y].add(numFound); 
     found[x][y] = true; 

     for(int i=0;i<9;i++) { 
      if(i != x) 
       if(possible[i][y].indexOf(numFound) != -1) 
        possible[i][y].remove(possible[i][y].indexOf(numFound)); 
     } 
     for(int i=0;i<9;i++) { 
      if(i != y) 
       if(possible[x][i].indexOf(numFound) != -1) 
        possible[x][i].remove(possible[x][i].indexOf(numFound)); 
     } 
     int cornerX = 0; 
     int cornerY = 0; 
     if(x > 2) 
      if(x > 5) 
       cornerX = 6; 
      else 
       cornerX = 3; 
     if(y > 2) 
      if(y > 5) 
       cornerY = 6; 
      else 
       cornerY = 3; 
     for(int i=cornerX;i<10 && i<cornerX+3;i++) 
      for(int j=cornerY;j<10 && j<cornerY+3;j++) 
       if(i != x && j != y) 
        if(possible[i][j].indexOf(numFound) != -1) 
         possible[i][j].remove(possible[i][j].indexOf(numFound)); 
    } 

    public boolean solved() { 
     for(int i=0;i<9;i++) 
      for(int j=0;j<9;j++) 
       if(!found[i][j]) 
        return false; 
     return true; 
    } 

    public void reset(int[][] board) 
    { 
     this.board = board; 
     init(); 
    } 

    public void init() 
    { 
     possible = new ArrayList[9][9]; 
     for(int i=0;i<9;i++) 
      for(int j=0;j<9;j++) 
      { 
       possible[i][j] = new ArrayList<Integer>(); 
       for(int k=1;k<10;k++) 
        possible[i][j].add(k); 
      } 
     found = new boolean[9][9]; 
    } 

    public void print() 
    { 
     for(int i=0;i<9;i++) 
     { 
      if(i%3==0 && i != 0) 
       System.out.println("- - - | - - - | - - -"); 
      for(int j=0;j<9;j++) 
      { 
       if(j%3==0 & j != 0) 
        System.out.print("| "); 
       System.out.print(board[i][j] + " "); 
      } 
      System.out.println(); 
     } 
     System.out.println(); 
    } 

    private int zerosLeft() 
    { 
     int empty = 0; 
     for(int i=0;i<9;i++) 
      for(int j=0;j<9;j++) 
       if(board[i][j] == 0) 
        empty++; 
     return empty; 
    } 

    private void data(int difficulty) 
    { 
     int empty = 0; 
     for(int i=0;i<9;i++) 
      for(int j=0;j<9;j++) 
       if(board[i][j] == 0) 
        empty++; 
     System.out.println(empty); 
    } 

    public static void main(String[] args) 
    { 
     SudokuGenerator sg = new SudokuGenerator(); 
     SudokuSolver ss = new SudokuSolver(); 
     int[][] tempBoard = {{4, 0, 1, 0, 9, 7, 0, 5, 8 }, 
         {2, 0, 0, 5, 3, 1, 4, 0, 6 }, 
         {5, 0, 6, 4, 0, 2, 0, 3, 9 }, 
         {0, 9, 0, 0, 0, 4, 3, 0, 2 }, 
         {0, 0, 0, 9, 0, 0, 6, 4, 7 }, 
         {7, 0, 4, 0, 0, 0, 9, 0, 5 }, 
         {0, 0, 7, 0, 0, 3, 8, 9, 4 }, 
         {8, 5, 0, 1, 4, 9, 7, 0, 0 }, 
         {9, 0, 3, 8, 7, 6, 0, 0, 0 }}; 
     ss.reset(tempBoard); 
     System.out.println(ss.solve()); 
     ss.print(); 
     ss.data(35); 
    } 

    int[][] board; 
    ArrayList<Integer>[][] possible; 
    boolean[][] found; 
} 

Tôi vẫn còn mới để lập trình, vì vậy mọi lời khuyên khác ngoài việc giải quyết điều này sẽ được hoan nghênh. (Đặc biệt tối ưu hóa possible. Đó là mã độc nhất mà tôi đã viết cho đến nay.)

Cảm ơn!

Answer 1

Tôi bắt đầu đọc mã của bạn, nhưng nó cảm thấy dài hơn thời gian cần thiết và các vòng lặp đó trở nên khá lộn xộn. Không có gì nhảy vào tôi ngay lập tức. Bạn đã nói rằng bạn không chỉ muốn các giải pháp, mà là lời khuyên.

Bạn phải tìm ra nếu vấn đề là với thiết kế của bạn (nó không hoạt động để giải Sudoku) hoặc nếu chỉ có một lỗi đơn giản ở đâu đó trong quá trình thực hiện. Có thể đi qua và viết bình luận về những gì mỗi vòng lặp hoàn thành, "kiểm tra vịt cao su", theo đó buộc phải giải thích mọi thứ, bạn sẽ dừng lại và nhận ra điều gì đó không cần thiết, hoặc không phải là thứ cần thiết. Điều đó giúp với các vấn đề về thiết kế.

Nếu sự cố được triển khai, bạn có biết cách gỡ lỗi chính thức ứng dụng không? Đặt điểm ngắt và đi qua hướng dẫn bằng lệnh? Nếu bạn có một lỗi nhỏ, nhưng bạn không thấy ở đâu, đó là cách để đi. Tìm một trường hợp ví dụ thực sự đơn giản mà không thành công, sau đó chạy thử nghiệm đó và phá vỡ nó ngay từ đầu. Bước qua, và làm theo logic. Hy vọng rằng, bạn sẽ thấy nơi nó đi awry. Việc viết các bài kiểm tra JUnit hoặc các câu lệnh đăng nhập là rất tốt, nhưng khi bạn có một lỗi phức tạp, bạn phải thực hiện một số việc gỡ rối điểm ngắt thực sự.

Khung chung của bạn là tốt, bạn có một số đối tượng để giữ dữ liệu và phương pháp giải quyết rõ ràng đẹp gọi một vài phương thức và vòng lặp khác nhau thông qua chúng. Nhưng mỗi phương pháp, wow, họ chắc chắn lộn xộn. Đó là loại mã, rất nhiều vòng lặp chặt chẽ bằng cách sử dụng cùng tên biến, rất nhiều thao tác mảng, nó rất dễ dàng để flub một cái gì đó và nhận được một lỗi và nó làm cho nó thực sự khó đọc và tìm lỗi.

Eclipse làm cho nó khá dễ dàng để gỡ lỗi java, nếu bạn chưa có trước đây. Rất nhiều hướng dẫn tốt trên google, vì vậy tôi sẽ không bận tâm^_ ~

Answer 2

Bạn dường như không thực hiện cơ chế quay lại. Có một số lần bạn phải đoán số nếu bạn không thực hiện đúng heuristic.

Phương pháp chẩn đoán là "thủ đoạn thương mại", dưới đây là list of common ones for sudoku.

Nếu bạn chỉ lập trình một vài trong số chúng, bạn sẽ bị chết và sẽ phải đoán. Điều này làm cho nó khó khăn hơn vì sẽ phải tính đến những dự đoán đó có thể sai. Backtracking là một chiến lược mà sẽ cho phép bạn "rollback" một vài dự đoán và thực hiện những cái khác nhau. Hãy suy nghĩ về nó như một cây khả năng để làm cho một số loại bruteforce để giải quyết các sudoku.

Vì vậy, 2 khả năng của bạn là triển khai nhiều chẩn đoán hơn hoặc tìm cách tạo phạm vi dự đoán rộng hơn