回溯法解数独，平均用时<0.2秒

lyb200

留个记号吧

yangyangzhifeng

香川群子 发表于 2016-3-5 14:30
本帖是VBA暴力解代码的精华帖。

我现在实现了DLX算法，比普通回溯法快多了，平均用时不到5毫秒
http://club.excelhome.net/forum. ... p;page=1#pid9640428

香川群子

yangyangzhifeng 发表于 2018-8-31 19:27
我现在实现了DLX算法，比普通回溯法快多了，平均用时不到5毫秒
http://club.excelhome.net/forum.php?mo ...

这个算法很有意思。

kangren6772

'Option Base 1
Type zb
  h As Long
  l As Long
  g As Long
End Type
Dim jgz(), zong&
Sub jiugong(ByRef wz() As zb, ByRef js() As zb, ByRef jg, ByVal i&, j1&)
  If i > j1 Then zong = zong + 1: ReDim Preserve jgz(zong): jgz(zong) = jg: Exit Sub
  Dim j&
  For j = 1 To 9
    If wz(js(i).h, j).h = 0 Then
      If wz(js(i).l, j).l = 0 Then
        If wz(js(i).g, j).g = 0 Then
          jg(js(i).h, js(i).l) = j
          wz(js(i).h, j).h = 1
          wz(js(i).l, j).l = 1
          wz(js(i).g, j).g = 1
          Call jiugong(wz, js, jg, i + 1, j1)
          wz(js(i).h, j).h = 0
          wz(js(i).l, j).l = 0
          wz(js(i).g, j).g = 0
        End If
      End If
    End If
  Next j
End Sub
Sub shudu()
  Erase jgz: zong = 0
  Dim wz(1 To 9, 1 To 9) As zb, js(81) As zb, jg, i&, j&, h&, l&, g&
  jg = Range("a1:i9")
  For i = 0 To 80
    h = (i \ 9) + 1
    l = (i Mod 9) + 1
    g = (i \ 9 \ 3) * 3 + (i Mod 9) \ 3 + 1
    If jg(h, l) > 0 Then
      wz(h, jg(h, l)).h = 1
      wz(l, jg(h, l)).l = 1
      wz(g, jg(h, l)).g = 1
    Else
      j = j + 1
      js(j).h = h
      js(j).l = l
      js(j).g = g
    End If
  Next i
  Call jiugong(wz, js, jg, 1, j)
  MsgBox zong
End Sub