杭州交通信息网国民党陈荃原型:在n*n棋盘上设置n个后,是其不互相攻击？
来源：百度文库 编辑：杭州交通信息网 时间：2024/05/06 04:41:34
经典是8皇后问题，答案是72。
N皇后问题
N皇后问题要求在NN的棋盘上放置N个皇后，使其不能互相攻击，即任意2个皇后不能处于棋盘上的同一行、同一列或同一斜线上。以下程序用回溯法求出所有满足要求的皇后布局数。其中PLACE用于检测当前位置处的皇后与已放置的皇后是否互相攻击。BACKTRACK实施回溯搜索。
DECLARE SUB BACKTRACK ()
DECLARE SUB PLACE (k!)
REM program nqueen
COMMON SHARED n, ok, answer, x()
DIM x(20)
INPUT "n=", n
answer = 0
FOR i = 1 TO 20
x(i) = 0: NEXT i
CALL BACKTRACK
PRINT " answer is ", answer
END
SUB BACKTRACK
x(1) = 0
k = 1
WHILE [16]
x(k) = x(k) + 1
ok = 0
WHILE (x(k) <= n) AND (ok = 0)
CALL PLACE(k)
IF ok = 0 THEN [17]
WEND
IF x(k) <= n THEN
IF [18] THEN answer = answer + 1 ELSE k = k + 1: x(k) = 0
ELSE [19]
END IF
WEND
END SUB
SUB PLACE (k)
ok = 1
FOR j = 1 TO k - 1
IF (ABS(k - j) = ABS(x(j) - x(k))) OR (x(j) = x(k)) THEN j = k - 1: [20]
NEXT j
END SUB
N皇后问题
N皇后问题要求在NN的棋盘上放置N个皇后，使其不能互相攻击，即任意2个皇后不能处于棋盘上的同一行、同一列或同一斜线上。以下程序用回溯法求出所有满足要求的皇后布局数。其中PLACE用于检测当前位置处的皇后与已放置的皇后是否互相攻击。BACKTRACK实施回溯搜索。
DECLARE SUB BACKTRACK ()
DECLARE SUB PLACE (k!)
REM program nqueen
COMMON SHARED n, ok, answer, x()
DIM x(20)
INPUT "n=", n
answer = 0
FOR i = 1 TO 20
x(i) = 0: NEXT i
CALL BACKTRACK
PRINT " answer is ", answer
END
SUB BACKTRACK
x(1) = 0
k = 1
WHILE [16]
x(k) = x(k) + 1
ok = 0
WHILE (x(k) <= n) AND (ok = 0)
CALL PLACE(k)
IF ok = 0 THEN [17]
WEND
IF x(k) <= n THEN
IF [18] THEN answer = answer + 1 ELSE k = k + 1: x(k) = 0
ELSE [19]
END IF
WEND
END SUB
SUB PLACE (k)
ok = 1
FOR j = 1 TO k - 1
IF (ABS(k - j) = ABS(x(j) - x(k))) OR (x(j) = x(k)) THEN j = k - 1: [20]
NEXT j
END SUB