# Sudoku

• (2 Pages)
• 1
• 2

## 25 Replies - 2654 Views - Last Post: 25 January 2009 - 10:36 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=82446&amp;s=8336e19e80f7c83e5f5b06dea5c547b1&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 nbl0066

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

# Sudoku

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

• Expert Schmexpert...

Reputation: 235
• 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

### #3 nbl0066

Reputation: 0
• 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

### #4 nbl0066

Reputation: 0
• 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

### #5 Gloin

• Expert Schmexpert...

Reputation: 235
• 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;
}

```

### #6 pbl

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

Reputation: 8378
• Posts: 31,956
• Joined: 06-March 08

## Re: Sudoku

Posted 23 January 2009 - 03:24 PM

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

### #7 nbl0066

Reputation: 0
• 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.File;

public class Sudoku
{
// The following is an instance of Scanner which you will use to
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"));

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" +

return valid;
}
}

```

### #8 Gloin

• Expert Schmexpert...

Reputation: 235
• 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.

### #9 nbl0066

Reputation: 0
• 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.

### #10 Gloin

• Expert Schmexpert...

Reputation: 235
• 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

### #11 nbl0066

Reputation: 0
• 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

### #12 Gloin

• Expert Schmexpert...

Reputation: 235
• 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

### #13 nbl0066

Reputation: 0
• 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])
```

### #14 Gloin

• Expert Schmexpert...

Reputation: 235
• 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?

### #15 nbl0066

Reputation: 0
• 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"));

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"