5 Replies - 1183 Views - Last Post: 05 June 2010 - 07:57 PM Rate Topic: -----

#1 Guest_John*


Reputation:

Sudoku program hitting infinite loop help!

Posted 05 June 2010 - 04:03 PM

Hi:

I'm having trouble with this program. It is supposed to read an imput file of an incomplete sudoku board, and output the completed sudoku board. I feel like its just about complete, but it seems to be hitting a loop that it isnt getting out of. anyone have any ideas? Code and imput file below.

/* SudokuIO.java
 * Gordon Tang
 * gtang
 * pa6
 * Reads and checks partially complete sudoku input from a file, and outputs a
 * completed sudoku grid.
 */

import java.util.Scanner;
import java.io.*;

class Sudoku{

   public static void main(String[] args){
      Scanner sc = null;
	  boolean isFilled;
	  int[][] grid = new int[10][10];
	  int[][][] possible = new int[10][10][10];
	  
      // Input checks for no file or multiple files, handles exception

      if(args.length != 1)
         usage();
      try{
         sc = new Scanner(new File(args[0]));
      }catch(FileNotFoundException e){
         System.err.println(args[0]+" (The system cannot find the file specified)");
         usage();
      }

      getGrid(grid, sc);
	  initializePossible(grid, possible);
	  updatePossible(grid, possible);
	  updateGrid(grid, possible);
      printGrid(grid);

      while(!isFilled(grid)){
         updatePossible(grid, possible);
         updateGrid(grid, possible);
      }

      printGrid(grid);

   }

   // Prints a usage message to stderr then exits the program.

   static void usage(){

      System.err.println("Usage: SudokuIO [InputFile]");
      System.exit(1);
   }

   // Extracts integers from the Scanner object sc and places them in the int
   // array G, row by row.

   static void getGrid(int[][] G, Scanner sc){
      int i, j;

      for(i=1; i<G.length; i++){
         for(j=1; j<G[i].length; j++){
            G[i][j] = sc.nextInt();
         }
      }
   }

   // Returns true if all entries in its array argument are non-zero, and
   // false otherwise.

   static boolean isFilled(int[][] G){
      int i, j;

      for(i=1; i<G.length; i++){
         for(j=1; j<G[i].length; j++){
            if(G[i][j] == 0)
               return false;
         }
      }
      return true;
   }
   
   // Prints the contents of its array argument to stdout.

   // Converts 0's to - , adds a space after every int, adds a new line after 
   // every third number

   static void printGrid(int[][] G){
      int i, j;

      for(i=1; i<G.length; i++){
         for(j=1; j<G[i].length; j++){
            if(G[i][j] == 0)
               System.out.print("- ");
            else
               System.out.print(G[i][j] + " ");
            if(j%3 == 0)
               System.out.print(" ");
         }
         System.out.println();
         if(i%3 == 0)
            System.out.println();
      }
   }

   // Uses the entries in the puzzle grid G to eliminate candidates from the 
   // possible array, known locally as P.

   static void updatePossible(int[][] G, int[][][] P){

      for(int i=1; i<10; ++i){
         for(int j=1; j<10; ++j){
            if(P[i][j][0]!=1){
               for(int m=1; m<P[i].length; ++m){
			      if(G[i][m]!=0){
				     int x = G[i][m];
                     if(P[i][j][x]!=0){
                        P[i][j][x]=0;
					    P[i][j][0]--;
                     }
				  }
               for(int n=1; n<P.length; ++n){
                  if(G[n][j]!=0){
				  int x = G[n][j];
				     if(P[i][j][x]!=0){
                        P[i][j][x]=0;
					    P[i][j][0]--;
                     }
                  }
			   }
               int I=((i-1)/3)*3+1;
               int J=((j-1)/3)*3+1;
                  for(int n=I; n<I+3; n++){
                     for(m=J; m<J+3; m++){
				        if(G[n][m]!=0){
					       int x = G[n][m];
                           if(P[i][j][x]!=0){
                              P[i][j][x]=0;
						      P[i][j][0]--;
						   }
                        }
                     }
                  }
               }
            }
         }
      }
   }

   // Fills currently unfilled cells in the puzzle grid G whose correct values
   // can be deduced from the information in P.

   static void updateGrid(int[][] G, int[][][] P){

      for(int i=1; i<G.length; i++){
         for(int j=1; j<G[i].length; j++){
            if(P[i][j][0] == 1){
               for(int k = 1; k<P[i][j].length; k++){
                  if(P[i][j][k] == 1){
                     G[i][j] = k;
                  }
               } 
            }
         }
      }
   }
   
   static void initializePossible(int[][]G, int[][][]P){
      int i, j;
	  
	  for(i=1; i<10; i++){
	     for(j=1; j<10; j++){
		    if(G[i][j]==0){
			   P[i][j][0]=9;
			   for(int k=1; k<10; k++){
			      P[i][j][k]=1;
			   }
			}
			else{
			   P[i][j][0]=1;
			   for(int k=1; k<10; k++){
			      P[i][j][k]=0;
			   }
			int m = G[i][j];
			P[i][j][m]=1;
			}
		 }
	  }
   }
   
}




IMPUT FILE

5 3 0 0 7 0 0 0 0
6 0 0 1 9 5 0 0 0
0 9 8 0 0 0 0 6 0

8 0 0 0 6 0 0 0 3
4 0 0 8 0 3 0 0 1
7 0 0 0 2 0 0 0 6

0 6 0 0 0 0 2 8 0
0 0 0 4 1 9 0 0 5
0 0 0 0 8 0 0 7 9


Thank you!

Is This A Good Question/Topic? 0

Replies To: Sudoku program hitting infinite loop help!

#2 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8346
  • View blog
  • Posts: 31,908
  • Joined: 06-March 08

Re: Sudoku program hitting infinite loop help!

Posted 05 June 2010 - 04:16 PM

your getGrid() method will have to do a scanner.nextLine() every 3 lines to read the empty line
Was This Post Helpful? 0
  • +
  • -

#3 Guest_John*


Reputation:

Re: Sudoku program hitting infinite loop help!

Posted 05 June 2010 - 04:21 PM

the getGrid() is working fine, if i run the program right now the output is


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

- - - - - - 2 - 7
- 4 - 1 - 7 - 8 -
7 - 9 - - - - - -

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


This puzzle is not filled


But then it continues running without producing any more output or ending the program.
Was This Post Helpful? 0

#4 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8346
  • View blog
  • Posts: 31,908
  • Joined: 06-March 08

Re: Sudoku program hitting infinite loop help!

Posted 05 June 2010 - 06:54 PM

Didn't have the patience to look through your algorithm that seems very basic but for this kind of problem you need a roolback algorithm that you do not have
I'll try to explain it in easy words
When you fill your rows you might end up in a situation where there are no acceptable solution for the last rows so you have to rool back and recreate the preceding rows as I did in my Code Snippet or Tutorial on Sudoku

This is what may make your program to be in an infinite loop

This post has been edited by pbl: 05 June 2010 - 06:55 PM

Was This Post Helpful? 0
  • +
  • -

#5 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8346
  • View blog
  • Posts: 31,908
  • Joined: 06-March 08

Re: Sudoku program hitting infinite loop help!

Posted 05 June 2010 - 07:09 PM

http://www.dreaminco...snippet3447.htm
Was This Post Helpful? 0
  • +
  • -

#6 Guest_John*


Reputation:

Re: Sudoku program hitting infinite loop help!

Posted 05 June 2010 - 07:57 PM

thanks for the help, i'm going to keep working on it and try and figure it out.
Was This Post Helpful? 0

Page 1 of 1