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 15 of 15

Thread: Sudoku: wrong output?

  1. #1
    Junior Member
    Join Date
    Apr 2012
    Posts
    7
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Sudoku: wrong output?

    Here is my "completed" code for a sudoku solver. THe only problem is that the output sudoku is wrong and i dont know where the error might be. Thanks for the help.

    Input file:

    3

    x x x | x x x | x x x
    x 1 x | 6 2 x | x 9 x
    x x 2 | x x 9 | 3 1 x
    ---------------------
    x x 4 | x x 6 | x 8 x
    x x 8 | 7 x 2 | 1 x x
    x 3 x | 8 x x | 5 x x
    ---------------------
    x 6 9 | 1 x x | 4 x x
    x 8 x | x 7 3 | x 5 x
    x x x | x x x | x x x

    Output:
    1 2 3 | 4 5 6 | 7 8 9
    4 5 6 | 7 8 9 | 1 2 3
    7 8 9 | 1 2 3 | 4 5 6
    ---------------------
    2 1 4 | 3 6 5 | 8 9 7
    3 6 5 | 8 9 7 | 2 1 4
    8 9 7 | 2 1 4 | 3 6 5
    ---------------------
    5 3 1 | 6 4 2 | 9 7 8
    6 4 2 | 9 7 8 | 5 3 1
    9 7 8 | 5 3 1 | 6 4 2

    import java.util.*;
    import java.io.*;
     
     
    class Sudoku
    {
        /* SIZE is the size parameter of the Sudoku puzzle, and N is the square of the size.  For 
         * a standard Sudoku puzzle, SIZE is 3 and N is 9. */
        static int SIZE;
     
    	static int N;
     
        /* The grid contains all the numbers in the Sudoku puzzle.  Numbers which have
         * not yet been revealed are stored as 0. */
        static int Grid[][];
     
        /* Default constructor.  This will initialize all positions to the default 0
         * value.  Use the read() function to load the Sudoku puzzle from a file or
         * the standard input. */
        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;
     
        }
     
        //***********************************SOLVE methods****************************************//
     
        /* The solve() method should remove all the unknown characters ('x') in the Grid
         * and replace them with the numbers from 1-9 that satisfy the Sudoku puzzle. */ 
        /** Recursive function to find a valid number for one single cell */
        public static void solve( int i, int j ) throws Exception
        {
     
        	      // Throw an exception to stop the process if the puzzle is solved  	   
        	    if(i>8)
        	    	throw new Exception( "Solution found" ) ;
     
        	         // Find a valid number for the empty cell
        	         for( int num = 1; num <10; num++ ) 
        	          {
        	            if( checkRow(i,num) && checkCol(j,num) && checkBox(i,j,num) )
        	            {
        	               Grid[i][j] = num ;    
     
        	               if(j<8) solve (i,j+1);
        	               else solve(i+1,0);
     
        	            }
        	         }
     
        	         // No valid number was found, clean up and return to caller
        	         Grid[i][j] = 0 ;
     
        	      }
     
        public void startSolve(){
        	try{
        		solve(0,0);}
        		catch(Exception exception)
        		{}
        	}
     
    //**********************************Some CHECK methods************************************//
     
        /** Checks if num is an acceptable value for the given row */
        static boolean checkRow( int i, int num )throws Exception
        {
           for( int j = 0; j < 9; j++ )
              if( Grid[i][j] == num )
                 return false ;
     
           return true ;
        }
     
        /** Checks if num is an acceptable value for the given column */
        static boolean checkCol( int j, int num )throws Exception
        {
           for( int i = 0; i < 9; i++ )
              if( Grid[i][j] == num )
                 return false ;
     
           return true ;
        }
     
        /** Checks if num is an acceptable value for the box around row and col */
        static boolean checkBox( int i, int j, int num )
        {
        	 int k = (i/3);
        	    int l = (j/3);
     
        	    int row = k * 3;
        	    int col = l * 3; 
     
        	    for (int x = 0; x < 3; x++)
        	        for (int y = 0; y < 3; y++)
        	        if(Grid[row+x][col+y] == num )
        	            return false;
     
        	    return true;
     
        }
     
     
        //********************************READ Methods*******************************************//
     
        /* readInteger is a helper function for the reading of the input file.  It reads
         * words until it finds one that represents an integer. For convenience, it will also
         * recognize the string "x" as equivalent to "0". */
        static int readInteger( InputStream in ) throws Exception
        { 
            int result = 0;
            boolean success = false;
     
            while( !success ) {
                String word = readWord( in );
     
                try {
                    result = Integer.parseInt( word );
                    success = true;
                } catch( Exception e ) {
                    // Convert 'x' words into 0's
                    if( word.compareTo("x") == 0 ) {
                        result = 0;
                        success = true; 
                    }
                    // Ignore all other words that are not integers
                }
            }
     
        return result;
        }
     
     
        /* readWord is a helper function that reads a word separated by white space. */
        static String readWord( InputStream in ) throws Exception
        {System.out.println("hello");
        StringBuffer result = new StringBuffer();
        int currentChar = in.read();
        String whiteSpace = " \t\n\r";
     
        // Ignore any leading white space
        while( currentChar!=-1 && whiteSpace.indexOf(currentChar) > -1 ) {
        currentChar = in.read();
        }
     
        // Read all characters until you reach white space
        while( whiteSpace.indexOf(currentChar) == -1 ) {
        result.append( (char) currentChar );
        currentChar = in.read();
     
        }
        return result.toString(); 
     
        }
     
     
        /* This function reads a Sudoku puzzle from the input stream in.  The Sudoku
         * grid is filled in one row at at time, from left to right.  All non-valid
         * characters are ignored by this function and may be used in the Sudoku file
         * to increase its legibility. */
        public void read( InputStream in ) throws Exception
        {
            for( int i = 0; i < N; i++ ) {
                for( int j = 0; j < N; j++ ) {
                    Grid[i][j] = readInteger( in );
                }
            }
        }
     
        //***************************PRINT methods****************************************//
     
        /* Helper function for the printing of Sudoku puzzle.  This function will print
         * out text, preceded by enough ' ' characters to make sure that the printint out
         * takes at least width characters.  */
        static void printFixedWidth( String text, int width )
        {
            for( int i = 0; i < width - text.length(); i++ )
                System.out.print( " " );
            System.out.print( text );
        }
     
     
        /* The print() function outputs the Sudoku grid to the standard output, using
         * a bit of extra formatting to make the result clearly readable. */
        public  void print()
        {
            // Compute the number of digits necessary to print out each number in the Sudoku puzzle
            int digits = (int) Math.floor(Math.log(N) / Math.log(10)) + 1;
     
            // Create a dashed line to separate the boxes 
            int lineLength = (digits + 1) * N + 2 * SIZE - 3;
            StringBuffer line = new StringBuffer();
            for( int lineInit = 0; lineInit < lineLength; lineInit++ )
                line.append('-');
     
            // Go through the Grid, printing out its values separated by spaces
            for( int i = 0; i < N; i++ ) {
                for( int j = 0; j < N; j++ ) {
                    printFixedWidth( String.valueOf( Grid[i][j] ), digits );
                    // Print the vertical lines between boxes 
                    if( (j < N-1) && ((j+1) % SIZE == 0) )
                        System.out.print( " |" );
                    System.out.print( " " );
                }
                System.out.println();
     
                // Print the horizontal line between boxes
                if( (i < N-1) && ((i+1) % SIZE == 0) )
                    System.out.println( line.toString() );
            }
        }
     
     
        //********************************MAIN()*******************************************//
     
        /* The main function reads in a Sudoku puzzle from the standard input, 
         * unless a file name is provided as a run-time argument, in which case the
         * Sudoku puzzle is loaded from that file.  It then solves the puzzle, and
         * outputs the completed puzzle to the standard output. */
        public static void main( String args[] ) throws Exception
        {
            InputStream in;
            if( args.length > 0 ) 
                in = new FileInputStream( args[0] );
            else
                in = System.in;
     
            // The first number in all Sudoku files must represent the size of the puzzle.  See
            // the example files for the file format.
            int puzzleSize = readInteger( in ); 
            if( puzzleSize > 100 || puzzleSize < 1 ) {
                System.out.println("Error: The Sudoku puzzle size must be between 1 and 100.");
                System.exit(-1);
            }
     
            Sudoku s = new Sudoku( puzzleSize );
     
            // read the rest of the Sudoku puzzle
         //s.read( in ); 						
     
            s.startSolve();
     
            // Print out the (hopefully completed!) puzzle
            s.print();
        }
    }
    Last edited by lisa92; April 15th, 2012 at 11:27 AM.


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    21,064
    Thanks
    52
    Thanked 2,282 Times in 2,253 Posts

    Default Re: Sudoku: wrong output?

    Can you add comments explaining what is wrong with the output and post what it should be.
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Member
    Join Date
    Mar 2012
    Location
    United States
    Posts
    118
    My Mood
    Inspired
    Thanks
    1
    Thanked 33 Times in 31 Posts

    Default Re: Sudoku: wrong output?

    After a quick look, I don't believe you ever check to see whether or not the grid position already has a value.

  4. #4
    Junior Member
    Join Date
    Apr 2012
    Posts
    7
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Sudoku: wrong output?

    Correct answer should be:
    5 9 6 | 3 1 7 | 2 4 8
    1 4 3 | 6 2 8 | 7 9 5
    8 7 2 | 4 5 9 | 3 1 6
    --------------------
    2 1 4 | 5 3 6 | 9 8 7
    6 5 8 | 7 9 2 | 1 3 4
    9 3 7 | 8 4 1 | 5 6 2
    --------------------
    7 6 9 | 1 8 5 | 4 2 3
    4 8 1 | 2 7 3 | 6 5 9
    3 2 5 | 9 6 4 | 8 7 1

    How could I check if the Grid[][] already has a value?

  5. #5
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    21,064
    Thanks
    52
    Thanked 2,282 Times in 2,253 Posts

    Default Re: Sudoku: wrong output?

    Where do you read in the data to fill the grid array?
    Add this line to the read() method right after the end of the for(j) loop's ending } and still inside the for(i) loop:
          System.out.println(i + " " +Arrays.toString(Grid[i]));
    It will show the contents of the array as it is read in so you can verify that the program is reading the file correctly.
    If you don't understand my answer, don't ignore it, ask a question.

  6. #6
    Junior Member
    Join Date
    Apr 2012
    Posts
    7
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Sudoku: wrong output?

    Ok I did that and I saw it doesnt read the last row of the sudoku...
    Also, in the main I called the method read() but now it doesnt want to go back to main(). It doesnt give me an error, it just loops about 30 times or so in read() and then stops.

  7. #7
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    21,064
    Thanks
    52
    Thanked 2,282 Times in 2,253 Posts

    Default Re: Sudoku: wrong output?

    Add another println statement in the readInteger() method that prints out the value of word after it is returned from the readWord method.
    If you don't understand my answer, don't ignore it, ask a question.

  8. The Following User Says Thank You to Norm For This Useful Post:

    lisa92 (April 14th, 2012)

  9. #8
    Junior Member
    Join Date
    Apr 2012
    Posts
    7
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Sudoku: wrong output?

    It prints out "x x x | x x x | x x x ".

  10. #9
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    21,064
    Thanks
    52
    Thanked 2,282 Times in 2,253 Posts

    Default Re: Sudoku: wrong output?

    Is that all? It should print out all of the input file.
    And the output should look like this:
    x
    x
    x
    |
    x
    x
    x
    |
    x
    x
    x

    One word on each line.
    If you don't understand my answer, don't ignore it, ask a question.

  11. #10
    Junior Member
    Join Date
    Apr 2012
    Posts
    7
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Sudoku: wrong output?

    Yes that is what I meant, sorry about that. But how is that supposed to help figure out whats the problem?

  12. #11
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    21,064
    Thanks
    52
    Thanked 2,282 Times in 2,253 Posts

    Default Re: Sudoku: wrong output?

    how is that supposed to help figure out whats the problem?
    It's called debugging,
    It helps you find where the problem is. Where does the printing stop? What is the last thing printed?
    What remains in the file to be read and printed?
    If you don't understand my answer, don't ignore it, ask a question.

  13. #12
    Junior Member
    Join Date
    Apr 2012
    Posts
    7
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Sudoku: wrong output?

    Quote Originally Posted by Norm View Post
    It's called debugging,
    It helps you find where the problem is. Where does the printing stop? What is the last thing printed?
    What remains in the file to be read and printed?
    This is the output. Final row 8 is not read.

    3
    x
    x
    x
    |
    x
    x
    x
    |
    x
    x
    x
    0 [0, 0, 0, 0, 0, 0, 0, 0, 0]
    x
    1
    x
    |
    6
    2
    x
    |
    x
    9
    x
    1 [0, 1, 0, 6, 2, 0, 0, 9, 0]
    x
    x
    2
    |
    x
    x
    9
    |
    3
    1
    x
    2 [0, 0, 2, 0, 0, 9, 3, 1, 0]
    ---------------------
    x
    x
    4
    |
    x
    x
    6
    |
    x
    8
    x
    3 [0, 0, 4, 0, 0, 6, 0, 8, 0]
    x
    x
    8
    |
    7
    x
    2
    |
    1
    x
    x
    4 [0, 0, 8, 7, 0, 2, 1, 0, 0]
    x
    3
    x
    |
    8
    x
    x
    |
    5
    x
    x
    5 [0, 3, 0, 8, 0, 0, 5, 0, 0]
    ---------------------
    x
    6
    9
    |
    1
    x
    x
    |
    4
    x
    x
    6 [0, 6, 9, 1, 0, 0, 4, 0, 0]
    x
    8
    x
    |
    x
    7
    3
    |
    x
    5
    x
    7 [0, 8, 0, 0, 7, 3, 0, 5, 0]
    x
    x
    x
    |
    x
    x
    x
    |
    x
    x

  14. #13
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    21,064
    Thanks
    52
    Thanked 2,282 Times in 2,253 Posts

    Default Re: Sudoku: wrong output?

    Now answer these questions I asked:
    Where does the printing stop? What is the last thing printed?
    What remains in the file to be read and printed?

    now it doesnt want to go back to main().
    Does that mean the program is in a loop? Would the answers to the above questions point to where the program is looping?
    If you don't understand my answer, don't ignore it, ask a question.

  15. #14
    Junior Member
    Join Date
    Apr 2012
    Posts
    7
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Sudoku: wrong output?

    The program stops after the above output is printed and its not a loop or an error, its just stops. The last row 0 [0, 0, 0, 0, 0, 0, 0, 0, 0] is supposed to be printed.

    In read(), in the first for loop I changed i < N to i<N-1 just to see what would happen and the program ran fine but of course the output of the sudoku was false.

    Thanks for the help!

  16. #15
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    21,064
    Thanks
    52
    Thanked 2,282 Times in 2,253 Posts

    Default Re: Sudoku: wrong output?

    I changed i < N to i<N-1
    That means you are not reading the last line of the file. What if there are numbers on the last line?

    That is not the solution. You need to find the endless looping and fix it.
    If you don't understand my answer, don't ignore it, ask a question.

Similar Threads

  1. Help with Sudoku function please
    By peperez in forum What's Wrong With My Code?
    Replies: 2
    Last Post: November 13th, 2011, 11:40 PM
  2. Replies: 3
    Last Post: October 19th, 2011, 11:55 PM
  3. Replies: 3
    Last Post: February 22nd, 2011, 07:43 PM
  4. Sudoku
    By mgutierrez19 in forum What's Wrong With My Code?
    Replies: 1
    Last Post: November 30th, 2009, 09:09 PM
  5. Sudoku Solver
    By MysticDeath in forum Java Theory & Questions
    Replies: 5
    Last Post: September 19th, 2009, 09:33 PM