Task

Solve a partially filled-in normal   9x9   Sudoku grid   and display the result in a human-readable format.

references

 Algorithmics of Sudoku   may help implement this.
 Python Sudoku Solver Computerphile video.


mata
function sudoku(a) {
	s = J(81,20,.)
	t = J(81,3,.)
	v = J(81,9,1)
	w = J(81,1,0)
	for (i=1; i<=9; i++) {
		for (j=1; j<=9; j++) {
			n = (i-1)*9+j
			k = floor((i-1)/3)*3+floor((j-1)/3)+1
			t[n,.] = i,j,k
		}
	}
	for (i=1; i<=81; i++) {
		for (j=i+1; j<=81; j++) {
			if (any(t[i,.]:==t[j,.])) {
				w[i]=w[i]+1
				w[j]=w[j]+1
				s[i,w[i]] = j
				s[j,w[j]] = i
			}
		}
	}
	w = J(81,1,1)
	for (i=1; i<=9; i++) {
		for (j=1; j<=9; j++) {
			if (a[i,j]<.) {
				push(a,s,t,v,w,(i-1)*9+j,a[i,j])
			}
		}
	}
	return(solve(a,s,t,v,w))
}
 
function solve(a,s,t,v,w) {
	for (q=1; q;) {
		q = 0
		for (n=1; n<=81; n++) {
			if (w[n]) {
				r = sum(v[n,.])
				if (r==0) {
					return(0)
				}
				else if (r==1) {
					q = 1
					push(a,s,t,v,w,n,selectindex(v[n,.]))
				}
			}
		}
	}
 
	if (all(w:==0)) {
		return(1)
	}
	else {
		m0 = n0 = .
		for (n=1; n<=81; n++) {
			m = sum(v[n,.])
			if (w[n] & m>1 & m<m0) {
				m0 = m
				n0 = n
			}
		}
		z = selectindex(v[n0,.])
		for (i=1; i<=m0; i++) {
			a2 = a
			v2 = v
			w2 = w
			push(a2,s,t,v2,w2,n0,z[i])
			if (solve(a2,s,t,v2,w2)) {
				a = a2
				return(1)
			}
		}
		return(0)
	}
}
 
function push(a,s,t,v,w,n,z) {
	w[n] = 0
	i = t[n,1]
	j = t[n,2]
	a[i,j] = z
	for (k=1; k<=20; k++) {
		v[s[n,k],z] = 0
	}
}
 
a = 5,3,.,.,7,.,.,.,.\
    6,.,.,1,9,5,.,.,.\
    .,9,8,.,.,.,.,6,.\
    8,.,.,.,6,.,.,.,3\
    4,.,.,8,.,3,.,.,1\
    7,.,.,.,2,.,.,.,6\
    .,6,.,.,.,.,2,8,.\
    .,.,.,4,1,9,.,.,5\
    .,.,.,.,8,.,.,7,9
 
sudoku(a)
a
end