4 Replies - 1044 Views - Last Post: 02 March 2011 - 06:43 PM Rate Topic: -----

#1 roamingstimuli  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 9
  • Joined: 02-March 11

Sudoku recursion assignment : Some advice needed

Posted 02 March 2011 - 06:14 PM

Hi all, first time member ( go easy! ).

Anyways, this assignment calls for the use of recursion
in a Sudoku Solver program.

I feel that my base case and condition is correct ( you can check
the output with those test lines ) but what has me knowing
it's incorrect is that it refuses to backtrack when it finds no more
possible solutions.

Instead of clearing the space behind it, it simply terminates.

As everything on the site warns, I'm not looking for code snippets.
Just looking for guidance. I enjoy figuring these things out but
being totally lost doesn't help.
Thank you guys in advance!

I have omitted most of the code and just placed the method that's giving me issues.
The others are known to work. The (int n) parameter passed to the getSolution method
is the number of blank spaces in the sudoku puzzle.

 private static int[][] getSolution(int n) {
        int count = 0;
        int row = 0;
        int col = 0;
        
        if(n == 0) {
            return grid;
        }
        
        //Gets position of first zero and starts from that point
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                if(grid[i][j] == 0) {
                    count++;
                    if(count == 1) {
                        row = i;
                        col = j;
                        break;
                    }
                }
            }
        }

        //Brute forces numbers out of 1-9 that could fit the space
        for(int num = 1; num < 10; num++) {
           if(checkRow(num,row) && checkCol(num,col) &&
                    checkSubGrid(num,row,col)) {
                grid[row][col] = num;
                //Test purposes
                //System.out.println("Good -- " + num + " Grid: " + row + " " + col);
                //Recursive call
                return getSolution(n-1);
            }
           else {
               //Sets space as zero and moves onto next number
               grid[row][col] = 0;
               //Test purposes
               //System.out.println("Bad -- " + num + " Grid: " + row + " " + col);
               
           }
        }
        
        
       
        //Null value if no solution is found
        return null;
    }




Is This A Good Question/Topic? 0
  • +

Replies To: Sudoku recursion assignment : Some advice needed

#2 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8347
  • View blog
  • Posts: 31,913
  • Joined: 06-March 08

Re: Sudoku recursion assignment : Some advice needed

Posted 02 March 2011 - 06:25 PM

What checkRow(), checkCol() and checkSubGrid() do ?

And when does your recursive method ends ? When it returns null ? What do you do with that null ?
Was This Post Helpful? 0
  • +
  • -

#3 roamingstimuli  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 9
  • Joined: 02-March 11

Re: Sudoku recursion assignment : Some advice needed

Posted 02 March 2011 - 06:32 PM

Oh well checkRow(),checkCol() and checkSubGrid() check if the given
number fits based on all the numbers currently in the row,col and subgrid
of the sudoku board.

I'll put those at the bottom of this post.

My recursive method SHOULD end when it returns 0.
If it returns 0, the puzzle is solved.
If it returns null, there is no solution found.

The 0 ( or the null ) are returned to another class
which outputs either the solution or a message that says
"No solution" but that alternate class is fine as
it was the one provided in the assignment.

Code for row,col,subgrid following:


private static boolean checkRow(int num,int row) {
        for(int c = 0; c < 9; c++) {
            if(grid[row][c] == num) {
                return false;
            }
        }
        return true;
    }

    private static boolean checkCol(int num,int col) {
        for(int r = 0; r < 9; r++) {
            if(grid[r][col] == num) {
                return false;
            }
        }
        return true;
    }

    private static boolean checkSubGrid(int num,int row,int col) {
        row = (row/3) * 3;
        col = (col/3) * 3;
        for(int r = 0; r < 3; r++) {
            for(int c = 0; c < 3; c++) {
                if(grid[row+r][col+c] == num) {
                    return false;
                }
            }
        }
        return true;
    }



Was This Post Helpful? 0
  • +
  • -

#4 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8347
  • View blog
  • Posts: 31,913
  • Joined: 06-March 08

Re: Sudoku recursion assignment : Some advice needed

Posted 02 March 2011 - 06:38 PM

View Postroamingstimuli, on 02 March 2011 - 08:32 PM, said:

My recursive method SHOULD end when it returns 0.
If it returns 0, the puzzle is solved.

It can't return 0 it returns and int[] array
And actually in your code it does not return 0 anywhere, wouldn't even compile
Was This Post Helpful? 0
  • +
  • -

#5 roamingstimuli  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 9
  • Joined: 02-March 11

Re: Sudoku recursion assignment : Some advice needed

Posted 02 March 2011 - 06:43 PM

Oh I just realized I wasn't clear in what I was posting earlier.

if(n == 0) {

return grid;

}



This would be one section where the recursion ends, otherwise referred to as the base case.

The other area is the return null portion for no solution.

This line here...

return getSolution(n-1);



will execute ONLY if a valid location is found for the number that wants to be inserted.
By faith of recursion, I suppose, that line calls the method again with 1 less zero than was previously on
the board because it filled in a space.

Unfortunately for both of us, the code does in fact compile. It just doesn't work how it's supposed to. :\
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1