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

 Page 1 of 1
﻿