绝对有解的⑨宫格拼图（另：打乱数组）

各种压力的猫君

*请先下载柳大的拼图游戏（http://www.66rpg.com/articles/18）

非常严重的问题……9宫格50%概率会无解……

于是下面脚本诞生

1. #==============================================================================
   
2. # ■ 绝对有解的⑨宫格 by 各种压力的猫君
   
3. #------------------------------------------------------------------------------
   
4. # 　完全没优化效率的原始版本。
   
5. #   适用于柳大的拼图无双（http://www.66rpg.com/articles/18）
   
6. #   插入 Scene_PT 以下 MAIN 以上。
   
7. #==============================================================================
   
8. 
   
9. class Scene_PT
   
10.   #--------------------------------------------------------------------------
    
11.   # ● 初始化对像
    
12.   #--------------------------------------------------------------------------
    
13.   alias randnumbers_66 randnumbers
    
14.   def randnumbers
    
15.     if @max_x == 3 && @max_y == 3
    
16.       possible9 # 绝对有解的⑨宫格 by 各种压力的猫君
    
17.     else
    
18.       randnumbers_66
    
19.     end
    
20.   end
    
21.   #--------------------------------------------------------------------------
    
22.   # ● 打乱数组 by 各种压力的猫君
    
23.   #--------------------------------------------------------------------------
    
24.   def shuffle_array(array)
    
25.     # 新数组
    
26.     new_array = []
    
27.     # 临时数组
    
28.     temp_array = []
    
29.     # 临时变量（循环次数）
    
30.     pass = 0
    
31.     # 循环
    
32.     loop do
    
33.       # 每30次调用一次Graphics.update，避免10s
    
34.       # Graphics.update if pass % 30 == 0
    
35.       # 当所有序列排列完毕后跳出循环
    
36.       break if temp_array.size == array.size
    
37.       # 在数组个数之内生成随机数
    
38.       temp_index = rand(array.size)
    
39.       # 判断是否已存在
    
40.       if temp_array.include?(temp_index)
    
41.         # 增加循环次数
    
42.         pass += 1
    
43.         next # 继续循环
    
44.       else
    
45.         temp_array.push(temp_index) # 压入数组
    
46.       end
    
47.       # 增加循环次数
    
48.       pass += 1
    
49.     end
    
50.     # 生成新数组
    
51.     for i in temp_array
    
52.       new_array.push array[i]
    
53.     end
    
54.     # 返回新数组
    
55.     return new_array
    
56.   end
    
57.   #--------------------------------------------------------------------------
    
58.   # ● 生成绝对有解的⑨宫格 by 各种压力的猫君
    
59.   #--------------------------------------------------------------------------
    
60.   def possible9
    
61.     # 生成0~8数组
    
62.     temp_array = []
    
63.     for i in 0..8
    
64.       temp_array.push(i)
    
65.     end
    
66.     # 打乱数组
    
67.     rand_9 = shuffle_array(temp_array)
    
68.     # 检查是否有解
    
69.     unless possible9?(rand_9)
    
70.       # 重排
    
71.       rand_9 = shuffle_array(temp_array)
    
72.     end
    
73.     # 删除空格
    
74.     rand_9.delete(8)
    
75.     # 写入变量
    
76.     @randnumbers = rand_9
    
77.   end
    
78.   #--------------------------------------------------------------------------
    
79.   # ● 检查⑨宫格是否有解 by 各种压力的猫君
    
80.   #--------------------------------------------------------------------------
    
81.   def possible9?(array)
    
82.     get_index = []
    
83.     correct_index = []
    
84.     need_exchange = 0
    
85.     for i in 0..8
    
86.       get_index.push(array.index(i))
    
87.     end
    
88.     #
    
89.     for i in 0..8
    
90.       correct_index.push(i)
    
91.     end
    
92.     #
    
93.     try_exchange = get_index.clone
    
94.     for i in 0..8
    
95.       if try_exchange[i] == correct_index[i]
    
96.         # 无需移动
    
97.       else
    
98.         # 需要对调次数+1
    
99.         need_exchange += 1
    
100.         # 实际对调
     
101.         try_exchange[i] = get_index[correct_index[i]]
     
102.         try_exchange[correct_index[i]] = get_index[i]
     
103.       end
     
104.     end
     
105.     #
     
106.     if need_exchange % 2 == 0
     
107.       # 有解
     
108.       return true
     
109.     else
     
110.       # 无解
     
111.       return false
     
112.     end
     
113.   end
     
114. end
     

复制代码

各种求优化 求讨论

orzfly

1. def possible?(array)
   
2.   dims = Math.sqrt(array.length).to_i
   
3.   return nil if dims ** 2 != array.length
   
4.   eq1 = inversion_number(array) % 2 == 0
   
5.   return eq1 if dims % 2 == 1
   
6.   eq2 = (array.index(0) / dims - (dims - 1)) % 2 == 0
   
7.   return (!eq1) == (eq2)
   
8. end
   
9. 
   
10. def inversion_number(array)
    
11.   t = 0; (array.length - 1).times { |x| array[0, x + 1].each { |y| t += 1 if y < array[x + 1] and y != 0 } }; t
    
12. end
    
13. 
    
14. print "#{possible?([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0])}\n"
    
15. print "#{possible?([1,2,3,4,5,6,7,8,9,10,11,0,12,13,14,15])}\n"
    
16. print "#{possible?([1,2,3,4,0,5,6,7,9,10,11,8,13,14,15,12])}\n"
    
17. print "#{possible?([1,2,3,4,5,6,7,8,0])}\n"
    
18. print "#{possible?([1,2,3,4,5,6,7,0,8])}\n"
    
19. print "#{possible?([2,1,3,4,5,6,7,8,0])}\n"

复制代码

参考资料 = = http://blog.csdn.net/tiaotiaoyly/article/details/2008233
我只是写了个ruby版而已@各种压力的猫君

打乱数组

1. array.sort_by{ rand }

复制代码

怕鼠的猫

线性代数中提到的 奇排列 和 偶排列。 随机生成之后判定一下乱序数。 你懂的。

1. a=Array.new(9){|i| i}.shuffle
   
2. b=(0..8).to_a.shuffle
   

复制代码

0..8 乱序数组。