Programming a Sudoku Solver

  • (2 Pages)
  • +
  • 1
  • 2

16 Replies - 5440 Views - Last Post: 09 June 2010 - 02:43 PM Rate Topic: -----

#1 rideNdirt  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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  Icon User is offline

  • The Ninjaducky
  • member icon



Reputation: 2874
  • View blog
  • Posts: 11,047
  • 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
Was This Post Helpful? 0
  • +
  • -

#3 pbl  Icon User is offline

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

Reputation: 8342
  • View blog
  • Posts: 31,880
  • 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
Was This Post Helpful? 2
  • +
  • -

#4 rideNdirt  Icon User is offline

  • New D.I.C Head

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


Was This Post Helpful? 0
  • +
  • -

#5 pbl  Icon User is offline

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

Reputation: 8342
  • View blog
  • Posts: 31,880
  • Joined: 06-March 08

Re: Programming a Sudoku Solver

Posted 02 June 2010 - 06:48 PM

View PostrideNdirt, 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
Was This Post Helpful? 0
  • +
  • -

#6 rideNdirt  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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 :bigsmile:
Was This Post Helpful? 0
  • +
  • -

#7 pbl  Icon User is offline

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

Reputation: 8342
  • View blog
  • Posts: 31,880
  • Joined: 06-March 08

Re: Programming a Sudoku Solver

Posted 02 June 2010 - 07:20 PM

View PostrideNdirt, 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 :bigsmile:

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.
Was This Post Helpful? 0
  • +
  • -

#8 rideNdirt  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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!
Was This Post Helpful? 0
  • +
  • -

#9 pbl  Icon User is offline

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

Reputation: 8342
  • View blog
  • Posts: 31,880
  • Joined: 06-March 08

Re: Programming a Sudoku Solver

Posted 02 June 2010 - 07:30 PM

View PostrideNdirt, 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
Was This Post Helpful? 0
  • +
  • -

#10 rideNdirt  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#11 pbl  Icon User is offline

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

Reputation: 8342
  • View blog
  • Posts: 31,880
  • Joined: 06-March 08

Re: Programming a Sudoku Solver

Posted 02 June 2010 - 07:38 PM

View PostrideNdirt, 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 ? :eek:
Tell me which school/college it is to make sure I'll never send my children there
Was This Post Helpful? 0
  • +
  • -

#12 rideNdirt  Icon User is offline

  • New D.I.C Head

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

Re: Programming a Sudoku Solver

Posted 02 June 2010 - 07:43 PM

:surrender:
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 :smartass:
Was This Post Helpful? 0
  • +
  • -

#13 rideNdirt  Icon User is offline

  • New D.I.C Head

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

Re: Programming a Sudoku Solver

Posted 04 June 2010 - 11:24 AM

View PostrideNdirt, on 02 June 2010 - 06:43 PM, said:

:surrender:
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 :smartass:


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!
Was This Post Helpful? 0
  • +
  • -

#14 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10659
  • View blog
  • Posts: 39,574
  • Joined: 27-December 08

Re: Programming a Sudoku Solver

Posted 04 June 2010 - 05:32 PM

View PostrideNdirt, 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 :bigsmile:


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. :)
Was This Post Helpful? 0
  • +
  • -

#15 rideNdirt  Icon User is offline

  • New D.I.C Head

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

Re: Programming a Sudoku Solver

Posted 08 June 2010 - 09:57 PM

View Postmacosxnerd101, on 04 June 2010 - 04:32 PM, said:

View PostrideNdirt, 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 :bigsmile:


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.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2