sudoku recursive backtracking

[fulmont99]

Hi All,
I am currently trying to program a solve function for a sudoku game. I am using wirths try algorithm to try and do this and I am finding it very difficult. Could anyone give me some tips on what im doing wrong?
At the minute im getting an array out of bounds exception because the function trys to check the value 10 for the second free space, im unsure how to stop this happening, and how to get the function to backtrack if it does. Here is the code

    public void solver(int row, int col, boolean ok)
    {
    	//Skip past any cells which are already filled
    	
    	while(!game[row][col].getText().equals("")) //skip past any cells already added
         	{         		
         		System.out.println("skipping " +row+" "+col);
         		         		
            	if(col == 8 )
            	{
            		totalSquares++;
            		solver(row+1,0,ok);          		
            	}
            	else
            	{
            		totalSquares++;
            		solver(row,col+1,ok);
            	}
         }
         
    	//k is initialised as 0
    	//repeat while puzzle not finished	
		while(totalSquares!=81 || ok)
    	{
    		//select the next candidate and initialise ok
    		k=k+1;  System.out.println("k+1= "+k);
    		ok=false;
    		
    		//check if the current value can be placed in this squaer
    		if(checkRow(row, k) && checkCol(col, k) && checkGrid(minigrid(row,col), k))
    		{
    			//add the value to the display (addvalue()) and remove from possible values for that row, column, minigrid
    			System.out.println("Adding "+k);
    			addvalue(row,col,k);														
	  	 		removeFromSets(row, col, minigrid(row,col), k);
	  	 		totalSquares++;
	  	 		
	  	 		//If not completed
	  	 		if(totalSquares!=81)
	  	 		{
	  	 			if(col==8)
	  	 			{
	  	 				// try the next square (recursive call)
	  	 				
	  	 				solver(row, col++, ok);    
	  	 				if(!ok)  // if the next value is not ok, remove the value
	  	 				{
	  	 					removevalue(row,col);
	  	 					addToSets(row, col, minigrid(row,col), k);
	  	 					totalSquares--;
	  	 				}
	  	 			}
	  	 			else
	  	 			{
	  	 				solver(row++, 0, ok);
	  	 				if(!ok)
	  	 				{
	  	 					removevalue(row,col);
	  	 					addToSets(row, col, minigrid(row,col), k);
	  	 					totalSquares--;
	  	 				}
	  	 			}
	  	 			
	  	 		}
	  	 		else
	  	 		{ //otherwise finished
	  	 			ok=true;
	  	 		}
    		}
    	}
    	
    }

 

[Diancecht]

At first sight:

- Recursion is ineffective, low performace and difficult to follow
- I think you don't check the exit condition for rows.


Cheers,
Dian

 

[fulmont99]

Thanks for the help but i got it working