slore

level 3:3,7,9,6,8,8,26 秒

level 5:52,17,85,64,57,34,82,51,14,35 秒


level 4:503,1402,690 秒

8 3 6  9 4 7  5 2 1
2 5 1  8 3 6  4 9 7
4 7 9  1 2 5  8 3 6

9 6 8  2 5 1  3 7 4
1 2 7  4 8 3  6 5 9
5 4 3  6 7 9  2 1 8

6 1 4  3 9 2  7 8 5
3 9 5  7 6 8  1 4 2
7 8 2  5 1 4  9 6 3


找到了9年前用回溯法解数独的VBS脚本,选择下一个可用时,是随机抽取一个,
所以运算时间不固定,有运气成分在里面.


不过,level 5运行10次也在1分钟内,level 4运行了3次,长的达26分钟?
level你是不是写反了.

另外,有个数独的小flash程序,做的挺好的,简单,而且各个格子4个角还可以临时设置候选值.

slore

居然是按字符串存储和处理的,如果用int估计会变快吧.  

slore

旋转90度，180度等，开4个进程并行跑，应该会某个路线快些，只用把初始数据按规律变换即可。

再有，4个线程的某单元格的候选项目共享，更快得出唯一解。

再有，改变搜索前进方向，上面旋转数独盘，左右，上下，4个方向同时了，还有顺时旋转前进，逆时针方向，先斜线，先小格等方向，可以开更多线程。

slore

回复 12# 523066680


单纯考虑算法的话，肯定有更优的，但是 多线程对于现在大内存，多核CPU才是更好的利用，而且很多问题都可以采用这个方法来提高。
至于探索路径，不一定非要0～81这个顺序，可以把每个格子的候选项，从小到大排列，按这个数据填，有大概率先填入正确的数据，可以减少尝试次数吧。那天有时间了ruby写下试试。

slore

class Soduku
  def initialize(str)
    @matrix = 9.times.map{[0]*9}
    str.reverse!       <-只加了一句，LEVEL4立马难度变低了
    nums = str.split('').map(&:to_i)
    ...
  end
复制代码

[3, 0, 0, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 9, 0]
[0, 8, 0, 2, 0, 0, 0, 0, 6]
[0, 0, 0, 0, 7, 0, 3, 4, 0]
[0, 5, 6, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 5, 0, 0, 0, 0, 0]
[0, 0, 0, 6, 0, 8, 0, 0, 2]
[1, 0, 0, 0, 0, 0, 0, 3, 0]
5.069903 秒
[3, 6, 9, 4, 1, 5, 2, 8, 7]
[2, 4, 1, 8, 6, 7, 5, 9, 3]
[5, 8, 7, 2, 9, 3, 4, 1, 6]
[8, 1, 2, 9, 7, 6, 3, 4, 5]
[9, 5, 6, 3, 8, 4, 7, 2, 1]
[4, 7, 3, 1, 5, 2, 8, 6, 9]
[6, 3, 8, 5, 2, 1, 9, 7, 4]
[7, 9, 4, 6, 3, 8, 1, 5, 2]
[1, 2, 5, 7, 4, 9, 6, 3, 8]

slore

至于探索路径，不一定非要0～81这个顺序，可以把每个格子的候选项，从小到大排列，按这个数据填，有大概率先填入正确的数据，可以减少尝试次数吧。

错了，如果按候选项探索的话，比如, [0,0]点可以用5和4,[8,8]可以用1,3，
都是最小的2个候选，但是填写0,0，在填8,8，变成了散点，如果50%概率选错了的话，
其他格子，无效探索反而变得多了，填写的多，但是排除无效值的情报却少了。

探索改成下面这样。

先选择出有最少候选项的位置，然后对它相同X,Y和Z区域的 格子 权值-1。
(假设最小的这个格子我们填入了一个数字，被影响的其他格子，候选项-1)
然后，被影响的格子里面，权值最低的(候选项-1后，最小的)，
是我们接下来优先探索的，同理，整理出，每次填入一个单元格，
受其影响的，候选项最少的格的探索路径。这样填入数据之间有关联，
如果填入了错误值，可以更早地回溯。

VBS代码移植为ruby脚本的，只在处理前，修改这1处，从几百秒到稳定10秒LEVEL4的结果输出，
很大的改善方案。

ans = candidate(x, y)
return false if ans.size <= 0

v = ans[0]  #取出候选的第一个
ans.delete v
@matrix[x][y] = v

改成， v = ans.sample #候选中随机抽1个，LEVEL4的结果，2秒～18秒之间

#魔法CODE
str.reserse!
v = ans.sample
复制代码

    sort_seq = []
    while
      sort_seq.push @solve_seq[min_seq]
      x = @solve_seq[min_seq][0]
      y = @solve_seq[min_seq][1]
      z = ((x / 3) * 3) + (y / 3)
      @solve_seq.delete_at(min_seq)

      break if @solve_seq.size == 0
      min = 10
      min_seq = -1
      @solve_seq.each_with_index do |seq, i|
        zz = ((seq[0] / 3) * 3) + (seq[1] / 3)
        if seq[0] == x || seq[1] == y || zz == z
          seq[2] -= 1
          if seq[2] < min
            min = seq[2]
            min_seq = i
          end
        end
      end
    end
    p sort_seq
    @solve_seq = sort_seq
复制代码

slore

回复 16# 523066680

VBS当时写代码,就有这个逻辑.先CreatePlan里面有presolvecount,然后才SolvePanes递归的.