我正在製作一個數獨程序,並且我創建了一個遞歸算法來解決一個數獨。問題在於,有時候它會完美運行,瞬間完成,有時會卡住,工作數秒鐘,有時我只好退出。 任何想法可能會造成這種情況?遞歸暴力數獨求解器耗時過長
我離開了代碼,因爲我不確定你是如何回答這個問題的(如果你複製並試用它或只是檢查邏輯)。如果你想,我可以寫出片段。
謝謝!
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);
}
}
編輯:我忘了提,solveSudoku方法 一個關鍵的東西,它重新安排一些值。這意味着如果我以** 3開頭,它不會有返回312的問題(這只是一個示例)。所以我認爲在那裏有一些嚴重的邏輯錯誤。
我不認爲這有什麼待解決的問題,但在removeElements中,你正在遞減我在for循環中。不要修改循環體中的循環計數器變量!這使得很難爭論關於循環的終止! – isnot2bad
解決Sudoku的代碼如何?這是一個相當大的問題,是一個蠻力。那裏也有一些隨機性。你可能沒有做錯任何事情。作爲練習,嘗試計算遞歸樹的大小。 – carlosdc
@ isnot2bad:刪除了那個,或者我剛剛遇到了一組隨機的網格,或者它現在預製好了。 – Switha