N_Queen 与柳湖

柳湖

问题从一个小组的招新传单中得来，写的很有趣，校鹅也非常的可爱，如下

柳湖的校鹅在某个时空中有了更强的领地意识，即在柳湖湖面中，它的周围不能有其他校鹅。假设栅格化的柳湖是一个由25个12米大小的正方形组成的大正方形，每个校鹅占据一个小正方形，它周围的直线和对角线的正方形内不能有其他校鹅。请问，我们的五只校鹅可以有多少种领地占据的可能？

问题翻译过来就是在一个二维数组中某一个元素周围的直线和对角线上不能有其他的元素存在，否则他们要打架，这和国际象棋中的皇后是一样的

1
2
3
4
5
6
0, 0, 0, 0 ,0							1, x, x, x ,x
0 ,0 ,0 ,0 ,0							x, x, 0, 0 ,0
0 ,0 ,0 ,0 ,0  让一只鹅皇后在[0,0]的位置--> x, 0, x, 0 ,0   那么我写x的地方就不能有其它的鹅了
0 ,0 ,0 ,0 ,0							x, 0, 0, x ,0
0 ,0 ,0 ,0 ,0							x, 0, 0, 0 ,x

问的是有多少种校鹅的排列方式。

校鹅

这里我采用编程的办法解决 (我写到最后，发现用时比手算多了不知道多少倍:-(

首先，要生成一个5X5的矩阵的所有元素的索引

1
2
3
4
5
6
7
8
#初始位置索引
def func()->list :
    available_index = [] 
    for i in range(0,5):
        for j in range(0,5):          
            available_index.append([i,j]) 
    return available_index

然后根据规则，找出一个元素占据了某一个位置时要排除的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#生成位置排除列表 
def position_deduct(arr)->list:
    row_index = arr[0]
    column_index = arr[1]
    deducted_list = []   
    i = row_index; j = column_index
    
    #计算直线上的不可用位置
    for m in range(-10,10):  #偏移量，随便取值
        for k in range(-10,10): #列
            if -i <= m <= 4-i :  
                deducted_position = [i+m,j]
                deducted_list.append(deducted_position)
            else:pass
            if -j <= k <= 4-j:  #行
                deducted_position = [i,j+k]
                deducted_list.append(deducted_position) 
    #计算对角线上的不可用位置 ok
    for k in range(-10,10):#主对角线
        if -i <= k <= 4-i and -j <= k <= 4-j:
            p = k
            deducted_position = [i+p,j+p]
            deducted_list.append(deducted_position)
    for k in range(-10,10):#副对角线
        if i-4 <= k <= i and -j <= k <= 4-j:
            p = k
            deducted_position = [i-p,j+p]
            deducted_list.append(deducted_position)
    #这里对生成的列表进行去重
    temp = []
    for item in deducted_list:
        if not item in temp:
            temp.append(item)
       
    deducted_list = temp
    return deducted_list

有了不可以使用的位置，还需要根据它找出可用的位置

1
2
3
4
5
#可用位置计算 
def available_position(position_pool,position_deduct_list):
    new_position_pool = [item for item in position_pool if item not in position_deduct_list]
    position_pool = new_position_pool
    return position_pool

好了，工具准备齐了，开始写主程序。问题有点复杂，我写的也很复杂，这种代码拿到网上要被痛批的

我用了五层的for循环，只为遍历每一种情况，最后生成的列表包含大量重复的子列表，还需要进一步处理，为什么会有重复呢，这是遍历不能避免的问题。这里很有改进的空间，用递归或许可以。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#主程序
def main(first_list):
    result_list = []
    for i in first_list:
        
        x_1 = 0;x_2 = 0;x_3= 0;x_4 = 0;x_5=0
        
        x_1 = i
        position_deduct_1 = position_deduct(i)
        second_list = available_position(first_list,position_deduct_1)
            
        for j in second_list:
               
            x_2 = j                   
            position_deduct_2 = position_deduct(j)                    
            third_list = available_position(second_list,position_deduct_2)
                
            for a in third_list:
                        
                x_3 = a
                position_deduct_3 = position_deduct(a)          
                fourth_list = available_position(third_list,position_deduct_3)
                for b in fourth_list:
                                
                    x_4 = b
                    position_deduct_4 = position_deduct(b)
                                    
                    fifth_list = available_position(fourth_list,position_deduct_4)
                    for c in fifth_list:
                        x_5 = c
                        result_list.append([x_1,x_2,x_3,x_4,x_5])
    #print(result_list)                                  
    return result_list

生成了如下的列表：

[[[0, 0], [1, 2], [2, 4], [3, 1], [4, 3]], [[0, 0], [1, 2], [2, 4], [4, 3], [3, 1]], [[0, 0], [1, 2], [3, 1], [2, 4], [4, 3]], [[0, 0], [1, 2], [3, 1], [4, 3], [2, 4]],…]

可以看到有很多重复的地方，重复的子列表表示的是重复的一个矩阵

那么先让它变成一个包含大量矩阵的列表

1
2
3
4
5
6
7
8
9
10
11
12
13

import numpy as np

def arraylist_convert(t):
    result = []
    for i in t:   
        arr = np.zeros([5,5],int)  
        for j in i:
            arr[j[0]][j[1]] = 1 #按照行标和列标赋值即可

        result.append(arr)
    return result

有了这样一个列表，去重即可。去重的部分是由AI写的，最后对最终所得列表进行计数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def remove_duplicate_arrays(arrays_list):
    unique_arrays = set()
    result = []

    for array in arrays_list:
        array_tuple = tuple(map(tuple, array))  # 将二维数组转换为元组
        if array_tuple not in unique_arrays:
            unique_arrays.add(array_tuple)
            result.append(array)
    return result

def count_num(arr):
    n = 0
    for i in arr:
        n += 1 
    return n


好了，写完了。完整代码如下

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#初始位置索引选择 ok
def func()->list :
    available_index = [] 
    for i in range(0,5):
        for j in range(0,5):          
            available_index.append([i,j]) 
    return available_index

#可用位置计算 ok
def available_position(position_pool,position_deduct_list):
    new_position_pool = [item for item in position_pool if item not in position_deduct_list]
    position_pool = new_position_pool
    return position_pool

#生成位置排除列表 ok
def position_deduct(arr)->list:
    row_index = arr[0]
    column_index = arr[1]
    deducted_list = []   
    i = row_index; j = column_index
    
    #计算直线上的不可用位置
    for m in range(-10,10):  #偏移量，随便取值
        for k in range(-10,10): #列
            if -i <= m <= 4-i :  
                deducted_position = [i+m,j]
                deducted_list.append(deducted_position)
            else:pass
            if -j <= k <= 4-j:  #行
                deducted_position = [i,j+k]
                deducted_list.append(deducted_position) 
    #计算对角线上的不可用位置 ok
    for k in range(-10,10):#主对角线
        if -i <= k <= 4-i and -j <= k <= 4-j:
            p = k
            deducted_position = [i+p,j+p]
            deducted_list.append(deducted_position)
    for k in range(-10,10):#副对角线
        if i-4 <= k <= i and -j <= k <= 4-j:
            p = k
            deducted_position = [i-p,j+p]
            deducted_list.append(deducted_position)
    #去重
    temp = []
    for item in deducted_list:
        if not item in temp:
            temp.append(item)
       
    deducted_list = temp
    return deducted_list

#主程序
def main(first_list):
    result_list = []
    for i in first_list:
        
        x_1 = 0;x_2 = 0;x_3= 0;x_4 = 0;x_5=0
        
        x_1 = i
        position_deduct_1 = position_deduct(i)
        second_list = available_position(first_list,position_deduct_1)
            
        for j in second_list:
               
            x_2 = j                   
            position_deduct_2 = position_deduct(j)                    
            third_list = available_position(second_list,position_deduct_2)
                
            for a in third_list:
                        
                x_3 = a
                position_deduct_3 = position_deduct(a)          
                fourth_list = available_position(third_list,position_deduct_3)
                for b in fourth_list:
                                
                    x_4 = b
                    position_deduct_4 = position_deduct(b)
                                    
                    fifth_list = available_position(fourth_list,position_deduct_4)
                    for c in fifth_list:
                        x_5 = c
                        result_list.append([x_1,x_2,x_3,x_4,x_5])
    print(result_list)                                  
    return result_list                                

import numpy as np
def arraylist_convert(t):
    result = []
    for i in t:   
        arr = np.zeros([5,5],int)  
        for j in i:
            arr[j[0]][j[1]] = 1

        result.append(arr)
    return result


def remove_duplicate_arrays(arrays_list):
    unique_arrays = set()
    result = []

    for array in arrays_list:
        array_tuple = tuple(map(tuple, array))  # 将二维数组转换为元组
        if array_tuple not in unique_arrays:
            unique_arrays.add(array_tuple)
            result.append(array)
    return result

def count_num(arr):
    n = 0
    for i in arr:
        n += 1 
    return n


#调用
init_list = func()
original_list = main(init_list)
r = arraylist_convert(original_list)
unique_arrays = remove_duplicate_arrays(r)
solve = count_num(unique_arrays)
print(solve)

一点想法

使用随机算法或许会简单一些

我觉得可以随机生成很多个矩阵，再判断他们到底符不符合要求，最后把符合要求的矩阵数除以总的生成矩阵的数量，得到概率，而题目所有矩阵的数量根据组合数可轻松算出来，乘以概率即可得到结果，这不比一个一个找简单多了。

#code_learning
N_Queen 与柳湖
https://silenzio111.github.io/2024/03/29/N-Queen/
作者
silenzio
发布于
2024年3月29日
许可协议