Question: Calculating Groebner basis for Sudoku

I'm trying to write a program that solves sudoku's using a Groebner basis. I introduced 81 variables x1 to x81, this is a linearisation of the sudoku board.

The space of valid sudokus is defined by:


for i=1,…,81 : Fi=(xi−1)(xi−2)⋯(xi−9) This represents the fact that all squares have integer values between 1 and 9.

for all xi and xj which are not equal but in the same row, column or block: Gij=(Fi−Fj)/(xi−xj) This represents that the variables xi and xj can not be equal.

All these Fi and Gij together define the space of valid sudokus. This conists of 891 polynomials.

Now to solve a sudoku we can add the clues to the space, so by example if the clue of a sudoku is the first square is a 5, then we add (x1−5) to the space. If we now take the groebner basis of this space we can directly see the solution for it.

I understand what I am doing this far. But I have trouble finding a computable manner for finding the groebner bases. I have succesfully done everything for 4*4 sudokus (or so-called shidokus). But Maple nor Singular are giving me a result for the groebner basis of the 9*9 sudoku space (Maple has not enough memory). You can see the commands I gave to Maple here: http://dl.dropbox.com/u/16797591/mapleSudoku.txt. (First I define the 891 polynomials, then I ask for a basis of it) I read papers saying it's feasible although imperformant to do what I strive for but I don't see how to find the solution, as they don't include many implementation details. Can anyone point me to a direction, making this problem easier for Maple or other software?

Please Wait...