Featured Post

1884

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]]):

 

 

Featured Post

In the creation of this animation the technique from here  was used.

 

                    

 

The code of this animation:

with(plots): with(plottools):
SmallHeart:=plot([1/20*sin(t)^3, 1/20*(13*cos(t)/16-5*cos(2*t)/16-2*cos(3*t)/16-cos(4*t)/16), t = 0 .. 2*Pi], color = "Red", thickness=3, filled):
F:=t->[sin(t)^3, 13*cos(t)/16-5*cos(2*t)/16-2*cos(3*t)/16-cos(4*t)/16]:
Gf:=display(translate(SmallHeart, 0,0.37)):
Gl:=display(translate(SmallHeart, 0,-1)):
G:=t->display(translate(SmallHeart, F(t)[])):
A:=display(seq(display(op([Gf,seq(G(-Pi/20*t), t=3..k),seq(G(Pi/20*t), t=3..k)]))$4,k=2..17),display(op([Gf,seq(G(-Pi/20*t), t=3..17),seq(G(Pi/20*t), t=3..17),Gl]))$30, insequence=true, size=[600,600]):
B:=animate(textplot,[[-0.6,0.25, "Happy"[1..round(n)]],color="Orange", font=[times,bolditalic,40], align=right],n=0..5,frames=18, paraminfo=false):
C:=animate(textplot,[[-0.2,0, "Valentine's"[1..round(n)]],color=green, font=[times,bolditalic,40], align=right],n=1..11,frames=35, paraminfo=false):
E:=animate(textplot,[[-0.3,-0.25, "Day!"[1..round(n)]],color="Blue", font=[times,bolditalic,40], align=right],n=1..4,frames=41, paraminfo=false):
T:=display([B, display(op([1,-1,1],B),C), display(op([1,-1,1],B),op([1,-1,1],C),E)], insequence=true):
K:=display(A, T, axes=none):
K;


The last frame of this animation:

display(op([1,-1],K), size=[600,600], axes=none);  # The last frame

                          

 

ValentinelDay.mw
 

Edit. The code was edited - the number of frames has been increased.



Maple 18 on 4K monitor

Maple 18 asked by wkehowski 10 Yesterday

Strange Behavior - Bug?

Maple 2016 asked by Thomas ... 95 February 23