[Exercise] Total number of Sudoku solutions

Joe

For the sake of this exercise, let's generalize the rules of the popular Sudoku game.

The game revolves around a n2 x n2 matrix (that's n-squared) divided into n x n squares (called subregions). The matrix must be filled such as each row, each column and each subregion is filled with each integer ranging from 1 to n2 (appearing exactly only once).

For the record, the classical Sudoku you're probably familiar with is a 3-Sudoku.

Easy problem
What is the total number of valid solutions for a 2-Sudoku?

Hard problem
What is the total number of valid solutions for a 3-Sudoku?

Very hard problem
Generalize the solution. Write a function that returns the total number of solutions for a n-Sudoku.

Remarks
I believe there are still no known solutions for the general solution.
But I'd love to exchange ideas on how we could do this.

EDIT: After some Googling (is Wikipedia-ing a word?) I came across a paper showing that the general solution is a NP-Complete problem. It doesn't really change much ... or does it?

Fischer

My friend asked me for a sudoku game last week, and now another question about it :)

the number of possible solutions read

this

this

You guys do the coding, I don't want to work on sudoku related stuff anymore!

Joe

Corrected the code.

There was indeed a problem by checking validity with the sum, because [1, 1, 4, 4] would be considered valid.
Instead I check for the existence of each face value (1 and 2 and 3 and 4) each time.
I now get a similar answer to the one shown in the link provided by arithma.

arithma

http://oeis.org/A107739
Your number is not there.

Joe

Corrected the code.

There was indeed a problem by checking validity with the sum, because [1, 1, 4, 4] would be considered valid.
Instead I check for the existence of each face value (1 and 2 and 3 and 4) each time.

I now get a similar answer to the one shown in the link provided by arithma.

Fischer

See this and this guys

Peter Norvig has a very nice article!