Sudoku algorithm with backtracking does not return any solution

Question

i'm a bit stuck with the Sudoku algorithm, i coded it using backtrack, and following the theorical steps this should work, and i tried to debuge it, but is too hard (and yes, it solve some numbers and does things)

i paste the code, i hope that you can help me, i really can't see where the problem is...

public void backtracking(int row,int col){
    if(row > 8){ 
        System.out.println("Solution Found!!"); 
        printSudoku(); 

    }
    if (m[row][col] != 0){
       next(row, col);
    }
    else {
        for(int i =1; i < n;i++) 
            if(row(row, i) && col(col, i)) {
                m[row][col] =i;
                next(row, col);
            }
        m[row][col] = 0;
    }


} 

public void next( int row, int col ) {
   if( col < 8)
       backtracking( row, col + 1 ) ;
   else
       backtracking( row+ 1, 0 ) ;
}

public boolean region(int x, int y, int numReg) {
    x = (x / 3) * 3 ;
    y = (y / 3) * 3 ;
    for( int r = 0; r < 3; r++ )
        for( int c = 0; c < 3; c++ )
        if( m[x+r][y+c] == numReg )
           return false ;

     return true ;
}

public boolean row(int x, int k){
    for(int i =0; i < 9; i++)
        if(m[x][i] == k)
            return false;
    return true;
}

public boolean col(int x, int k){
    for(int i =0; i < 9; i++)
        if(m[i][x] == k)
            return false;
    return true;
}

I ommited the "printSudoku" method, is just a double for and you know.

did you already read the questiions about backtracking and sudoku, i.e. : this question or this one even this one — icrovett
– icrovett, Commented Apr 22, 2013 at 17:05
i did, and my solution is based in that questions, but it doesn't work.... i'm not asking just for fun :S — Santanor
– Santanor, Commented Apr 22, 2013 at 18:25

raffael · Accepted Answer · 2013-04-22 17:42:20Z

1

The code seems almost right. As far as i can see you just forgot to call the region method. And I can't see where the variable n is coming from. Try it with this slightly modified backtracking method:

    public static void backtracking(int row, int col) {
    if (row > 8) {
        System.out.println("Solution Found!!");
        printSudoku();
        System.exit(0); //exiting after solution is found
    }
    if (m[row][col] != 0) {
        next(row, col);
    } else {
        for (int i = 1; i <= 9; i++) //replaced i < n with i<=9
            if (row(row, i) && col(col, i) && region(row, col, i)) { //calling region method too
                m[row][col] = i;
                next(row, col);
            }
        m[row][col] = 0;
    }

}

edited Apr 22, 2013 at 17:42

answered Apr 22, 2013 at 17:36

raffael

2,4664 gold badges27 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Santanor Over a year ago

it worked!! Thank you, but... if i may, i have other question for you. If the Sudoku is bad-builded, and i want to find all the solutions aviable? i can't simply delete the "System.exit" line.... do i have to recall the "backtracking" method? or simply modify the "row" of course i want to know what is the correct way to do it, not just "this works and i don't know why :P"

raffael Over a year ago

good question. simply removing System.exit won't work because row is 9 and the next thing you do is access m[row][col]. calling backtracking(0,0) will print the same solution again. I think (not tested) you would have to add another backtracking variable witch starts the for loop at a different number: for (int j = n; j < n+ 9; j++) int i = (j%9)+1

Santanor Over a year ago

hi, maybe you don't care, but had to change the "next" methot to make the algotithm aviable to find all the solutions, it was easy, and not too much lines to change, but i did it!! :D

Collectives™ on Stack Overflow

Sudoku algorithm with backtracking does not return any solution

1 Answer 1

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related