Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 5 of 5

Thread: Sudoku Solution Generator

  1. #1
    Junior Member
    Join Date
    May 2014
    Posts
    3
    My Mood
    Lurking
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Sudoku Solution Generator

    I know what is going wrong with the program but I am honestly lost on how to fix it. The problem is that is eventually getting stuck because there is no possible place to put a number. I would really appreciate some help on how to fix this problem, or even just some hints to guide me in the right direction please.
    The main file.
    package sudoku;
    public class Sudoku {
     
        public static void main(String[] args) {
            //creating the arrays that will store the solution and the puzzle
            int solution[][] = new int[9][9];
            int puzzle[][] = new int[9][9];
            //creating the object
            SudokuMaker newSudoku = new SudokuMaker();
            //this asks if you want directions
            newSudoku.Directions();
            //this asks the difficulty of puzzle you want
            newSudoku.Difficulty();
            //this sends solution to a method to create the solution
            newSudoku.Solution(solution);
            //this sets puzzle and solution equal to each other
            //switch tester with solution and comment 
            //out newSudoku.Soltuion and newSudoku.PrintArray(solution)
            //since the Soltuion method doesn't always work
            newSudoku.Equalizer(solution,puzzle);
            //this takes out numbers making it a puzzle
            newSudoku.PuzzleMaker(puzzle);
            //This prints them out
            System.out.println("Here is the puzzle.");
            newSudoku.PrintArray(puzzle);
            System.out.println("Here is the solution.");
            newSudoku.PrintArray(solution);
        }
    }
    The class file.
    package sudoku;
    import java.util.*;
     
    public class SudokuMaker {
        //This is so I can use random numbers later on
        Random randomnum = new Random();
        //So I can ask questions of the user
        Scanner reader = new Scanner(System.in);
        //my state variables
        int x;
     
        //this method asks if you want directions or not by using Scanner with a string
        //if you say yes it prints the directions if no it does nothing
        //if you do something else it ends the program
        public void Directions(){
            String choice;
            System.out.println("Do you want the directions? Yes or no.");
            choice=reader.nextLine();
            if (choice.equalsIgnoreCase("Yes") || choice.equalsIgnoreCase("Y")){
                System.out.println("This program will print out a Sudoku puzzle and answer for you.\nIn the puzzle it will will have numbers placed in a 9 by 9 box.\nThere will be columns, rows and 9 3 by 3 boxes.\nYou can only have one copy of the numbers 1 through 9 in each column, row, and 3 by 3 box.\nThere will be boxes with the number 0 in them.\nThis is where you put a number that could possibly be there.\nThis program will aslo tell you the solution.");
            }
            else if(choice.equalsIgnoreCase("No")||choice.equalsIgnoreCase("N")){
     
            }
            else{
                System.out.println("That was not an option. No Sudoku for you. Now ending program.");
                System.exit(0);
            }
        }
     
        //this program asks what difficulty you want
        //choice 1 is easy and choice 2 is hard
        //this uses a scanner and int to read that
        //there is a while loop in there for if in case you pick something other than 1 or 2 it ends the program
        public void Difficulty(){
            boolean validInput=false;
            System.out.println("Pick a difficulty.\n1. Easy\n2. Hard");
            while(!validInput){
                try{
                    x=reader.nextInt();
                    validInput=true;
                    if(x>3){
                        System.out.println("That was not an option. No Sudoku for you. Now ending program.");
                        System.exit(0);
                    }
                    else if(x<1){
                        System.out.println("That was not an option. No Sudoku for you. Now ending program.");
                        System.exit(0);
                    }
                }
                catch(InputMismatchException e){
                    System.out.println("That was not an option. No Sudoku for you. Now ending program.");
                    System.exit(0);
                }
            }
        }
     
        //this program sets up a nested loop that will print any 9by9 array sent to it
        public void PrintArray(int k[][]) {
            for (int row = 0; row < 9; row++) {
                for (int col = 0; col < 9; col++) {
                    System.out.print(k[row][col] + "\t");
                }
                System.out.println(" ");
            }
        }
     
        //this program makes the solution
        //it does this by having two integers one for columns and one for rows
        //it then calls a method which places all the numbers
        //it does this by using a loop from 1-9 and sending it the number that the loop is using
        //the it returns the solution
        public int[][] Solution(int sol[][]) {
            int col=0;
            int row=0;
            for(int num=1;num<10;num++){
                NumberPlacer(num,sol);
            }
            return sol;
        }
     
        //this says if there is a number greater than zero do not put a number here
        //this makes it so if a number was already placed somewhere it won't be overwritten
        public boolean Forbidden(int row, int col,int sol[][]){
            if(sol[row][col]>0){
                return true;
            }
            return false;
        }
     
        //this method does most of the work
        //it starts with box 5(the middle box) and puts a number there
        //it then goes to the boxes on the left(box 4)and puts a number there while also making sure it is possible to put the number there
        //after that it does the same for the box to the right(box 6), above(box 2), and below(box 7) of box 5
        //it then does the four corner boxes, box 1, box 3, box 7, box 9
        //it does this for all numbers sent which is one through 9
        public void NumberPlacer(int num, int sol[][]){
            int col=0;
            int row=0;
            //box5
            while(true){
                row=RowSet2(row);
                col=ColSet2(col);
                while(Forbidden(row,col,sol)){
                    row=RowSet2(row);
                    col=ColSet2(col);
                }
                sol[row][col]=num;
                if(!CheckCol(col,row,num,sol)||!CheckRow(row,col,num,sol)){
                    sol[row][col]=0;
                } 
                else if(CheckCol(col,row,num,sol)&&CheckRow(row,col,num,sol)){
                    break;
                }
            }
            //box4
            while(true){
                row=RowSet2(row);
                col=ColSet1(col);
                while(Forbidden(row,col,sol)){
                    row=RowSet2(row);
                    col=ColSet1(col);
                }
                sol[row][col]=num;
                if(!CheckRow(row,col,num,sol)){
                    sol[row][col]=0;
                } 
                else if(CheckRow(row,col,num,sol)){
                    break;
                }
            }
            //box6
            while(true){
                row=RowSet2(row);
                col=ColSet3(col);
                while(Forbidden(row,col,sol)){
                    row=RowSet2(row);
                    col=ColSet3(col);
                }
                sol[row][col]=num;
                if(!CheckRow(row,col,num,sol)){
                    sol[row][col]=0;
                } 
                else if(CheckRow(row,col,num,sol)){
                    break;
                }
            }
            //box2
            while(true){
                row=RowSet1(row);
                col=ColSet2(col);
                while(Forbidden(row,col,sol)){
                    row=RowSet1(row);
                    col=ColSet2(col);
                }
                sol[row][col]=num;
                if(!CheckCol(col,row,num,sol)){
                    sol[row][col]=0;
                } 
                else if(CheckCol(col,row,num,sol)){
                    break;
                }
            }
            //box8
            while(true){
                row=RowSet3(row);
                col=ColSet2(col);
                while(Forbidden(row,col,sol)){
                    row=RowSet3(row);
                    col=ColSet2(col);
                }
                sol[row][col]=num;
                if(!CheckCol(col,row,num,sol)){
                    sol[row][col]=0;
                } 
                else if(CheckCol(col,row,num,sol)){
                    break;
                }
            }
            //box1
            while(true){
                row=RowSet1(row);
                col=ColSet1(col);
                while(Forbidden(row,col,sol)){
                    row=RowSet1(row);
                    col=ColSet1(col);
                }
                sol[row][col]=num;
                if(!CheckCol(col,row,num,sol)||!CheckRow(row,col,num,sol)){
                    sol[row][col]=0;
                } 
                else if(CheckCol(col,row,num,sol)&&CheckRow(row,col,num,sol)){
                    break;
                }
            }
            //box3
            while(true){
                row=RowSet1(row);
                col=ColSet3(col);
                while(Forbidden(row,col,sol)){
                    row=RowSet1(row);
                    col=ColSet3(col);
                }
                sol[row][col]=num;
                if(!CheckCol(col,row,num,sol)||!CheckRow(row,col,num,sol)){
                    sol[row][col]=0;
                } 
                else if(CheckCol(col,row,num,sol)&&CheckRow(row,col,num,sol)){
                    break;
                }
            }
            //box7
            while(true){
                row=RowSet3(row);
                col=ColSet1(col);
                while(Forbidden(row,col,sol)){
                    row=RowSet3(row);
                    col=ColSet1(col);
                }
                sol[row][col]=num;
                if(!CheckCol(col,row,num,sol)||!CheckRow(row,col,num,sol)){
                    sol[row][col]=0;
                } 
                else if(CheckCol(col,row,num,sol)&&CheckRow(row,col,num,sol)){
                    break;
                }
            }
            //box9
            while(true){
                row=RowSet3(row);
                col=ColSet3(col);
                while(Forbidden(row,col,sol)){
                    row=RowSet3(row);
                    col=ColSet3(col);
                }
                sol[row][col]=num;
                if(!CheckCol(col,row,num,sol)||!CheckRow(row,col,num,sol)){
                    sol[row][col]=0;
                } 
                else if(CheckCol(col,row,num,sol)&&CheckRow(row,col,num,sol)){
                    break;
                }
            }
        }
     
        //this is for the first row of boxes or rows 0-2
        public int RowSet1(int row){
            row=randomnum.nextInt(3);
            return row;
        }
     
        //this is for the second row of boxes or rows 3-5
        public int RowSet2(int row){
            row=randomnum.nextInt(3)+3;
            return row;
        }
     
        //this is for the third row of boxes or rows 6-8
        public int RowSet3(int row){
            row=randomnum.nextInt(3)+6;
            return row;
        }
     
        //this is for the first cols of boxes or cols 0-2
        public int ColSet1(int col){
            col=randomnum.nextInt(3);
            return col;
        }
     
        //this is for the second cols of boxes or cols 3-5
        public int ColSet2(int col){
            col=randomnum.nextInt(3)+3;
            return col;
        }
     
        //this is for the first cols of boxes or cols 6-8
        public int ColSet3(int col){
            col=randomnum.nextInt(3)+6;
            return col;
        }
     
        //this checks the row for the number it is sent and makes sure it is not in that row other than that spot the number is in
        public boolean CheckRow(int row, int y, int num, int sol[][]) {
            for (int col = 0; col < 9; col++) {
                if((row==row)&&(col==y)){
                    continue;
                }
                if (sol[row][col] == num) {
                    return false;
                }
            }
            return true;
        }
     
        //this checks the col for the number it is sent and makes sure it is not in that col other than that spot the number is in
        public boolean CheckCol(int col,int x, int num, int sol[][]) {
            for (int row = 0; row < 9; row++) {
                if((col==col)&&(row==x)){
                    continue;
                }
                if (sol[row][col] == num) {
                    return false;
                }
            }
            return true;
        }
     
        //this is to set two 9by9 arrays equal to each other
        public int[][] Equalizer(int sol[][], int puzz[][]){
            for(int row=0;row<9;row++){
                for(int col=0;col<9;col++){
                    puzz[row][col]=sol[row][col];
                }
            }
            return puzz;
        }
     
        //this creates the puzzle depending on what difficulty you chose
        //it chooses random spots to set too 0
        //these are still solvable 
        public int[][] PuzzleMaker(int puzz[][]){
            int numberRemoved=0;
            int row=0;
            int col=0;
            if(x==1){
                //box1
                while(numberRemoved<4){
                    row=RowSet1(row);
                    col=ColSet1(col);
                    while(puzz[row][col]==0){
                        row=RowSet1(row);
                        col=ColSet1(col);
                    }
                    puzz[row][col]=0;
                    numberRemoved++;
                }
                numberRemoved=0;
                //box2
                while(numberRemoved<4){
                    row=RowSet1(row);
                    col=ColSet2(col);
                    while(puzz[row][col]==0){
                        row=RowSet1(row);
                        col=ColSet2(col);
                    }
                    puzz[row][col]=0;
                    numberRemoved++;
                }
                numberRemoved=0;
                //box3
                while(numberRemoved<4){
                    row=RowSet1(row);
                    col=ColSet3(col);
                    while(puzz[row][col]==0){
                        row=RowSet1(row);
                        col=ColSet3(col);
                    }
                    puzz[row][col]=0;
                    numberRemoved++;
                }
                numberRemoved=0;
                //box4
                while(numberRemoved<4){
                    row=RowSet2(row);
                    col=ColSet1(col);
                    while(puzz[row][col]==0){
                        row=RowSet2(row);
                        col=ColSet1(col);
                    }
                    puzz[row][col]=0;
                    numberRemoved++;
                }
                numberRemoved=0;
                //box5
                while(numberRemoved<4){
                    row=RowSet2(row);
                    col=ColSet2(col);
                    while(puzz[row][col]==0){
                        row=RowSet2(row);
                        col=ColSet2(col);
                    }
                    puzz[row][col]=0;
                    numberRemoved++;
                }
                numberRemoved=0;
                //box6
                while(numberRemoved<4){
                    row=RowSet2(row);
                    col=ColSet3(col);
                    while(puzz[row][col]==0){
                        row=RowSet2(row);
                        col=ColSet3(col);
                    }
                    puzz[row][col]=0;
                    numberRemoved++;
                }
                numberRemoved=0;
                //box7
                while(numberRemoved<4){
                    row=RowSet3(row);
                    col=ColSet1(col);
                    while(puzz[row][col]==0){
                        row=RowSet3(row);
                        col=ColSet1(col);
                    }
                    puzz[row][col]=0;
                    numberRemoved++;
                }
                numberRemoved=0;
                //box8
                while(numberRemoved<4){
                    row=RowSet3(row);
                    col=ColSet2(col);
                    while(puzz[row][col]==0){
                        row=RowSet3(row);
                        col=ColSet2(col);
                    }
                    puzz[row][col]=0;
                    numberRemoved++;
                }
                numberRemoved=0;
                //box9
                while(numberRemoved<4){
                    row=RowSet3(row);
                    col=ColSet3(col);
                    while(puzz[row][col]==0){
                        row=RowSet3(row);
                        col=ColSet3(col);
                    }
                    puzz[row][col]=0;
                    numberRemoved++;
                }
            }
            else if(x==2){
               //box1
                while(numberRemoved<5){
                    row=RowSet1(row);
                    col=ColSet1(col);
                    while(puzz[row][col]==0){
                        row=RowSet1(row);
                        col=ColSet1(col);
                    }
                    puzz[row][col]=0;
                    numberRemoved++;
                }
                numberRemoved=0;
                //box2
                while(numberRemoved<5){
                    row=RowSet1(row);
                    col=ColSet2(col);
                    while(puzz[row][col]==0){
                        row=RowSet1(row);
                        col=ColSet2(col);
                    }
                    puzz[row][col]=0;
                    numberRemoved++;
                }
                numberRemoved=0;
                //box3
                while(numberRemoved<5){
                    row=RowSet1(row);
                    col=ColSet3(col);
                    while(puzz[row][col]==0){
                        row=RowSet1(row);
                        col=ColSet3(col);
                    }
                    puzz[row][col]=0;
                    numberRemoved++;
                }
                numberRemoved=0;
                //box4
                while(numberRemoved<5){
                    row=RowSet2(row);
                    col=ColSet1(col);
                    while(puzz[row][col]==0){
                        row=RowSet2(row);
                        col=ColSet1(col);
                    }
                    puzz[row][col]=0;
                    numberRemoved++;
                }
                numberRemoved=0;
                //box5
                while(numberRemoved<5){
                    row=RowSet2(row);
                    col=ColSet2(col);
                    while(puzz[row][col]==0){
                        row=RowSet2(row);
                        col=ColSet2(col);
                    }
                    puzz[row][col]=0;
                    numberRemoved++;
                }
                numberRemoved=0;
                //box6
                while(numberRemoved<5){
                    row=RowSet2(row);
                    col=ColSet3(col);
                    while(puzz[row][col]==0){
                        row=RowSet2(row);
                        col=ColSet3(col);
                    }
                    puzz[row][col]=0;
                    numberRemoved++;
                }
                numberRemoved=0;
                //box7
                while(numberRemoved<5){
                    row=RowSet3(row);
                    col=ColSet1(col);
                    while(puzz[row][col]==0){
                        row=RowSet3(row);
                        col=ColSet1(col);
                    }
                    puzz[row][col]=0;
                    numberRemoved++;
                }
                numberRemoved=0;
                //box8
                while(numberRemoved<5){
                    row=RowSet3(row);
                    col=ColSet2(col);
                    while(puzz[row][col]==0){
                        row=RowSet3(row);
                        col=ColSet2(col);
                    }
                    puzz[row][col]=0;
                    numberRemoved++;
                }
                numberRemoved=0;
                //box9
                while(numberRemoved<5){
                    row=RowSet3(row);
                    col=ColSet3(col);
                    while(puzz[row][col]==0){
                        row=RowSet3(row);
                        col=ColSet3(col);
                    }
                    puzz[row][col]=0;
                    numberRemoved++;
                }
            }
     
            return puzz;
        }
    }
    Thanks everyone for your help.


  2. #2
    Super Moderator
    Join Date
    Jun 2013
    Location
    So. Maryland, USA
    Posts
    4,495
    My Mood
    Mellow
    Thanks
    152
    Thanked 610 Times in 597 Posts

    Default Re: Sudoku Solution Generator

    Welcome to the forum! Thank you for taking the time to learn to post code correctly. If you haven't already, please read this topic to learn other useful info for new members.

    Where does it appear to be getting stuck? If you're not sure, add prints throughout the program to determine how far it gets and where it is getting stuck. Once you know that, find the specific code, whether it's a loop or recursive logic - whatever it is, that is causing the program to become stuck. Then work that code to determine why it is not escaping. Add additional prints to get the variable values at the point it gets stuck and determine why those values are preventing progress.

    Your program is commented at the method level (thanks), but I don't see an overall description of what it does. It looks like:

    It gets the difficulty level from the user
    Generates a puzzle

    And after that I get lost. I don't understand the output of the puzzle generator. Is an entire puzzle created, all filled in, and stored as the solution? Is then that solution presented to the user with some of the numbers removed (set to zero) as the puzzle to solve?

    The NumberPlacer() method is also confusing. Can you describe how that works? How is it determined that a valid and solvable puzzle has been created?

  3. #3
    Junior Member
    Join Date
    May 2014
    Posts
    3
    My Mood
    Lurking
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Sudoku Solution Generator

    I did have print statements in there. Basically it asks if you want directions or not, it then asks the difficulty which you understood. I then have it set up so a method has a different method in a loop such that starting with number 1 it will put a 1 in each three by three box. Then it does the 2;s and 3's and so on up till and including the number 9. I did have print statements earlier on and where it get's is completely random every time. As it goes through putting the numbers there it checks the row and column to see if this number is allowed there. If it isn't it puts it in a different spot, however sometimes there are no other spots it can put the number. The program then takes the solution(provided it finished) and depending on the difficulty takes some numbers out to create the puzzle. The puzzle method works I have checked with several different hard coded Sudoku solutions. The problem is that a solution is not always being made and it gets stuck on a number and the code never finishes.

  4. #4
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,237
    Thanks
    176
    Thanked 817 Times in 760 Posts
    Blog Entries
    5

    Default Re: Sudoku Solution Generator

    While I did not look through all of your code (its a lot of code, much of which seems like extra code unrelated to the problem), I'll make some assumptions - one of which is that it is getting 'stuck' when it tries to create a random, complete puzzle. Another assumption is that the algorithm used to create the solution randomly fills up the grid, relying on the rules as it goes -this by itself will not always create a solution, and your algorithm will most likely need to backtrack (think recursion) to find the placement of numbers. This being said, an even easier way to create a randomized, solved sudoku is via column/row shuffling. See: How To Create a Solved Sudoku

    If these assumptions are incorrect, I recommend restating your problem and trimming down your code to a point in which it focuses on the problem at hand (as an SSCCE).

  5. #5
    Junior Member
    Join Date
    May 2014
    Posts
    3
    My Mood
    Lurking
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Sudoku Solution Generator

    Okay thank you very much. I will try to come up with a way to shuffle the rows and columns like the way they show in the link you put.

Similar Threads

  1. Sudoku
    By Puleng in forum What's Wrong With My Code?
    Replies: 1
    Last Post: February 14th, 2014, 02:50 AM
  2. Sudoku
    By davasile in forum What's Wrong With My Code?
    Replies: 1
    Last Post: November 20th, 2013, 11:18 PM
  3. Help with turning Sudoku into Magic Sudoku
    By Murlio in forum Java Theory & Questions
    Replies: 1
    Last Post: November 4th, 2012, 01:49 PM
  4. Good people what's wrong with my sudoku generator[newbie needs help]
    By Achtung in forum What's Wrong With My Code?
    Replies: 8
    Last Post: October 21st, 2012, 11:17 AM
  5. Replies: 0
    Last Post: January 25th, 2011, 12:24 AM

Tags for this Thread