Sudoku

  • (2 Pages)
  • +
  • 1
  • 2

25 Replies - 1902 Views - Last Post: 25 January 2009 - 10:36 PM Rate Topic: -----

#1 nbl0066  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 21
  • Joined: 23-January 09

Sudoku

Post icon  Posted 23 January 2009 - 02:43 PM

Hello, I am trying to construct a sudoku solver and I'm having problems with the method to check the row for duplicates. Here is the code. The first is the method and the second part is the if statement that calls the boolean to print out the result. We are working with three input files.. two with errors and one without. What is happening is all of the files are showing errors. I'd appreciate help!



/**
	 * Verifies a row in a sudoku puzzle and returns if the rules are followed or broken. 
	 * 
	 * @param 
	 * @param 
	 */
	public boolean verifyRows (int row, int[][] puzzle)
	{
	   final int SIZE = 9;
	   int col1;
	   int col2;
	   
	   for (col1 = 0; col1 < SIZE; col1++)
	   {
		   for(col2 = 0; col2 < SIZE; col2++)
		   {  
				if (puzzle[col1][0] != puzzle[col2][0])
				{
					col1++;
				}
				else if(puzzle[col1][1] == puzzle[col2][1])
				{ 
					return true;
				}
		   }
		  
	   }
	   return false;
   } 





if(verifyRows (row, puzzle))
			{
			System.out.println ("There are conflicts.");
		}
		else
		{
			System.out.println("There are NO conflicts!");
		}




Is This A Good Question/Topic? 0
  • +

Replies To: Sudoku

#2 Gloin  Icon User is offline

  • Expert Schmexpert...
  • member icon

Reputation: 235
  • View blog
  • Posts: 4,489
  • Joined: 04-August 08

Re: Sudoku

Posted 23 January 2009 - 02:56 PM

The idea is to check if a number occurs more than once in a row.

I suggest you create an array[9] of boolean (call it column), initialize it to false.
Go through the puzzle array on the row your about to check. If you find a number in one of the row, you change the value of column[number] to true. First however, check if column[number] was already true because in that case you can stop searching and return true (since that implies you have a conflict).

public boolean verifyRows (int row, int[][] puzzle) {
  boolean column[] = new boolean[9];
  for(int i = 0; i < column.length; i++)
	column[i] = false;
  for (int col = 0; col < puzzle.length; col++) {
	if (puzzle[row][col] != 0) {
	  if(column[puzzle[row][col]-1])
		return true;
	  else
		column[puzzle[row][col]-1] = true;
	}
  }
  return false;
} 



This post has been edited by Gloin: 23 January 2009 - 03:06 PM

Was This Post Helpful? 0
  • +
  • -

#3 nbl0066  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 21
  • Joined: 23-January 09

Re: Sudoku

Posted 23 January 2009 - 03:01 PM

thanks for that! i am very new to java and its hard for me to put ideas into code quite yet ... can you help me a little by showing me what is wrong in the code? thank you so much
Was This Post Helpful? 0
  • +
  • -

#4 nbl0066  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 21
  • Joined: 23-January 09

Re: Sudoku

Posted 23 January 2009 - 03:14 PM

this piece of code has this error
 if(column[puzzle[row][col]-1])



java.lang.ArrayIndexOutOfBoundsException: -2
Was This Post Helpful? 0
  • +
  • -

#5 Gloin  Icon User is offline

  • Expert Schmexpert...
  • member icon

Reputation: 235
  • View blog
  • Posts: 4,489
  • Joined: 04-August 08

Re: Sudoku

Posted 23 January 2009 - 03:17 PM

That's because I didn't know how you represented an empty position. I guess by -1. It only takes a very little change to correct though..

public boolean verifyRows (int row, int[][] puzzle) {
  boolean column[] = new boolean[9];
  for(int i = 0; i < column.length; i++)
	column[i] = false;
  for (int col = 0; col < puzzle.length; col++) {
	if (puzzle[row][col] != -1) { // <- Only changed 0 to -1
	  if(column[puzzle[row][col]-1])
		return true;
	  else
		column[puzzle[row][col]-1] = true;
	}
  }
  return false;
} 




Was This Post Helpful? 0
  • +
  • -

#6 pbl  Icon User is offline

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

Reputation: 8334
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: Sudoku

Posted 23 January 2009 - 03:24 PM

"Free advice worthes every cent"
You are on wrong track
You are not to write a method to check the column, a method to check the row and a method to check a region

So you need a class Square that represents a sudoku square which contain:
- at least the value of the square
- possibly if it is shown or not
- possibly its candidate

Then you build an array of
Square[][] bigArray = new Square[9][9];
and you fill bigArray with your problem

OK up to here our algorithms are the same
Now you have to create another class named NineSquare which contains an array of Square[9]

class NineSquare {
	 Square[] square = new Square[9];
}


Now you need 9 columns of NineSquare, 9 Rows of NineSquare and 9 Region of NineSquare
It is easier to put then in a 2 dimensional array

NiveSquare[][] toTest = new NineSquare[3][9];

Where:
- toTest[0][...] are for the columns
- toTest[1][...] are for the lines
- toTest[2][...] are for the regions

Now you have to make this equalities to have each of the elemnt of this array to "point" to the corresponding one in bigArray:
So for the columns
toTest[0][0] will have in its array of Square bigSquare[0][0], bigSquare[0][1], bigSquare[0][2].....;
toTest[0][1] ...... bigSquare[1][0], bigSquare[1][1], bigSquare[1][2],....;
....
for the lines
toTest[1][0] will have int ist array of square bigSquare[0][0], bigSquare[1][0], bigSquare[2][0], ....;
...
for the region
toTest[2][0] will have bigArray [0][0], [0,1], [0,2], [1,0], [1,1], [1,2], [2,0], [2,1] and [2,2]

Now to check for duplicity (that was your initial question) you can have a method checkForDouble that receives as parameter a NineSquare object

boolean duplicate = false;
for(int i = 0; i < 3; i++) {
   for(int j = 0; j < 9; j++) {
	   duplicate = checkForDouble(test[i][j]);
	   if(duplicate)
		  break;
   }
   if(duplicate)
	  break;
}
 
....
// this method check for duplicate
boolean checkForDuplicate(NineSquare nine) {
	// now the method will check for duplicate in the 9 square of the object NineSquare received as parameter
	// the method does NOT have to know if it is a column, a line or a region
}



Happy coding
Was This Post Helpful? 0
  • +
  • -

#7 nbl0066  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 21
  • Joined: 23-January 09

Re: Sudoku

Posted 23 January 2009 - 03:35 PM

wow well thank you for that..that is really helpful for me as I'm learning java..the problem is our teacher prefers us to use the separate methods for this

i'm compiling...now instead of saying all of the files have errors... it is now saying all the files "do not have errors"

I will show you my entire code (keep in mind that alot of it has yet to be complete) the only thing I am currently working on is ...reading the files into arrays.. and doing the verifyRows method ....

import java.util.Scanner;
import java.io.*;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.File;

public class Sudoku
{
	// The following is an instance of Scanner which you will use to
	// read from the user.
	public Scanner kbd = new Scanner (System.in);
	public Scanner sudoku1;
	public Scanner sudoku2;
	public Scanner sudoku3;
	
	public static void main (String[] args) throws IOException
	{
		Sudoku program = new Sudoku ();
		
		program.run ();
	}
	
	public void run () throws IOException
	{
		boolean error;
		String filename;
		char choice;
		int v = 0;
		int d = 0;
		int Yposition;
		int Xposition;
		int row = 0;
		int col = 0;
		int value = 3;
		int rowNumber = 0;

		final int SIZE = 9;
		
		int[][]puzzle;
		puzzle = new int[9][9];
		
		sudoku1 = new Scanner (new File ("sudoku1.txt"));
		sudoku2 = new Scanner (new File ("sudoku2.txt"));
		sudoku3 = new Scanner (new File ("sudoku3.txt"));

		BufferedReader in = new BufferedReader(new FileReader("sudoku1.txt"));
		String str;
		int strNumber = 0;

		while( ( str = in.readLine() ) != null ) 
		{
			for (int ndxCol=0; ndxCol<str.length() && ndxCol < SIZE; ndxCol++ ) 
			{
				if ( str.charAt(ndxCol) == ' ' ) 
					{
						puzzle[strNumber][ndxCol] = -1;
					}
				else if ( str.charAt(ndxCol) >= '1' && str.charAt(ndxCol) <= '9' ) 
					{
						final String s = str.substring(ndxCol, ndxCol+1);
						puzzle[strNumber][ndxCol] = Byte.parseByte( s );
					}
				else 
				   {
						System.out.println( "ERROR in the file format" );
						System.exit( -1 );
				   }  
			 }
				strNumber ++;
		}

		in.close();
	 
		System.out.println ("Enter Input File (sudoku1, sudoku2, or sudoku3): ");
		filename = kbd.next();
		System.out.print("Would you like to (v)erify the current state or (d)etermine" +
						  " the possible values for a cell: ");
		choice = kbd.next().charAt(0);
		
		if (choice == 'v')
		{
			verifyRows(row, puzzle);
		}
		else
		{
			System.out.println("Enter X position (1-9): ");
			Xposition = kbd.nextInt();
			System.out.println("Enter Y position (1-9): ");
			Yposition = kbd.nextInt();
			
			determineXValue(Xposition, Yposition);
		}
		
		if(verifyRows (row, puzzle))
			{
			System.out.println ("There are conflicts.");
		}
		else
		{
			System.out.println("There are NO conflicts!");
		}
	}

	/**
	 * Verifies a row in a sudoku puzzle and returns if the rules are followed or broken. 
	 * 
	 * @param 
	 * @param 
	 */
	public boolean verifyRows (int row, int[][] puzzle) 
	{
		final int PUZZLE_SIZE = 9;
		final int COLUMN_SIZE = 9;
		
		boolean column[] = new boolean[9];
		for(int i = 0; i < COLUMN_SIZE; i++)
			column[i] = false;
			for (int col = 0; col < PUZZLE_SIZE; col++) 
			{
				if (puzzle[row][col] != -1) 
				{
					if(column[puzzle[row][col]-1])
					{
						return true;
					}
					else
					{
						column[puzzle[row][col]-1] = true;
					}   
				}
			}
		 return false;
   } 

	public boolean verifyColumns(int col, int[][]puzzle)
	{
		final int SIZE = 9;
		int row1;
		int row2;
	   
		for (row1 = 0; row1 < SIZE; row1++)
		{
		   for(row2 = 0; row2 < SIZE; row2++)
		   {
				   if (puzzle[row1][0] != puzzle[row2][1])
				   {
					   col++;
				   }
				   else if(puzzle[row1][0] == puzzle[row2][1])
				   { 
					   return true;
				   }
			  }
		  }
		return false;
	  }
	
	
	public boolean verifyBoxes(int row, int col, int[][]puzzle)
	{
		final int GRID_SIZE = 9;
		final int BOX_SIZE = 3;
		int leftCol = ((col / BOX_SIZE) * BOX_SIZE);
		int topRow = ((row / BOX_SIZE) * BOX_SIZE);
		for (row = 0; row < GRID_SIZE; row++)
		{
			for (col = 0; col < GRID_SIZE; col++)
			{

					return false;
			}
		}
		return true;

	}
	/**
	 * Determines possible valid numbers for a given cell on the X radius in the sudoku puzzle. 
	 * 
	 * @param 
	 * @param 
	 * @return
	 */
	public boolean determineXValue(int XPosition, int YPosition)
	{
		boolean valid = false;
		
		
		System.out.println("The cell at position (" + XPosition + "," + YPosition + ") can" +
		"accept the following values: ");
		System.out.println("The cell at position (" + XPosition + "," + YPosition + ") can" +
		"accept the no values!");
		System.out.println("The cell at position (" + XPosition + "," + YPosition + ") is" +
		"already filled in!");
		
		
		return valid;
	}
}


Was This Post Helpful? 0
  • +
  • -

#8 Gloin  Icon User is offline

  • Expert Schmexpert...
  • member icon

Reputation: 235
  • View blog
  • Posts: 4,489
  • Joined: 04-August 08

Re: Sudoku

Posted 23 January 2009 - 03:40 PM

Not to put down pbl's solution in any way. (He's likely the best Java programmer on this site) but the way you structured your program so far, I'd go with my method. Changing it to check the columns instead of the rows would be extremely simple.
Was This Post Helpful? 0
  • +
  • -

#9 nbl0066  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 21
  • Joined: 23-January 09

Re: Sudoku

Posted 23 January 2009 - 03:45 PM

Yes I am sticking to the method you showed me... but the problem is that it is not working so I'm trying to figure out what is still going on that is causing the method not to work. It is returning true everytime which is saying that there are no errors... but I know there are.
Was This Post Helpful? 0
  • +
  • -

#10 Gloin  Icon User is offline

  • Expert Schmexpert...
  • member icon

Reputation: 235
  • View blog
  • Posts: 4,489
  • Joined: 04-August 08

Re: Sudoku

Posted 23 January 2009 - 03:47 PM

Yes, of course.. Everywhere I say row, it's likely row-1, just different indexation.

Nah.. that probably isn't it..

should verifyRows check all rows?

This post has been edited by Gloin: 23 January 2009 - 03:50 PM

Was This Post Helpful? 0
  • +
  • -

#11 nbl0066  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 21
  • Joined: 23-January 09

Re: Sudoku

Posted 23 January 2009 - 03:51 PM

yes i do want that method to check all of the rows
Was This Post Helpful? 0
  • +
  • -

#12 Gloin  Icon User is offline

  • Expert Schmexpert...
  • member icon

Reputation: 235
  • View blog
  • Posts: 4,489
  • Joined: 04-August 08

Re: Sudoku

Posted 23 January 2009 - 03:56 PM

In that case you have to put in a loop in the method. What then is the point of taking an argument 'row' as parameter to the method..

A method that checks all rows would look like this..


public boolean verifyRows (int[][] puzzle) { // Notice that I removed one parameter
  boolean column[] = new boolean[9];
  for (int row = 0; row < puzzle.length; row++) { // <-- Inserted one more loop
	for(int i = 0; i < column.length; i++)
	  column[i] = false;
	for (int col = 0; col < puzzle.length; col++) {
	  if (puzzle[row][col] != -1) { 
		if(column[puzzle[row][col]-1])
		  return true;
		else
		  column[puzzle[row][col]-1] = true;
	  }
	}
  }
  return false;
} 



This post has been edited by Gloin: 23 January 2009 - 03:57 PM

Was This Post Helpful? 0
  • +
  • -

#13 nbl0066  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 21
  • Joined: 23-January 09

Re: Sudoku

Posted 23 January 2009 - 04:02 PM

java.lang.ArrayIndexOutOfBoundsException: -2

						if(column[puzzle[row][col]-1])

Was This Post Helpful? 0
  • +
  • -

#14 Gloin  Icon User is offline

  • Expert Schmexpert...
  • member icon

Reputation: 235
  • View blog
  • Posts: 4,489
  • Joined: 04-August 08

Re: Sudoku

Posted 23 January 2009 - 04:15 PM

Did you change to the method where I compared to -1?

Can you post the whole code?
Was This Post Helpful? 0
  • +
  • -

#15 nbl0066  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 21
  • Joined: 23-January 09

Re: Sudoku

Posted 23 January 2009 - 04:28 PM

sorry i posted that before i figured out how to fix it... i know im getting somewhere if im realizing an error what it means and how to fix it... the method either still isnt working or else i am not reading in the file properly.. im trying to do some research as how to read in the file into the 2d array but so far no luck... if you still have the time and patience with me.. here is my code for my file reader... and beneath that are the 3 files

sudoku1 = new Scanner (new File ("sudoku1.txt"));
		sudoku2 = new Scanner (new File ("sudoku2.txt"));
		sudoku3 = new Scanner (new File ("sudoku3.txt"));

		BufferedReader in = new BufferedReader(new FileReader("sudoku1.txt"));
		String str;
		int strNumber = 0;

		while( ( str = in.readLine() ) != null ) 
		{
			for (int ndxCol=0; ndxCol<str.length() && ndxCol < SIZE; ndxCol++ ) 
			{
				if ( str.charAt(ndxCol) == ' ' ) 
					{
						puzzle[strNumber][ndxCol] = -1;
					}
				else if ( str.charAt(ndxCol) >= '1' && str.charAt(ndxCol) <= '9' ) 
					{
						final String s = str.substring(ndxCol, ndxCol+1);
						puzzle[strNumber][ndxCol] = Byte.parseByte( s );
					}
				else 
				   {
						System.out.println( "ERROR in the file format" );
						System.exit( -1 );
				   }  
			 }
				strNumber ++;
		}

		in.close();


FILE 1
"3 1
6 5
5 983
8 63 2
5
9 38 6
714 9
2 8
4 3 "

FILE 2
" 38 29
2 45
167 6
2
3452
4 3 6
27 4"

FILE 3
"832591674
496387251
571264983
185746392
267953418
943812765
714638529
329175846
658429137"
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2