Help. Sudoku Board Generation Algorithm
 

Hi. I'm creating a Sudoku game for a C++ project. I'm still on the first step, and trying to generate a random Sudoku Board. My plan is to generate a fully complete board, then remove numbers from it one at a time, checking after each time whether it is solvable.
However, I can't get the computer to generate a correct board. So far, I can get it to display the columns correctly, each column containing the number 1 through 9 exactly once. But the rows and boxes both have repeating numbers in them. My algorithm is as follows:

1) For each column, put the number 1 through 9 in each column in random locations.
2) After that, I basically use brute force and randomization. Since the rows and boxes most likely won't be correct, keep on generating a random board and check after each time whether the board is correct or not(whether row/box has a repeating number).

So the problem is that using brute force takes way too long, and the program freezes before generating a good board. It goes through about 75,000 to 100,00 bad board iterations before it freezes. Help greatly appreciated!

I don't know a whole lot about Sudoku, but try google. I found this result, and it looked good. Perhaps it will help you:
http://today.java.net/pub/a/today/20...s-in-java.html

No offense, but the code on that site apparently requires a Java Library that costs money. Also, I'm working in C++, and don't know much Java, even though they are familiar. Thanks for the help, though.
Does anybody know how to simply generate a correct Sudoku board, where each column, row, and 3x3 box has the numbers 1-9 appering exactly once. I'm not looking for code, I would just appreciate any help and maybe even an algorithm.

Once you place a number in a column , then it obviously can't be used in a 'shared' entity (row OR square). That means when you are choosing numbers for, say, the shared row, you choice is not from among all digits, but only from among those not in the column. By restricting the set you make random choices from, you'll no doubt have a somewhat easier time of it.

Thanks. That would certainly make the board generation easier and faster. I won't be able to test it out until Tuesday because the code is at school, but I greatly appreciate the tip. If anyone knows of a method that is even faster, help is appreciated, but this method of restricting values should work.

Well, ultimately, a valid board is the outcome of restrictions, right? Ruling things out in the beginning is more efficient than tossing them out time after time. It's better not to have to cull a half-barrel of bad apples one has just filled when one can shit-can them as they arrive. Quite honestly, I have not applied any thought to Sudoku. Maybe it would be interesting if I did.

Interestingly, I have been playing around with Sudoku and C++ as well - though I haven't done board generation yet. What I have done is a function that checks which numbers may appear in any one square. And the next step would be a solving algorithm. Loads of optimization fun there :)

A solving algorithm is easy. I find the generation algorithm much more interesting.

Could somebody post code for/explain how a C++ Sudoku solver would work? I've always been kinda curious, since I started wasting so much time playing that game.

Essentially the solver goes through and eliminates number possibilities from every square using a few rules (number allready in row/column/box). It then waits until there is only 1 place a certain number can go, and so on. Bad explaination i know. Its essentially the same way you can systematically solve them on paper, it just goes very quickly on a computer.