用JavaScript写生成数独算法时浏览器变慢

Question

我的想法是这样的：先定义一个数组sudoku9,然后通过for循环依次把数字1填入到每个小九宫格中，然后再把数字2填入到每个小九宫格中，以此类推。小九宫格的编号从0~8，数字在每个小九宫格的位置（position）可以是0~8。请问有什么可以改进的地方

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);//把数字填入到某个小九宫格中
      }
       }
   }

//根据position和n计算出在数组sudoku中的位置,并通过数组coor返回坐标
   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("算出来的coor=("+coor+")");
    return coor;
   }

//随机产生在[min,max]之间的随机数
   function RandomNumBoth(Min,Max){
      var Range = Max - Min;
      var Rand = Math.random();
      var num = Min + Math.round(Rand * Range); //四舍五入
      return num;
   }

//将数字m填入到第n个小九宫格中
   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;
     
   } 
//判断在数组sudoku中填入的数字num所在的列上是否有相同的数字
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;
   }
//判断在数组sudoku中填入的数字num所在的行上是否有相同的数字
   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;
          }
        }
    }
   }
//判断在要填入数字的位置上是否已经有其他数字
   function judgeElse(n,x,y){
    if(sudoku[x][y]!=0){
      return false;
    }
    return true;
   }

Answer 1

fillNumberInOneArray 将数字 m 填入到 第 n 个小宫格中，为什么要随机选一个位置放呢？后期快放满的时候，冲突的概率越来越大，根本不收敛的呀。你都能 judgeElse 了，为什么不能在生成 random 坐标之前就排除一下已经放了数字的格子呢？这一步浪费的效率不计其数，甚至导致了算法有极大可能无法停止。9个格子有一个空位，用random去撞这个空位置，那有 8/9 的概率撞不到，一直死循环。

已经被占的格子提前排除，这是其一。其二，假设小9宫格都剩下3个格子，需要放 7 了对吧，随机一下，得到一个空格子，检查了一下横竖，发现不能放，接下来你需要标记这个格子不可用，否则下次再 random 还有 1/3 的概率打中这个不可用的格子，导致算法不收敛。犯过的错，为什么下次还要继续犯？下次你就该排除掉它，在剩下的选项里挑，否则这次试错就没有意义啦，那这就不是算法，完全就是在碰运气。

function calculateCoordinate(position,n) 也可以精简一下，没必要那么多 switch-case：

function calculateCoordinate(position, n) {
  // 先计算九宫格是几排几列的九宫格, 我们把数独看成是 3*3 的9个9宫格
  var nx = n % 3;
  var ny = Math.floor(n / 3); 

  var px = position % 3;
  var py = Math.floor(position / 3);
  // 同样的套路处理小9宫格内的坐标，
  
  // 转换一下坐标系
  var returnX = px + nx * 3; 
  var returnY = py + ny * 3;
  return [returnY, returnX];
}