Re: [問題] 關於這份程式碼 (八皇后)
※ 引述《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)
→
03/27 01:23, , 1F
03/27 01:23, 1F
※ 編輯: tkcn 來自: 220.132.160.117 (03/27 01:25)
→
03/27 01:34, , 2F
03/27 01:34, 2F
→
03/27 01:38, , 3F
03/27 01:38, 3F
推
03/27 01:44, , 4F
03/27 01:44, 4F
推
03/27 03:31, , 5F
03/27 03:31, 5F
推
03/27 05:21, , 6F
03/27 05:21, 6F
推
03/27 07:22, , 7F
03/27 07:22, 7F
→
03/27 07:24, , 8F
03/27 07:24, 8F
推
03/27 07:26, , 9F
03/27 07:26, 9F
推
03/27 07:30, , 10F
03/27 07:30, 10F
推
03/27 07:34, , 11F
03/27 07:34, 11F
推
03/27 17:12, , 12F
03/27 17:12, 12F
討論串 (同標題文章)