我还想说我不在乎算法生成哪种解决方案,因为我知道对于相同数量的移动有很多解决方案。
我只想要任何解决当前难题的最少可能动作的解决方案。
谢谢你。真的没有任何模式我能想到我所知道的就是最小的数字必须在前面,最大的数字必须在后面,但诀窍是它一次移动两个数字,一个从前面,一个从后面一起移动,就像与更可修改的堆栈一起排序。
这个游戏只有2个动作。。
- 在任何偏移量处左循环(最后一个字节除外) 右
- 任意偏移处的循环旋转(最后一个字节除外)
这是它的功能代码
Public Function CyclicRotationOffset(ByVal data() As Byte, ByVal beginOffset As Integer, ByVal leftDirection As Boolean) As Byte()
'Left Direction = true
'--------------------------------------------------------
'Shifted cyclically rotation If [a, b, c] then [b, c, a]
'--------------------------------------------------------
'Left Direction = false
'--------------------------------------------------------
'Shifted cyclically rotation If [a, b, c] then [c, a, b]
'--------------------------------------------------------
If beginOffset = UBound(data) Then
'last byte cannot do anything.
Return data
End If
Dim newdata() As Byte
ReDim newdata(UBound(data))
If leftDirection = True Then
newdata(UBound(newdata)) = data(beginOffset) '1st element will be last.
For i = beginOffset To UBound(data) - 1
newdata(i) = data(i + 1)
Next i
Else
newdata(beginOffset) = data(UBound(data)) 'last element will be first.
For i = beginOffset + 1 To UBound(data)
newdata(i) = data(i - 1)
Next i
End If
If beginOffset > 0 Then
Buffer.BlockCopy(data, 0, newdata, 0, beginOffset)
End If
Return newdata
End Function
这里有两个例子
----------------------------------------------------------
数据,用蛮力(和功能)在 6 个动作中解决。
2, 7, 3, 1, 6, 4, 5, 8, 9
--------------------------------- -------------
蛮力旋转
3 左,3 右
----------------------------- -----------------
1, 左
2, 左
0, 右
6, 右
3, 左
5, 右
--------------- ------------------------------
2, 3, 1, 6, 4, 5, 8, 9, 7
2, 3 , 6, 4, 5, 8, 9, 7, 1
1, 2, 3, 6, 4, 5, 8, 9, 7
1, 2, 3, 6, 4, 5, 7, 8, 9
1, 2, 3, 4, 5, 7, 8, 9, 6
1, 2, 3, 4, 5, 6, 7, 8, 9 <- 最后一个产生排序的答案
----------------------------------------------
这里有一个更难的示例(这让我难过)
7 步解决(用蛮力)
data=
3, 9, 7, 4, 2, 5, 1, 6, 8
answer=
1, 2, 3, 4, 5, 6, 7 , 8, 9
4 左, 3
右
移动
6, 左
0, 右
3, 左
7, 右
2, 左
3, 左
1, 右
3, 9, 7, 4, 2, 5, 6, 8, 1
1 , 3, 9, 7, 4, 2, 5, 6, 8
1, 3, 9, 4, 2, 5, 6, 8, 7
1, 3, 9, 4, 2, 5, 6, 7, 8
1, 3, 4, 2, 5, 6, 7, 8, 9
1, 3, 4, 5, 6, 7, 8, 9, 2
1, 2, 3, 4, 5, 6, 7, 8, 9
这是我的代码,它为第一个难题找到了 6 move 解决方案,但对于第二个难题,它没有正确处理它,因此解决方案需要14 move而不是最佳的 7 move 。
Public Structure OffsetMove
Dim moveId As Byte
Dim randomOffset As Byte
Public Sub New(ByVal moveId As Byte, ByVal randomOffset As Byte)
Me.moveId = moveId
Me.randomOffset = randomOffset
End Sub
End Structure
Public Function SortDataCyclic(ByVal data() As Byte) As List(Of OffsetMove)
Dim answer() As Byte
ReDim answer(UBound(data))
Buffer.BlockCopy(data, 0, answer, 0, data.Length)
Array.Sort(answer)
Dim newdata() As Byte
ReDim newdata(UBound(data))
Buffer.BlockCopy(data, 0, newdata, 0, data.Length)
Dim i As Long = 0
Dim j As Long = 0
Dim k As Long = 0
Dim l As Long = 0
Dim solutionCount As Integer = 0
Dim movesTaken As New List(Of OffsetMove)
Debug.Print("---------------------------------------------")
Dim sortedPairs As New List(Of Byte)
While j < 8
If sortedPairs.Count >= 3 Then
'Insertion right cyclic rotations go here
While l < 9
k = 0
While k < 9
If newdata(k) > newdata(8) Then Exit While
k += 1
End While
If k = 9 Then
'fully sorted already, nothing left to insert.
Exit While
End If
newdata = CyclicRotationOffset(newdata, k, False)
movesTaken.Add(New OffsetMove(1, k))
printDebug(newdata)
l += 1
End While
'Exit the while, everything is sorted.
Exit While
'1, 2, x, x, x, x
ElseIf j + 1 < 9 AndAlso _
newdata(j + 1) = (newdata(j) + 1) Then
sortedPairs.Add(j)
j += 2
'1, x, 2, x, x, x
ElseIf j + 2 < 9 AndAlso _
newdata(j + 2) = (newdata(j) + 1) Then
newdata = CyclicRotationOffset(newdata, (j + 1), True)
movesTaken.Add(New OffsetMove(0, (j + 1)))
printDebug(newdata)
j = 0
'No pair pattern at all.
Else
newdata = CyclicRotationOffset(newdata, j, True)
movesTaken.Add(New OffsetMove(0, j))
printDebug(newdata)
End If
End While
Return movesTaken
End Function
Public Sub printDebug(ByVal data() As Byte)
Debug.Print(data(0) & ", " & data(1) & ", " & data(2) & ", " & data(3) & ", " & data(4) & ", " & data(5) & ", " & data(6) & ", " & data(7) & ", " & data(8))
End Sub