LebGeeks

A community for technology geeks in Lebanon.

You are not logged in.

#1 September 24 2012

Joe
Member

[Exercise] Total number of Sudoku solutions

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?

Offline

#2 September 24 2012

Fischer
Member

Re: [Exercise] Total number of Sudoku solutions

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!

Last edited by Fischer (September 25 2012)

Offline

#3 September 25 2012

Joe
Member

Re: [Exercise] Total number of Sudoku solutions

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.

Last edited by Joe (September 25 2012)

Offline

#4 September 25 2012

arithma
Member

Re: [Exercise] Total number of Sudoku solutions

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

Offline

#5 September 25 2012

Joe
Member

Re: [Exercise] Total number of Sudoku solutions

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.

Offline

#6 September 25 2012

Fischer
Member

Re: [Exercise] Total number of Sudoku solutions

See this and this guys

Peter Norvig has a very nice article!

Offline

Board footer