Форум

Deff · #31 (**permalink**) 23.12.2015, 14:57

Вроде родил алгоритм, если не отвлекут седни выложу

Deff · #32 (**permalink**) 24.12.2015, 00:28

Ну вчерне(осталось еще парочку рандомов сделать...

<!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>

рони · #33 (**permalink**) 24.12.2015, 00:40

Deff,

Deff · #34 (**permalink**) 24.12.2015, 00:45

рони,
Ну еще осталось покрутить матрицу и перестановки триад меж собою
рони, Ночью Вчера осенило, (из перво-сделанной таблицы), двигать в первой триаде не на одну ячейку а на высоту минитаблы, а в остальных метод тот жа, чо и в первоначальном скрипте

рони · #35 (**permalink**) 24.12.2015, 00:47

Deff,

Deff · #36 (**permalink**) 24.12.2015, 02:23

Забавно, из 10 000 табличек подряд, не повторилось ни одной... (создались за 40 сек...
~~Думаю: вот стоит добавлять рандом...~~ (Ведь могу переборщить и будут повторяться, хотя наверно нун просто проверить версию с дополнениями...
Гы, из 100 000 тож ни одного повтора (388 сек)
===========================
Статистика на миллионе табличек:
дважды повторились идентичные: 9359, (0.9% от всех)
Трижды: 110,
Четырежды: 3;
===========
Время создания: 4230сек;
________________________________________________
Выяснил что за 800 000 антикореляционные возможности текущих перестановок существенно снижаются, вероятнсть совпадений возрастает... Мон прикинуть число комбинаций за счет перестановок наверно в районе 10^7 - 10^8
Нун добавлять Варианты перестановок.
Википедь пишет, что число Вариантов табличек в районе 10^21 (Т.е у меня чичас 21/3 (= 7) - не хватает как раз двух вариантов свапа триад и кручения матрицы

Deff · #37 (**permalink**) 24.12.2015, 22:12

.forEach Замедлил в 4 раза с 4.5с на 1000 до 20с (ужос)
Выкинул нафиг(удобен но не для длинных тестов)

рони · #38 (**permalink**) 24.12.2015, 22:47

Deff,

рони · #39 (**permalink**) 24.12.2015, 23:44

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>

Deff · #40 (**permalink**) 24.12.2015, 23:59

Ну да, у тьву шустро - 10000 за 3.5 сек(В Мозилле)) (Но у я свой тестил со старой оперы, своё там существенно медленней, и второе - у мну добавлено еще рандомы и кручение таблы. Ксать неплохо бы выводить цифру текущего кол-ва, а то в Опере думал зависло

Форум

Справочник

Discord чат

Курсы javascript