在线观看不卡亚洲电影_亚洲妓女99综合网_91青青青亚洲娱乐在线观看_日韩无码高清综合久久

鍍金池/ 問(wèn)答/人工智能  數(shù)據(jù)分析&挖掘  HTML/ 用JavaScript寫(xiě)生成數(shù)獨(dú)算法時(shí)瀏覽器變慢

用JavaScript寫(xiě)生成數(shù)獨(dú)算法時(shí)瀏覽器變慢

我的想法是這樣的:先定義一個(gè)數(shù)組sudoku9,然后通過(guò)for循環(huán)依次把數(shù)字1填入到每個(gè)小九宮格中,然后再把數(shù)字2填入到每個(gè)小九宮格中,以此類推。小九宮格的編號(hào)從0~8,數(shù)字在每個(gè)小九宮格的位置(position)可以是0~8。請(qǐng)問(wèn)有什么可以改進(jìn)的地方

var sudoku=[
     [0,0,0,0,0,0,0,0,0],
     [0,0,0,0,0,0,0,0,0],
     [0,0,0,0,0,0,0,0,0],
     [0,0,0,0,0,0,0,0,0],
     [0,0,0,0,0,0,0,0,0],
     [0,0,0,0,0,0,0,0,0],
     [0,0,0,0,0,0,0,0,0],
     [0,0,0,0,0,0,0,0,0],
     [0,0,0,0,0,0,0,0,0],
  ];

function generateSudoku(){
    for(var i=1;i<10;i++){
      for(var j=0;j<9;j++){
        fillNumberInOneArray(i,j);//把數(shù)字填入到某個(gè)小九宮格中
      }
       }
   }

//根據(jù)position和n計(jì)算出在數(shù)組sudoku中的位置,并通過(guò)數(shù)組coor返回坐標(biāo)
   function calculateCoordinate(position,n){
    var i=0,j=0;
    var coor=[0,0]
      switch(position){
      case 0:{
         i=(n%3)*3;
         j=parseInt(n/3)*3;
        break;
      }
      case 1:{
         i=(n%3)*3+1;
         j=parseInt(n/3)*3;
        break;
      }
      case 2:{
         i=(n%3)*3+2;
         j=parseInt(n/3)*3;
        break;
      }
      case 3:{
         i=(n%3)*3;
         j=parseInt(n/3)*3+1;
        break;
      }
      case 4:{
         i=(n%3)*3+1;
         j=parseInt(n/3)*3+1;
        break;
      }
      case 5:{
         i=(n%3)*3+2;
         j=parseInt(n/3)*3+1;
        break;
      }
      case 6:{
        i=(n%3)*3;
        j=parseInt(n/3)*3+2;
        break;
      }
      case 7:{
         i=(n%3)*3+1;
         j=parseInt(n/3)*3+2;
        break;
      }
      case 8:{
         i=(n%3)*3+2;
         j=parseInt(n/3)*3+2;
        break;
      }
      
    }
    coor=[j,i];
    //console.log("算出來(lái)的coor=("+coor+")");
    return coor;
   }

//隨機(jī)產(chǎn)生在[min,max]之間的隨機(jī)數(shù)
   function RandomNumBoth(Min,Max){
      var Range = Max - Min;
      var Rand = Math.random();
      var num = Min + Math.round(Rand * Range); //四舍五入
      return num;
   }

//將數(shù)字m填入到第n個(gè)小九宮格中
   function fillNumberInOneArray(m,n){
      do{
        var position=RandomNumBoth(0,8);
      var coor=calculateCoordinate(position,n);
    }while(!judgeElse(n,coor[0],coor[1])||!lockRow(m,n,coor[1])||!lockColumn(m,n,coor[0]))
     sudoku[coor[0]][coor[1]]=m;
     
   } 
//判斷在數(shù)組sudoku中填入的數(shù)字num所在的列上是否有相同的數(shù)字
function lockRow(num,n,y){
    var ii=parseInt(n/3);
    if(ii==1){
      for(var i=0;i<3;i++){
          if(sudoku[i][y]==num){
            return false;
          }
        }
      }else if(ii==2){
        for(var i=0;i<6;i++){
          if(sudoku[i][y]==num){
            return false;
          }
        }
      }
      return true;
   }
//判斷在數(shù)組sudoku中填入的數(shù)字num所在的行上是否有相同的數(shù)字
   function lockColumn(num,n,x){
    var jj=n%3;
    if(jj==1){
      for(var j=0;j<3;j++){
          if(sudoku[x][j]==num){
            return false;
          }
        }
    }else if(jj==2){
      for(var j=0;j<6;j++){
          if(sudoku[x][j]==num){
            return false;
          }
        }
    }
   }
//判斷在要填入數(shù)字的位置上是否已經(jīng)有其他數(shù)字
   function judgeElse(n,x,y){
    if(sudoku[x][y]!=0){
      return false;
    }
    return true;
   }
回答
編輯回答
尐飯團(tuán)

fillNumberInOneArray 將數(shù)字 m 填入到 第 n 個(gè)小宮格中,為什么要隨機(jī)選一個(gè)位置放呢?后期快放滿的時(shí)候,沖突的概率越來(lái)越大,根本不收斂的呀。你都能 judgeElse 了,為什么不能在生成 random 坐標(biāo)之前就排除一下已經(jīng)放了數(shù)字的格子呢?這一步浪費(fèi)的效率不計(jì)其數(shù),甚至導(dǎo)致了算法有極大可能無(wú)法停止。9個(gè)格子有一個(gè)空位,用random去撞這個(gè)空位置,那有 8/9 的概率撞不到,一直死循環(huán)。

已經(jīng)被占的格子提前排除,這是其一。其二,假設(shè)小9宮格都剩下3個(gè)格子,需要放 7 了對(duì)吧,隨機(jī)一下,得到一個(gè)空格子,檢查了一下橫豎,發(fā)現(xiàn)不能放,接下來(lái)你需要標(biāo)記這個(gè)格子不可用,否則下次再 random 還有 1/3 的概率打中這個(gè)不可用的格子,導(dǎo)致算法不收斂。犯過(guò)的錯(cuò),為什么下次還要繼續(xù)犯?下次你就該排除掉它,在剩下的選項(xiàng)里挑,否則這次試錯(cuò)就沒(méi)有意義啦,那這就不是算法,完全就是在碰運(yùn)氣。

function calculateCoordinate(position,n) 也可以精簡(jiǎn)一下,沒(méi)必要那么多 switch-case:

function calculateCoordinate(position, n) {
  // 先計(jì)算九宮格是幾排幾列的九宮格, 我們把數(shù)獨(dú)看成是 3*3 的9個(gè)9宮格
  var nx = n % 3;
  var ny = Math.floor(n / 3); 

  var px = position % 3;
  var py = Math.floor(position / 3);
  // 同樣的套路處理小9宮格內(nèi)的坐標(biāo),
  
  // 轉(zhuǎn)換一下坐標(biāo)系
  var returnX = px + nx * 3; 
  var returnY = py + ny * 3;
  return [returnY, returnX];
}
2018年6月29日 02:03