Java sudoku solver not changing empty cells

Question

I am in the process of writing a sudoku solver (still need to write the box check and actually complete the program) but I'm testing it as I know. The puzzle I'm testing right now is "very easy" as in there is only one empty cell in any row/column. THe puzzle starts with "empty" cells as zeros. My issues is that when I run the program and print out the puzzle after solve() is called, the zeros aren't changing and the original puzzle is just printed out. Not sure what my issue is, would appreciate some direction!

public ArrayList<Integer> create(){

    ArrayList<Integer> possible = new ArrayList<Integer>(); 

    for(int i=1; i<10; i++){
        possible.add(i);
    }
    return possible;
}
public sudoku( int size )
{
    SIZE = size;
    N = size*size;

    Grid = new int[N][N];
    for( int i = 0; i < N; i++ ) 
        for( int j = 0; j < N; j++ ) 
            Grid[i][j] = 0;
}

public void solve()
{ 
    int a, b, c, d, i, j, k, l; 

    int count = 0;
    int value= 0;

    for(i=0; i<N;i++){
        for(j=0; j<N;j++){  
            if(Grid[i][j]==0){

                ArrayList<Integer> possible = create();

                //check row             
                for(a=0; a<N;a++){
                    for(b=0; b<N; b++){  
                        if(Grid[a][0]==possible.get(a)){
                            possible.set(a, 0);
                        }
                    }
                }
                //check column
                for(c=0; c<N;c++){
                    for(d=0; d<N;d++){  
                        if(Grid[0][d]==possible.get(d)){
                            possible.set(d,0);
                        }
                    }
                }
                for(k=0; k<9; k++){
                    if(possible.get(k)!=0){
                        count++;
                    }
                }
                if(count==1){
                    for(l=0; l<9; l++){
                        if(possible.get(l)!=0){
                            value=possible.get(l);
                        }
                    }
                }
                Grid[i][j]=value;
            }
        }
    }
}

Answer 1

You are always checking only the first row and first column and the way you check for the possible numbers is also not doing what you want.

A few tips first:

First of all, it is not necessary to always define a new variable for the loops, you can reuse them and then you won't have too many of them and you won't get so easily confused in them.

Secondly, if you name all the variables a, b, c, d, etc. you can also easily get confused. While it is ok to name variables in loops as i, j, if you have too many loops, it may be better to think of better names. In this case row and column for example.

Why don't you remove the numbers from the possible list? Something like:

int index = possible.indexOf(a);
if (index != -1) possible.remove(index);

Then it would be easier to determine how many values you still have left. You can simply do:

if (possible.size()==1) value = possible.get(0);

And one last note, to obey the convention for variable names, you should probably use grid instead of Grid.

And now the code:

public void solve() { 
    int row, column, i;
    int count = 0;
    int value= 0;
    int index = 0;

    for(row=0; row<N; row++){
        for(column=0; column<N; column++){  
            if(Grid[row][column]==0){

                ArrayList<Integer> possible = create();

                //check row             
                for(i=0; i<N; i++){
                    index = possible.indexOf(Grid[row][i]);
                    if (index != -1) possible.remove(index);
                }
                //check column
                for(i=0; i<N; i++){
                    index = possible.indexOf(Grid[i][column]);
                    if (index != -1) possible.remove(index);
                }

                if (possible.size()==1) value = possible.get(0);

                Grid[row][column]=value;
            }
        }
    }
}

EDIT: Rewritten the whole answer into a better form.

Answer 2

Look at your line if(Grid[a][0]==possible.get(a)) (and similar spots). What is it doing there vs what do you actually want?

Your possible array looks something like this: [1,2,3,4,5,6,7,8,9]

and your grid (just the first row, since you're only checking Grid[a][0]) might look something like this: [3,7,8,1,2,9,5,0,4]

Your loop is looking at each element stepwise individually and seeing if they're equal, like this:

if(1 == 3) ... it's not
if(2 == 7) ... it's not
if(3 == 8) ... it's not

... etc

So, as you can see, when you do your

for(k=0; k<9; k++){
    if(possible.get(k)!=0){
        count++;
    }
}

Your possible array is still going to be full of options most of the time, unless your first row happens to be some variation on [1,2,3,4,5,6,7,8,9] with a 0 in one of the spaces... so count is definitely going to be > 1

So, your next loop (for(l=0; l<9; l++)) next gets executed, so value is still (as you initialized it) 0.

Try stepping through a debugger on these points and seeing how the arrays are interacting.

Answer 3

if(Grid[a][0]==possible.get(a))

if(Grid[0][d]==possible.get(d))

You don't use b or c in these lines. You probably want:

if(Grid[a][i]==possible.get(b))

if(Grid[j][d]==possible.get(c))

Also, the Grid[i][j]=value check should be inside the if block.

You might want to use a Set for the possible values instead of an ArrayList.