सुडोकू सॉल्वर बग

Question

मुझे नहीं पता कि मैं क्या गलत कर रहा हूं, और मैं पूरे दिन इस कोड पर देख रहा हूं। यह जावा में एक "मानक" सुडोकू सॉल्वर है, जो int[][] 0 के साथ खाली रिक्त स्थान लेता है। यह देखते हुए कि मैं केवल 35 छेद वाले बोर्ड में गुजर रहा हूं, यह बड़ी संख्या में समस्याओं को हल करने में सक्षम होना चाहिए, लेकिन केवल ~ 66% हल कर सकता है। दूसरों में, कुछ (आमतौर पर 2 या 4) खाली रिक्त स्थान शेष होते हैं, जो हल करना असंभव है (यानी एक अनुचित संख्या board में लिखी गई है।) लगभग हमेशा, यह 9 गुम हो जाएगा।

मैं समझता हूं कि ऐसा सरल समाधान सभी सुडोकस को हल नहीं करेगा। मैं जानबूझ कर इसे आसान दे रहा हूँ।

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

मैं प्रोग्रामिंग के लिए अभी भी नया हूं, इसलिए इसे हल करने के अलावा अन्य सलाह का स्वागत होगा। (विशेष रूप से possible को अनुकूलित करना। यह आज तक लिखा गया सबसे बड़ा कोड है।)

धन्यवाद!

Answer 1

मैंने आपका कोड पढ़ना शुरू कर दिया, लेकिन यह लंबे समय से ऐसा लगता है, और उन लूपों को बहुत गन्दा हो जाता है। तुरंत मुझ पर कुछ भी नहीं निकलता है। आपने कहा था कि आप सिर्फ समाधान नहीं चाहते हैं, लेकिन सलाह।

आपको यह पता लगाना होगा कि समस्या आपके डिजाइन के साथ है (यह सुडोकू को हल करने के लिए काम नहीं करती है) या अगर कार्यान्वयन में कहीं भी एक साधारण बग है। हो सकता है कि प्रत्येक पाश क्या पूरा कर रहा है, "रबड़ बतख परीक्षण" पर टिप्पणियां लिखें और लिखें, जिससे सब कुछ समझाने के लिए मजबूर किया जा रहा है, आप खुद को रोक देंगे और महसूस करेंगे कि कुछ अनावश्यक है, या यह नहीं होना चाहिए। यह डिजाइन समस्याओं के साथ मदद करता है।

यदि समस्या कार्यान्वित है, तो क्या आप जानते हैं कि औपचारिक रूप से किसी एप्लिकेशन को कैसे डिबग करना है? ब्रेकपॉइंट्स सेट करें और निर्देश के माध्यम से निर्देश के माध्यम से चलना? अगर आपको थोड़ा बग मिला है, लेकिन आप नहीं देखते हैं कि, कहां जाना है। वास्तव में एक साधारण उदाहरण केस खोजें जो विफल रहता है, फिर उस परीक्षण को चलाएं और शुरुआत में इसे तोड़ दें। के माध्यम से कदम, और तर्क के साथ पालन करें। उम्मीद है कि आप देखेंगे कि यह कहाँ से घबरा गया है। JUnit परीक्षण या लॉग कथन लिखना बहुत अच्छा है, लेकिन जब आपको एक मुश्किल बग मिलती है, तो आपको कुछ वास्तविक ब्रेकपॉइंट डीबगिंग करना होगा।

आपका सामान्य ढांचा अच्छा है, आपके पास डेटा रखने के लिए कुछ ऑब्जेक्ट्स हैं, और एक अच्छी साफ हल विधि है जो उनके माध्यम से कुछ अलग तरीकों और लूप को कॉल करती है। लेकिन उन तरीकों में से प्रत्येक, वाह, वे निश्चित रूप से गन्दा हैं। उस तरह का कोड, एक ही वैरिएबल नामों का उपयोग करके तंग लूपों के बहुत सारे, सरणी हेरफेर के बहुत सारे, कुछ फ़्लब करना और बग प्राप्त करना इतना आसान है और यह बग को पढ़ने और खोजने में वाकई मुश्किल है।

ग्रहण जावा को डीबग करना बहुत आसान बनाता है, अगर आपने पहले नहीं किया है। Google पर बहुत अच्छे ट्यूटोरियल हैं, इसलिए मैं^_ ~

Answer 2

परेशान नहीं करूंगा आप बैकट्रैकिंग तंत्र को लागू नहीं कर रहे हैं। यदि आपके पास सही ह्युरिस्टिक लागू नहीं है तो आपको कुछ बार अनुमान लगाना होगा।

हेरिस्टिक "व्यापार की चाल" हैं, यहां एक list of common ones for sudoku है।

यदि आपने केवल उनमें से कुछ प्रोग्राम किए हैं, तो आप मृत-अंत में पहुंच जाएंगे और अनुमान लगाना होगा। यह अधिक कठिन बनाता है क्योंकि इन्हें ध्यान में रखना होगा कि उन अनुमान गलत हो सकते हैं। बैकट्रैकिंग एक ऐसी रणनीति है जो आपको कुछ अनुमानों को "रोलबैक" करने और अलग-अलग बनाने की अनुमति देगी। सुडोकू को हल करने के लिए किसी प्रकार का ब्रूटफोर्स बनाने की संभावनाओं के पेड़ के रूप में इसके बारे में सोचें।

तो अपने 2 संभावनाएं अधिक heuristics लागू करने या अनुमान का एक व्यापक रेंज