101 lines
1.5 KiB
Text
101 lines
1.5 KiB
Text
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
|