作者tkcn (小安)
看板C_and_CPP
標題Re: [問題] 關於這份程式碼 (八皇后)
時間Sat Mar 27 01:14:46 2010
※ 引述《wudidog (嗚啦啦)》之銘言：
: http://www.matrix67.com/blog/archives/266
網站我沒仔細看，因為我覺得跟程式似乎沒啥關係呀 (抓頭)
其實關鍵是在 p := pos and -pos 這行，
換成大家習慣的語法就是 p = pos & -pos
這是一個 low level hacking 的技巧，
pos & -pos 會得到 pos's bit pattern 第一個 1 的位置。
例子 (1)
pos = 0110
-pos = 1010
pos&-pos = 0010
^
例子 (2)
pos = 101000
-pos = 011000
pos&-pos = 001000
^
--------
如果想要再拿下一個位置:
p = pos & -pos; // (a) 算出第一個 1 的位置
pos ^= p; // (b) pos -= p 也可，把 pos 的 "p 位置" 設為 0
重複步驟 a, b 即可。
------
拿到這可以幹嘛?
假設我用一個變數 pos 的 bit pattern 表示可以下子的位置，(只考慮一個 row)
0 代表不能下，1 代表可以下，
那麼我就可以用 pos & -pos 得到我第一個要嘗試下子的位置。
用 backtracking 解 8-queen 需要紀錄 3 個方向不能下子的位置，
分別是垂直線和兩條斜線，
我用 3 個 bit pattern 來表示。
所以在第 1 行的時候 3 個 pattern 分別是:
( 這裡用 0 表示可以下，跟前面的定義相反，
不過可以用 not 輕鬆的轉換，原因後面講。 )
垂直: / 斜線 \ 斜線
00000000 00000000 00000000
只要把這 3 個 pattern 做 or 運算，就會得到我在這個 row 可以下子的位置。
假設我在第一個 row 把 queen 下在第 3 個位置，
那麼 pattern 就會變成:
00000100 00000100 00000100
到了下一個 row 我就把 / 做 shift left, \ 做 shift right (用遞迴傳入)，變成:
00000100 00001000 00000010
同樣再做 or 運算就會得到: 00001110
這就是這個 row 可以下子的 bit pattern 啦!
配合前面的 pos & -pos，這題解起來就很輕鬆了。
(記得要做 not，然後第二次定義的 0, 1 意義相反是因為做 shift 的時候希望補的是 0)
---
表達的很爛，請多包涵 Orz
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.132.160.117
※ 編輯: tkcn 來自: 220.132.160.117 (03/27 01:17)
※ 編輯: tkcn 來自: 220.132.160.117 (03/27 01:21)
→ tkcn:看來看去，其實這題根本沒用到 gray code (ci) 03/27 01:23
※ 編輯: tkcn 來自: 220.132.160.117 (03/27 01:25)
→ netsphere:我看了也覺得沒有用到 M67他可能指是下面那題用graycode 03/27 01:34
→ tkcn:沒錯，分隔線上下完全沒關係 XD 03/27 01:38
推 VictorTom:推一下, 神奇, 就在這裡XD 03/27 01:44
推 walker2009:講解推! 03/27 03:31
推 yauhh:解釋很好呀. 網頁格雷碼那個真看不出想講什麼,程式結構類似? 03/27 05:21
推 wudidog:感謝t大,我也很納悶,因為我有嘗試把gray code用進程式 03/27 07:22
→ wudidog:但速度反而變慢,原以為是實作的問題,沒想到真相只有一個.. 03/27 07:24
推 wudidog:原來是上下文沒關係 XD (昏 03/27 07:26
推 wudidog:倒是真的沒想到可以用pos & -pos這種技巧 03/27 07:30
推 wudidog:再補推一個,講解的真的很詳細! 03/27 07:34
推 tabinoyume:原來有這招 長知識^^ 03/27 17:12