Programming Forums - View Single Post

Manan · May 28th, 2006, 7:50 PM

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!

May 28th, 2006, 7:50 PM	#1
Manan Newbie Join Date: May 2006 Posts: 13 Rep Power: 0	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!