## A compact Sudoku solver via Groebner

by: Maple

Sudoku is a well known Latin square type game, see https://en.wikipedia.org/wiki/Sudoku

Here is a Sudoku game and its (unique) solution:

A,Sol:=  # A = Sudoku matrix, 0 for each empty cell
Matrix(9, [
[0,0,3,0,9,0,1,0,0],
[0,5,0,3,0,0,7,0,0],
[1,0,2,0,0,5,0,6,4],
[0,1,0,0,2,0,9,0,0],
[2,0,0,6,0,3,0,0,1],
[0,0,7,0,8,0,0,3,0],
[7,6,0,9,0,0,8,0,5],
[0,0,8,0,0,7,0,9,0],
[0,0,4,0,6,0,2,0,0]]),
Matrix(9, [
[4,7,3,2,9,6,1,5,8],
[8,5,6,3,4,1,7,2,9],
[1,9,2,8,7,5,3,6,4],
[3,1,5,7,2,4,9,8,6],
[2,8,9,6,5,3,4,7,1],
[6,4,7,1,8,9,5,3,2],
[7,6,1,9,3,2,8,4,5],
[5,2,8,4,1,7,6,9,3],
[9,3,4,5,6,8,2,1,7]]);

The procedure which follows is a very compact Sudoku solver. It uses Groebner bases. I hope that you will like it.
The input is the Sudoku matrix and the solution matrix is returned.
Note that the Sudoku matrix must be valid and must have a unique solution.
(Otherwise, theoretically, the error "Invalid Sudoku matrix" should appear.)
Note also that the procedure may be very slow for some games or Maple may crash. This happened to me once with a very "hard" matrix.

I was impressed that Maple's implementation for Groebner bases works now so well for this problem!

A few years ago on this site: http://www.mapleprimes.com/questions/131939-Calculating-Groebner-Basis-For-Sudoku
it was an attempt to solve the problem with this method but it failed (due to wrong number of polynomials).

```sudoku:=proc(A::'Matrix'(9,integer))
local x_A,x,Q,R,r, i,j,u,v,G;
Q:=proc(X,Y) normal((mul(X-i,i=1..9)-mul(Y-i,i=1..9))/(X-Y)) end;
x_A:=seq(seq( `if`(A[i,j]>0,x[i,j]-A[i,j],NULL),i=1..9),j=1..9);
R:={seq({seq(x[i,j],j=1..9)},i=1..9), seq({seq(x[i,j],i=1..9)},j=1..9),
seq(seq({seq(seq(x[3*u+i,3*v+j],i=1..3),j=1..3)},u=0..2),v=0..2)};
G:=Groebner:-Basis({seq(seq(seq(Q(u,v),u=r minus {v}),v=r),r=R),x_A},'_vv');
if nops(G)<>81 then error "Invalid Sudoku matrix" fi;
eval(Matrix(9,symbol=x), `union`(map(u->solve({u}), G)[]));
end:
```

sudoku(A) < A; # Solving the previous game

# Let's solve another one:
A:=Matrix(9,9,[[0,0,0,4,0,0,0,8,0],[0,5,2,7,0,0,4,0,0],[3,0,0,0,0,0,0,0,0],[5,1,0,8,0,0,0,0,0],[0,0,0,5,0,0,6,7,0],[0,9,0,0,7,0,0,0,3],[2,4,0,0,0,5,0,0,0],[9,0,0,0,0,0,0,3,8],[0,0,0,0,0,0,9,4,0]]):
sudoku(A) < A;

Matrix   # A Sudoku matrix which crashes Maple!
(9,[[8,0,0,0,0,0,0,0,0],[0,0,3,6,0,0,0,0,0],[0,7,0,0,9,0,2,0,0],[0,5,0,0,0,7,0,0,0],[0,0,0,0,4,5,7,0,0],[0,0,0,1,0,0,0,3,0],[0,0,1,0,0,0,0,6,8],[0,0,8,5,0,0,0,1,0],[0,9,0,0,0,0,4,0,0]]):

## how to check the dependency of groebner basis or a...

how to check the dependency of groebner basis or a set of polynomials?

## Solving with Groebner basis...

Suppose that a finite set of polynomials in C[x,y,z] has a finite number of solutions (i.e. the generated ideal is 0-dimensional).

Suppose also that the Groebner basis wrt plex(x,y,z) is

[f(z), g(y,z), h(y,z), k(x,y,z)]

As well known, the system can be now easily solved: choose a root z0 of f, plug it into g and h and look for a common root (y0) etc.

The question is the following:
Is it true that for EVERY root z0 of f there exist y0, z0 such that (x0,y0,z0) satisfy the system?

In all the examples I have seen this is true, but I don't know whether this is true in general or there is a counterexample.

[This is not a pure Maple question but I know that some members here work in this area].

Thank you.

## Is there a method to relate groebner bases with mo...

Is there a method to relate groebner bases with monomials ideals

## Error when I generate the normal set (Gröbner bas...

Hi all,

I am using Maple 2016.

I have defined 5 polynomials: f1, f2, f3, f4 and f5 with 5 unknowns q1,q2 ,q3, q4 and lamda.

After this, I generated the Gröbner basis. But when I try to find the normal set I got an error.

with(Groebner);

f1 := lamda*q1-(3380075947548081*q1*(1/140737488355328)-259050600068343*q2*(1/140737488355328)-1826834460600733*q3*(1/1125899906842624)+4414049272733425*q4*(1/9007199254740992))*(q2*(8289619202186977*q1*(1/9007199254740992)+3380075947548081*q2*(1/281474976710656)-4414049272733425*q3*(1/18014398509481984)-1826834460600733*q4*(1/2251799813685248))+q3*(1826834460600733*q1*(1/2251799813685248)-4414049272733425*q2*(1/18014398509481984)+843667886835955*q3*(1/70368744177664)-215663898201129*q4*(1/9007199254740992))-q4*(4414049272733425*q1*(1/18014398509481984)+1826834460600733*q2*(1/2251799813685248)+431327796402257*q3*(1/18014398509481984)+843667886835955*q4*(1/70368744177664))-q1*(3380075947548081*q1*(1/281474976710656)-259050600068343*q2*(1/281474976710656)-1826834460600733*q3*(1/2251799813685248)+4414049272733425*q4*(1/18014398509481984)));
f2 := lamda*q2+(259050600068343*q1*(1/140737488355328)+3380075947548081*q2*(1/140737488355328)-4414049272733425*q3*(1/9007199254740992)-1826834460600733*q4*(1/1125899906842624))*(q2*(8289619202186977*q1*(1/9007199254740992)+3380075947548081*q2*(1/281474976710656)-4414049272733425*q3*(1/18014398509481984)-1826834460600733*q4*(1/2251799813685248))+q3*(1826834460600733*q1*(1/2251799813685248)-4414049272733425*q2*(1/18014398509481984)+843667886835955*q3*(1/70368744177664)-215663898201129*q4*(1/9007199254740992))-q4*(4414049272733425*q1*(1/18014398509481984)+1826834460600733*q2*(1/2251799813685248)+431327796402257*q3*(1/18014398509481984)+843667886835955*q4*(1/70368744177664))-q1*(3380075947548081*q1*(1/281474976710656)-259050600068343*q2*(1/281474976710656)-1826834460600733*q3*(1/2251799813685248)+4414049272733425*q4*(1/18014398509481984)));
f3 := (1826834460600733*q1*(1/1125899906842624)-4414049272733425*q2*(1/9007199254740992)+843667886835955*q3*(1/35184372088832)-862655592804515*q4*(1/18014398509481984))*(q2*(8289619202186977*q1*(1/9007199254740992)+3380075947548081*q2*(1/281474976710656)-4414049272733425*q3*(1/18014398509481984)-1826834460600733*q4*(1/2251799813685248))+q3*(1826834460600733*q1*(1/2251799813685248)-4414049272733425*q2*(1/18014398509481984)+843667886835955*q3*(1/70368744177664)-215663898201129*q4*(1/9007199254740992))-q4*(4414049272733425*q1*(1/18014398509481984)+1826834460600733*q2*(1/2251799813685248)+431327796402257*q3*(1/18014398509481984)+843667886835955*q4*(1/70368744177664))-q1*(3380075947548081*q1*(1/281474976710656)-259050600068343*q2*(1/281474976710656)-1826834460600733*q3*(1/2251799813685248)+4414049272733425*q4*(1/18014398509481984)))+lamda*q3;
f4 := lamda*q4-(4414049272733425*q1*(1/9007199254740992)+1826834460600733*q2*(1/1125899906842624)+862655592804515*q3*(1/18014398509481984)+843667886835955*q4*(1/35184372088832))*(q2*(8289619202186977*q1*(1/9007199254740992)+3380075947548081*q2*(1/281474976710656)-4414049272733425*q3*(1/18014398509481984)-1826834460600733*q4*(1/2251799813685248))+q3*(1826834460600733*q1*(1/2251799813685248)-4414049272733425*q2*(1/18014398509481984)+843667886835955*q3*(1/70368744177664)-215663898201129*q4*(1/9007199254740992))-q4*(4414049272733425*q1*(1/18014398509481984)+1826834460600733*q2*(1/2251799813685248)+431327796402257*q3*(1/18014398509481984)+843667886835955*q4*(1/70368744177664))-q1*(3380075947548081*q1*(1/281474976710656)-259050600068343*q2*(1/281474976710656)-1826834460600733*q3*(1/2251799813685248)+4414049272733425*q4*(1/18014398509481984)));
f5 := q1^2+q2^2+q3^2+q4^2-1;
ord := tdeg(q1, q2, q3, q4, lamda);
tdeg(q1, q2, q3, q4, lamda)
G := Basis([f1, f2, f3, f4, f5], ord);

IsZeroDimensional(G);
false
ns, rv := NormalSet(G, ord);
Error, (in Groebner:-NormalSet) The case of non-zero-dimensional varieties is not handled.

Thank you.

## Groebner basis and polynomial ideals...

Hi, I have a big system with 27 polynomial equations in 16 unknowns: f_1=...=f_27=0.  I can store these equations but I cannot calculate a Grobner basis of the ideal  J generated by my polynomials (allocation problem) - I use the library "with(FGb)"-  What interests me is whether my system is minimal in the following sense.

If, for example,  I remove f_1, is the ideal generated by (f_2,...f_27)  J again ? That is to say, is f_1 in the ideal generated by f_2,...,f_27 ? I would like to get an answer "yes" or "no" for each removed  f_i.

My question: can we solve the problem above  without calculating a Grobner basis of J?

## Could you please introduce me some examples s.t. t...

I need  some examples s.t. the computation of their lexicographic Groebner basis is heavy?

Thank you so much.

## Maple is slow after using Groebner and PolynomialI...

After using the Groebner and PolynomialIdeals packages, Maple goes into a long calculation when I make an entry of the form

name:=polynomial expression. This can take 10's of minutes for an expression of two lines. The only solution I have found is to save the sheet and restart it and enter the line name:= etc. before loading Groebner and PolynomialIdeals. This is most inconvenient. Is there a better workaround?

## how to translate this mathematica code into maple ...

``````curve =2{t (3 t^4+50 t^2-33),7 t^6-60 t^4+15 t^2+2}/(t^2+1)^3;
implicit =GroebnerBasis[Thread[{x, y}== curve],{x, y}, t]//First550731776-41620992 x^2+585816 x^4+625 x^6-182250 x^4 y -41620992 y^2+1171632 x^2 y^2+1875 x^4 y^2+364500 x^2 y^3+585816 y^4+1875 x^2 y^4-36450 y^5+625 y^6http://mathematica.stackexchange.com/questions/87136/how-to-convert-a-rational-parametric-plane-curve-into-implicit-form``````

## Groebner produces inconsistent result...

Hello,

Calculated a Grobasis basis. Used the 19 of the 29 equations to produce a Sylvester type matrix to get a univarite polynomial. The problem I am having is I can't produce a consistant matrix. I think the problem may lie in how I sort the equations. I have used this method once before and it worked to produce the result then. Run the worksheet and the run it again and most likely a different outcome occurs. I copy and pasted the polynmial list to make this worksheet. The coefficients are very long. Have annotated the worksheet to help explain.

## Eliminating redundant equations ...

I have a system of 16 polynomial equations in 15 variables. Independently I know there is at least a one parameter familiy of solutions to this system, so there is reason to think at least two of the equations are redundent. I would like to use Maple to decipher which of the equations are redundent, but I am unsure how to proceed.

So far I have looked at the Groebner package, and it seems like the Reduce and InterReduce commands will be useful. Say I call the set of 16 polynomials X and define a lexicographical order T on the variables. I then ask maple to compute

Reduce(X,X,T)

and receive a list with 7 zeroes and 9 polynomials. What exactly is this telling me? Does this mean that maple has used polynomial division and found that 7 of the equations are redundent?

## Listing monomials...

I an experimenting with Groebner basis. Have a set 17 equations. There are 12 unknowns. Using 14 of the equations and tdeg, the system produced 65 equations. How do I get a list of the monomials in this new list?

## IdealMembership Testing...

I was using Maple18 for the Ideal Membership Problem. While checking it I got the following error

Error, (in F4:-GroebnerBasis) argument `[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-48,-48,48,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]/A1[119295][119295]` is incorrect or out of order

Please tell me, how can I resolve this error ?.

Thank You.

## Error in Basis ...

do not know why Basis got error in this case.

how to calculate this Basis?

with(LinearAlgebra):
prej := Matrix([[diff(eq2,a),diff(eq2,b),diff(eq2,c)],[diff(eq3,a),diff(eq3,b),diff(eq3,c)],[diff(eq4,a),diff(eq4,b),diff(eq4,c)]]);
jaco := Determinant(prej);
jaco := -a*b*c^2+c^2;
g3 := [diff(jaco,a),diff(jaco,b),diff(jaco,c)];
K := [r-g3[1],u-g3[2],v-g3[3]];
G := Basis(K, 'tord', degrevlex(r,u,v));

Error, (in LinearAlgebra:-Basis) invalid input: LinearAlgebra:-Basis expects its 1st argument, V, to be of type {Vector, {list(Vector), set(Vector)}} but received [b*c^2+r, a*c^2+u, 2*a*b*c-2*c+v]

## How to find polynomial map?...

how to calculate the polynomial map for a system of  polynomials

assume system of polynomial is in terms of a,b,c

how to find polynomial map

(r - something in terms of a,b,c)

(u - something in terms of a,b,c)

(v - something in terms of a,b,c)

 1 2 3 4 Page 1 of 4
﻿