Рекурсивный алгоритм sudoku для рекурсивной обработки занимает слишком много времени

Question

Я делаю программу sudoku, и я создал «рекурсивный алгоритм для решения судоку. Проблема в том, что иногда она работает отлично и мгновенно, иногда она застревает и работает 10 секунд, а иногда мне просто нужно ее бросить. Любые идеи, что может быть причиной этого?

Я оставил код таким, какой он есть, так как я не уверен, как вы отвечаете на вопрос (если вы скопируете и попробуйте или просто проверите логику). Если хотите, я могу просто написать фрагменты.

Спасибо!

import java.util.Random; 

/** 
* @Program Sudoku 
* 
* @date November 2013 
* @hardware MacBook Pro 17", mid 2010, i7, 8GiB RAM 
* @IDE eclipse SDK 4.3.1 
* @purpose generates a valid 9x9 sudoku grid 
* 
*/ 
public class SudokuSolver //seems to werk !! 
{ 
    //create a validitychecker object(will be used as Sudoku.isValid();) 
    validityChecker Sudoku = new validityChecker(); 

    //Create a 2D array where the full sudoku grid will be stored 
    private int[][] grid = new int[9][9]; 

    //Creates a 2D array for the playable sudoku grid (with elements removed) 
    private int[][] playingGrid = new int[9][9]; 

    private Random Ran = new Random(); 



    /** 
    * @purpose use this construct if you wish to generate a new sudoku 
    * @param difficultyLevel removes amount of elements from sudoku using the equation elementToRemove=40+15*difficultyLevel 
    */ 
    SudokuSolver(int difficultyLevel) 
    { 

      //generate an empty grid 
      generateBaseGrid(); 
      //populate it with a valid sudoku 
      solveSudoku(0,0); 
      //store this in a new from which elements shall be removed 
      for(int i = 0; i < grid.length; i++) 
       playingGrid[i] = grid[i].clone();    
      //calculate the amount of elements to be removed 
      int difficultyMultiplier = 15; 
      int baseDifficulty = 40; 
      int difficulty = baseDifficulty+difficultyLevel*difficultyMultiplier; 

      //and remove them 
      removeElements(difficulty); 
    } 

    /** 
    * @purpose use this constructor if you just want to use methods and solve 
    * @param the sudoku you wish to solve. values have to be within the range 1-9(inclusive), and -1 for unknown 
    * @note to get the solved sudoku use the fullGrid getter. 
    */ 


    SudokuSolver(int[][] pg) 
    { 
     //lets clone out the arrays - we don't want to just have references ... 
     for(int i = 0; i < pg.length; i++) 
      grid[i] = pg[i].clone();  
     for(int i = 0; i < grid.length; i++) 
      playingGrid[i] = grid[i].clone(); 
     int coords[] = findOnes(grid); 
     solveSudoku(coords[0],coords[1]); 
     System.out.println(coords[0]+" "+coords[1]); 
    } 

    /** 
    * Use this if you only wish to use the internal methods 
    */ 
    SudokuSolver() 
    {} 


    //this method was implemented later, and I'm too lazy to change methods that use the procedure, but don't call the method. Maybe in next version 
    /** 
    * @purpose creates a copy of the passed array 
    * @param the array you wish to be copied 
    * @return returns a clone of the passed 2D array 
    */ 
    public int[][] cloneBoard(int[][] sudokuArray) 
    { 
     int[][] result = new int[9][9]; 
     for(int i = 0; i < sudokuArray.length; i++) 
      result[i] = sudokuArray[i].clone(); 
     return result; 
    } 


    /* 
    *@purpose fills the grid with -1s; This is for proper functionality during validation 
    */ 
    private void generateBaseGrid() 
    { 
    //iterates through all the values and stores -1s in it 
    for(int r=0;r<9;r++) 
     for(int c=0;c<9;c++) 
      grid[r][c] = -1; 
    //System.out.println("Base Grid Created"); 
    } 



    /** 
    * @purpose checks if there are -1s in the grid, if so the grid is playable (its not a solution) 
    * @return true if its playable 
    */ 
    public boolean isGridPlayable() 
    { 
     for(int i=0;i<9;i++) 
      for(int j=0;j<9;j++) 
       if(grid[i][j]==-1) 
        return true; 
     return false; 
    } 

    /** 
    * 
    * @return the generated grid with all elements (for one without some elements use theGrid()) for generator 
    * @return the solved grid for solver 
    */ 
    public int[][] fullGrid() 
    { 

     return grid; 

    } 

    /** 
    * @purpose returns the playing grid 
    * @return the playable grid 
    */ 
    public int[][] theGrid() 
    { 
     return playingGrid; 
    } 

    /* 
    * @purpose removes "amnt" of elements from the playingGrid 
    * @return whether the current method was successful 
    * @param the amount of elements to be removed 
    */ 
    private boolean removeElements(int amnt) 
    { 
     if(amnt==0) //yay base case 
      return true; 
     for(int i=0; i<20;i++) 
     { 
      int r=Ran.nextInt(9); 
      int c=Ran.nextInt(9); 

      int element=playingGrid[r][c]; 

      if(element!=-1) 
      { 
       playingGrid[r][c]=-1; 
        if(removeElements(amnt-1)) 
         {return true;} 


      }else{playingGrid[r][c]=element;//removed as per suggestioni--;} 
      } 
     } 
    return false; 
    } 






    //--------------Debugging-------------------------------- 
    public void printUserGrid(int[][] printie) 
    { 
     for(int i=0;i<9;i++) 
     { 
     for(int j=0;j<9;j++) 
      { 
      int x = printie[i][j]; 
      String bexp = Integer.toString(x); 
      if(x==-1) 
       bexp="[]"; 
      else bexp+=" "; 
      System.out.print(bexp+" "); 
      if(j==2||j==5) 
       System.out.print(" "); 
      } 
     System.out.println(); 
     if(i==2||i==5) 
      System.out.println(); 
     } 
    } 





// //----------Main only for debugging----------------------- 
    public static void main(String[] args) 
    { 
     SudokuSolver Generator = new SudokuSolver(2); 
     int[][] generatedGrid = Generator.theGrid(); 
     int[][] fullGrid = Generator.fullGrid(); 
     Generator.printUserGrid(fullGrid); 

//  Generator.printUserGrid(generatedGrid); 
     System.out.println("\n\n"); 


     SudokuSolver Solver = new SudokuSolver(generatedGrid); 
     Solver.printUserGrid(fullGrid); 


    } 

} 

EDIT: Одна ключевая вещь, я забыл упомянуть, метод solveSudoku, он перестраивает некоторые значения. Это означает, что если я начинаю с ** 3, у него нет проблемы с возвратом 312 (это просто пример для иллюстрации). Поэтому я предполагаю, что где-то там есть какая-то серьезная логическая ошибка.

Answer 1

Это моя версия SudokuSolver:

import java.awt.*; 
import java.awt.event.*; 
import javax.swing.*; 

class Sudoku 
{ 
    //This member has been intentionally left public, as the solved sudoku is 
    //obtained from here and user will find it much easier to handle this. 
    //The Sudoku input has to be given through this instance variable only. 
    //Moreover, many a times, Sudoku inputs as an edit-able 2D array is more 
    //comfortable than passing a whole 9x9 2D array as a constructor parameter. 
    public String SUDOKU[][]=new String[9][9]; 
    //This variable records the nature of the Sudoku whether solvable or not 
    public boolean VALID=true; 
    public Sudoku()//this constructor can be used to create SUDOKU objects 
    { 
     for(int i=0;i<9;i++) 
      for(int j=0;j<9;j++) 
       SUDOKU[i][j]=""; 
    } 
    private Sudoku(String SDK[][])//This is constructor kept private for program use 
    { 
     SUDOKU=SDK; 
    } 
    //This function checks if a certain digit is possible in a particular cell 
    private boolean isPossible(int n,int i,int j) 
    { 
     for(int a=i/3*3;a<i/3*3+3;a++) 
      for(int b=j/3*3;b<j/3*3+3;b++) 
       if(SUDOKU[a][b].length()==1 && n==Integer.parseInt(SUDOKU[a][b])) 
        return false; 
     for(int k=0;k<9;k++) 
      if(SUDOKU[i][k].length()==1 && n==Integer.parseInt(SUDOKU[i][k]) || SUDOKU[k][j].length()==1 && n==Integer.parseInt(SUDOKU[k][j])) 
       return false; 
     return true; 
    } 
    //The following function is compulsory as it is the only function to place appropriate 
    //possible digits in the cells of the Sudoku. The easiest Sudokus will get solved here. 
    private void fillPossibles() 
    { 
     boolean newdigit=false; 
     for(int i=0;i<9;i++) 
      for(int j=0;j<9;j++) 
       if(SUDOKU[i][j].length()!=1) 
       { 
        SUDOKU[i][j]=""; 
        int count=0; 
        for(int k=1;k<10;k++) 
         if(isPossible(k,i,j)) 
         { 
          SUDOKU[i][j]+=k; 
          count++; 
         } 
        if(count==1) 
         newdigit=true; 
       } 
     if(newdigit) 
      fillPossibles(); 
    } 
    //This following function is optional, if the Sudoku is known to be genuine. As, 
    //in that case it only increases the solving speed!! But if the nature is not known, 
    //this function becomes necessary because the nature of the Sudoku is checked here. 
    //It returns true if any cell is filled with a digit and false for all other cases 
    private boolean deepFillPossibles(int ai,int aj,int bi,int bj,boolean first) 
    { 
     if(SUDOKU!=null) 
      for(char c='1';c<='9';c++) 
      { 
       int count=0,digit=0,possibility=0,i=0,j=0; 
       boolean valid=true; 
       for(int a=ai;a<bi;a++) 
        for(int b=aj;b<bj;b++) 
        { 
         if(SUDOKU[a][b].length()==0) 
          valid=false; 
         for(int k=0;k<SUDOKU[a][b].length();k++) 
          if(SUDOKU[a][b].charAt(k)==c) 
          { 
           if(SUDOKU[a][b].length()>1) 
           { 
            i=a; j=b; count++; 
           } 
           if(SUDOKU[a][b].length()==1) 
            digit++; 
           possibility++; 
          } 
        } 
       //the following code is executed only if solution() is called first time 
       if(first && (digit>1 || valid && possibility==0)) 
       { 
        SUDOKU=null; return false; 
       } 
       if(count==1) 
       { 
        SUDOKU[i][j]=String.valueOf(c); 
        fillPossibles(); return true; 
       } 
      } 
     return false; 
    } 
    //This function is also optional if Sudoku is genuine. It only combines the solving 
    //power of fillPossibles() and deepFillPossibles() to reduce memory consumption 
    //in the next stages. In many cases the Sudoku gets solved at this stage itself. 
    private void solution(boolean first) 
    { 
     fillPossibles(); 
     for(int i=0;i<9;i++) 
      if(deepFillPossibles(i,0,i+1,9,first) || deepFillPossibles(0,i,9,i+1,first) || 
      deepFillPossibles(i/3*3,i%3*3,i/3*3+3,i%3*3+3,first)) 
       i=-1; 
    } 
    //This function is the most challenging. No Sudoku can ever escape solution after 
    //passing this stage. It uses ECHO TREE logic implementing brute force to check all 
    //kinds of combinations until solution is obtained. It returns a null for no solution. 
    private void treeSolution(Tracker track) 
    { 
     if(SUDOKU==null) 
     { 
      track.TRACK_SUDOKU=null; 
      return; 
     } 
     solution(false); 
     //For a genuine sudoku the statement could have been replaced by "fillPossibles();" 
     //(Only it would make solving slower and increase memory consumption!) 
     //But it is risky if there is a doubt regarding the genuineness of the Sudoku 
     int a=-1,b=-1; 
     for(int i=0;i<9;i++) 
      for(int j=0;j<9;j++) 
       if(SUDOKU[i][j].length()>1 && a==-1) 
       { 
        a=i; b=j; 
       } 
       else if(SUDOKU[i][j].length()==0) 
        return; 
     if(a==-1)//checks if the Sudoku is solved or not setting necessary flags 
     { 
      track.TRACK_SOLUTION++; 
      for(int i=0;i<9;i++) 
       for(int j=0;j<9;track.TRACK_SUDOKU[i][j]=SUDOKU[i][j],j++); 
      return; 
     } 
     String temp[][]=new String[9][9]; 
     for(int k=0;k<SUDOKU[a][b].length();k++) 
     { 
      for(int i=0;i<9;i++) 
       for(int j=0;j<9;temp[i][j]=SUDOKU[i][j],j++); 
      temp[a][b]=String.valueOf(SUDOKU[a][b].charAt(k)); 
      new Sudoku(temp).treeSolution(track); 
      //The following condition stops the braching TREE if the Sudoku is solved by 
      //echoing back to the root, depending on the flags set on being solved 
      if(track.TRACK_SOLUTION==2 || track.TRACK_SUDOKU==null) 
       return; 
     } 
     return; 
    } 
    //This is the last function which has public access and can be called by the user. 
    //It sets the Sudoku as null if non-genuine and VALIDity as false if no unique solution 
    public void solve() 
    { 
     try 
     { 
      for(int i=0;i<9;SUDOKU[i][8]=SUDOKU[i][8],SUDOKU[8][i]=SUDOKU[8][i],i++); 
     } 
     catch(Exception e) 
     { 
      SUDOKU=null; VALID=false; return; 
     } 
     Tracker track=new Tracker(); 
     solution(true); 
     treeSolution(track); 
     SUDOKU=track.TRACK_SOLUTION==0?null:track.TRACK_SUDOKU; 
     if(track.TRACK_SOLUTION!=1) 
      VALID=false; 
    } 
} 

//the following class is purposely designed to easily track the changes during solution, 
//including the nature of the Sudoku and the solution of the Sudoku(if possible) 

class Tracker 
{ 
    protected int TRACK_SOLUTION=0; 
    protected String TRACK_SUDOKU[][]=new String[9][9]; 
} 

public class SudokuSolver extends JApplet implements KeyListener, MouseListener 
{ 
    private String SUDOKU[][]=new String[9][9]; 
    private Sudoku SDK=new Sudoku(); 
    private Image BOX[][]=new Image[9][9],SELECT_IMG;//BOX is an array of square images 
    private int SELECT_ROW=4,SELECT_COLUMN=4;//stores the position of the selection box 
    //this function is used to initialize the coloured square images and fonts 
    public void init() 
    { 
     resize(190,190); 
     setFont(new Font("Dialog",Font.BOLD,12)); 
     addMouseListener(this); 
     addKeyListener(this); 
     Graphics g; 
     for(int i=0;i<9;i++) 
      for(int j=0;j<9;SUDOKU[i][j]="",j++) 
      { 
       BOX[i][j]=createImage(22,22); 
       g=BOX[i][j].getGraphics(); 
       if((i/3+j/3)%2==0) 
        g.setColor(Color.yellow); 
       else 
        g.setColor(Color.green); 
       g.fillRect(0,0,21,21); 
       g.setColor(Color.black); 
       g.drawRect(0,0,21,21); 
      } 
     //the following statements colour the selection box red 
     SELECT_IMG=createImage(22,22); 
     g=SELECT_IMG.getGraphics(); 
     g.setColor(Color.red); 
     g.fillRect(0,0,21,21); 
     g.setColor(Color.black); 
     g.drawRect(0,0,21,21); 
    } 
    public void mouseExited(MouseEvent e){} 
    public void mouseEntered(MouseEvent e){} 
    public void mouseReleased(MouseEvent e){} 
    public void mouseClicked(MouseEvent e){} 
    //the following function handles the mouse click operations 
    public void mousePressed(MouseEvent e) 
    { 
     if(SDK.SUDOKU==null) 
     { 
      SDK.SUDOKU=new String[9][9]; 
      for(int i=0;i<9;i++) 
       for(int j=0;j<9;SUDOKU[i][j]="",SDK.SUDOKU[i][j]="",j++); 
      SDK.VALID=true; 
     } 
     if(e.getY()<190 && e.getX()<190 && e.getY()%21!=0 && e.getX()%21!=0) 
     { 
      SELECT_ROW=e.getY()/21; 
      SELECT_COLUMN=e.getX()/21; 
     } 
     repaint(); 
    } 
    public void keyReleased(KeyEvent e){} 
    //this function manages the operations associated with the various keys 
    public void keyPressed(KeyEvent e) 
    { 
     int code=e.getKeyCode(); 
     if(code==KeyEvent.VK_DELETE || code==KeyEvent.VK_BACK_SPACE || code==KeyEvent.VK_SPACE) 
     { 
      SUDOKU[SELECT_ROW][SELECT_COLUMN]=""; SDK.SUDOKU[SELECT_ROW][SELECT_COLUMN]=""; 
     } 
     switch(code) 
     { 
      case KeyEvent.VK_Y : if(SDK.SUDOKU!=null) SDK.VALID=true; break; 
      case KeyEvent.VK_UP : SELECT_ROW=(SELECT_ROW+8)%9; break; 
      case KeyEvent.VK_DOWN : SELECT_ROW=(SELECT_ROW+1)%9; break; 
      case KeyEvent.VK_LEFT : SELECT_COLUMN=(SELECT_COLUMN+8)%9; break; 
      case KeyEvent.VK_RIGHT : SELECT_COLUMN=(SELECT_COLUMN+1)%9; break; 
      case KeyEvent.VK_ENTER : SDK.solve(); break; 
      case KeyEvent.VK_N : if(SDK.SUDOKU!=null){ SDK.VALID=true; code=KeyEvent.VK_ESCAPE;} 
      case KeyEvent.VK_ESCAPE : if(SDK.SUDOKU==null) 
             { 
              SDK.SUDOKU=new String[9][9]; 
              for(int i=0;i<9;i++) 
               for(int j=0;j<9;SUDOKU[i][j]="",SDK.SUDOKU[i][j]="",j++); 
              SDK.VALID=true; 
             } 
             else 
              for(int i=0;i<9;i++) 
               for(int j=0;j<9;SDK.SUDOKU[i][j]=SUDOKU[i][j],j++); 
     } 
     repaint(); 
    } 
    //this function is for entering the numbers in the sudoku grid 
    public void keyTyped(KeyEvent e) 
    { 
     char code=e.getKeyChar(); 
     if(Character.isDigit(code)) 
      switch(code) 
      { 
       case '1': SUDOKU[SELECT_ROW][SELECT_COLUMN]="1"; SDK.SUDOKU[SELECT_ROW][SELECT_COLUMN]="1"; break; 
       case '2': SUDOKU[SELECT_ROW][SELECT_COLUMN]="2"; SDK.SUDOKU[SELECT_ROW][SELECT_COLUMN]="2"; break; 
       case '3': SUDOKU[SELECT_ROW][SELECT_COLUMN]="3"; SDK.SUDOKU[SELECT_ROW][SELECT_COLUMN]="3"; break; 
       case '4': SUDOKU[SELECT_ROW][SELECT_COLUMN]="4"; SDK.SUDOKU[SELECT_ROW][SELECT_COLUMN]="4"; break; 
       case '5': SUDOKU[SELECT_ROW][SELECT_COLUMN]="5"; SDK.SUDOKU[SELECT_ROW][SELECT_COLUMN]="5"; break; 
       case '6': SUDOKU[SELECT_ROW][SELECT_COLUMN]="6"; SDK.SUDOKU[SELECT_ROW][SELECT_COLUMN]="6"; break; 
       case '7': SUDOKU[SELECT_ROW][SELECT_COLUMN]="7"; SDK.SUDOKU[SELECT_ROW][SELECT_COLUMN]="7"; break; 
       case '8': SUDOKU[SELECT_ROW][SELECT_COLUMN]="8"; SDK.SUDOKU[SELECT_ROW][SELECT_COLUMN]="8"; break; 
       case '9': SUDOKU[SELECT_ROW][SELECT_COLUMN]="9"; SDK.SUDOKU[SELECT_ROW][SELECT_COLUMN]="9"; break; 
       default : SUDOKU[SELECT_ROW][SELECT_COLUMN]=""; SDK.SUDOKU[SELECT_ROW][SELECT_COLUMN]=""; 
      } 
    } 
    //the paint() function is designed to print the the sudoku grid and other messages 
    public void paint(Graphics g) 
    { 
     if(!SDK.VALID) 
     { 
      g.setColor(Color.white); 
      g.fillRect(1,1,188,188); 
      g.setColor(Color.black); 
      g.drawRect(0,0,189,189); 
      if(SDK.SUDOKU==null) 
      { 
       g.drawString("INVALID SUDOKU!!",45,80); 
       g.drawString("[PRESS ESCAPE TO RE-ENTER]",10,105); 
      } 
      else 
      { 
       g.drawString("INCOMPLETE SUDOKU!!",30,60); 
       g.drawString("Would you like to see a",30,90); 
       g.drawString("possible solution?",45,105); 
       g.drawString("Y/N",80,120); 
      } 
     } 
     else 
     { 
      for(int i=0;i<9;i++) 
       for(int j=0;j<9;j++) 
       { 
        g.drawImage(BOX[i][j],j*21,i*21,null); 
        g.drawString(SDK.SUDOKU[i][j],8+j*21,15+i*21); 
       } 
      g.drawImage(SELECT_IMG,SELECT_COLUMN*21,SELECT_ROW*21,null); 
      g.drawString(SDK.SUDOKU[SELECT_ROW][SELECT_COLUMN],8+SELECT_COLUMN*21,15+SELECT_ROW*21); 
     } 
    } 
} 

Я пытался использовать минимальную грубую силу там, где это возможно

Answer 2

То, что вы пытаетесь решить это Artificial Intelligence проблема. Переход на brute-force, или лучше называемый простой backtracking, на самом деле означает, что вы, возможно, имеете экспоненциальную временную сложность.

Ожидается, что экспоненциальное решение займет много времени. В некоторых случаях, когда order of guesswork соответствует фактическому решению, ваш решатель вернется с результатом быстрее.

Так что вы можете сделать:

1. Чтение по методике А. И. называется Constraint Satisfaction, и попытаться осуществить это.
2. Читайте о конкретных методах решения судокуиии, возможно, в какой-то исследовательской работе, если есть, и попытайтесь реализовать это.