我还想说,我不在乎算法生成哪种解决方案,因为我知道对于相同的移动量有很多解决方案
我只想要任何一个解决方案,对于当前的谜题来说,都是最不可能的
谢谢。我真的想不出任何模式,我只知道最低的数字必须在前面,最大的数字必须放在后面,但诀窍是它一次移动两个数字——一个从前面移动,一个从后面移动,就像排序一样,把一个更可修改的堆栈放在一起。
这个游戏只有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
----------------------------------------------
Brute强制旋转
三左三右
----------------------------------------------
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次移动中解决(使用蛮力)
数据=
3、9、7、4、2、5、1、6、8
答案=
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步的解决方案,但对于第二个谜题,它没有正确处理,所以解决方案需要14步,而不是最佳的7步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
我使用了您的代码,得到了与您不同的结果集。我认为这部分与你在sortedPairs上的逻辑有关。在while循环中计数。我也被I、j、k和l之间的差异弄糊涂了。所以我用一些稍微不同的逻辑重写了While循环。
Dim currentNumber As Integer = 1
Dim currentPositionOfNumber As Integer = 0
While currentNumber - 1 < 8
currentPositionOfNumber = GetIndexOfNumber(newdata, currentNumber)
If currentNumber - 1 = currentPositionOfNumber Then
'do nothing
ElseIf currentNumber = currentPositionOfNumber Then
'If the number needed to move is in the spot to the immediate right of where it needs to be, then just rotate left once
newdata = CyclicRotationOffset(newdata, currentNumber - 1, True)
movesTaken.Add(New OffsetMove(1, k))
printDebug(newdata)
ElseIf currentPositionOfNumber = 8 Then
'if number needed to move is in last position, then rotate it to correct position
newdata = CyclicRotationOffset(newdata, currentNumber - 1, False)
movesTaken.Add(New OffsetMove(1, k))
printDebug(newdata)
ElseIf currentNumber = newdata(currentPositionOfNumber + 1) - 1 Then
'if the number is not in any of the above positions, but the number immediately to it's right is the next higher, then just rotate left until the pair are in correct position
Do Until GetIndexOfNumber(newdata, currentNumber) = currentNumber - 1
newdata = CyclicRotationOffset(newdata, currentNumber - 1, True)
movesTaken.Add(New OffsetMove(1, k))
printDebug(newdata)
Loop
Else
'rotate left once, then rotate right to correct position
newdata = CyclicRotationOffset(newdata, currentPositionOfNumber, True)
movesTaken.Add(New OffsetMove(1, k))
printDebug(newdata)
newdata = CyclicRotationOffset(newdata, currentNumber - 1, False)
movesTaken.Add(New OffsetMove(1, k))
printDebug(newdata)
End If
currentNumber += 1
End While
我还有一个函数,它可以查找正在评估的currentNumber在数组中的位置
Public Function GetIndexOfNumber(data() As Byte, number As Integer) As Integer
For i = 0 To 8
If data(i) = number Then Return i
Next
End Function
有了这个,我得到了以下结果。。。测试1=6次移动测试2=7移动