API tools faq
paste
mramine364

sudoku-app2.js

mramine364
Sep 9th, 2016
123
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
JavaScript 29.00 KB | None | 0 0
raw download clone embed print report
  1.  
  2.  
  3. function sudoku_cell() {
  4.     return {
  5.         p: [1,2,3,4,5,6,7,8,9],
  6.         v: 0,
  7.         rand: function(){
  8.             let max = this.p.length-1;
  9.             let min = 0;
  10.             let i = Math.floor( Math.random()*(max-min+1)+min );
  11.             this.v = this.p.splice(i,1)[0];
  12.             return this.v;
  13.         },
  14.         remove: function(el){ // remove elem if contains return true, else false
  15.             for(let i=0;i<this.p.length;i++){
  16.                 if( this.p[i]==el ){
  17.                     this.p.splice(i,1);
  18.                     return true;
  19.                 }
  20.             }
  21.             return false;
  22.         },
  23.         isEmpty: function(){
  24.             if( this.v==0 && this.p.length==0 )
  25.                 return true;
  26.             return false;
  27.         }
  28.     }
  29. }
  30.  
  31. function sudoku_cell_copy(v, p) {
  32.     return {
  33.         p: p,
  34.         v: v,
  35.         rand: function(){
  36.             let max = this.p.length-1;
  37.             let min = 0;
  38.             let i = Math.floor( Math.random()*(max-min+1)+min );
  39.             this.v = this.p.splice(i,1)[0];
  40.             return this.v;
  41.         },
  42.         remove: function(el){ // remove elem if contains
  43.             for(let i=0;i<this.p.length;i++){
  44.                 if( this.p[i]==el ){
  45.                     this.p.splice(i,1);
  46.                     break;
  47.                 }
  48.             }
  49.         },
  50.         isEmpty: function(){
  51.             if( this.v==0 && this.p.length==0 )
  52.                 return true;
  53.             return false;
  54.         }
  55.     }
  56. }
  57.  
  58. let steps=0;
  59.  
  60. let sudoku = { // 9*9 sudoku
  61.     t: null,
  62.     init: function(){
  63.         this.t = [];
  64.         for(let i=0;i<9;i++){
  65.             let mt = [];
  66.             for(let j=0;j<9;j++){
  67.                 mt.push( sudoku_cell() );
  68.             }
  69.             this.t.push(mt);
  70.         }
  71.     },
  72.     eliminate: function(t, n, ki, kj){
  73.         // row elimination
  74.         for(let i=0;i<9;i++){
  75.             if( t[ki][i].v==0 ){
  76.                 t[ki][i].remove(n);
  77.             }
  78.             if( t[ki][i].isEmpty() ){
  79.                 return false;
  80.             }
  81.         }
  82.         // column elimination
  83.         for(let i=0;i<9;i++){
  84.             if( t[i][kj].v==0 ){
  85.                 t[i][kj].remove(n);
  86.             }
  87.             if( t[i][kj].isEmpty() ){
  88.                 return false;
  89.             }
  90.         }
  91.         // mini-grid elimination
  92.         let ci=Math.floor(ki/3)*3, cj=Math.floor(kj/3)*3;
  93.         for(let i=0;i<3;i++){
  94.             for(let j=0;j<3;j++){
  95.                 if( t[ci+i][cj+j].v==0 ){
  96.                     t[ci+i][cj+j].remove(n);
  97.                 }
  98.                 if( t[ci+i][cj+j].isEmpty() ){
  99.                     return false;
  100.                 }
  101.             }
  102.         }
  103.         return true;
  104.     },
  105.     copy: function(t){
  106.         let r = [];
  107.         for(let i=0;i<9;i++){
  108.             let mt = [];
  109.             for(let j=0;j<9;j++){
  110.                 let obj = sudoku_cell_copy(t[i][j].v, t[i][j].p.slice());
  111.                 mt.push( obj );
  112.             }
  113.             r.push(mt);
  114.         }
  115.         return r;
  116.     },
  117.     gen: function(t, ki, kj, n, lki, lkj){
  118.        
  119.         // steps++;
  120.         // if( steps>100 )
  121.         //  return null;
  122.         // eleminate possibilities
  123.         if( !(ki==0 && kj==0) && !this.eliminate(t, n, lki, lkj) ){
  124.             return null;
  125.         }
  126.         // this.print(t);
  127.         // next
  128.         let nki, nkj;
  129.         if( kj==8 ){
  130.             nki = ki+1;
  131.             nkj = 0;
  132.         }else{
  133.             nki = ki;
  134.             nkj = kj+1;
  135.         }
  136.        
  137.         while( t[ki][kj].p.length!=0 ){
  138.             let nv = t[ki][kj].rand();
  139.             if( nki==9 ){
  140.                 // job done
  141.                 return t;
  142.             }
  143.             let r = this.gen(this.copy(t), nki, nkj, nv, ki, kj);
  144.             if( r!=null ){
  145.                 // this.print(r);
  146.                 return r;
  147.             }
  148.         }
  149.         return null;
  150.     },
  151.     rand: function(){
  152.         console.log(" init.. ");
  153.         this.init();
  154.         console.log(" randering.. ");
  155.         let r = this.gen(this.t, 0, 0, 0, 0, 0);
  156.         // console.log(r);
  157.         console.log(" printing.. ");
  158.         this.print(r);
  159.         console.log(" digging.. ");
  160.         this.dig(r, 30);
  161.         this.print(r);
  162.         console.log(" solving.. ");
  163.         let s;
  164.         // console.log(s);
  165.         while( (s=this.solve(r)).length>1 ){
  166.             // for(let i=0;i<s.length;i++){
  167.             //  console.log(" -------------- ");
  168.             //  this.print(s[i]);
  169.             // }
  170.            
  171.             let objs = [];
  172.             // mn:
  173.             for(let i=0;i<9;i++){
  174.                 for(let j=0;j<9;j++){
  175.                     if( s[0][i][j].v!=s[1][i][j].v ){
  176.                         objs.push({
  177.                             i: i, j: j,
  178.                             v: s[0][i][j].v
  179.                         });
  180.                     }
  181.                 }
  182.             }
  183.             // let str="";
  184.             // for(let i=0;i<objs.length;i++){
  185.             //  str+="["+objs[i].i+","+objs[i].j+","+objs[i].v+"]; ";
  186.             // }
  187.             // console.log(str);
  188.  
  189.             // console.log(" ------bgrid-------- ");
  190.             // this.print(r);
  191.  
  192.             let obj = objs[Math.floor(Math.random()*objs.length)];
  193.             // console.log(obj.i, obj.j, obj.v);
  194.            
  195.             r[obj.i][obj.j].v = obj.v;
  196.             this.eliminate(r, obj.v, obj.i, obj.j);
  197.  
  198.             // console.log(" ------grid-------- ");
  199.             // this.print(r);
  200.         }
  201.         console.log(" final randering.. ");
  202.         // this.print(r);
  203.         // console.log(s);
  204.         return [r, s[0]];
  205.     },
  206.     print: function(t){
  207.         // let obj =null;
  208.         let str = "";
  209.         for(let i=0;i<9;i++){          
  210.             for(let j=0;j<9;j++){
  211.                 // if( obj==null && t[i][j].v==0 ){
  212.                 //  obj = t[i][j];
  213.                 //  // console.log(obj.v, obj.p.join(", "));
  214.                 // }
  215.                 str += t[i][j].v;
  216.                 if( j%3==2 )
  217.                     str += " ";
  218.             }
  219.             str +="\n";
  220.         }
  221.         console.log(str);
  222.     },
  223.     dig: function(t, N){
  224.         let pz = [];
  225.         for(let i=0;i<9;i++){      
  226.             let tpz = [];
  227.             for(let j=0;j<9;j++){
  228.                 tpz.push( {i: i, j: j} );
  229.             }
  230.             pz.push( tpz );
  231.         }
  232.         let n=9*9;
  233.         while(n>N){
  234.             let ti = Math.floor( Math.random()*pz.length );
  235.             let tj = Math.floor( Math.random()*pz[ti].length );
  236.             let obj = pz[ti][tj];
  237.             t[obj.i][obj.j].v = 0;
  238.             pz[ti].splice(tj, 1);
  239.             if( pz[ti].length==0 ){
  240.                 pz.splice(ti, 1);
  241.             }
  242.             n--;
  243.         }
  244.         return t;
  245.     },
  246.     solve: function(t){
  247.         for(let i=0;i<9;i++){
  248.             for(let j=0;j<9;j++){
  249.                 if( t[i][j].v==0 ){
  250.                     t[i][j].p = [1,2,3,4,5,6,7,8,9];
  251.                 }
  252.             }
  253.         }
  254.         for(let i=0;i<9;i++){
  255.             for(let j=0;j<9;j++){
  256.                 if( t[i][j].v!=0 ){
  257.                     this.eliminate(t, t[i][j].v, i, j);
  258.                 }
  259.             }
  260.         }
  261.         let sols = [];
  262.         this._solve(sols, this.copy(t), 0, 0, 0);
  263.         return sols;
  264.     },
  265.     _solve: function(sols, t, si ,sj, n){
  266.         // steps++;
  267.         // if( steps>10000 )
  268.         //  return null;
  269.         if( sols.length>1 )
  270.             return null;
  271.         if( !(si==0 && sj==0) && !this.eliminate(t, n, si, sj) ){
  272.             return null;
  273.         }
  274.         // console.log("t")
  275.         // this.print(t);
  276.         let i=si, j=sj;
  277.         while( i<9 && t[i][j].v!=0 ){
  278.             if( j==8 ){
  279.                 j=0;
  280.                 i++;
  281.             }else{
  282.                 j++;
  283.             }
  284.         }
  285.         if( i==9 ){
  286.             // console.log("i==9")
  287.             // this.print(t);
  288.             sols.push( t );
  289.             return null;
  290.         }
  291.         while( t[i][j].p.length>0 ){
  292.             let nv = t[i][j].rand();
  293.             this._solve(sols, this.copy(t), i, j, nv);
  294.             if( sols.length>1 )
  295.                 return null;
  296.         }
  297.     }
  298. };
  299.  
  300. let sts=0;
  301. let sudoku_Eval = {
  302.  
  303.     byInclusion: function(t){
  304.         let b = 0;
  305.         for(let i=0;i<t.length;i++){
  306.             for(let j=0;j<t[i].length;j++){
  307.                 if( t[i][j].v==0 && t[i][j].p.length==1 ){
  308.                     t[i][j].v=t[i][j].p[0];                
  309.                     // console.log('inclusion: row '+(i+1)+', col '+(j+1)+' val='+t[i][j].v)
  310.                     if( !sudoku.eliminate(t, t[i][j].v, i, j) ) // mean that the grid is unsolvable
  311.                         return -1;
  312.                     b++;
  313.                 }
  314.             }
  315.         }
  316.         return b;
  317.     },
  318.  
  319.     byExclusionRegion: function(t){
  320.         let b=0;
  321.         for(let ki=0;ki<3;ki++){
  322.             for(let kj=0;kj<3;kj++){
  323.                 let oc = [];
  324.                 for(let i=0;i<9;i++){
  325.                     oc.push({
  326.                         o: 0,
  327.                         i: 0, j: 0
  328.                     });
  329.                 }
  330.                 for(let i=0;i<3;i++){
  331.                     for(let j=0;j<3;j++){
  332.                         if( t[3*ki+i][3*kj+j].v==0 ){
  333.                             for(let k=0;k<t[3*ki+i][3*kj+j].p.length;k++){
  334.                                 if( ++oc[t[3*ki+i][3*kj+j].p[k]-1].o==1 ){                                 
  335.                                     oc[t[3*ki+i][3*kj+j].p[k]-1].i = 3*ki+i;
  336.                                     oc[t[3*ki+i][3*kj+j].p[k]-1].j = 3*kj+j;
  337.                                 }
  338.                             }
  339.                         }
  340.                     }
  341.                 }
  342.                 let i=0;
  343.                 while(i<oc.length){
  344.                     if( oc[i].o==1 ){
  345.                         t[oc[i].i][oc[i].j].v=i+1;                     
  346.                         // console.log('exclusion region: row '+(oc[i].i+1)+', col '+(oc[i].j+1)+' val='+(i+1))
  347.                         if( !sudoku.eliminate(t, i+1, oc[i].i, oc[i].j) ) // mean that the grid is unsolvable
  348.                             return -1;
  349.                         b++;
  350.                     }
  351.                     i++;
  352.                 }
  353.             }
  354.         }
  355.         return b;
  356.     },
  357.     byExclusionColumn: function(t){
  358.         let b=0;
  359.         for(let kj=0;kj<9;kj++){           
  360.             let oc = [];
  361.             for(let i=0;i<9;i++){
  362.                 oc.push({
  363.                     o: 0,
  364.                     i: 0, j: 0
  365.                 });
  366.             }
  367.             for(let i=0;i<9;i++){              
  368.                 if( t[i][kj].v==0 ){
  369.                     for(let k=0;k<t[i][kj].p.length;k++){
  370.                         if( ++oc[t[i][kj].p[k]-1].o==1 ){
  371.                             oc[t[i][kj].p[k]-1].i = i;
  372.                             oc[t[i][kj].p[k]-1].j = kj;
  373.                         }
  374.                     }
  375.                 }
  376.             }
  377.             let i=0;
  378.             while(i<oc.length){
  379.                 if( oc[i].o==1 ){
  380.                     t[oc[i].i][oc[i].j].v=i+1;
  381.                     // console.log('exclusion column: row '+(oc[i].i+1)+', col '+(oc[i].j+1)+' val='+(i+1))
  382.                     if( !sudoku.eliminate(t, i+1, oc[i].i, oc[i].j) ) // mean that the grid is unsolvable
  383.                             return -1;
  384.                     b++;
  385.                 }
  386.                 i++;
  387.             }          
  388.         }
  389.         return b;
  390.     },
  391.     byExclusionRow: function(t){
  392.         let b=0;
  393.         for(let ki=0;ki<9;ki++){           
  394.             let oc = [];
  395.             for(let i=0;i<9;i++){
  396.                 oc.push({
  397.                     o: 0,
  398.                     i: 0, j: 0
  399.                 });
  400.             }
  401.             for(let i=0;i<9;i++){              
  402.                 if( t[ki][i].v==0 ){
  403.                     for(let k=0;k<t[ki][i].p.length;k++){
  404.                         if( ++oc[t[ki][i].p[k]-1].o==1 ){
  405.                             oc[t[ki][i].p[k]-1].i = ki;
  406.                             oc[t[ki][i].p[k]-1].j = i;
  407.                         }
  408.                     }
  409.                 }              
  410.             }
  411.             let i=0;
  412.             while(i<oc.length){
  413.                 if( oc[i].o==1 ){
  414.                     t[oc[i].i][oc[i].j].v=i+1;
  415.                     // console.log('exclusion row: row '+(oc[i].i+1)+', col '+(oc[i].j+1)+' val='+(i+1))
  416.                     if( !sudoku.eliminate(t, i+1, oc[i].i, oc[i].j) ) // mean that the grid is unsolvable
  417.                             return -1;
  418.                     b++;
  419.                 }
  420.                 i++;
  421.             }          
  422.         }
  423.         return b;
  424.     },
  425.  
  426.     byExclusivepairRegion: function(t){
  427.         let b=0;
  428.         for(let kc=0;kc<9;kc++){
  429.             let ci = Math.floor(kc/3) , cj = kc%3;
  430.             fi:
  431.             for(let i=0;i<9;i++){
  432.                 while(i<9 &&
  433.                     !(t[3*ci+Math.floor(i/3)][3*cj+i%3].v==0 &&
  434.                       t[3*ci+Math.floor(i/3)][3*cj+i%3].p.length==2)) i++;
  435.                 if( i==9 ) break;
  436.                 let rri = Math.floor(i/3), rci = i%3;
  437.  
  438.                 for(let j=i+1;j<9;j++){
  439.                     console.log()
  440.                     while(j<9 &&
  441.                     !(t[3*ci+Math.floor(j/3)][3*cj+j%3].v==0 &&
  442.                       t[3*ci+Math.floor(j/3)][3*cj+j%3].p.length==2)) j++;
  443.                    
  444.                     if( j==9 ) break fi;
  445.                     let rrj = Math.floor(j/3), rcj = j%3;
  446.  
  447.                     if( t[3*ci+rri][3*cj+rci].p[0]==t[3*ci+rrj][3*cj+rcj].p[0]
  448.                         &&  t[3*ci+rri][3*cj+rci].p[1]==t[3*ci+rrj][3*cj+rcj].p[1] ){
  449.  
  450.                         for(let k=0;k<9;k++){
  451.                             let rrk = Math.floor(k/3), rck = k%3;
  452.  
  453.                             if( k==i || k==j || t[3*ci+rrk][3*cj+rck].v!=0 ) continue;
  454.                             t[3*ci+rrk][3*cj+rck].remove(t[3*ci+rri][3*cj+rci].p[0]);
  455.                             t[3*ci+rrk][3*cj+rck].remove(t[3*ci+rri][3*cj+rci].p[1]);
  456.                             if( t[3*ci+rrk][3*cj+rck].p.length==1 ){
  457.                                 t[3*ci+rrk][3*cj+rck].v = t[3*ci+rrk][3*cj+rck].p[0];                              
  458.                                 // console.log('exclusive pair region: row '+(3*ci+rrk+1)+', col '+(3*cj+rck+1)
  459.                                     // +' val='+(t[3*ci+rrk][3*cj+rck].v))
  460.                                 if( !sudoku.eliminate(t, t[3*ci+rrk][3*cj+rck].v, 3*ci+rrk, 3*cj+rck) ) // mean that the grid is unsolvable
  461.                                     return -1;
  462.                                 b++;
  463.                             }
  464.                         }
  465.                     }                  
  466.                 }          
  467.             }  
  468.         }
  469.         return b;
  470.     },
  471.     byExclusivepairColumn: function(t){
  472.         let b=0;
  473.         for(let kj=0;kj<9;kj++){
  474.             fi:
  475.             for(let i=0;i<9;i++){
  476.                 while(i<9 && !(t[i][kj].v==0 && t[i][kj].p.length==2)) i++;
  477.                 if( i==9 ) break;
  478.                 for(let j=i+1;j<9;j++){
  479.                     while(j<9 && !(t[j][kj].v==0 && t[j][kj].p.length==2)) j++;
  480.                     if( j==9 ) break fi;
  481.                     if( t[i][kj].p[0]==t[j][kj].p[0]
  482.                         && t[i][kj].p[1]==t[j][kj].p[1] ){
  483.                         for(let k=0;k<9;k++){
  484.                             if( k==i || k==j || t[k][kj].v!=0 ) continue;
  485.                             t[k][kj].remove(t[i][kj].p[0]);
  486.                             t[k][kj].remove(t[i][kj].p[1]);
  487.                             if( t[k][kj].p.length==1 ){
  488.                                 t[k][kj].v=t[k][kj].p[0];
  489.                                 // sudoku.eliminate(t, t[k][kj].v, k, kj);
  490.                                 // console.log('exclusive pair column: row '+(k+1)+', col '+(kj+1)
  491.                                 //  +' val='+(t[k][kj].v))
  492.                                 if( !sudoku.eliminate(t, t[k][kj].v, k, kj) ) // mean that the grid is unsolvable
  493.                                     return -1;
  494.                                 b++;
  495.                             }
  496.                         }
  497.                     }                  
  498.                 }          
  499.             }  
  500.         }
  501.         return b;
  502.     },
  503.     byExclusivepairRow: function(t){
  504.         let b=0;
  505.         for(let ki=0;ki<9;ki++){
  506.             fi:
  507.             for(let i=0;i<9;i++){
  508.                 while(i<9 && !(t[ki][i].v==0 && t[ki][i].p.length==2)) i++;
  509.                 if( i==9 ) break;
  510.                 for(let j=i+1;j<9;j++){
  511.                     while(j<9 && !(t[ki][j].v==0 && t[ki][j].p.length==2)) j++;
  512.                     if( j==9 ) break fi;
  513.                     if( t[ki][i].p[0]==t[ki][j].p[0]
  514.                         && t[ki][i].p[1]==t[ki][j].p[1] ){
  515.                         for(let k=0;k<9;k++){
  516.                             if( k==i || k==j || t[ki][k].v!=0 ) continue;
  517.                             t[ki][k].remove(t[ki][i].p[0]);
  518.                             t[ki][k].remove(t[ki][i].p[1]);
  519.                             if( t[ki][k].p.length==1 ){
  520.                                 t[ki][k].v=t[ki][k].p[0];
  521.                                 // sudoku.eliminate(t, t[ki][k].v, ki, k);
  522.                                 // console.log('exclusive pair column: row '+(ki+1)+', col '+(k+1)
  523.                                 //  +' val='+(t[ki][k].v))
  524.                                 if( !sudoku.eliminate(t, t[ki][k].v, ki, k) ) // mean that the grid is unsolvable
  525.                                     return -1;
  526.                                 b++;
  527.                             }
  528.                         }
  529.                     }                  
  530.                 }          
  531.             }  
  532.         }
  533.         return b;
  534.     },
  535.  
  536.     byExclusivetripletRegion: function(t){
  537.         let b=0;
  538.         for(let kc=0;kc<9;kc++){
  539.             let ci=Math.floor(kc/3), cj=kc%3;
  540.             fi:
  541.             for(let i=0;i<9;i++){
  542.                 while(i<9 &&
  543.                     !(t[3*ci+Math.floor(i/3)][3*cj+i%3].v==0 &&
  544.                       t[3*ci+Math.floor(i/3)][3*cj+i%3].p.length==3)) i++;
  545.                 let rri = Math.floor(i/3), rci = i%3;
  546.  
  547.                 if( i==9 ) break;
  548.                 for(let j=i+1;j<9;j++){
  549.                     while(j<9 &&
  550.                         !(t[3*ci+Math.floor(j/3)][3*cj+j%3].v==0 &&
  551.                           t[3*ci+Math.floor(j/3)][3*cj+j%3].p.length==3)) j++;
  552.                     let rrj = Math.floor(j/3), rcj = j%3;
  553.  
  554.                     if( j==9 ) break fi;
  555.                     for(let k=j+1;k<9;k++){
  556.                         while(k<9 &&
  557.                             !(t[3*ci+Math.floor(k/3)][3*cj+k%3].v==0 &&
  558.                               t[3*ci+Math.floor(k/3)][3*cj+k%3].p.length==3)) k++;
  559.                         let rrk = Math.floor(k/3), rck = k%3;
  560.  
  561.                         if( k==9 ) break fi;
  562.  
  563.                         if( t[3*ci+rri][3*cj+rci].p[0]==t[3*ci+rrj][3*cj+rcj].p[0] &&
  564.                             t[3*ci+rri][3*cj+rci].p[0]==t[3*ci+rrk][3*cj+rck].p[0] &&
  565.                             t[3*ci+rri][3*cj+rci].p[1]==t[3*ci+rrj][3*cj+rcj].p[1] &&
  566.                             t[3*ci+rri][3*cj+rci].p[1]==t[3*ci+rrk][3*cj+rck].p[1] &&
  567.                             t[3*ci+rri][3*cj+rci].p[2]==t[3*ci+rrj][3*cj+rcj].p[2] &&
  568.                             t[3*ci+rri][3*cj+rci].p[2]==t[3*ci+rrk][3*cj+rck].p[2] ){
  569.  
  570.                             for(let l=0;l<9;l++){
  571.                                 let rrl = Math.floor(l/3), rcl = l%3;
  572.                                 if( l==i || l==j || l==k || t[l][kj].v!=0 ) continue;
  573.                                 t[3*ci+rrl][3*cj+rcl].remove(t[3*ci+rri][3*cj+rci].p[0]);
  574.                                 t[3*ci+rrl][3*cj+rcl].remove(t[3*ci+rri][3*cj+rci].p[1]);
  575.                                 t[3*ci+rrl][3*cj+rcl].remove(t[3*ci+rri][3*cj+rci].p[2]);
  576.                                 if( t[3*ci+rrl][3*cj+rcl].p.length==1 ){
  577.                                     t[3*ci+rrl][3*cj+rcl].v=t[3*ci+rrl][3*cj+rcl].p[0];                                
  578.                                     // console.log('exclusive triplet region: row '+(3*ci+rrl+1)+', col '+(3*cj+rcl+1)
  579.                                     // +' val='+(t[3*ci+rrl][3*cj+rcl].v));
  580.                                     if( !sudoku.eliminate(t, t[3*ci+rrl][3*cj+rcl].v, 3*ci+rrl, 3*cj+rcl) ) // mean that the grid is unsolvable
  581.                                         return -1;
  582.                                     b++;
  583.                                 }
  584.                             }
  585.                         }
  586.  
  587.                     }                                  
  588.                 }          
  589.             }  
  590.         }
  591.         return b;
  592.     },
  593.     byExclusivetripletColumn: function(t){
  594.         let b=0;
  595.         for(let kj=0;kj<9;kj++){
  596.             fi:
  597.             for(let i=0;i<9;i++){
  598.                 while(i<9 && !(t[i][kj].v==0 && t[i][kj].p.length==3)) i++;
  599.                 if( i==9 ) break;
  600.                 for(let j=i+1;j<9;j++){
  601.                     while(j<9 && !(t[j][kj].v==0 && t[j][kj].p.length==3)) j++;
  602.                     if( j==9 ) break fi;
  603.                     for(let k=j+1;k<9;k++){
  604.                         while(k<9 && !(t[k][kj].v==0 && t[k][kj].p.length==3)) k++;
  605.                         if( k==9 ) break fi;
  606.  
  607.                         if( t[i][kj].p[0]==t[j][kj].p[0] && t[i][kj].p[0]==t[k][kj].p[0]
  608.                         && t[i][kj].p[1]==t[j][kj].p[1] && t[i][kj].p[1]==t[k][kj].p[1]
  609.                         && t[i][kj].p[2]==t[j][kj].p[2] && t[i][kj].p[2]==t[k][kj].p[2] ){
  610.  
  611.                             for(let l=0;l<9;l++){
  612.                                 if( l==i || l==j || l==k || t[l][kj].v!=0 ) continue;
  613.                                 t[l][kj].remove(t[i][kj].p[0]);
  614.                                 t[l][kj].remove(t[i][kj].p[1]);
  615.                                 t[l][kj].remove(t[i][kj].p[2]);
  616.                                 if( t[l][kj].p.length==1 ){
  617.                                     t[l][kj].v=t[l][kj].p[0];
  618.                                     sudoku.eliminate(t, t[l][kj].v, l, kj);
  619.                                     // console.log('exclusive triplet column: row '+(l+1)+', col '+(kj+1)
  620.                                     // +' val='+(t[l][kj].v))
  621.                                     if( !sudoku.eliminate(t, t[l][kj].v, l, kj) ) // mean that the grid is unsolvable
  622.                                         return -1;
  623.                                     b++;
  624.                                 }
  625.                             }
  626.                         }
  627.  
  628.                     }                                  
  629.                 }          
  630.             }  
  631.         }
  632.         return b;
  633.     },
  634.     byExclusivetripletRow: function(t){
  635.         let b=0;
  636.         for(let ki=0;ki<9;ki++){
  637.             fi:
  638.             for(let i=0;i<9;i++){
  639.                 while(i<9 && !(t[ki][i].v==0 && t[ki][i].p.length==3)) i++;
  640.                 if( i==9 ) break;
  641.                 for(let j=i+1;j<9;j++){
  642.                     while(j<9 && !(t[ki][j].v==0 && t[ki][j].p.length==3)) j++;
  643.                     if( j==9 ) break fi;
  644.                     for(let k=j+1;k<9;k++){
  645.                         while(k<9 && !(t[ki][k].v==0 && t[ki][k].p.length==3)) k++;
  646.                         if( k==9 ) break fi;
  647.  
  648.                         if( t[ki][i].p[0]==t[ki][j].p[0] && t[ki][i].p[0]==t[ki][k].p[0]
  649.                         && t[ki][i].p[1]==t[ki][j].p[1] && t[ki][i].p[1]==t[ki][k].p[1]
  650.                         && t[ki][i].p[2]==t[ki][j].p[2] && t[ki][i].p[2]==t[ki][k].p[2] ){
  651.  
  652.                             for(let l=0;l<9;l++){
  653.                                 if( l==i || l==j || l==k || t[ki][l].v!=0 ) continue;
  654.                                 t[ki][l].remove(t[ki][i].p[0]);
  655.                                 t[ki][l].remove(t[ki][i].p[1]);
  656.                                 t[ki][l].remove(t[ki][i].p[2]);
  657.                                 if( t[ki][l].p.length==1 ){
  658.                                     t[ki][l].v=t[ki][l].p[0];
  659.                                     sudoku.eliminate(t, t[ki][l].v, ki, l);
  660.                                     // console.log('exclusive triplet row: row '+(ki+1)+', col '+(l+1)
  661.                                     // +' val='+(t[ki][l].v))
  662.                                     if( !sudoku.eliminate(t, t[ki][l].v, ki, l) ) // mean that the grid is unsolvable
  663.                                         return -1;
  664.                                     b++;
  665.                                 }
  666.                             }
  667.                         }
  668.  
  669.                     }                                  
  670.                 }          
  671.             }
  672.         }
  673.         return b;
  674.     },
  675.  
  676.     // Multiple choice is the same as backtracking
  677.     eval: function(t, sol){
  678.        
  679.         let score1, score2, score3;
  680.         let ic={n:0};let ie={n:0};let iep={n:0};let iet={n:0};let imc={n:0};
  681.         let sc={n:0};
  682.         let mnbc = 9;
  683.         for(let i=0;i<9;i++){
  684.             // let tt=[];
  685.             let nbc=0;
  686.             for(let j=0;j<9;j++){
  687.                 if( t[i][j].v==0 ){
  688.                     t[i][j].p=[1,2,3,4,5,6,7,8,9];
  689.                 }else{
  690.                     t[i][j].p=[];sc.n++;nbc++;
  691.                 }
  692.             }
  693.             if( mnbc>nbc )
  694.                 mnbc = nbc;
  695.         }
  696.         // score 1
  697.         if( sc.n>=50 )
  698.             score1=1;
  699.         else if( sc.n<=49 && sc.n>=36 )
  700.             score1=2;
  701.         else if( sc.n<=35 && sc.n>=32 )
  702.             score1=3;
  703.         else if( sc.n<=31 && sc.n>=28)
  704.             score1=4;
  705.         else if( sc.n<=27 && sc.n>=22)
  706.             score1=5;
  707.  
  708.         // score 2
  709.         if( mnbc>=5 )
  710.             score2=1;
  711.         else if( mnbc==4 )
  712.             score2=2;
  713.         else if( mnbc==3 )
  714.             score2=3;
  715.         else if( mnbc==2 )
  716.             score2=4;
  717.         else// if( mnbc==1 || mnbc==0 )
  718.             score2=5;
  719.  
  720.         console.log(" start sc.n",sc.n)
  721.  
  722.         for(let i=0;i<9;i++){
  723.             for(let j=0;j<9;j++){
  724.                 if( t[i][j].v!=0 ){
  725.                     sudoku.eliminate(t, t[i][j].v, i, j);
  726.                 }
  727.             }
  728.         }
  729.         console.log('start solving...');
  730.         sudoku.print(t);
  731.         let st = this._solve(sudoku.copy(t),0,0,0, ic,ie,iep,iet,imc, sc);
  732.         if( st!=null ){
  733.             sudoku.print(st);
  734.             for(let i=0;i<9;i++){
  735.                 let tt = [];
  736.                 for(let j=0;j<9;j++){
  737.                     tt.push(st[i][j]);
  738.                 }
  739.                 sol.push(tt);
  740.             }
  741.         }else{
  742.  
  743.         }
  744.  
  745.         // score 2
  746.         if( imc.n>0 )
  747.             score3=5;
  748.         else if( iet.n>0 )
  749.             score3=4;
  750.         else if( iep.n>0 )
  751.             score3=3;
  752.         else if( ie.n>0 )
  753.             score3=2;
  754.         else if( ic.n>0 )
  755.             score3=1;
  756.  
  757.         console.log('inclusion count: ', ic.n);
  758.         console.log('exclusion count: ', ie.n);
  759.         console.log('exclusive pair count: ', iep.n);
  760.         console.log('exclusive triplet count: ', iet.n);
  761.         console.log('multiple choice count: ', imc.n);
  762.  
  763.         let nl = Math.round((score1+score2+score3)/3), level="?";
  764.         switch(nl){
  765.             case 1:
  766.             level = "Extremely Easy";
  767.             break;
  768.             case 2:
  769.             level = "Easy";
  770.             break;
  771.             case 3:
  772.             level = "Medium";
  773.             break;
  774.             case 4:
  775.             level = "Difficult";
  776.             break;
  777.             case 5:
  778.             level = "Evil";
  779.             break;
  780.         }
  781.  
  782.         console.log('scores: ', score1, score2, score3);
  783.         console.log('nl: ', nl);
  784.         console.log('level: ', level);
  785.         return level;
  786.     },
  787.     _solve: function(t,nbr,i,j, ic,ie,iep,iet,imc, sc){
  788.         // if(sts>100)
  789.         //  return null;
  790.         // sts++;
  791.         if( nbr!=0 )
  792.             if( !sudoku.eliminate(t, nbr, i, j) )
  793.                 return null;
  794.        
  795.         if(sc.n==82) return t;
  796.         let n;
  797.         while( true ){
  798.             // if(sts>100)
  799.             //  return null;
  800.             // sts++;
  801.             n=this.byInclusion(t);
  802.             // console.log('inclusion n='+n);
  803.             if( n>0 ){
  804.                 // sudoku.print(t);
  805.                 ic.n+=n;
  806.                 sc.n+=n;
  807.                 // console.log(sc.n)
  808.                 if(sc.n==81) return t;
  809.                 continue;
  810.             }
  811.             else if(n==-1)
  812.                 return null;
  813.  
  814.             n=this.byExclusionColumn(t);
  815.             // console.log('exclusion n='+n);
  816.             if( n>0 ){
  817.                 // sudoku.print(t);
  818.                 ie.n+=n;
  819.                 sc.n+=n;
  820.                 // console.log(sc.n)
  821.                 if(sc.n==81) return t;
  822.                 continue;
  823.             }
  824.             else if(n==-1)
  825.                 return null;
  826.             n=this.byExclusionRegion(t);
  827.             // console.log('exclusion n='+n);
  828.             if( n>0 ){
  829.                 // sudoku.print(t);
  830.                 ie.n+=n;
  831.                 sc.n+=n;
  832.                 // console.log(sc.n)
  833.                 if(sc.n==81) return t;
  834.                 continue;
  835.             }
  836.             else if(n==-1)
  837.                 return null;
  838.             n=this.byExclusionRow(t);
  839.             // console.log('exclusion n='+n);
  840.             if( n>0 ){
  841.                 // sudoku.print(t);
  842.                 ie.n+=n;
  843.                 sc.n+=n;
  844.                 // console.log(sc.n)
  845.                 if(sc.n==81) return t;
  846.                 continue;
  847.             }
  848.             else if(n==-1)
  849.                 return null;
  850.            
  851.             n=this.byExclusivepairColumn(t);
  852.             // console.log('exclusion pair n='+n);
  853.             if( n>0 ){
  854.                 // sudoku.print(t);
  855.                 iep.n+=n;
  856.                 sc.n+=n;
  857.                 // console.log(sc.n)
  858.                 if(sc.n==81) return t;
  859.                 continue;
  860.             }
  861.             else if(n==-1)
  862.                 return null;
  863.             n=this.byExclusivepairRegion(t);
  864.             // console.log('exclusion pair n='+n);
  865.             if( n>0 ){
  866.                 // sudoku.print(t);
  867.                 iep.n+=n;
  868.                 sc.n+=n;
  869.                 // console.log(sc.n)
  870.                 if(sc.n==81) return t;
  871.                 continue;
  872.             }
  873.             else if(n==-1)
  874.                 return null;
  875.             n=this.byExclusivepairRow(t);
  876.             // console.log('exclusion pair n='+n);
  877.             if( n>0 ){
  878.                 // sudoku.print(t);
  879.                 iep.n+=n;
  880.                 sc.n+=n;
  881.                 // console.log(sc.n)
  882.                 if(sc.n==81) return t;
  883.                 continue;
  884.             }
  885.             else if(n==-1)
  886.                 return null;
  887.            
  888.             n=this.byExclusivetripletColumn(t);
  889.             // console.log('exclusion triplet n='+n);
  890.             if( n>0 ){
  891.                 // sudoku.print(t);
  892.                 iet.n+=n;
  893.                 sc.n+=n;
  894.                 // console.log(sc.n)
  895.                 if(sc.n==81) return t;
  896.                 continue;
  897.             }
  898.             else if(n==-1)
  899.                 return null;
  900.             n=this.byExclusivetripletRegion(t);
  901.             // console.log('exclusion triplet n='+n);
  902.             if( n>0 ){
  903.                 // sudoku.print(t);
  904.                 iet.n+=n;
  905.                 sc.n+=n;
  906.                 // console.log(sc.n)
  907.                 if(sc.n==81) return t;
  908.                 continue;
  909.             }
  910.             else if(n==-1)
  911.                 return null;
  912.             n=this.byExclusivetripletRow(t);
  913.             // console.log('exclusion triplet n='+n);
  914.             if( n>0 ){
  915.                 // sudoku.print(t);
  916.                 iet.n+=n;
  917.                 sc.n+=n;
  918.                 // console.log(sc.n)
  919.                 if(sc.n==81) return t;
  920.                 continue;
  921.             }
  922.             else if(n==-1)
  923.                 return null;           
  924.  
  925.             break;
  926.         }
  927.  
  928.         let ni=i, nj=j;
  929.         while( ni<9 && t[ni][nj].v!=0 ){
  930.             if(nj==8){
  931.                 ni++;
  932.                 nj=0;
  933.             }else{ nj++; }
  934.         }
  935.  
  936.         if( ni==9 )
  937.             return t;
  938.        
  939.         else{          
  940.             while( t[ni][nj].p.length>0 ){
  941.                 let nb = t[ni][nj].p[0];
  942.                 t[ni][nj].p.shift();
  943.                 t[ni][nj].v = nb;
  944.                 imc.n++;
  945.                 sc.n++;
  946.                 // console.log('multiple choice: row '+(ni+1)+', col '+(nj+1)
  947.                                     // +' val='+(nb))
  948.  
  949.                 // console.log("sc.n",sc.n)
  950.                 // sudoku.eliminate(t, nb, ni, nj);
  951.                 let nic={n:ic.n}, nie={n:ie.n}, niep={n:iep.n}, niet={n:iet.n}, nimc={n:imc.n};
  952.                 let nsc = {n:sc.n};
  953.                 let s = this._solve(sudoku.copy(t),nb,ni,nj, nic,nie,niep,niet,nimc, nsc);
  954.                 if( s!=null ){
  955.                     // console.log('s!=null')
  956.                     ic.n = nic.n;
  957.                     ie.n = nie.n;
  958.                     iep.n = niep.n;
  959.                     iet.n = niet.n;
  960.                     imc.n = nimc.n;
  961.                     sc.n = nsc.n;
  962.                     return s;
  963.                 }
  964.                 // console.log('multiple choice remove: row '+(ni+1)+', col '+(nj+1)
  965.                                      // +' val='+(t[ni][nj].v))
  966.                 imc.n--;
  967.                 sc.n--;
  968.                 // console.log("sc.n",sc.n)
  969.             }      
  970.             // no solution found
  971.             return null;
  972.         }
  973.  
  974.     }
  975.  
  976. }
  977.  
  978. let enter = document.getElementById('enter');
  979. let evaluate = document.getElementById('evaluate');
  980. let play = document.getElementById('play');
  981.  
  982. let generate = document.getElementById('generate');
  983. let check = document.getElementById('check');
  984. let clear = document.getElementById('clear');
  985. let note = document.getElementById('note');
  986.  
  987. enter.addEventListener('click', function(event){
  988.     sudoku_UI.enter();
  989. });
  990. evaluate.addEventListener('click', function(event){
  991.     sudoku_UI.evaluate();
  992. });
  993. play.addEventListener('click', function(event){
  994.     sudoku_UI.play();
  995. });
  996. generate.addEventListener('click', function(event){
  997.     console.log('click');
  998.     try{
  999.         sudoku_UI.gen();       
  1000.     }
  1001.     catch(e){
  1002.         console.log(e);
  1003.     }
  1004.     let sto = setTimeout(function(){
  1005.         // console.log(sudoku_UI.sol)
  1006.         while( sudoku_UI.sol==undefined ){
  1007.             try{
  1008.                 sudoku_UI.gen();       
  1009.             }
  1010.             catch(e){
  1011.                 console.log(e);
  1012.             }
  1013.         }
  1014.         clearTimeout(sto);
  1015.     }, 100);
  1016.    
  1017. });
  1018. check.addEventListener('click', function(event){
  1019.     sudoku_UI.check();
  1020. });
  1021. clear.addEventListener('click', function(event){
  1022.     sudoku_UI.clear();
  1023. });
  1024.  
  1025. let sudoku_UI = {
  1026.     init: function(){
  1027.         let rs = document.getElementsByClassName('row');
  1028.         for(let i=0;i<rs.length;i++){
  1029.             this.grid_UI.push( rs[i].getElementsByClassName('col') );
  1030.         }
  1031.     },
  1032.     enter: function(){
  1033.         note.textContent = "";
  1034.         this.sol = null;
  1035.         for(let i=0;i<9;i++){
  1036.             for(let j=0;j<9;j++){              
  1037.                 this.grid_UI[i][j].innerHTML = "<input class='inp' maxlength=1>";              
  1038.             }
  1039.         }
  1040.         let inps = document.getElementsByClassName('inp');
  1041.         for(let i=0;i<inps.length;i++){
  1042.             inps[i].addEventListener('input', function(event){
  1043.                 // console.log(event)
  1044.                 if( !this.value.match(/[1-9]/g) ){
  1045.                     this.value = "";
  1046.                 }
  1047.             });
  1048.         }
  1049.         this.grid= [];
  1050.     },
  1051.     evaluate: function(){
  1052.         note.textContent = "";
  1053.         let tg = this.grid;
  1054.         this.grid=[];
  1055.         for(let i=0;i<9;i++){
  1056.             let t=[];
  1057.             for(let j=0;j<9;j++){
  1058.                 let inp = this.grid_UI[i][j].getElementsByClassName('inp');
  1059.                 if(inp.length==0){
  1060.                     //exception                
  1061.                     if(tg==null)
  1062.                         return null;
  1063.                     else
  1064.                         t.push(sudoku_cell_copy(parseInt(this.grid_UI[i][j].textContent),  []));
  1065.                 }else{
  1066.                     let n = inp[0].value;
  1067.                     if( n!="" ){
  1068.                         this.grid_UI[i][j].innerHTML = n;
  1069.                         t.push(sudoku_cell_copy(n, []));
  1070.                     }else{
  1071.                         t.push(sudoku_cell_copy(0, [1,2,3,4,5,6,7,8,9]));
  1072.                     }
  1073.                 }
  1074.             }
  1075.             this.grid.push(t);
  1076.         }
  1077.         // sudoku.print(this.grid);
  1078.         this.sol = [];
  1079.         let level = sudoku_Eval.eval(this.grid, this.sol);
  1080.         note.className = "";
  1081.         if( this.sol==[] )
  1082.             note.textContent = "This grid doesn't accept a solution";
  1083.         else       
  1084.             note.textContent = "This grid is "+level;
  1085.     },
  1086.     play: function(){
  1087.         note.textContent = "";
  1088.         this.grid=[];
  1089.         for(let i=0;i<9;i++){
  1090.             let t=[];
  1091.             for(let j=0;j<9;j++){
  1092.                 let inp = this.grid_UI[i][j].getElementsByClassName('inp');
  1093.                 if(inp.length==0){
  1094.                     //exception
  1095.                     note.className = "";
  1096.                     note.textContent = "You should enter grid to play it.";
  1097.                     return null;
  1098.                 }else{
  1099.                     let n = inp[0].value;
  1100.                     if( n!="" ){
  1101.                         this.grid_UI[i][j].innerHTML = n;
  1102.                         t.push(sudoku_cell_copy(n,[]));
  1103.                     }else{
  1104.                         t.push(sudoku_cell_copy(0,  [1,2,3,4,5,6,7,8,9]));
  1105.                     }
  1106.                 }
  1107.             }
  1108.             this.grid.push(t);
  1109.         }
  1110.         this.sol = [];
  1111.         let level = sudoku_Eval.eval(this.grid, this.sol);
  1112.         note.className = "";
  1113.         if( this.sol==[] ){        
  1114.             note.textContent = "This grid doesn't accept a solution";
  1115.         }else      
  1116.             note.textContent = "This grid is "+level;
  1117.     },
  1118.     grid_UI: [],
  1119.     grid: null,
  1120.     sol: null,
  1121.     gen: function(){
  1122.         // let s, r;
  1123.         note.className = "";
  1124.         note.textContent = "Generating... (it may take long time)";
  1125.         let tab = sudoku.rand();
  1126.         // console.log(tab)
  1127.         this.grid = tab[0];
  1128.         this.sol = tab[1];
  1129.         if( this.sol==undefined )
  1130.             return null;
  1131.         // console.log(this.sol);
  1132.         // sudoku.print(this.sol);
  1133.         note.textContent = "";
  1134.         for(let i=0;i<this.grid.length;i++){
  1135.             for(let j=0;j<this.grid[i].length;j++){
  1136.                 if( this.grid[i][j].v==0 ){
  1137.                     this.grid_UI[i][j].innerHTML = "<input class='inp' maxlength=1>";
  1138.                 }else{
  1139.                     this.grid_UI[i][j].textContent = this.grid[i][j].v;
  1140.                 }
  1141.             }
  1142.         }
  1143.         let inps = document.getElementsByClassName('inp');
  1144.         for(let i=0;i<inps.length;i++){
  1145.             inps[i].addEventListener('input', function(event){
  1146.                 // console.log(event)
  1147.                 if( !this.value.match(/[1-9]/g) ){
  1148.                     this.value = "";
  1149.                 }
  1150.             });
  1151.         }
  1152.  
  1153.     }, 
  1154.     check: function(){
  1155.         if( this.grid==null )
  1156.             return null;
  1157.         else{
  1158.             note.className = "";
  1159.             note.textContent = "No grid is entered or generated.";
  1160.         }
  1161.         let emp = 0;
  1162.         for(let i=0;i<this.grid.length;i++){
  1163.             for(let j=0;j<this.grid[i].length;j++){
  1164.                 if( this.grid[i][j].v==0 ){
  1165.                     let inp = this.grid_UI[i][j].getElementsByClassName('inp');
  1166.                     // console.log(inp)
  1167.                     if( inp.length==0 ){
  1168.                         // exception                       
  1169.                         return null;
  1170.                     }
  1171.                     if( inp[0].value!="" ){
  1172.                         if( inp[0].value!=this.sol[i][j].v ){
  1173.                             note.className = "not-ok-note";
  1174.                             note.textContent = "You have made some mistakes.";
  1175.                             inp[0].className = "inp not-ok-try";
  1176.                             return null;
  1177.                         }
  1178.                         else{
  1179.                             inp[0].className = "inp";
  1180.                         }
  1181.                     }
  1182.                     else/* if( inp[0].value=="" )*/{
  1183.                         inp[0].className = "inp";
  1184.                         emp++;
  1185.                     }
  1186.                 }/*else{
  1187.                     this.grid_UI[i][j].textContent = this.grid[i][j].v;
  1188.                 }*/
  1189.             }
  1190.         }
  1191.         note.className = "ok-note";
  1192.         if( emp>0 ){
  1193.             note.textContent = "Everything is OK, you still have "+emp+" to go!";
  1194.         }else{
  1195.             note.textContent = "Sudoku solved. Congratulations!";
  1196.         }
  1197.     },
  1198.     clear: function(){
  1199.         if( this.grid==null )
  1200.             return null;
  1201.         for(let i=0;i<this.grid.length;i++){
  1202.             for(let j=0;j<this.grid[i].length;j++){
  1203.                 if( this.grid[i][j].v==0 ){
  1204.                     let inp = this.grid_UI[i][j].getElementsByClassName('inp');
  1205.                     // console.log(inp)
  1206.                     if( inp.length==0 ){
  1207.                         // exception                       
  1208.                         return null;
  1209.                     }
  1210.                     inp[0].value="";
  1211.                     inp[0].className = "inp";              
  1212.                 }
  1213.             }
  1214.         }
  1215.     }
  1216. }
  1217.  
  1218. sudoku_UI.init();
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!