2

I'm sort of new to Java. Here is my stab at trying to make a Sudoku solver. As of right now this doesn't have a GUI, to enter the problem you have to modify the code itself. Usually the the program completes the Sudoku in around 30 milliseconds (starting with some filled values) and around 100 milliseconds if it has to start from scratch (starting with a blank sudoku). The problem I faced was that sometimes the programs keeps running without providing a solution, I have to manually stop it. Is that because the sudoku has only 1 or few solutions? or is it because it gets stuck it some kind of loop. What I also notice is that if the far bottom far right (8,8) is filled in the program doesn't even try to solve the sudoku. Perhaps because of the way my code is written it thinks that the sudoku is already solved. Could I instead have it check for the last unfilled spot instead of a fixed position?

package sudoku;

public class Sudoku {

    static int userGrid[][]=new int[][]
            {{0,0,0,0,0,0,0,0,0},
             {0,0,0,0,0,0,0,0,0},
             {0,0,0,0,0,0,0,0,0},
             {0,0,0,0,0,0,0,0,0},
             {0,0,0,0,0,0,0,0,0},
             {0,0,0,0,0,0,0,0,0},
             {0,0,0,0,0,0,0,0,0},
             {0,0,0,0,0,0,0,0,0},
             {0,0,0,0,0,0,0,0,0}};//[Horizontal][Vertical]
    static int grid[][]=new int[9][9];//Program experiments

public static void main(String[] args) {
    for(int i=0;i<9;i+=1) {
        for (int j=0;j<9;j+=1) {
            grid[i][j]=userGrid[i][j];
        }
    }
    print(grid);
    double timeStart=System.currentTimeMillis();
    print(loop(0, 0, grid));
    double timeEnd=System.currentTimeMillis();
    System.out.println("That took "+(timeEnd - timeStart)+" milliseconds to complete");
}
public static int[][] loop(int y, int x, int[][] grid) {
    while(!validity(8, 8, grid) || grid[8][8]==0)//while it's not solved
        {
            if(userGrid[y][x]!=0){

                int yy,xx;
                if (x==8) {yy=y+1;xx=0;} else {yy=y; xx=x+1;}
                loop(yy, xx, grid);

            } else {
            if(grid[y][x]<9) {//going forward

               grid[y][x]+=1;
               if(validity(y, x, grid)) {
                   int yy,xx;
                   if (x==8) {yy=y+1;xx=0;} else {yy=y; xx=x+1;}
                   loop(yy, xx, grid);
               }
            } else {
                grid[y][x]=0;
                break;}
        }
    }
    return grid;
}
public static boolean validity(int x, int y, int[][] grid) {
    String temp="";
    for(int i=0;i<9;i+=1) {
        temp+=Integer.toString (grid[i][y]);//horizontal
        temp+=Integer.toString (grid[x][i]);//vertical
        temp+=Integer.toString (grid[(x/3)*3+i/3][(y/3)*3+i%3]);//square 
    }
    int count=0, idx=0;
    while((idx=temp.indexOf(Integer.toString (grid[x][y]),idx))!=-1)
    {idx+=1;count+=1;}
    return count==3;
}

public static void print(int[][] grid) {
    System.out.println();
    for(int i=0;i<9;i+=1) {
        for (int j=0;j<9;j+=1) {
            System.out.print(grid[i][j]);
        }
        System.out.println();
    }
}
}

EDIT: I debugged the code and found the problems

The glitch was solved by looking for the last unfilled number instead of the bottom rightmost number (8,8)

Another problem I was experiencing was that it would not backtrack behind the preexisting numbers and would get stuck in an infinite loop. That was why it was running endlessly.

FIXED code:

package sudoku;

public class Sudoku {

    static int userGrid[][]=new int[][]
            {{2,0,0,4,0,0,0,0,0},
             {0,0,4,0,9,0,0,0,0},
             {0,0,0,0,6,0,8,7,0},
             {7,0,2,0,0,0,0,8,0},
             {0,0,0,7,0,0,0,0,9},
             {0,4,9,0,0,2,0,0,5},
             {0,8,0,0,0,7,1,9,3},
             {0,5,0,0,0,4,0,0,0},
             {0,0,0,8,0,0,0,0,0}};//[Horizontal][Vertical]
    static int grid[][]=new int[9][9];//Program experiments

    //static String pGrid[][]=new String[9][9];//Possibilities

public static void main(String[] args) {
    for(int i=0;i<9;i+=1) {
        for (int j=0;j<9;j+=1) {
            grid[i][j]=userGrid[i][j];
        }
    }
    print(grid);
    double timeStart=System.currentTimeMillis();

    int lastPos = findLastCell();
    if (lastPos == 0){
        return;
    }
    int lastY = lastPos % 16;
    int lastX = lastPos / 16;

    print(loop(0, 0, lastY, lastX, grid));
    double timeEnd=System.currentTimeMillis();
    System.out.println("That took "+(timeEnd - timeStart)+"            milliseconds to complete");


}

public static int findLastCell(){
    for (int i=8; i>=0; i--){
        for (int j=8; j>=0; j--){
            if (userGrid[i][j]==0){
                return ((j * 16) + i);
            }
        }
    }
    return 0;
}

public static int[][] loop(int y, int x, int lastY, int lastX, int[][] grid) {
    while(!validity(lastY, lastX, grid) || grid[lastY][lastX]==0)//while it's not solved
        {
            while (userGrid[y][x]!=0){
                if (x==8)
                {
                    // System.out.println("Here 2");
                    y=y+1;
                    x=0;
                }
                else
                {
                    x=x+1;
                }  
            }
            if(grid[y][x]<9) {//going forward

               grid[y][x]+=1;
               if(validity(y, x, grid)) {
                   int yy,xx;
                   if (x==8)
                   {
                       //System.out.println("Here");
                       yy=y+1;
                       xx=0;
                   }
                   else
                   {
                       yy=y;
                       xx=x+1;
                   }
                   loop(yy, xx, lastY, lastX, grid);
               }
            } else {
                grid[y][x]=0;
                break;}
        }
    return grid;
}

public static boolean validity(int x, int y, int[][] grid) {
    String temp="";
    for(int i=0;i<9;i+=1) {
        temp+=Integer.toString (grid[i][y]);//horizontal
        temp+=Integer.toString (grid[x][i]);//vertical
    }
    for (int i=0; i<3; i++){
        for (int j=0; j<3; j++){
        temp+=Integer.toString (grid[(x/3)*3+i][(y/3)*3+j]);
        //square (Java doesn't round the divided no.s if they
        //are fractions. It jjust outputs them as 0
        }
    }

    int count=0, idx=0;
    while((idx=temp.indexOf(Integer.toString (grid[x][y]),idx))!=-1)
    {idx+=1;count+=1;}

    return count==3;
}

public static void print(int[][] grid) {
    System.out.println();
    for(int i=0;i<9;i+=1) {
        for (int j=0;j<9;j+=1) {
            System.out.print(grid[i][j]);
        }
        System.out.println();
    }
}
}

I will, however, add that the answers I received were less than helpful.

4
  • Very ambiguous question. There are lots of sudoku backtracking solution questions on stackoverflow. Do they help?
    – K.Nicholas
    Feb 7, 2016 at 18:44
  • Most of them are done differently and no one is far enough to have experienced this glitch. I am unclear on what details might be needed
    – Dr. K1NG
    Feb 7, 2016 at 21:08
  • 1
    Me too. Surely you don't expect us to debug your code?
    – K.Nicholas
    Feb 8, 2016 at 6:43
  • Maybe you could start decoupling your code and add methods like checkRow checkColumn and redesign your loop.
    – user
    Feb 8, 2016 at 12:21

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.