Hey guys, I'm doing a program about finding out the solution of a sudoku puzzle and was wondering if I could get some ideas from anyone. I've been thinking about how I'm going to check every box of the small 3x3's and am kind of stumped. What would be the best and most efficient way of doing that? Done working for today but want to sleep on some ideas.
The key is that both the row and the column total to 3, for each "house". Using % 3 for each row, and then % 3 for each column in the inner loop (here I'm imagining a 2D array for the Sudoku board), is usually used.
You might want to start working it through with a 4 x 4 grid, and each house being 2 x 2. Using % 2 and a pencil and paper at first, is more productive than trying to imagine it as you program, sometimes.
% is what again? I cant exactly remember what that was
its the remainder or something along that line isnt it?
The most efficient way is not having to check it at all, at least that is the idea behind the common ways for tacking the problem, e.g. the "dancing-links" algorithm for representing the problem.
Basically don't do it by checking if inserting a number breaks the rules. Instead do it by eliminating the possible moves which would break the rules, as you insert each item.
E.g. when inserting a 7 into the 2nd row, 3rd column, take away the option of choosing a 7 in the same row, column, or box in a subsequent move.
One might represent the possible values that can go in a given cell using bit-flags. Masking out the 7th bit, for example, means that you may not try a 7 there later.
The idea is the same as for the Sieve of Eratosthenes. In that, you don't check for primes directly, rather you mark off the ones that aren't prime and see what you have left.
Why this technique really makes a massive difference for the Sudoku solver, is that you can then very easily try the places that have fewer possible legal moves left first for minimal extra cost. That help's reduces backtracking's exponential worst case complexity, which reduces the time taken from several minutes or more, to several milliseconds with a good solver.
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
I understand what you're saying but a user inserting the data is not what i'm supposed to be thinking of it, its supposed to just check if a solution is correct or not.
I was not talking about user inserted data at all, I'm talking about an algorithm that finds the solution to an initially partially-filled board. That seems to be what you asked for originally.
Are you now saying that you instead want something that validates a completely-filled-in board to check that it is valid? Are you aware that this is not useful as part of a solving algorithm because repeatedly doing that is ridiculously slow?
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
Yes, a completely-filled-in board read in from a file. Its the program that was assigned to me with its own instructions.
% is the C operator for modulo arithmetic. You need to run through the C tutorial that is linked at the top of the forum!
There are a zillion Sudoku programs in C on the net, so I don't believe you'll have a lot of trouble finding an example of what you want.
Okay, if you're just verifying the board then it should be easy. Adak's advice should help.
To get further help, you'll need to post some code.
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
