Sudoku Board Generation Algorithm. HELP!

[Manan]

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 know there is another sudoku algorithm thread, but that one involves solving, not generating a board.

[teknomage1]

Solving is harder than pure generation because you're searching for a specific solution.
I think you can be a bit smarter in your generation if instead of generating random digits 1-9, you instead make pools of numbers (I would use linked lists to represent the pools), and remove digits from the pool as you fill in the puzzle row by row. If I understand the rules of the game correctly, you'd need one pool for each column, one for each row, and one for each of the 9 3x3 blocks.

So you algorithm would be to randomly generate the first row, remove the digits you used from the corresponding pools, then as you generate each consecutive row, you pull a number from that row's pool, check to see that the digit you are trying to assign is in the column's pool, and the block pool before you assign it, then remove it from the pools. If your number is missing from one of the pools, go back to the row pool and try again.
It should guarantee that anything you generate is a valid puzzle board. I'm not sure if it will get stuck in an unassignable state towards the end though.

[teknomage1]

Hmm, so based on my testing, the algorithm I proposed never seems to make it past 44 squares before it gets stuck and needs to delete a number of steps and start over.

[teknomage1]

Okay so applying a bit more brainpower to the problem, all sudoku puzzles are basicaly the same but with the numbers in a different order, so if you have one vaild solution, you can use those numbers as a template for any others. The easiest one I can see is:

1 2 3|4 5 6|7 8 9|
4 5 6|7 8 9|1 2 3|
7 8 9|1 2 3|4 5 6|

2 3 4|5 6 7|8 9 1|
5 6 7|8 9 1|2 3 4|
8 9 1|2 3 4|5 6 7|

3 4 5|6 7 8|9 1 2|
6 7 8|9 1 2|3 4 5|
9 1 2|3 4 5|6 7 8|

If you treat those numbers as indexes into an array where each digit only appears once, you can generate any random puzzle. Here're two examples:

array:[9, 8, 7, 6, 5, 4, 3, 2, 1]
9 8 7|6 5 4|3 2 1|
6 5 4|3 2 1|9 8 7|
3 2 1|9 8 7|6 5 4|

8 7 6|5 4 3|2 1 9|
5 4 3|2 1 9|8 7 6|
2 1 9|8 7 6|5 4 3|

7 6 5|4 3 2|1 9 8|
4 3 2|1 9 8|7 6 5|
1 9 8|7 6 5|4 3 2|

array:[3, 7, 2, 5, 1, 4, 9, 6, 8]
8 6 9|4 1 5|2 7 3|
4 1 5|2 7 3|8 6 9|
2 7 3|8 6 9|4 1 5|

6 9 4|1 5 2|7 3 8|
1 5 2|7 3 8|6 9 4|
7 3 8|6 9 4|1 5 2|

9 4 1|5 2 7|3 8 6|
5 2 7|3 8 6|9 4 1|
3 8 6|9 4 1|5 2 7|

[teknomage1]

I imagine there's probably more than one valid template, or else people'd probably get bored much quicker.

[teknomage1]

Hmm wikipedia says there are 5,472,730,538 templates.

[Manan]

Thanks, teknomage.
As for your "pool of possibilites" idea, there could be a step to make it work. Couldn't it be possible to redo the entire row when a random number is generated. It may take longer, but this way, it will never reach an unassignable state, because it can just start that row over again.

I like the template idea, and thought I could add to that. It would be possible to randomly turn the board 90, 180, or 270 degrees to offer three new templates based off of just 1. I could also shift every row or column by 3 or 6 squares to offer even more possible templates based off of 1.

[Manan]

Also, for the template thing, you won't always have the same puzzle even if you have the same template. After filling the board with the template, I can take out different numbers, and then it'll basically be a different challenge altogether.

[teknomage1]

That's true, and even with a single template you still have 9! (362880) possibilities just from doing the relabelling. And each extra template you add yeilds another 9! solutions.

[Manan]

Well, I've got the template system to work properly and generate a correctly filled-in grid. Now, I'm going to remove one number at a time, and check to see if it is solvable after each number is removed. If it isn't solvable, go back and put the number back in.

I'm constantly getting an error when I try to pass a matrix as a reference parameter. Here is my code:

void FillPossibilities(int &Buffer[9][9])

When I do this I get the following error:
error: declaration of 'Buffer' as array of references

Why can't I pass the matrix as a reference parameter? Is there something wrong with my syntax? Or, is it possible to return a matrix from a function? Any help is greatly appreciated.

[kyoryu]

Arrays are passed as pointers anyway, so there's no need to pass it in as a reference.

[Manan]

Oh. I haven't learned pointers yet in my c++ class. I'll check it out in the book and see what I can do. If I can't figure it out, I'll just come here for help.

[Manan]

I've decided to use a template, because I have way too little time to actually do a totally random board generator. But I'm having another problem declaring 2d arrays.

if(randTemplate == 1)
	{ //If template 2 is chosen
		int buffer[9][9] = {

             {n[6],n[7],n[8], n[1],n[0],n[4], n[2],n[5],n[3] },
             {n[1],n[4],n[5], n[2],n[8],n[3], n[6],n[0],n[7] },
             {n[2],n[0],n[3], n[5],n[7],n[6], n[4],n[1],n[8] },

             {n[8],n[2],n[1], n[7],n[6],n[0], n[5],n[3],n[4] },
             {n[5],n[3],n[0], n[4],n[2],n[8], n[1],n[7],n[6] },
             {n[7],n[6],n[4], n[3],n[1],n[5], n[8],n[2],n[0] },

             {n[0],n[5],n[7], n[8],n[4],n[2], n[3],n[6],n[1] },
             {n[4],n[1],n[2], n[6],n[3],n[7], n[0],n[8],n[5] },
             {n[3],n[8],n[6], n[0],n[5],n[1], n[7],n[4],n[2] }
          };
}

The above segment of code works perfectly. However, I want to declare int buffer[][] outside the if statement. This is because, it is currently a local variable and I want to use it outside the if statement. Here is what I'm trying to do:

int buffer[9][9];
if(randTemplate == 1)
	{ //If template 2 is chosen
		buffer[][] = {

             {n[6],n[7],n[8], n[1],n[0],n[4], n[2],n[5],n[3] },
             {n[1],n[4],n[5], n[2],n[8],n[3], n[6],n[0],n[7] },
             {n[2],n[0],n[3], n[5],n[7],n[6], n[4],n[1],n[8] },

             {n[8],n[2],n[1], n[7],n[6],n[0], n[5],n[3],n[4] },
             {n[5],n[3],n[0], n[4],n[2],n[8], n[1],n[7],n[6] },
             {n[7],n[6],n[4], n[3],n[1],n[5], n[8],n[2],n[0] },

             {n[0],n[5],n[7], n[8],n[4],n[2], n[3],n[6],n[1] },
             {n[4],n[1],n[2], n[6],n[3],n[7], n[0],n[8],n[5] },
             {n[3],n[8],n[6], n[0],n[5],n[1], n[7],n[4],n[2] }
          };
}

I get about 50-60 errors when I do this. I've even tried getting rid of the [][], and I also tried making it [9][9], but it won't work. Help is greatly appreciated

[teknomage1]

Sorry, I missed your array question earlier. I think you just need to maybe initialize your buffer when you declare it, then assign to it via buffer = {...},

Also Peter Norvig (important AI coder at Google amongst other things), has posted an excellent sudoku article here: http://norvig.com/sudoku.html

[Manan]

Its ok. I figured it out, thanks to help from my teacher. I can only use ({..}, {...}) that technique when initializing the matrices, and not for already initialized matrices. Therefore, I used the memcpy command. So basically:

int buffer[9][9];
if(randTemplate == 1)
	{ //If template 2 is chosen
	     int buffer2[9][9] = {

             {n[6],n[7],n[8], n[1],n[0],n[4], n[2],n[5],n[3] },
             {n[1],n[4],n[5], n[2],n[8],n[3], n[6],n[0],n[7] },
             {n[2],n[0],n[3], n[5],n[7],n[6], n[4],n[1],n[8] },

             {n[8],n[2],n[1], n[7],n[6],n[0], n[5],n[3],n[4] },
             {n[5],n[3],n[0], n[4],n[2],n[8], n[1],n[7],n[6] },
             {n[7],n[6],n[4], n[3],n[1],n[5], n[8],n[2],n[0] },

             {n[0],n[5],n[7], n[8],n[4],n[2], n[3],n[6],n[1] },
             {n[4],n[1],n[2], n[6],n[3],n[7], n[0],n[8],n[5] },
             {n[3],n[8],n[6], n[0],n[5],n[1], n[7],n[4],n[2] }
             };
             memcpy (buffer, buffer2, sizeof buffer);
      }