-
八皇后問題
鎖定
八皇后問題回溯算法思路
八皇后問題(3張)
回溯算法優於窮舉法。將列A的皇后放在第一行以後，列B的皇后放在第一行已經發生衝突。這時候不必繼續放列C的皇后，而是調整列B的皇后到第二行，繼續衝突放第三行，不衝突了才開始進入列C。如此可依次放下列A至E的皇后，如圖2所示。將每個皇后往右邊橫向、斜向攻擊的點位用叉標記，發現列F的皇后無處安身。這時回溯到列E的皇后，將其位置由第4行調整為第8行，進入列F，發現皇后依然無處安身，再次回溯列E。此時列E已經枚舉完所有情況，回溯至列D，將其由第2行移至第7行，再進入列E繼續。按此算法流程最終找到如圖3所示的解，成功在棋盤裏放下了8個“和平共處”的皇后。繼續找完全部的解共92個。
回溯算法求解八皇后問題的原則是：有衝突解決衝突，沒有衝突往前走，無路可走往回退，走到最後是答案。為了加快有無衝突的判斷速度，可以給每行和兩個方向的每條對角線是否有皇后佔據建立標誌數組。放下一個新皇后做標誌，回溯時挪動一箇舊皇后清除標誌。
八皇后問題編程實現
八皇后問題Haskell
queens :: Int -> [[Int]]
queens n = map reverse $ queens' n
where queens' 0 = [[]]
queens' k = [q:qs | qs <- queens' (k-1), q <- [1..n], isSafe q qs]
isSafe try qs = not (try `elem` qs || sameDiag try qs)
sameDiag try qs = any (\(colDist,q) -> abs (try - q) == colDist) $ zip [1..] qs八皇后問題GO
package main
import "fmt"
func main() {
var balance = [8]int{0, 0, 0, 0, 0, 0, 0, 0}
queen(balance, 0)
}
func queen(a [8]int, cur int) {
if cur == len(a) {
fmt.Print(a)
fmt.Println()
return
}
for i := 0; i < len(a); i++ {
a[cur] = i
flag := true
for j := 0; j < cur; j++ {
ab := i - a[j]
temp := 0
if ab > 0 {
temp = ab
} else {
temp = -ab
}
if a[j] == i || temp == cur-j {
flag = false
break
}
}
if flag {
queen(a, cur+1)
}
}
}
八皇后問題JS
function queen(a, cur) {
if (cur==a.length) { console.log(a); return; }
for (var i = 0; i < a.length; i++) {
a[cur] = i;
var flag = true;
for (var j = 0; j < cur; j++) {
var ab = i - a[j];
if (a[j]==i||(ab>0?ab:-ab)==cur-j) { flag=false; break };
};
if (flag) { queen(a,cur+1); }
};
};
queen([1,1,1,1,1,1,1,1],0);
八皇后問題C++
#include <iostream>
using namespace std;
const int N = 8;
int arr[10], total_cnt;
// arr記錄每一行(X)皇后的Y座標
bool isPlaceOK(int *a, int n, int c) {
for (int i = 1; i <= n - 1; ++i) {
if (a[i] == c || a[i] - i == c - n || a[i] + i == c + n)
return false;
//檢查位置是否可以放
//c是將要放置的位置
//a[i] == c如果放在同一列，false
//a[i] -+ i = c -+ n 如果在對角線上，false
}
return true;
}
void printSol(int *a) {
for (int i = 1; i <= N; ++i) { //遍歷每一行
for (int j = 1; j <= N; ++j) { //遍歷每一列
cout << (a[i] == j ? "X" : "-") << " ";;
} //如果標記數組中這一行的皇后放在j位置，則輸出X，否則輸出-，
//用空格分隔
cout << endl; //每一行輸出一個換行
}
cout << endl; //每一組數據一個換行分隔
}
void addQueen(int *a, int n) {
if (n > N) { //n代表從第一行開始放置
printSol(a);
total_cnt++;
return ;
}
for (int i = 1; i <= N; ++i) { //i從第1列到第N列遍歷
if (isPlaceOK(a, n, i)) {
a[n] = i; //如果可以放置，就把皇后放在第n行第i列
addQueen(a, n + 1);
}
}
}
int main() {
addQueen(arr, 1);
cout << "total: " << total_cnt << " solutions.\n";
return 0;
}八皇后問題Pascal
program queen; var a:array[1..8]of longint; //記錄皇后的行座標 b,c,d:array[-7..16]of longint; //行，右上，右下斜線的佔位標誌 m,ans:longint; procedure queen(j:longint); var i:longint; begin if j>8 then begin inc(ans); //滿足條件，找到一種方案 exit; end; for i:=1 to 8 do//每個皇后位置有八種可能 if(b[i]=0)and(c[i+j]=0)and(d[j-i]=0)then //如果位置沒有被佔則運行 begin a[j]:=i; //皇后放置在此行 b[i]:=1; //佔領第i行 c[i+j]:=1; //佔領右上 d[j-i]:=1; //佔領右下 queen(j+1); //遞歸 b[i]:=0; //回溯，恢復行佔位標誌 c[i+j]:=0; //回溯，恢復斜上方（右上）佔位標誌 d[j-i]:=0; ///回溯，恢復斜下方（右下）佔位標誌 end; end; begin //主程序 for m:=-7 to 16 do //數據初始化為0 begin b[m]:=0; //行數據初始化為0 c[m]:=0; //右上數據初始化為0 d[m]:=0; //右下數據初始化為0 end; ans:=0; queen(1); //開始放置第一個皇后 writeln(ans); end.
八皇后問題Java
public class Queen {
private int[] column; //同欄是否有皇后，1表示有
private int[] rup; //右上至左下是否有皇后
private int[] lup; //左上至右下是否有皇后
private int[] queen; //解答
private int num; //解答編號
public Queen() {
column = new int[8+1];
rup = new int[(2*8)+1];
lup = new int[(2*8)+1];
for (int i = 1; i <= 8; i++)
column[i] = 0;
for (int i = 1; i <= (2*8); i++)
rup[i] = lup[i] = 0; //初始定義全部無皇后
queen = new int[8+1];
}
public void backtrack(int i) {
if (i > 8) {
showAnswer();
} else {
for (int j = 1; j <= 8; j++) {
if ((column[j] == 0) && (rup[i+j] == 0) && (lup[i-j+8] == 0)) {
//若無皇后
queen[i] = j; //設定為佔用
column[j] = rup[i+j] = lup[i-j+8] = 1;
backtrack(i+1); //循環調用
column[j] = rup[i+j] = lup[i-j+8] = 0;
}
}
}
}
protected void showAnswer() {
num++;
System.out.println("\n解答" + num);
for (int y = 1; y <= 8; y++) {
for (int x = 1; x <= 8; x++) {
if(queen[y]==x) {
System.out.print("Q");
} else {
System.out.print(".");
}
}
System.out.println();
}
}
public static void main(String[] args) {
Queen queen = new Queen();
queen.backtrack(1);
}
}
八皇后問題Erlang
-module(queen).
-export([printf/0, attack_range/2]).
-define(MaxQueen, 4).%尋找字符串所有可能的排列
%perms([]) ->% [[]];
%perms(L) ->% [[H | T] || H <- L, T <- perms(L -- [H])].
perms([]) ->[[]];
perms(L) ->[[H | T] || H <- L, T <- perms(L -- [H]), attack_range(H,T) == []].printf() ->L = lists:seq(1, ?MaxQueen),io:format("~p~n", [?MaxQueen]),perms(L).
%檢測出第一行的數字攻擊到之後各行哪些數字%left向下行的左側檢測%right向下行的右側檢測
attack_range(Queen, List) ->attack_range(Queen, left, List) ++ attack_range(Queen, right, List).attack_range(_, _, []) ->[];
attack_range(Queen, left, [H | _]) when Queen - 1 =:= H ->[H];
attack_range(Queen, right, [H | _]) when Queen + 1 =:= H ->[H];
attack_range(Queen, left, [_ | T]) ->attack_range(Queen - 1, left, T);attack_range(Queen, right, [_ | T]) ->attack_range(Queen + 1, right, T).
八皇后問題python
def queen(A, cur=0): if cur == len(A): print(A) return 0 for col in range(len(A)): # 遍歷當前行的所有位置 A[cur] = col for row in range(cur): # 檢查當前位置是否相剋 if A[row] == col or abs(col - A[row]) == cur - row: break else: # 如果完成了整個遍歷，則説明位置沒有相剋 queen(A, cur+1) # 計算下一行的位置 queen([None]*8)
八皇后問題C#
using System;
using System.Collections.Generic;
namespace EightQueens_CSharp {
public class EightQueens {
private List<int[]> solutions;
public List<int[]> GetSolutions(int queenCount) {
solutions = new List<int[]>();
List<int> queenList = new List<int>();
for (int i = 0; i < queenCount; i++) {
queenList.Add(0);
}
putQueen(queenCount, queenList, 0);
printSolutions(solutions);
return solutions;
}
private void putQueen(int queenCount, List<int> queenList, int nextY) {
for (queenList[nextY] = 0; queenList[nextY] < queenCount; queenList[nextY]++) {
if (checkConflict(queenList, nextY) == false) {
nextY++;
if (nextY < queenCount) {
putQueen(queenCount, queenList, nextY);
}
else {
solutions.Add(queenList.ToArray());
Console.WriteLine(string.Join(", ", queenList));
}
nextY--;
}
}
}
private bool checkConflict(List<int> queenList, int nextY) {
for (int positionY = 0; positionY < nextY; positionY++) {
if (Math.Abs(queenList[positionY] - queenList[nextY]) == Math.Abs(positionY - nextY) || queenList[positionY] == queenList[nextY]) {
return true;
}
}
return false;
}
private void printSolutions(List<int[]> solutions) {
int count = 0;
foreach (var solution in solutions) {
Console.WriteLine("Solution: {0}", count++);
int queenCount = solution.Length;
for (int i = 0; i < queenCount; i++) {
printLine(solution[i], queenCount);
}
Console.WriteLine("------------------");
}
}
private void printLine(int pos, int width) {
for (int i = 0; i < width; i++) {
if (pos == i) {
Console.Write(" x");
}
else {
Console.Write(" .");
}
}
Console.WriteLine();
}
}
}
八皇后問題Scheme
#lang racket (define (enumerate-interval low high) (cond ((> low high) null) ((= low high) (list high)) (else (cons low (enumerate-interval (+ 1 low) high))))) (define (flatmap proc seq) (foldr append null (map proc seq))) (define empty-board null) (define (safe? test-column positions) (define (two-coordinate-safe? coordinate1 coordinate2) (let ((row1 (row coordinate1)) (row2 (row coordinate2)) (col1 (column coordinate1)) (col2 (column coordinate2))) (if (or (= row1 row2) (= (abs (- row1 row2)) (abs (- col1 col2)))) #f #t))) (let ((test-coordinate (get-coordinate-by-column test-column positions))) (foldr (lambda (coordinate results) (and (two-coordinate-safe? test-coordinate coordinate) results)) #t (remove test-coordinate positions)))) (define (adjoin-position new-row new-column existing-positions) (cons (make-coordinate new-row new-column) existing-positions)) (define (make-coordinate row column) (list row column)) (define (row coordinate) (car coordinate)) (define (column coordinate) (cadr coordinate)) (define (get-coordinate-by-column target-column coordinates) (cond ((null? coordinates) null) ((= target-column (column (car coordinates))) (car coordinates)) (else (get-coordinate-by-column target-column (cdr coordinates))))) (define (queens board-size) (define (queen-cols k) (if (= k 0) (list empty-board) (filter (lambda (positions) (safe? k positions)) (flatmap (lambda (rest-of-queens) (map (lambda (new-row) (adjoin-position new-row k rest-of-queens)) (enumerate-interval 1 board-size))) (queen-cols (- k 1)))))) (queen-cols board-size)) ;敲（queens 8），得到運行結果,每個座標，第一個代表行，第二個代表列 ;純遞歸思路，運行環境racket 7.5
八皇后問題lua
local num = 0;
local t = socket.gettime();
local function searchQueen(tab)
local data = clone(tab)
if data[2] == #data[1] then
num = num + 1
-- return print("result..", num, " ==> ", table.concat(data[1], ","))
return
end
data[2] = data[2] + 1;
for i = 1, 8 do
data[1][data[2]] = i
local bOk = true
for j = 1, data[2]-1 do
if (data[1][j] == i) or (math.abs(i - data[1][j]) == data[2] - j) then
bOk = false
break
end
end
if bOk then
searchQueen(data)
end
end
end
searchQueen({{0,0,0,0,0,0,0,0}, 0})
print("EIGHT QUEEN result == ", num, "\ntime cost == ", socket.gettime() - t)