【小伟哥游戏之路】Python之八皇后问题的算法实例

今天是2019年10月24日 程序员节日

正好在看到python资料中 出现了八皇后的问题

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。

PYTHON 实现

#* queen problem with recurison
BOARD_SIZE = 8

def under_attack(col, queens):
   left = right = col
   for r, c in reversed(queens):
 #左右有冲突的位置的列号
       left, right = left - 1, right + 1

       if c in (left, col, right):
           return True
   return False

def solve(n):
   if n == 0:
       return [[]]

   smaller_solutions = solve(n - 1)

   return [solution+[(n,i+1)]
       for i in xrange(BOARD_SIZE)
           for solution in smaller_solutions
               if not under_attack(i+1, solution)]
for answer in solve(BOARD_SIZE):
   print answer

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;
static int gEightQueen[8] = { 0 }, gCount = 0;
void print()//输出每一种情况下棋盘中皇后的摆放情况
{
    for (int i = 0; i < 8; i++)
    {   
        int inner;
        for (inner = 0; inner < gEightQueen[i]; inner++)
            cout << "0";
            cout <<"#";
        for (inner = gEightQueen[i] + 1; inner < 8; inner++)
            cout << "0";
        cout << endl;
    }
    cout << "==========================\n";
}
int check_pos_valid(int loop, int value)//检查是否存在有多个皇后在同一行/列/对角线的情况
{
    int index;
    int data;
    for (index = 0; index < loop; index++)
    {
        data = gEightQueen[index];
        if (value == data)
            return 0;
        if ((index + data) == (loop + value))
            return 0;
        if ((index - data) == (loop - value))
            return 0;
    }
    return 1;
}
void eight_queen(int index)
{
    int loop;
    for (loop = 0; loop < 8; loop++)
    {
        if (check_pos_valid(index, loop))
        {
            gEightQueen[index] = loop;
            if (7 == index)
            {
                gCount++, print();
                gEightQueen[index] = 0;
                return;
            }
            eight_queen(index + 1);
            gEightQueen[index] = 0;
        }
    }
}
int main(int argc, char*argv[])
{
    eight_queen(0);
    cout << "total=" << gCount << endl;
    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).