Detect Infinite Loop?

Question

I'm working on a Sudoku solver program. The idea is that the user inputs the Sudoku puzzle and the program solves it for them.

The program works fine when entering any normal puzzle. However, there are some puzzles that are impossible to solve. Here is one example that I entered: https://i.sstatic.net/BnWc9.png

The input is perfectly legal, but top right square cannot be filled in since all numbers 1-9 have been used in that row and column. If I hit "Solve", my program freezes as it enters an infinite loop.

So my question here is, how can I prevent this from happening?

I tried implementing the "boolean flag" approach, but on second thought I realized that it's probably not feasible.

Here is my solver method:

public boolean solve(int i, int j) { for (int a = 0; a < 9; a++) { for (int b = 0; b < 9; b++) { if (sudokuArray[a][b] == 0) { for (int k = 1; k <= 9; k++) { sudokuArray[a][b] = k; if (checkNumber(a, b, k) && solve(a, b)) { return true; }else { sudokuArray[a][b] = 0; } } return false; } } } return true; }

The checkNumber() method checks if number k can be legally inserted in row a, column b and returns true/false accordingly.

Ideas? Tips?

Thanks.

PS: Added checkNumber() as requested:

public boolean checkNumber(int i, int j, int num) { for (int a = 0; a < 9; a++) { if (a != i) { if (sudokuArray[a][j] == num) { return false; } } if (a != j) { if (sudokuArray[i][a] == num) { return false; } } } for (int a = (i / 3) * 3; a < (i / 3) * 3 + 3; a++) { for (int b = (j / 3) * 3; b < (j / 3) * 3 + 3; b++) { if ((a != i) && (b != j)) { if (sudokuArray[a][b] == num) { return false; } } } } return true; }

Is it really infinite? Not just taking too long while still making some progress? It's a pretty huge search tree after all. — user555045
– user555045, Commented Mar 9, 2014 at 15:42
Yes, its infinite. Have a look at the screenshot - you'll see that it's impossible to enter a legal number at the top right square. — Chris
– Chris, Commented Mar 9, 2014 at 15:43
Please share code of method checkNumber(). Is this method taking more time? — Braj
– Braj, Commented Mar 9, 2014 at 15:44
Chris it is impossible to detect an infinite loop en.wikipedia.org/wiki/Halting_problem Try another approach. — NinjaStars
– NinjaStars, Commented Mar 9, 2014 at 15:50

Rakem · Accepted Answer · 2015-03-03 03:20:33Z

This is just an idea (i would comment but this account is too new). Try making it so that if all numbers from 0-9 return false, then it returns an error of some sort. For example if it hasn't found an answer by 9, then move up to 10. If the program detects a 10, do some kind of System.out.println("Unsolvable") or something along those lines. Sorry if I'm confusing you by the way. I've been told I'm bad at explaining things.

Collectives™ on Stack Overflow

Detect Infinite Loop?

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related