Deff, если есть желание проверь на повторяемость
<!DOCTYPE HTML>
<html>
<head>
<title>Untitled</title>
<meta charset="utf-8">
<style type="text/css">
div{
border: 3px groove #8B4513;
float: left;
}
</style>
</head>
<body>
<script>
Array.prototype.shuffle = function() {
for (var a = this.length - 1; 0 < a; a--) {
var b = Math.floor(Math.random() * (a + 1)),
c = this[b];
this[b] = this[a];
this[a] = c
}
return this
};
function fn() {
for (var f = [], b = [], g = {}, h = {}, n = 0, a = 0; 9 > a; a++) b.push(a + 1), g[a] = {}, h[a] = {};
for (var c = 0; 9 > c;) {
for (var a = b.slice(), d = [], k = 0; 9 > d.length;) {
var l = d.length,
q = (l / 3 | 0) + 3 * (c / 3 | 0),
e = (3 > l ? a.slice(-6) : a).filter(function(a) {
return !h[l][a] && !g[q][a] && -1 === d.indexOf(a)
});
if (e.length) {
var m = Math.floor(Math.random() * e.length),
e = e[m];
d.push(e);
m = a.indexOf(e);
a.splice(m, 1)
} else a = b.slice(), d = [];
k++;
if (50 <= k) {
k = 0;
break
}
}
a = d.concat(a.shuffle());
b = !c || a.every(function(a, p, b) {
b = (p / 3 | 0) + 3 * (c / 3 | 0);
return !g[b][a] &&
!h[p][a]
});
n++;
if (40 <= n) break;
b ? (f.push(a), a.forEach(function(a, b, d) {
g[(b / 3 | 0) + 3 * (c / 3 | 0)][a] = h[b][a] = !0
}), c++) : (c--, 0 > c && (c = 0), a = f[c] || [], f.length = c, a.forEach(function(a, b, d) {
g[(b / 3 | 0) + 3 * (c / 3 | 0)][a] = h[b][a] = !1
}));
b = a
}
return 9 == f.length ? f : fn()
};
var d = performance.now();
for (var i=0; i<10000 ; i++) {fn()};
alert('10000 => '+((performance.now()-d)/100|0)/10 + 's') //время генерации 10000
for (var i=0; i<500 ; i++) {document.write('<div>'+fn().join('<br>')+'</div>') }//500 вариантов для визуальной проверки
</script>
</body>
</html>