• Post Reply Bookmark Topic Watch Topic
  • New Topic

sudoku solver backtracking algorithm  RSS feed

 
Derryl Larson
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hey,
can anybody help me with my code? It's about a backtracking algorithm trying to solve a sudoku, represented by an array of integer arrays. For testing matters, the start field is empty. I can't figure out what's the problem...

P.S.: The other methods in the code should work as intended...
 
Ulf Dittmer
Rancher
Posts: 42972
73
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What is the problem? In other words, what does the code do now, and what should it be doing instead?
 
Junilu Lacar
Sheriff
Posts: 11476
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm not really sure what kind of help you're expecting here. There's not enough context in the code that you have given to allow anyone else to comment intelligently about what could be wrong. What's the expected outcome? What's the actual outcome from running this snippet? Why do you think it's this particular code that has a problem and not something else in another part of the code?
 
Derryl Larson
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Actually, the code should fill every element of every array with a valid integer value, starting with [0][0] and then recursively going on to the next field. If no valid input is possible for a element, the code should backtrack to and change the last valid element.
For testing manners, all elements are set on their default value. This is the programm for printing out the final result:

But instead, it just gives me this:
1 2 3 4 5 6 7 8 9
4 5 6 8 9 2 9 3 9
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
 
Carey Brown
Saloon Keeper
Posts: 3310
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Derryl Larson wrote:Hey,
can anybody help me with my code? It's about a backtracking algorithm trying to solve a sudoku, represented by an array of integer arrays. For testing matters, the start field is empty. I can't figure out what's the problem...

P.S.: The other methods in the code should work as intended...


I see several problems here. You really need three nested loops: rows, cols, digits. You need to pass in a callback object because there may be more than one solution and you need to invoke a callback method when a solution is found - without unwinding the recursion. If you are not going to pass a copy array during recursion then you need to reset the incoming row/col position to zero before returning (thereby unwinding the recursion).
 
Derryl Larson
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Somehow like this?
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Derryl Larson wrote:Actually, the code should fill every element of every array with a valid integer value, starting with [0][0] and then recursively going on to the next field. If no valid input is possible for a element, the code should backtrack to and change the last valid element.

My comments:

1. I'm not sure that will work as a strategy. How far should it backtrack? One element? One row? Something else? There doesn't seem to be much "plan" to this solution beyond a "let's try this" idea, which I suspect will end up being a "brute force" solution which could take a VERY long time for any decent size Sudoku puzzle.

2. Why does solve() return a boolean? All that says is "I failed" or "got it!" doesn't it? Wouldn't it be better for it to return something that says where it failed - ie, some sort of "position"?

IMO, methods that return booleans can usually be improved on unless what they're doing can be specifically described by a name that suggests a boolean.
For example:
  List.contains(item);

And even then, (again, IMO):
  List.indexOf(item);
is a far superior method, because it returns the index where 'item' was found (or -1), rather than just "yep, found it".

Winston
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!