Requesting help: Excel VBA Sudoku Grid Generator

desenso

Hello all,

I've read through the forums and looked at all the examples I could. I'm a new programmer and took it upon myself to work on a Sudoku creator for my intro class. Little did I know that I was out of my depth, but now I want to finish it.

As I haven't taken any algorithms classes, I'm not schooled on the differences and "logical" solutions they provide. I think I understand the concept of a backtracking algorithm but can't seem to implement it (with any success)

The way my program works is this: a string of 81 numbers is sequentially generated, number by number, by generating a random integer 1-9 and checking if it meets the "rules" (if it exists in the rows, columns, and box). Assuming it passes this constraint, that number is passed to the program, and it moves on to the next. The grid is then filled by taking that sequential list of numbers and filling in the rows left to right - like how you would read it if it were a paragraph of text.

All of this works fine. What happens, however, is the first 40 or 50 numbers lead it to a "dead end" which it cannot get past. This, I gather, is what the algorithm is intended to solve. I've tried various ways of having the program go "backward", clear the last few values, and try again - either with a static number, or by generating a random number of "Backward" steps - but none of these have amounted to a single solvable puzzle. In the end, the program just constantly generates new values for about the 5th or 6th line (this is usually where it "stalls").

I've tried to decipher examples in C and other languages, but they are so foreign to me that they don't seem to do any good. I was wondering if anyone could give me a hint on what the next logical progression would be for my program to check.

I appreciate any help anyone can give. I'll continue to read through all the information on this forum and TRY to find a solution.

desenso · Posted: Sun Nov 06, 2005 3:45 am Post subject:

Update:

A typo caused me to lose 8 hours of my life. It was in a part of the code that I took for granted, but a user error (in a simple addition, none the less) caused the program to fail 100% of the time.

Now that I've fixed it, I've generated a few "solvable" puzzles. However, after running the code for the last 10 to 15 minutes I have yet to come up with another working grid (I allow it 999 recursions, a recursion being stepping back a random number of cells (from 1 to 5), clearing, and trying to generate from that point).

SO I know that my solution will, mathematically, produce a working grid. The problem now is the chance of that happening is incredibly small, apparently. ANy tips?

desenso · Posted: Sun Nov 06, 2005 4:52 am Post subject:

Second update: the code now works much better. It generates in about 5 to 10 seconds in Excel. I know that my Algorithm is rough, and refining it might reduce this drastically, but for the time being I can work on other aspects of the program.

I'm still open to some tips if anyone has suggestions about how I could improve it, given what I've already said.

Ruud · Site Admin

Hi,

3 posts and no reply. Sad

This forum can be cruel sometimes.

Check my post in this topic:
http://www.setbb.com/phpbb/viewtopic.php?t=293&mforum=sudoku

Ruud.

dom · Posted: Fri Nov 11, 2005 11:53 am Post subject:

There is an easy recursive algorithm if you're into such things...

Puzzled

desenso · Posted: Sun Nov 20, 2005 8:51 pm Post subject:

Hey thanks for the replies Smile

My code all works.. the only thing that's not great at the moment is the time it takes to generate the grid... i took a break from the project.. went back and made a few modifications that has improved it a bit, but it still takes roughly 15 seconds to make a grid...