Struggling to make algorithm to generate board for a puzzle game

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#.