0
public boolean solveSudoku() {
    int row, col;
    for (Map.Entry<Pair<Integer, Integer>, List<Integer>> entry : amap.entrySet()) {      // iterate through map (amap)

        row = entry.getKey().getKey();
        col = entry.getKey().getValue();
        for (Integer num : entry.getValue()) {
            if (isSafe(row, col, num)) {
                dpuzzle[row][col] = num;

                if (solveSudoku()) { // recursive call?
                    return true;
                } else {
                    dpuzzle[row][col] = 0; // replace it 
                }
            }

        }
        return false;

    }
    return true;
}

I have implemented a Sudoku solver using the byGroup method first to eliminate the impossible candidate for each empty cell and store them to a map, the key of the Map is the (i,j)of the grid, and the arraylist in the value of Map is the possible candidates, and the solveSudoku() supposed to recursively call itself to solve the puzzle using the possible candidate from the ArrayList. However it spit out :

Exception in thread "main" java.lang.StackOverflowError
at soduku.BacktrackSolver.solveSudoku(BacktrackSolver.java:113)
at soduku.BacktrackSolver.solveSudoku(BacktrackSolver.java:121)

these are the line

for (Map.Entry<Pair<Integer, Integer>, List<Integer>> entry : amap.entrySet()) {

and

if (solveSudoku()) {

Please enlighten me, if I have made any mistake as this is my first attempt in using Java data structures.

karel
  • 5,489
  • 46
  • 45
  • 50
Kevin Lam
  • 1
  • 4
    What is a StackOverflowError: https://stackoverflow.com/questions/214741/what-is-a-stackoverflowerror – Boken Mar 11 '19 at 09:40
  • i suppose you got some kind of endless loop causing this. – Alan Mar 11 '19 at 09:43
  • You are probably making an infinite loop of recursive calls. This can come from the fact that you try to solve recursively the same problem. You can use a debugger to find why. – Arnaud Denoyelle Mar 11 '19 at 09:44
  • Your recursion is based in the `amap.entrySet()` value, which is a class property. As you're not decrementing the number of entries anywhere, the method keeps calling itself endlessly. – Aritz Mar 11 '19 at 09:46
  • 3
    You're not changing `amap` from one call to the next. So when the method calls itself, the behaviour will be identical; hence the endless recursion. – Dawood ibn Kareem Mar 11 '19 at 09:46
  • Dawood ibn Kareem: i think that is the problem, but how can i iterate through the map when i want to call the next entry – Kevin Lam Mar 11 '19 at 09:48
  • As mentioned before, you want to ensure `amap` is updated before you incur recursion (i.e. somewhere around this line `dpuzzle[row][col] = num;`, stepping through the code with a debugger should convince you whether your assignments to `amap` or `entry` are sticking or not) otherwise, you have no way of getting past the cause of the first recursion call, before you reach your `return true` or `return false`. – DarceVader Mar 11 '19 at 11:21

0 Answers0