In June’s 2006 edition of the Scientific American there is an article about “The Science behind Sudoku,” written by Jean-Paul Delahaye.
In this article he explains the rules of Sudoku, its history and strategies, as well as methods of generating Sudoku puzzles are all in this article. Delahaye also deals with the maximal and minimal number of given starting squares that still guarantee a unique solution: 77 and 17, respectively (the latter has not been proven, but no one has found a Sudoku puzzle with 16 squares filled in that has a unique solution).
Sudoku variants on the standard 9 x 9 grid are given at the end of the article. Happy Puzzling!