text: java - Sudoku recursion problematic while backtraking. (Brute Force) - Stack Overflow
  Sudoku recursion problematic while backtraking. (Brute Force) [duplicate]
  Sudoku solver in java, using backtracking and recursion I am creating a program that will solve a sudoku using recursion and brute force. My key problem is that I do not understand how I could concievably make it backtrack one it gets stuck.
  The general algorithm of the program is the following:
  Find the number of zeros in the sudoku.
  In the location of the first 0 (getNextEmpty method does this), insert a number(insertnumber checks to make sure a value complies with sudoku rules and returns true if it does).
  Then I make a recursive call, end when there are no more zeroes (n is the number of zeros).
  If the program reaches a point that it gets stuck, I must backtrack to change a piece. But how is this possible? The Cell class actually holds the location of the cell to be adjusted in an array of the format [row, column]. It has methods to return the row, column, or smaller grid associated with that cell.
  I am not asking for hand-holding or all the code, just a nudge in the right direction will suffice as I am legitimately interested in understanding the recursion.
  int n = getZeroes();
  }//end getSolution
  Cell cell = getNextEmpty();
  fits = insertNumber(cell, i);
  //I do not understand what I should do here
  return getSolution(n - 1);
  java algorithm recursion sudoku share|improve this question edited Nov 30 '12 at 20:28
  "brute force" ?
  yes, the intention is to try every combination until it works. Rather than a calculated approach to solving the sudoku.
  Have you done some back-of-the-envelope math to find out if this is halfway reasonable to brute strength? I don't know the problem too well, but this strikes me as something that could spin for a few hundred or thousand years if you get a "hard" puzzle. Or much, much longer if you get an impossible one (for which you'll have to enumerate every wrong path).
  Yes, we are required to solve it this way. there are specifically 4 puzzles me must solve, each will take only a few miliseconds. I know that worst case scenario puzzles may take upwards of 650,000 attempts. This is now the case for me however.
  Are both method headers provided to you in your assignment or did you write one of them?
  marked as duplicate by George Stocker♦ Jul 16 '12 at 17:30
  A nudge in the right direction. Your approach needs a little tweaking since you're not keeping track of all the information you need to solve the grid.
  break; // means i fits in Cell
  // i doesn't fit... try the next i
  // There are no numbers that fit in this Cell
  // What should happen?
  // Did I make a bad guess?
  // How do I BACKTRACK and correct a previous guess?
  share|improve this answer answered Mar 1 '12 at 0:31
  I was thinking along these lines. I had considered creating an arraylist with a record of all of the moves and backtrack when it runs into a problem. However, was told by my professor "This is not necessary. you are only making 1 "move". The recursive call makes all of the other moves." This seems to be throwing me off.
  Take a look at the pseudocode in Backtracking. You almost have the right idea. You just need to get your loop into the right place.
  Sorry... I meant to say you need to get your recursive call into the right place... not your loop
  hmm, this is really making me think about this, thank you for the tip. Let me see what I can do.
  Another hint: What is i? If i fits, what should you do? Where did they put the recursive call in the pseudocode I linked you?
  Generally in a recursive brute force, you use syntax similar to the code below. That is done because you can count that after you did any action, that is the new "starting position".
  So it would be similar to this:
  private void Guess(int[][] grid)
  if(/**grid is a solution **/)
  //signal success
  if(/*seed out any bad, unacceptable answers you may have missed*/)
  return;//this includes cases when there are no more zeros
  //for every possible move,
  //make a modified grid, with one move done, and call
  Guess(ModifiedGrid);//for every possible move, generally you can modify
  //grid itself, because its passed by value
  share|improve this answer answered Mar 1 '12 at 0:27
  It's generally better NOT to work with a static grid, because backtracking is difficult, I here use a standard approach with the grid being passed by value. The only limit is that it may run out of memory, but in theory it's the optional way of brute forcing.
  Unfortunatly I am required to use this static grid for the assignment.
  you can then make another static array that will contain all changes you make, something like a Map<int, int[2]>, basically you enter the change #, it returns the position x,y of the change you made. You can then undo that change. The code for this will probably be a bit longer though, but I hope you understand. If I helped please vote up!
  He doesn't actually need to do any of that... he's really close to a working solution... its a matter adding like 5 lines of code. What you suggested would actually work, but that's not the way a dancing links algorithm is supposed to work. You let your recursion handle correcting bad guesses.
  Yeah, I'm only a student also XD (feel free to read bio), but this solution seems more efficient to me if you HAVE to make a static outer "initial" data, can you please PM (or similar, I'm new here) to me why it's actually more effective that way if the architecture is already ruined?
  Not the answer you're looking for?	Browse other questions tagged java algorithm recursion sudoku or ask your own question.	asked