java sudoku backtracking recursive

Question

hey i have worte this program to solve sudoko but it just workd for a few cells of sudoku matrix and for other cells returns 0 . can u understand whats wrong with this? i am new in java coding and it really hurts not to be able to write a simple program.

public class sudoku {

static int sud[][] = new int[9][9];

public static void main(String args[]) {

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            sud[i][j] = 0;
        }
    }
    solve(sud);
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            System.out.print(sud[i][j]);
        }
        System.out.print("\n");
    }
}

public static boolean solve(int[][] sud) {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (sud[i][j] != 0) {
                continue;
            }
            for (int x = 1; x < 10; x++) {
                if (!used(i, j, x)) {
                    sud[i][j] = x;
                    if (solve(sud)) {
                        return true;
                    }
                }
            }
            return false;
        }
    }
    return true;

}

public static boolean isinrow(int i, int j, int x) {
    for (int t = 0; t < 9; t++) {
        if (sud[i][t] == x) {
            return true;
        }
    }
    return false;
}

public static boolean isincol(int i, int j, int x) {
    for (int t = 0; t < 9; t++) {
        if (sud[t][j] == x) {
            return true;
        }
    }
    return false;

}

public static boolean isinsq(int sr, int sc, int x) {
    for (sr = 0; sr < 3; sr++) {
        for (sc = 0; sc < 3; sc++) {
            if (sud[sr][sc] == x) {
                return true;
            }
        }
    }
    return false;
}

static boolean used(int i, int j, int x) {
    if (!isinrow(i, j, x)) {
        if (!isincol(i, j, x)) {
            if (!isinsq(i - (i % 3), j - (j % 3), x)) {
                return false;
            }
        }
    }
    return true;
}

}

this is output : 123456789 456789000 000000000 000000000 000000000 000000000 000000000 000000000 000000000 — cmin
– cmin, Commented Nov 12, 2013 at 16:14

thermite · Accepted Answer · 2013-11-12 18:42:49Z

1

your problem is in this function you were doing

 public static boolean isinsq(int sr, int sc, int x) {
    for ( sr = 0; sr < 3; sr++) {
         //  ^ you are reseting the value of sr that you pass in
          //   effectivel making it so that you always check the first square
        for (  sc = 0; sc < 3; sc++) {
               // ^ same here    
            if (sud[sr][sc] == x) {
                return true;
            }
        }
    }
    return false;
}

this was resetting sr back to 0 so you only ever checked the top left corner not the coordinates that you were passing in. you should have done something like:

public static boolean isinsq(int xcorner, int ycorner, int x) {
    for (int sr = xcorner; sr < 3; sr++) {
           //^ here w create a new variable with the starting value that you passed in
        for ( int sc = ycorner; sc < 3; sc++) {
                   //^ here w create a new variable with the starting value that you passed in
            if (sud[sr][sc] == x) {
                return true;
            }
        }
    }
    return false;
}

as an asside your Double nested for loop in solve is unnecessary and adds a bunch of overhead. Instead of looking for the next open spot why not assume they are all open and check to see if they aren't this way your recursion will take care of that iterating for you. Consider something like this (its also more simple....at least to me)

bool solve(int[][] sud, int x, int y)
{
//here need to make sure that when x>9 we set x to 0 and increment y
//also if x == 9 and y == 9 need to take care of end condition

if(sud[x][y]==0) //not a pre given value so we are ok to change it
{
    for(int i =1; i<10; ++i)
    {
        sud[x][y] = i;
        if(validBoard(sud)) //no point in recursing further if the current board isnt valid
        {
            if(solve(sud, x+1,y))
            {
                return true;
            }
        }
    }
}
else
{
    return solve(x+1,y);
}
return false;
}

I left some areas that need filling (where's the fun in having me do it for you :). And as everyone else has suggested you should use more meaningful variable names.

edited Nov 12, 2013 at 18:42

answered Nov 12, 2013 at 16:42

thermite

5026 silver badges21 bronze badges

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

2 Comments

cmin Over a year ago

becuz of if (!isinsq(i - (i % 3), j - (j % 3), x)) that will ckeck all the squares, i did what u said but my output is the same :(

cmin Over a year ago

oh i got it! now its better with a better output:))

Jazzy Josh · Accepted Answer · 2013-11-12 16:26:07Z

0

It looks to me that isInSq is always going to check the top left square since you wipe out your arguments when you go into the loop. You should be going from sr to sr + 2 and the same for sc. I don't think that's the only problem, but it looks like a good place to start.

As another tip, I would fix your variable names. You may be able to understand them, but it make it a lot harder for others to read.

answered Nov 12, 2013 at 16:26

Jazzy Josh

2721 silver badge7 bronze badges

Collectives™ on Stack Overflow

java sudoku backtracking recursive

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related