Вроде родил алгоритм, если не отвлекут седни выложу
|
Ну вчерне(осталось еще парочку рандомов сделать...
<!DOCTYPE html> <html> <head> <meta http-equiv="content-type" content="text/html; charset=UTF-8"> <meta name="robots" content="noindex"> <title> Sudoku </title> <script src='http://code.jquery.com/jquery-1.11.0.js'></script> <style> #out td{ width:34px; height:34px; text-align:center; vaertical-align: middle; } #out, #out tr, #out td{ padding: 0px; margin: 0px; border:none 0; border-collapse:collapse; } #out td{ border: rgba(0,0,0,.2) solid 1px; color: rgba(0,0,204,.611) } #out td:nth-child(3n+1) { border-left: rgba(0,0,0,.2) solid 3px; } #out tr:nth-child(3n) { border-bottom: rgba(0,0,0,.2) solid 3px; } #out{ table-layout:fixed; border-top: rgba(0,0,0,.2) solid 3px; border-right: rgba(0,0,0,.2) solid 3px; } </style> </head> <body> <div id=wrap><table id=out><tbody> <tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr> <tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr> <tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr> <tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr> <tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr> <tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr> <tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr> <tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr> <tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr> </tbody></table></div> <p></p> <p></p> <input type="button" value="Запустить!" onclick="getSudoku ()"> <script> function indexRandom(lng){ var a = {},i,out=[],n=0; while (n!=lng){ i = Math.floor(lng*Math.random()); if(typeof(a[i])=='undefined'){ a[i]=i; out.push(a[i]); n++; } } return out; } //Cдвиг группы из N строк на n-ячеек влево; function shiftLinetoN(Nstart,N,n,arr){ var j,x; for(j=Nstart;j<Nstart+N;j++){ for(x=0;x<n;x++)arr[j].unshift(arr[j].pop()); } } //Рандомная перестановка группы из трёх строк; function swap3nLines (Nstart,arr){ var i,del,index = indexRandom(3); del = arr.slice(Nstart,Nstart+3); for(i=0;i<3;i++) arr[Nstart+index[i]]=del[i]; } getSudoku = function () { var i,j,ind, arr = []; //Таблица; var line0 = arr[0] = [1,2,3,4,5,6,7,8,9]; //Рандом-Перестановка элементов первой строки; var ind=indexRandom(9); arr[0].forEach(function (x,i){arr[0][i]=ind[i]+1;}); var line1 = arr[1] = arr[0].slice(0); shiftLinetoN(1,1,3,arr); var line2 = arr[2] = arr[1].slice(0); shiftLinetoN(2,1,3,arr); //Cоздаём остальные cтроки таблицы; for(j=3;j<9;j++){ arr[j]=arr[j%3].slice(0); if(j%3==2) shiftLinetoN(j-2,3,parseInt(j/3),arr); } //Рандом-Перестановка строк в триадах строк; for(j=0;j<6;j++){ if(j%3==2) swap3nLines(j-2,arr); } //Записываем в таблу $('#out td').each(function (j){ $(this).html(arr[parseInt(j/9)][j%9]); }); } //alert(JSON.stringify(del)) </script> </body> </html> |
Deff,
:dance: |
рони,
Ну еще осталось покрутить матрицу и перестановки триад меж собою рони, Ночью Вчера осенило, (из перво-сделанной таблицы), двигать в первой триаде не на одну ячейку а на высоту минитаблы, а в остальных метод тот жа, чо и в первоначальном скрипте |
Deff,
:yes: |
Забавно, из 10 000 табличек подряд, не повторилось ни одной... (создались за 40 сек...
Гы, из 100 000 тож ни одного повтора (388 сек) =========================== Статистика на миллионе табличек: дважды повторились идентичные: 9359, (0.9% от всех) Трижды: 110, Четырежды: 3; =========== Время создания: 4230сек; ________________________________________________ Выяснил что за 800 000 антикореляционные возможности текущих перестановок существенно снижаются, вероятнсть совпадений возрастает... Мон прикинуть число комбинаций за счет перестановок наверно в районе 10^7 - 10^8 Нун добавлять Варианты перестановок. Википедь пишет, что число Вариантов табличек в районе 10^21 (Т.е у меня чичас 21/3 (= 7) - не хватает как раз двух вариантов свапа триад и кручения матрицы |
.forEach Замедлил в 4 раза с 4.5с на 1000 до 20с (ужос)
Выкинул нафиг(удобен но не для длинных тестов) |
Deff,
:) |
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> |
Ну да, у тьву шустро - 10000 за 3.5 сек(В Мозилле)) (Но у я свой тестил со старой оперы, своё там существенно медленней, и второе - у мну добавлено еще рандомы и кручение таблы. Ксать неплохо бы выводить цифру текущего кол-ва, а то в Опере думал зависло
|
Часовой пояс GMT +3, время: 09:04. |