[TheAnomalyCoder]

This is not homework, just a fun little project I really want to finish because it's been sitting in my folder forever.
Anyhow, I made this simple solver, and at first it began with only row/column/boxes. I then decided I could do more, how about a bit of recursion?
I started reading about the topic, and I'm not quite sure on what the structure would look like in the recursive function itself.

Can anyone here guide me towards what the general structure of the recursive method would look like?
I would really appreciate it, I've been playing around with this for a bit too long and have gotten nowhere.

This post has been edited by TheAnomalyCoder: 16 May 2010 - 07:04 PM

[pbl]

Don't really see how recursion could be useful in solving a Sudoku problem or even where, just for the fun of it, it could be implemented. Baavgay might
Hope you didn'y write methods to validate column, row and area. They are all sets of 9 cells and the same methods (receiving an array of 9 cells) should be used.

[TheAnomalyCoder]

pbl, on 16 May 2010 - 06:37 PM, said:

Don't really see how recursion could be useful in solving a Sudoku problem or even where, just for the fun of it, it could be implemented. Baavgay might
Hope you didn'y write methods to validate column, row and area. They are all sets of 9 cells and the same methods (receiving an array of 9 cells) should be used.

Well recursion as in trying numbers in, going from cell to cell until it's not valid then going back..
I did, but it is at this point irrelevant, I'm just trying to finish it, but that is true I think I will re-write a few methods in the interest of efficiency.
Thanks for the tips, now I still need to figure out a method for higher level puzzles..
Perhaps the term brute force will be more appropriate?

[pbl]

TheAnomalyCoder, on 16 May 2010 - 08:45 PM, said:

pbl, on 16 May 2010 - 06:37 PM, said:

Don't really see how recursion could be useful in solving a Sudoku problem or even where, just for the fun of it, it could be implemented. Baavgay might
Hope you didn'y write methods to validate column, row and area. They are all sets of 9 cells and the same methods (receiving an array of 9 cells) should be used.

Well recursion as in trying numbers in, going from cell to cell until it's not valid then going back..
I did, but it is at this point irrelevant, I'm just trying to finish it, but that is true I think I will re-write a few methods in the interest of efficiency.
Thanks for the tips, now I still need to figure out a method for higher level puzzles..
Perhaps the term brute force will be more appropriate?

Is is quite rare (I do not say it does not happen) that recursion is more efficient than a single iteration.
You need something like:

boolean isThereDuplicate(Cell[] cell) {
    for(int i = 0; i < cell.length; i++) {
       for(int j = i+1; j < cell.length; j++) {
          if(cell[i].number == cell[j].number)
             return true;
       }
    }
    return false;
}

This method receives as parameter an array of cells for a column, a row or a region

[TheAnomalyCoder]

pbl, on 16 May 2010 - 06:57 PM, said:

TheAnomalyCoder, on 16 May 2010 - 08:45 PM, said:

pbl, on 16 May 2010 - 06:37 PM, said:

Don't really see how recursion could be useful in solving a Sudoku problem or even where, just for the fun of it, it could be implemented. Baavgay might
Hope you didn'y write methods to validate column, row and area. They are all sets of 9 cells and the same methods (receiving an array of 9 cells) should be used.

Well recursion as in trying numbers in, going from cell to cell until it's not valid then going back..
I did, but it is at this point irrelevant, I'm just trying to finish it, but that is true I think I will re-write a few methods in the interest of efficiency.
Thanks for the tips, now I still need to figure out a method for higher level puzzles..
Perhaps the term brute force will be more appropriate?

Is is quite rare (I do not say it does not happen) that recursion is more efficient than a single iteration.
You need something like:

boolean isThereDuplicate(Cell[] cell) {
    for(int i = 0; i < cell.length; i++) {
       for(int j = i+1; j < cell.length; j++) {
          if(cell[i].number == cell[j].number)
             return true;
       }
    }
    return false;
}

This method receives as parameter an array of cells for a column, a row or a region

I happen to have such a method, it's one whole method for both a row, col, and region, and I could have 3 separate methods if needed.

I've also had a suggestion to use Stack(The data structure).
Does anyone have any ideas on a good approach for using stack?

[pbl]

TheAnomalyCoder, on 16 May 2010 - 09:17 PM, said:

I happen to have such a method, it's one whole method for both a row, col, and region, and I could have 3 separate methods if needed.

Good show

Quote

I've also had a suggestion to use Stack(The data structure).
Does anyone have any ideas on a good approach for using stack?

Stack are useful for unknown collection/array/list size
In your case it is always 9 (or at least a predefined value) so do not see how Stack can be useful in your context

[TheAnomalyCoder]

pbl, on 16 May 2010 - 07:30 PM, said:

TheAnomalyCoder, on 16 May 2010 - 09:17 PM, said:

I happen to have such a method, it's one whole method for both a row, col, and region, and I could have 3 separate methods if needed.

Good show

Quote

I've also had a suggestion to use Stack(The data structure).
Does anyone have any ideas on a good approach for using stack?

Stack are useful for unknown collection/array/list size
In your case it is always 9 (or at least a predefined value) so do not see how Stack can be useful in your context

I actually coded my program a bit differently. I have an array of 81 objects, each object representing a cell on the board, a two dimmensional array for the board, each object has an array of possible values, etc.
So what would best for higher level Sudoku Puzzles?

[pbl]

TheAnomalyCoder, on 16 May 2010 - 09:37 PM, said:

I actually coded my program a bit differently. I have an array of 81 objects, each object representing a cell on the board, a two dimmensional array for the board, each object has an array of possible values, etc.
So what would best for higher level Sudoku Puzzles?

Not very differently if you have
9 column objects containing the good extract of your 81 cell objects
9 row objects containing the good extract of your 81 cell objects
9 area objects containing the good extract of your 81 cell objects

[macosxnerd101]

How about just an int[][] to store values 0-9 in each cell? Also, I don't see the need for another Stack when we have the call Stack for recursion. You might also want to check out the Wikipedia page on algorithms of sudoku for ideas. Brute force is probably not the way to go here, especially with recursion, as it takes O((n^2)!) time (linear permutations are O(n!) time, since we have n*n grid, it takes O((n^2)!) time).

[pbl]

macosxnerd101, on 16 May 2010 - 10:25 PM, said:

How about just an int[][] to store values 0-9 in each cell? Also, I don't see the need for another Stack when we have the call Stack for recursion. You might also want to check out the Wikipedia page on algorithms of sudoku for ideas. Brute force is probably not the way to go here, especially with recursion, as it takes O((n^2)!) time (linear permutations are O(n!) time, since we have n*n grid, it takes O((n^2)!) time).

int[][] is not enough... I wrote so many Sudoku solver/generator (the generator is in the Code Snippet) I can tell you that
you need an array of Cell objects which contain actual value, possible values, and so on
You also need column, row, area objects that reference the initial array in the 3 different ways

[Ember]

macosxnerd101, on 16 May 2010 - 08:25 PM, said:

How about just an int[][] to store values 0-9 in each cell? Also, I don't see the need for another Stack when we have the call Stack for recursion. You might also want to check out the Wikipedia page on algorithms of sudoku for ideas. Brute force is probably not the way to go here, especially with recursion, as it takes O((n^2)!) time (linear permutations are O(n!) time, since we have n*n grid, it takes O((n^2)!) time).

You might be right about run time, but if you were to do some simple pruning, it is entirely feasible to do recursion with this type of problem

Back in my data structures class we had to build the N-Queens algorithm (recursively) that finds out how many queens can be placed on a NxN board, without them conflicting. Our TA said that if we were to modify the base case enough-- and to touch on pbl's logic, tweak the objects enough-- then we could easily create a Sudoku solver as well.

Without pruning, you are right about the recursive algorithm failing pretty hard. In the N-Queens project I couldn't get past an 8x8 board without pruning techniques. With pruning, I could get to around a 12x12 board without too much run time. And as I said before, I don't think we would need to run past a 9x9 Sudoku board solver.

This post has been edited by Ember: 16 May 2010 - 09:52 PM

[TheAnomalyCoder]

//A single block in a sudoku is represented by an instance of this class
public class Cell {
	//This variable represents what neighborhood a given cell is in
	int cell_neighborhood =0;
	//This is the Sudoku Cell's value
	int value = 0;
	//This is the x coordinate of the cell
	int xloc = 0;
	//This is the y coordinate of the cell
	int yloc = 0;
	//This integer is used for stating which number the
	//Given cell is in the neighborhood:
	/**
	 * 1 2 3
	 * 4 ? 6
	 * 7 8 9
	 * The question mark in the table above would be assigned
	 * A value of 4 for the variable numberinneighborhood
	 */
	int numberinneighborhood;
	int[] possiblevalues = {1,2,3,4,5,6,7,8,9};
}

That is my Class for the Cell, 81 instances are initialized and placed into an array of objects.
I think the program could solve the puzzle using a combination of my basic row,col, and box methods.
Instead of trying values 1-9, it would loop through the possible values of each cell. (There are methods to eliminate possible values, and they are called in the program). I'll look into Sudoku methods, but I think Brute Force will be simple enough for my purposes.

I mean, how about simply running the basic methods until it has multiple working values for each cell, the proceed to the recursive or Brute Force method? Then every time a number is used, it runs a method that changes the possible values for cells in that box/row/col whose value has just been changed, and it will proceed if it can, else it will restore the value that has just been used, run a method that restores the possible values, and then repeats that process. . Oh and of course it would ignore cells that have values.

Anyhow I have to go to school now, I'll be back in about 6 hours.

This post has been edited by TheAnomalyCoder: 17 May 2010 - 05:30 AM