2.1.Backtracking

• 1.Introduction (參考自:)

  • 中文稱作回溯法

  • 運用遞迴依序窮舉各個維度的數值, 製作所有可能的多維度數值, 並且在遞迴途中避免枚舉出不正確的多維度數值

• 2.解析

  • 當num改成字串的"ABC", Recursive tree可以表示如下(圖片來源: http://www.eandbsoftware.org/print-all-permutations-of-a-given-string/)

    

  • Backtracking的架構 (參考自:http://programming-study-notes.blogspot.tw/2014/03/backtracking.html)

      void backtracking()
      {
          if (填完所有空格) {
              輸出解答;
              return;
          }
          for (int i = 1; i <= 9; ++i) {
              if (i符合規則) {
                  將i填入空格;
                  backtracking(); // 遞迴下去填下個空格
                  將i從空格移除;
              }
          }
      }