# Programming a Sudoku Solver

• (2 Pages)
• 1
• 2

## 16 Replies - 6048 Views - Last Post: 09 June 2010 - 02:43 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=176040&amp;s=2444c71fff3517df36c638f634408d12&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 rideNdirt

• New D.I.C Head

Reputation: 0
• Posts: 34
• Joined: 13-May 10

# Programming a Sudoku Solver

Posted 01 June 2010 - 10:21 PM

I have searched the old posts and some of the code snippets and they've helped some, but I think I've looked at the program requirements too long and thought about it too much to where my brain isn't really working right now.

So far I have a 2D int array the reads in a file and initializes/creates the sudoku board in the array.

I am struggling with a method that solves the puzzle. In order to 'help' solve the puzzle, I have a 3D array which uses index 0 to hold the number of candidates left for each cell. The array is initialized to set this to 9 for all empty cells for now. Once a candidate has been eliminated, it decrements the number in index 0. I also have a variable K, which is the number to test (1-9). If K is a candidate, the 3D array is set to 1 for each number K that is a candidate.

The issue I am stuck on is testing the row, column and box for K to see if it's a candidate of the cell while solving. How do I search the row for the number I'm testing? This might be an easy solve!

Here is my sudo-code, I'm not sure if my logic is wrong or what because I can't seem to convert it to code. I'd really appreciate any help!

```for(row 1 -> 9) {
for(col 1 -> 9) {
if(index 0 in 3D array != 1
&& index K in 3D array != 1) {
is K in the row?
if yes, set P[row][col][k] = 0
decrement P[row][col][0]
if K is not in the row, test the column
repeat above
if K is not in the column, test the box
repeat above

```

Is This A Good Question/Topic? 0

## Replies To: Programming a Sudoku Solver

### #2 Dogstopper

Reputation: 2920
• Posts: 11,195
• Joined: 15-July 08

## Re: Programming a Sudoku Solver

Posted 02 June 2010 - 05:20 AM

Quote

The issue I am stuck on is testing the row, column and box for K to see if it's a candidate of the cell while solving. How do I search the row for the number I'm testing? This might be an easy solve!

To search a horizontal row, you can write something like this:
```public int isInRow(int searchNum, int rowNum) {
for (int i = 0; i < array[rowNum].length; i++) {
if (array[rowNum][i] == searchNum) {
return i;
else
return -1;
}
}

```

You can do the same for columns

### #3 pbl

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

Reputation: 8362
• Posts: 31,955
• Joined: 06-March 08

## Re: Programming a Sudoku Solver

Posted 02 June 2010 - 04:36 PM

You are not out of the woods if you process that way.
You should not be checking for column, row and region. All these methods are base on a unique problem/solution: find if unicity of number is respected for 9 different cells.
If you have different code (or nested loops) to check for row/column/region your code will expand for ever

You should have an array of [9][9] Cells objects
You should have a class name NineCells containing 9 Cell objects
You should have 9 ColumnObject extending NiceCells containing the cells of the 9 columns (the same cells as the ones contained in the 9X9 array)
You should have 9 RowObject extending NiceCells containing the cells of the 9 rows (the same cells as the ones contained in the 9X9 array)
You should have 9 RegionObject extending NiceCells containing the cells of the 9 regions (the same cells as the ones contained in the 9X9 array)

Then to check for duplicioty, twins, ... you can have methods like

boolean checkForUnicity(NiceCells niceCells) {}

this method can receive as parameter any RowObject, ColObject or RegionObject. Does not have to care about which index to increment. It just checks for the 9 cells within the NiceCells object

### #4 rideNdirt

• New D.I.C Head

Reputation: 0
• Posts: 34
• Joined: 13-May 10

## Re: Programming a Sudoku Solver

Posted 02 June 2010 - 06:34 PM

@PBL - sounds super cool, and I would implement if I was required to solve anything other than level 1 sudoku! More or less I should be able to solve the puzzle doing candidate elimination alone. I worked on it some more and made it out of sudo-code, yay! It compiles but doesn't solve the puzzle yet I don't think. Check out my method here to update the 3D array possible with possible candidates. Also there is an anchor method to set the anchor for each 3x3 box and an update grid, which assigns the candidate to the original 2D array. It looks like a mess to me, but can you see logic errors?

```static void updatePossible(int[][] G, int[][][] P) {
int row, col, k;
for(row = 1; row < G.length; row++) {
for(col = 1; col < G.length; col++) {
for(k = 1; k <= 9; k++) {
if(P[row][col][0] != 1 && P[row][col][k] != 1) {
if(G[row] == P[row][k]) {
P[row][col][k] = 0; //assign k as a non-candidate
P[row][col][0] --; //decrement number in [0]
} else if(G[col] == P[col][k]) {
P[row][col][k] = 0;
P[row][col][0] --;
} else {
int Row = anchor(row);
int Col = anchor(col);
for(int s = Row; s <= Row+2; s++) {
for(int t = Col; t <= Col+2; t++) {
if(((s!= row)||(t!= col))) {
P[s][t][k] = 0;
P[s][t][0] --;
}
}
}
}
}
}
}
}
} //end updatePossible

static int anchor(int a) {
return a - ((a - 1)%3);
}//end anchor

static void updateGrid(int[][] G, int[][][] P) {
int row, col, k;
for(row = 1; row < G.length; row++) {
for(col = 1; col < G.length; col++) {
for(k = 1; k <= 9; k++) {
G[row][col] = P[row][col][k];
}
}
}
} //end updateGrid

```

### #5 pbl

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

Reputation: 8362
• Posts: 31,955
• Joined: 06-March 08

## Re: Programming a Sudoku Solver

Posted 02 June 2010 - 06:48 PM

rideNdirt, on 02 June 2010 - 07:34 PM, said:

It looks like a mess to me

As you say
I'll look at the mess if ever I have free time to decipher it

### #6 rideNdirt

• New D.I.C Head

Reputation: 0
• Posts: 34
• Joined: 13-May 10

## Re: Programming a Sudoku Solver

Posted 02 June 2010 - 06:51 PM

Haha, I appreciate it! I just need a second pair of eyes. I didn't mess with it much after coding it late last night but now that I have a fresh head I will work on it more. If you'd like the whole program in context let me know and I can PM it over

### #7 pbl

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

Reputation: 8362
• Posts: 31,955
• Joined: 06-March 08

## Re: Programming a Sudoku Solver

Posted 02 June 2010 - 07:20 PM

rideNdirt, on 02 June 2010 - 07:51 PM, said:

Haha, I appreciate it! I just need a second pair of eyes. I didn't mess with it much after coding it late last night but now that I have a fresh head I will work on it more. If you'd like the whole program in context let me know and I can PM it over

If you don't do it with Object and just use int array and iterations better to do it with C at least you could use int * for your region.

### #8 rideNdirt

• New D.I.C Head

Reputation: 0
• Posts: 34
• Joined: 13-May 10

## Re: Programming a Sudoku Solver

Posted 02 June 2010 - 07:25 PM

Not familiar with C yet, only C++ and Java, and I'm sure my professor wouldn't appreciate a C program in a java class!

### #9 pbl

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

Reputation: 8362
• Posts: 31,955
• Joined: 06-March 08

## Re: Programming a Sudoku Solver

Posted 02 June 2010 - 07:30 PM

rideNdirt, on 02 June 2010 - 08:25 PM, said:

Not familiar with C yet, only C++ and Java, and I'm sure my professor wouldn't appreciate a C program in a java class!

So use C++ it inherits the pointers from C and this is what you want pointers. They will easily, and more clearly, replace your anchor

### #10 rideNdirt

• New D.I.C Head

Reputation: 0
• Posts: 34
• Joined: 13-May 10

## Re: Programming a Sudoku Solver

Posted 02 June 2010 - 07:33 PM

Ah okay, I see what you're saying. Unfortunately, the anchor method the way its written is required per the assignment.

### #11 pbl

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

Reputation: 8362
• Posts: 31,955
• Joined: 06-March 08

## Re: Programming a Sudoku Solver

Posted 02 June 2010 - 07:38 PM

rideNdirt, on 02 June 2010 - 08:33 PM, said:

Ah okay, I see what you're saying. Unfortunately, the anchor method the way its written is required per the assignment.

You mean this is a school assigment ?
A Sudoku solver, in Java, without any object creation ?
Tell me which school/college it is to make sure I'll never send my children there

### #12 rideNdirt

• New D.I.C Head

Reputation: 0
• Posts: 34
• Joined: 13-May 10

## Re: Programming a Sudoku Solver

Posted 02 June 2010 - 07:43 PM

Yes a sudoku solver in java with no Objects. Only 2 arrays, 1 2D array, 1 3D array and a bunch of methods! The assignment doesn't call for objects at all. And I'm not telling what school

### #13 rideNdirt

• New D.I.C Head

Reputation: 0
• Posts: 34
• Joined: 13-May 10

## Re: Programming a Sudoku Solver

Posted 04 June 2010 - 11:24 AM

rideNdirt, on 02 June 2010 - 06:43 PM, said:

Yes a sudoku solver in java with no Objects. Only 2 arrays, 1 2D array, 1 3D array and a bunch of methods! The assignment doesn't call for objects at all. And I'm not telling what school

I figured it out eventually. It was really silly actually, after putting in tons of debugging lines, I found a semicolon at the end of an if statement. DOH! Once I removed it, program ran as designed. Thanks for talking it out with me though!

### #14 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11247
• Posts: 42,313
• Joined: 27-December 08

## Re: Programming a Sudoku Solver

Posted 04 June 2010 - 05:32 PM

rideNdirt, on 02 June 2010 - 09:51 PM, said:

If you'd like the whole program in context let me know and I can PM it over

Please avoid using the PM system for coding help, and keep all these requests in the appropriate forums. It restricts the learning to only you and the participants of the conversation, not the entire community.

### #15 rideNdirt

• New D.I.C Head

Reputation: 0
• Posts: 34
• Joined: 13-May 10

## Re: Programming a Sudoku Solver

Posted 08 June 2010 - 09:57 PM

macosxnerd101, on 04 June 2010 - 04:32 PM, said:

rideNdirt, on 02 June 2010 - 09:51 PM, said:

If you'd like the whole program in context let me know and I can PM it over

Please avoid using the PM system for coding help, and keep all these requests in the appropriate forums. It restricts the learning to only you and the participants of the conversation, not the entire community.

I only say this because I wouldn't want my entire program plagiarized, risking academic dishonesty. I use this forum to help me, not code for me.