數(shù)獨(dú)游戲非常流行,其規(guī)則就是1到9數(shù)字填入9*9宮格并要求每一行、每一列、每一個(gè)粗線(小型)宮內(nèi)的數(shù)字不重復(fù),對(duì)此我們來(lái)看一下JavaScript遍歷求解數(shù)獨(dú)問(wèn)題的主要思路小結(jié)

數(shù)獨(dú)規(guī)則
數(shù)獨(dú)游戲，經(jīng)典的為9×9=81個(gè)單元格組成的九宮格，同時(shí)也形成了3×3=9個(gè)小九宮格，要求在81個(gè)小單元格中填入數(shù)字1~9，并且數(shù)字在每行每列及每個(gè)小九宮格中都不能重復(fù)。

數(shù)獨(dú)技巧

直觀法
候選數(shù)法
相關(guān)二十格：一個(gè)數(shù)字只與其所在行列及小九宮格的二十格相關(guān)

我的思路

精心設(shè)計(jì)了有效性判定函數(shù)，最多一次遍歷81個(gè)小單元格就能做出方案的有效性判定。
同理設(shè)計(jì)了相關(guān)20格判定，一次0~9的循環(huán)就完成有效性判定。
用數(shù)組模擬堆棧，為搜索提供回溯信息。
利用對(duì)象具有map性質(zhì)，來(lái)輔助判斷方案的有效性，大大簡(jiǎn)化了算法。

方案設(shè)計(jì)與實(shí)現(xiàn)
只用了一個(gè)二維數(shù)組存儲(chǔ)數(shù)獨(dú)方案，一個(gè)一維數(shù)組作堆棧，一個(gè)布爾變量作回溯標(biāo)識(shí)。

1.變量定義：

var problem = [        //這是書(shū)上提到的難度10.7的題
  [8,0,0,0,0,0,0,0,0],
  [0,0,3,6,0,0,0,0,0],
  [0,7,0,0,9,0,2,0,0],
  [0,5,0,0,0,7,0,0,0],
  [0,0,0,0,4,5,7,0,0],
  [0,0,0,1,0,0,0,3,0],
  [0,0,1,0,0,0,0,6,8],
  [0,0,8,5,0,0,0,1,0],
  [0,9,0,0,0,0,4,0,0]
]
var stack = [],flag = false;

2.方案有效性判定：
充分利用了javascript對(duì)象的哈希特性，為了方便調(diào)試，判定有效時(shí)函數(shù)的返回值為0，無(wú)效時(shí)分三種情況，行沖突、列沖突、小九宮格沖突，分別返回1，2，3。前期判定用了它，后來(lái)增加了相關(guān)二十格判定，在找答案時(shí)這個(gè)函數(shù)就用不上了。

function checkValid(sudo){
  let subSudo = {}            //輔助變量，用來(lái)判定小九宮格是否沖突
  for(let i = 0; i<9; i++){
    let row = {}, col = {}       //輔助變量，用來(lái)判定行、列是否沖突
    for(let j = 0; j<9; j++){
      let cur1 = sudo[i][j], cur2 = sudo[j][i]      //一次內(nèi)循環(huán)同時(shí)完成行列的判定
      if(row[cur1])          //當(dāng)前元素已經(jīng)在行中出現(xiàn)，優(yōu)化掉零的判斷，key為0時(shí)值為0，不需要額外判斷
        return 1;          //返回錯(cuò)誤代碼
      else
        row[cur1] = cur1      //當(dāng)前元素未在行中出現(xiàn)，存入輔助變量中  
      if(col[cur2])          //列的判定與行類(lèi)似，優(yōu)化掉零的判斷，key為0時(shí)值為0，不需要額外判斷
        return 2;
      else
        col[cur2] = cur2;
      let key = Math.floor(i/3)+'-'+Math.floor(j/3)    //為不同的小九宮格生成不同的key
      if(subSudo[key]){         //小九宮格中已經(jīng)有元素，優(yōu)化掉零的判斷，key為0時(shí)值為0，不需要額外判斷
        if(subSudo[key][cur1])    //對(duì)某一個(gè)小九宮格的判定與行類(lèi)似
          return 3
        else
          subSudo[key][cur1] = cur1
      }else{              //這是某小九宮格中的第一個(gè)元素
        subSudo[key] = {}       //為小九宮格新建一個(gè)輔助變量，并將第一個(gè)元素存入其中
        subSudo[key][cur1] = cur1
      }         
    }
  }
  return 0;                //程序能運(yùn)行到這，說(shuō)明方案有效
}

3.相關(guān)二十格判定
原理同整體判定，亮點(diǎn)在小九宮格的定位上。

function check20Grid(sudo,i,j){        
  let row = {}, col = {}, subSudo = {}        //輔助變量
  for(let k = 0; k < 9; k++){
    let cur1 = sudo[i][k], cur2 = sudo[k][j]
    if(cur1){                    //當(dāng)前元素已經(jīng)在行中出現(xiàn)，優(yōu)化掉零的判斷，key為0時(shí)值為0，不需要額外判斷
      if(row[cur1])
        return 1;                //返回錯(cuò)誤代碼
      else
        row[cur1] = cur1            //當(dāng)前元素未在行中出現(xiàn)，存入輔助變量中
    }
    if(cur2){                    //列的判定與行類(lèi)似，優(yōu)化掉零的判斷，key為0時(shí)值為0，不需要額外判斷
      if(col[cur2])
        return 2;
      else
        col[cur2] = cur2;
    }
    //轉(zhuǎn)化循環(huán)變量到小九宮格的坐標(biāo)
    let key = sudo[Math.floor(i/3)*3 + Math.floor(k/3)][Math.floor(j/3)*3+Math.floor(k%3)]
    if(subSudo[key])                //九宮格判定與行類(lèi)似，優(yōu)化掉零的判斷，key為0時(shí)值為0，不需要額外判斷
      return 3
    else
      subSudo[key] = key
  }
  return 0;
}

4.遍歷求解
利用元素狀態(tài)初值為零的元素即為待定的特性，并加上堆棧的輔助，沒(méi)有再開(kāi)辟額外的存儲(chǔ)空間。

function findAnswer(){
  for(let i = 0; i<9; i++){
    for(let j = 0; j<9; ){
      if(problem[i][j] === 0 || flag){       //當(dāng)前位置為待定元素的首次處理或回溯到當(dāng)前位置，兩種情況看似不同，其實(shí)處理相同，自加1即可
        flag = false;
        let k = problem[i][j] + 1;        //搜索向下一個(gè)合法值邁進(jìn)
        while(k<10){               //循環(huán)找到下一個(gè)合法值
          problem[i][j] = k;          //填值
          if(check20Grid(problem,i,j) == 0){  //判定合法，相關(guān)二十格判定
            stack.push([i,j++])        //存儲(chǔ)回溯點(diǎn)，并步進(jìn)
            break;
          }
          k++;
        }
        if(k>9){                 //當(dāng)前位置找不到合法值，回溯
          problem[i][j] = 0;          //回溯前歸零
          let rt = stack.pop();         //堆棧中取回溯信息
          if(!rt)                //無(wú)解判斷，返回0
            return 0;  
          i=rt[0]                //穿越
          j=rt[1]
          flag = true;
        }
      }else{                    //當(dāng)前位置數(shù)字為題目給定
        j++;
      }
    }
  }
  return 1;                      //成功找到一組解
}

您可能感興趣的文章: