また、同じ量の動きに対して多くの解があることを知っているので、アルゴリズムがどの解を生成するかは気にしないと言いたいです。
現在のパズルで可能な最小の動きである解決策が欲しいだけです。
ありがとうございました。私が知っていることは、最小の数字が前に、最大の数字が後ろになければならないということだけを考え出すことができるパターンは実際にはありませんが、トリックは、2 つの数字を同時に前から 1 つと後ろから 1 つを一緒に移動することです。より変更可能なスタックを一緒に並べ替えます。
このゲームには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
ここに 2 つの例があります
--------------------------------------------------
データ、ブルート フォース (および関数) を使用して 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 <- 最後の 1 つはソートされた回答を生成します
----------------------------------------------
ここは難しい例 (これは私を困惑させた)
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 つの動きの解決策を見つける私のコードは次のとおりですが、2 番目のパズルでは正しく処理されないため、解決策は最適な 7 つの動きではなく14 回の動きになります。
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