• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

sudoku solver backtracking algorithm

 
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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...
 
Rancher
Posts: 43081
77
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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?
 
Sheriff
Posts: 17652
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Saloon Keeper
Posts: 10781
86
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Somehow like this?
 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
reply
    Bookmark Topic Watch Topic
  • New Topic