北京大学Julia语言入门讲义第23章： Julia编程示例–递归趣例

import time

## 检查一种摆法是否合法
## x是长度为8的列表，代表从低位到高位的8进制数字，
## 用每个数字代表一行的棋子所在的列。
def is_solution(x):
    for i in range(7):
        for j in range(i+1, 8):
            di = x[j] - x[i]
            if di==0 or di==j-i or di==i-j :
                return False
    return True
            
## 穷举进入下一个摆法
def next_board(x):
    x[0] += 1
    for i in range(7):
        if(x[i]==8):
            x[i+1] += 1
            x[i] = 0
    return x
            
def queens_exaust():
    board = [0]*8
    nmax = 8**8
    ## boards用来存放所有的摆法，
    ## 每种摆法表示为8个元素的列表
    boards = []
    nb = 0
    for i in range(nmax):
        if is_solution(board):
            print(str(nb) + ',' + ','.join(map(str, board)))
            boards.append(board.copy())
            nb += 1
        
        board = next_board(board)
    return boards


time_start=time.time()
res1 = queens_exaust()
time_end=time.time()
print('穷举法用时', time_end-time_start)
print('解的个数：', len(res1))

## 检查一种摆法是否合法
## x是长度为8的数组，第i个元素是第i行的棋子所在的列序号
function is_solution(x)
    for i in 1:7
        for j in (i+1):8
            di = x[j] - x[i]
            if di==0 || di==j-i || di==i-j
                return false
            end
        end
    end
    return true
end

## 穷举进入下一个摆法
## 把长度为8的数组x看成是有8位数的8进制数，但数字都加1，
## 次序是从低位到高位
function next_board(x)
    x[1] += 1
    for i in 1:7
        if x[i]==9
            ## 进位
            x[i+1] += 1
            x[i] = 1
        end
    end

    return x
end

function queens_exaust()
    board = ones(Int8, 8)
    nmax = 8^8
    nbmax = 1000
    nb = 0
    boards = zeros(Int8, nbmax, 8)
    for i in 1:nmax
        if is_solution(board)
            nb += 1
            println(board)
            boards[nb,:] = board
        end

        board = next_board(board)
    end
    boards = boards[1:nb,:]
    return boards
end
@time queens_exaust()

## 用长度为8的列表A表示一种摆法，
## 用cur表示当前要摆放的棋子序号，0 <= cur < 8
def queens(A, cur=0):
    if cur == len(A):
        ## 如果当前棋子序号为8，表示找到了一种摆法
        print(','.join(map(str, A)))
        boards.append(A.copy())
        return 0
    ## 对每颗棋子col遍历
    for col in range(len(A)):
        ## 将当前棋子cur摆放在col列，
        A[cur] = col
        ## 设置摆放是否合法的初值为真
        flag = True
        ## 判断cur号棋子摆放在col列，是否与0到cur-1号棋子有冲突
        ## row是用来遍历0到cur-1号棋子的变量
        for row in range(cur):
            ## 以下判断摆放在第cur行、第col列的棋子，
            ## 是否与第row行、A[row]列的棋子冲突
            if A[row] == col or abs(col - A[row]) == cur - row:
                flag = False
                break
        ## 如果摆放第cur号棋子在第col列成功，
        ## 就考虑下一颗棋子（递归调用）；
        ## 如果摆放不成功，就摆放到col的下一列继续判断
        ## 这样会遍历每颗棋子与前面棋子的不冲突的位置
        if flag:
            queens(A, cur+1)

boards = []
queens([None]*8)

## 递归算法
## 用长度为8的数组A表示一种摆法，
## 用cur表示当前要摆放的棋子序号，1 <= cur <= 8
function queens()
    nbmax = 1000
    nb = 0
    boards = zeros(Int8, nbmax, 8)

    function queens_rec(A, cur=1)
        if cur == 9
            ## 如果当前棋子序号为9，表示找到了一种摆法
            nb += 1
            boards[nb,:] = A
            ##println(join(string.(A), ","))
            return
        end # if cur

        ## 对当前要摆放的棋子遍历所有列位置试摆放
        for col in 1:8
            ## 将当前棋子cur摆放在col列，
            A[cur] = col
            ## 设置摆放是否合法的初值为真
            flag = true
            ## 判断cur号棋子摆放在col列，是否与1到cur-1号棋子有冲突
            ## row是1到cur-1号棋子的变量
            for row in 1:(cur-1)
                ## 以下判断摆放在第cur行、第col列的棋子，
                ## 是否与第row行、A[row]列的棋子冲突
                if A[row] == col || abs(col - A[row]) == cur - row
                    flag = false
                    break
                end
            end # for row

            ## 如果摆放第cur号棋子在第col列成功，
            ## 就考虑下一颗棋子（递归调用）；
            ## 如果摆放不成功，就摆放到col的下一列继续判断
            ## 这样会遍历每颗棋子与前面棋子的不冲突的位置
            if flag
                queens_rec(A, cur+1)
            end
        end # for col
    end # function queens_rec

    queens_rec(zeros(Int8, 8), 1)
    boards = boards[1:nb,:]
    println("找到解的个数：", nb)

    return boards
end # function queens
@time queens()

import DataFrames: DataFrame
import CSV

function board_equals(x, y)
    ## 棋盘的8元素存储到8x8的0-1矩阵存储
    bs = length(x)
    function board_to_mat(z)
        mat = zeros(Int,bs,bs)
        for i in 1:bs
            mat[i,z[i]] = 1
        end # for i
        return mat
    end # board_to_mat

    xm = board_to_mat(x)
    ym = board_to_mat(y)

    # 左右反射
    function reflect_lr(z)
        return z[:, end:-1:begin]
    end # reflect_lr

    # 上下反射
    function reflect_ud(z)
        return z[end:-1:begin, :]
    end # reflect_ud

    function idtran(z)
        return z
    end
    
    # 逆时针旋转90度, rotl90
    # 旋转180度, rot180
    # 顺时针旋转90度，rotr90
    # 转置：transpose
    # 沿反对角线反转：reflect_lr ∘ rotl90

    funcs = [reflect_lr, reflect_ud, 
        rotl90, rotr90, rot180,
        transpose, reflect_lr ∘ rotl90]

    for i in 1:length(funcs)
        f = funcs[i]
        ynew = f(ym)
        if all(ynew .== xm)
            return true
        end # if
    end # for f

    return false
end # board_equals

## 标记通过变换可以得到的摆法
function group_boards(boards)
    b = copy(boards)
    nb = size(b, 1)    # 摆法个数
    g = zeros(Int, nb) # 分组编码，每种摆法一个值
    ng = 1   # 分组编码初值
    g[1] = 1 # 第一中摆法分组为1 

    for j in 2:nb # 对从第二种摆法开始的每一种摆法
        newgroup = true
        for i in 1:(j-1) 
            ## 判断第j种摆法是否与前面的第i种摆法可转换，
            ## 如果可转换，将第j摆法标记为第i中摆法的分组编码
            if board_equals(b[i,:], b[j,:])
                g[j] = g[i]
                newgroup = false
                break
            end # if
        end # for i
        if newgroup
            ng += 1
            g[j] = ng
        end # if
    end # for j

    ## 保存为csv
    println("找到分组个数：", ng)
    grouped = [1:nb boards g]
    qn = ["solution"; "Q" .* string.(1:8); "group"]
    df = DataFrame(grouped, Symbol.(qn))
    sort!(df, :group)
    df[:, :solution] = 1:nb
    CSV.write("queens_group_julia.csv", df)
    
    return grouped
end # group_boards

boards = queens()
grouped = group_boards(boards);