Struggling to make algorithm to generate board for a puzzle game

Question

I'm looking to make a number puzzle game. For the sake of the question, let's say the board is a grid consisting of 4 x 4 squares. (In the actual puzzle game, this number will be 1..15)

A number may only occur once in each column and once in each row, a little like Sudoku, but without "squares".

Valid:

[1, 2, 3, 4
2, 3, 4, 1
3, 4, 1, 2
4, 1, 2, 3]

I can't seem to come up with an algorithm that will consistently generate valid, random n x n boards.

I'm writing this in C#.

Answer 1

Start by reading my series on graph colouring algorithms:

http://blogs.msdn.com/b/ericlippert/archive/tags/graph+colouring/

It is going to seem like this has nothing to do with your problem, but by the time you're done, you'll see that it has everything to do with your problem.

---

OK, now that you've read that, you know that you can use a graph colouring algorithm to describe a Sudoku-like puzzle and then solve a specific instance of the puzzle. But clearly you can use the same algorithm to generate puzzles.

Start by defining your graph regions that are fully connected.

Then modify the algorithm so that it tries to find two solutions.

Now create a blank graph and set one of the regions at random to a random colour. Try to solve the graph. Were there two solutions? Then add another random colour. Try it again. Were there no solutions? Then back up a step and add a different random colour.

Keep doing that -- adding random colours, backtracking when you get no solutions, and continuing until you get a puzzle that has a unique solution. And you're done; you've got a random puzzle generator.

Answer 2

It seems you could use this valid example as input to an algorithm that randomly swapped two rows a random number of times, then swapped two random columns a random number of times.