宝石游戏步骤计算，换句话说一些数学

Question

我有一个程序可以扫描图像并将宝石转换为特定数字。看下面的图片：

所以我有一个带有数字的表格。数字 1 代表黄色宝石，2 代表蓝色宝石，等等...

比如：

    A  B  C  D  E
1 | 1  2  3  4  5
2 | 3  5  2  4  1
3 | 1  4  4  1  2
4 | 3  3  2  1  5
5 | 5  1  5  2  5

我想计算一个步骤，以水平或垂直获得 3 个相等的数字（宝石）。例如，在此表中，如果我将 E2 与 D2 交换，D2 将是 1，并且 D2、D3、D4 创建一个有效步骤，因为它都是 1。我使用的是 VB.NET 2010。

我的表格大小为 8x8，这只是上面的一个示例。

现在我只有多个变量中的值（A1=1，A2=3，等等..）

我希望你理解我的问题，任何帮助将不胜感激。

Answer 1

给你：

Module Module1

    Sub Main()
        Dim input = {{1, 3, 2, 4, 1, 1, 2, 1},
                     {1, 2, 5, 3, 2, 1, 3, 4},
                     {2, 1, 5, 4, 3, 2, 5, 4},
                     {3, 5, 1, 5, 2, 4, 1, 2},
                     {4, 2, 5, 1, 5, 2, 4, 2},
                     {2, 3, 2, 2, 5, 1, 3, 1},
                     {2, 1, 5, 4, 3, 2, 5, 4},
                     {3, 5, 1, 3, 2, 4, 1, 2}}

        Console.WriteLine("INPUT:")
        Console.Write("   |")
        For i = 1 To input.GetLength(1)
            Console.Write("{0,3}", GetColumnName(i))
        Next
        Console.Write(vbCrLf)
        Console.Write("---+")
        For i = 1 To input.GetLength(1)
            Console.Write("---")
        Next
        Console.Write(vbCrLf)

        For y = 0 To input.GetUpperBound(0)
            Console.Write("{0,3}|", y + 1)
            For x = 0 To input.GetUpperBound(1)
                Console.Write("{0,3}", input(y, x))
            Next
            Console.Write(vbCrLf)
        Next

        Console.WriteLine("{0}{0}SOLUTION:", vbCrLf)
        For Each match In Solve(input)
            Console.WriteLine("Move {0} {1} for a match of {2}", match.Item1, match.Item2, match.Item3)
        Next
        Console.ReadLine()
    End Sub

    Function Solve(ByVal input As Integer(,)) As IEnumerable(Of Tuple(Of String, Char, Integer))
        Dim matches As New List(Of Tuple(Of String, Char, Integer))
        Dim result As Tuple(Of Boolean, Tuple(Of String, Char, Integer))
        Dim test As Integer(,)

        Dim maxX = input.GetUpperBound(0) - 1
        Dim maxY = input.GetUpperBound(1) - 1

        For x = 0 To maxX
            For y = 0 To maxY
                ReDim test(If(maxX - x > 4, 3, maxX - x), If(maxY - y > 4, 3, maxY - y))
                For x1 = x To x + test.GetLength(0) - 1
                    For y1 = y To y + test.GetLength(1) - 1
                        test(x1 - x, y1 - y) = input(y1, x1)
                    Next
                Next

                'check if the result is a match
                For Each result In {IsMatchOnThird(test), IsMatchOnSecond(test), IsMatchOnFirst(test)}  '<-- Updated Line
                    If result.Item1 = True Then
                        Dim matchPoint = Tuple.Create(CInt(result.Item2.Item1.Split(","c)(0)),
                                                      CInt(result.Item2.Item1.Split(","c)(1)))

                        matches.Add(Tuple.Create(GetColumnName(matchPoint.Item1 + x + 1) & CStr(matchPoint.Item2 + y + 1),
                                                 result.Item2.Item2, result.Item2.Item3))
                    End If
                Next
            Next
        Next

        Return RemoveDuplicates(matches)
    End Function

   Public Function GetColumnName(ByVal colIndex As Integer) As String
        Dim result As New List(Of String)

        Do While colIndex > 0
            result.Insert(0, Chr(65 + CInt((colIndex - 1) Mod 26)))
            colIndex = (colIndex - 1) \ 26
        Loop

        Return String.Join("", result.ToArray)
    End Function

    Function RemoveDuplicates(ByVal list As IEnumerable(Of Tuple(Of String, Char, Integer))) As IEnumerable(Of Tuple(Of String, Char, Integer))

        'remove those where gems and swap direction are the same
        Dim l = (From i In list Order By i.Item3 Descending, i.Item1, i.Item2).ToList
        For i = l.Count - 1 To 1 Step -1
            If (l(i).Item1 = l(i - 1).Item1) AndAlso (l(i).Item2 = l(i - 1).Item2) Then
                l.RemoveAt(i)
            End If
        Next

        l = (From i In list Order By i.Item1, i.Item3 Descending).ToList
        For i = l.Count - 1 To 1 Step -1
            If (l(i).Item1 = l(i - 1).Item1) AndAlso (l(i).Item2 = l(i - 1).Item2) Then
                l.RemoveAt(i)
            End If
        Next

        Return From i In l Order By i.Item3 Descending, i.Item1
    End Function

    Function IsMatchOnThird(ByVal input As Integer(,)) As Tuple(Of Boolean, Tuple(Of String, Char, Integer))
        Dim size = Math.Min(input.GetLength(0), 4).ToString & "C," & Math.Min(input.GetLength(1), 4).ToString & "R"
        Dim i = input
        Dim isValid = Function(test As Integer()) test.All(Function(v) v = test(0))


        Select Case size
            Case "4C,4R"
                If isValid({i(0, 0), i(0, 1), i(1, 2)}) Then
                    Return Tuple.Create(True, Tuple.Create("1,2", "L"c, If(isValid({i(0, 0), i(0, 3)}), 4, 3)))
                ElseIf isValid({i(1, 0), i(1, 1), i(0, 2)}) Then
                    Return Tuple.Create(True, Tuple.Create("0,2", "R"c, If(isValid({i(1, 0), i(1, 3)}), 4, 3)))
                ElseIf isValid({i(0, 0), i(1, 0), i(2, 1)}) Then
                    Return Tuple.Create(True, Tuple.Create("2,1", "U"c, If(isValid({i(0, 1), i(3, 0)}), 4, 3)))
                ElseIf isValid({i(0, 1), i(1, 1), i(2, 0)}) Then
                    Return Tuple.Create(True, Tuple.Create("2,0", "D"c, If(isValid({i(0, 1), i(3, 1)}), 4, 3)))
                End If
            Case "4C,3R"
                If isValid({i(0, 0), i(0, 1), i(1, 2)}) Then
                    Return Tuple.Create(True, Tuple.Create("1,2", "L"c, 3))
                ElseIf isValid({i(1, 0), i(1, 1), i(0, 2)}) Then
                    Return Tuple.Create(True, Tuple.Create("0,2", "R"c, 3))
                ElseIf isValid({i(0, 0), i(1, 0), i(2, 1)}) Then
                    Return Tuple.Create(True, Tuple.Create("2,1", "U"c, If(isValid({i(0, 1), i(3, 0)}), 4, 3)))
                ElseIf isValid({i(0, 1), i(1, 1), i(2, 0)}) Then
                    Return Tuple.Create(True, Tuple.Create("2,0", "D"c, If(isValid({i(0, 1), i(3, 1)}), 4, 3)))
                End If
            Case "4C,2R"
                If isValid({i(0, 0), i(1, 0), i(2, 1)}) Then
                    Return Tuple.Create(True, Tuple.Create("2,1", "U"c, If(isValid({i(0, 1), i(3, 0)}), 4, 3)))
                ElseIf isValid({i(0, 1), i(1, 1), i(2, 0)}) Then
                    Return Tuple.Create(True, Tuple.Create("2,0", "D"c, If(isValid({i(0, 1), i(3, 1)}), 4, 3)))
                End If
            Case "3C,4R"
                If isValid({i(0, 0), i(0, 1), i(1, 2)}) Then
                    Return Tuple.Create(True, Tuple.Create("1,2", "L"c, If(isValid({i(0, 0), i(0, 3)}), 4, 3)))
                ElseIf isValid({i(1, 0), i(1, 1), i(0, 2)}) Then
                    Return Tuple.Create(True, Tuple.Create("0,2", "R"c, If(isValid({i(1, 0), i(1, 3)}), 4, 3)))
                ElseIf isValid({i(0, 0), i(1, 0), i(2, 1)}) Then
                    Return Tuple.Create(True, Tuple.Create("2,1", "U"c, 3))
                ElseIf isValid({i(0, 1), i(1, 1), i(2, 0)}) Then
                    Return Tuple.Create(True, Tuple.Create("2,0", "D"c, 3))
                End If
            Case "3C,3R"
                If isValid({i(0, 0), i(0, 1), i(1, 2)}) Then
                    Return Tuple.Create(True, Tuple.Create("1,2", "L"c, 3))
                ElseIf isValid({i(1, 0), i(1, 1), i(0, 2)}) Then
                    Return Tuple.Create(True, Tuple.Create("0,2", "R"c, 3))
                ElseIf isValid({i(0, 0), i(1, 0), i(2, 1)}) Then
                    Return Tuple.Create(True, Tuple.Create("2,1", "U"c, 3))
                ElseIf isValid({i(0, 1), i(1, 1), i(2, 0)}) Then
                    Return Tuple.Create(True, Tuple.Create("2,0", "D"c, 3))
                End If
            Case "3C,2R"
                If isValid({i(0, 0), i(1, 0), i(2, 1)}) Then
                    Return Tuple.Create(True, Tuple.Create("2,1", "U"c, 3))
                ElseIf isValid({i(0, 1), i(1, 1), i(2, 0)}) Then
                    Return Tuple.Create(True, Tuple.Create("2,0", "D"c, 3))
                End If
            Case "2C,4R"
                If isValid({i(0, 0), i(0, 1), i(1, 1)}) Then
                    Return Tuple.Create(True, Tuple.Create("1,1", "L"c, If(isValid({i(0, 1), i(0, 3)}), 4, 3)))
                ElseIf isValid({i(1, 0), i(1, 1), i(0, 2)}) Then
                    Return Tuple.Create(True, Tuple.Create("0,2", "R"c, If(isValid({i(1, 0), i(1, 3)}), 4, 3)))
                End If
            Case "2C,3R"
                If isValid({i(0, 0), i(0, 1), i(1, 1)}) Then
                    Return Tuple.Create(True, Tuple.Create("1,1", "L"c, 3))
                ElseIf isValid({i(1, 0), i(1, 1), i(0, 2)}) Then
                    Return Tuple.Create(True, Tuple.Create("0,2", "R"c, 3))
                End If
        End Select

        Return Tuple.Create(False, Tuple.Create("None", "."c, 0))
    End Function

    Function IsMatchOnSecond(ByVal input As Integer(,)) As Tuple(Of Boolean, Tuple(Of String, Char, Integer))
        Dim i = input
        Dim isValid = Function(test As Integer()) test.All(Function(v) v = test(0))
        Dim xLength = input.GetLength(0)
        Dim yLength = input.GetLength(1)

        If xLength >= 3 AndAlso yLength >= 3 Then
            If isValid({i(0, 0), i(1, 1), i(0, 2)}) Then
                Return Tuple.Create(True, Tuple.Create("1,1", "L"c, 3))
            ElseIf isValid({i(1, 0), i(2, 1), i(1, 2)}) Then
                Return Tuple.Create(True, Tuple.Create("2,1", "L"c, 3))
            ElseIf isValid({i(1, 0), i(0, 1), i(1, 2)}) Then
                Return Tuple.Create(True, Tuple.Create("0,1", "R"c, 3))
            ElseIf isValid({i(2, 0), i(1, 1), i(2, 2)}) Then
                Return Tuple.Create(True, Tuple.Create("1,1", "R"c, 3))
            ElseIf isValid({i(0, 0), i(1, 1), i(2, 0)}) Then
                Return Tuple.Create(True, Tuple.Create("1,1", "U"c, 3))
            ElseIf isValid({i(0, 1), i(1, 2), i(2, 1)}) Then
                Return Tuple.Create(True, Tuple.Create("1,2", "U"c, 3))
            ElseIf isValid({i(0, 2), i(1, 1), i(2, 2)}) Then
                Return Tuple.Create(True, Tuple.Create("1,1", "D"c, 3))
            ElseIf isValid({i(0, 1), i(1, 0), i(2, 1)}) Then
                Return Tuple.Create(True, Tuple.Create("1,0", "D"c, 3))
            End If
        End If

        Return Tuple.Create(False, Tuple.Create("None", "."c, 0))
    End Function

    Private Function IsMatchOnFirst(ByVal input As Integer(,)) As Tuple(Of Boolean, Tuple(Of String, Char, Integer)) '<-- New method
        Dim i = input
        Dim isValid = Function(test As Integer()) test.All(Function(v) v = test(0))
        Dim xLength = input.GetLength(0)
        Dim yLength = input.GetLength(1)

        If xLength >= 3 AndAlso yLength >= 3 Then
            If isValid({i(0, 0), i(1, 1), i(1, 2)}) Then
                Return Tuple.Create(True, Tuple.Create("0,0", "R"c, 3))
            ElseIf isValid({i(1, 0), i(2, 1), i(2, 2)}) Then
                Return Tuple.Create(True, Tuple.Create("1,0", "R"c, 3))
            ElseIf isValid({i(2, 0), i(1, 1), i(1, 2)}) Then
                Return Tuple.Create(True, Tuple.Create("2,0", "L"c, 3))
            ElseIf isValid({i(1, 0), i(0, 1), i(0, 2)}) Then
                Return Tuple.Create(True, Tuple.Create("1,0", "L"c, 3))
            ElseIf isValid({i(0, 0), i(1, 1), i(2, 1)}) Then
                Return Tuple.Create(True, Tuple.Create("0,0", "D"c, 3))
            ElseIf isValid({i(0, 1), i(1, 2), i(2, 2)}) Then
                Return Tuple.Create(True, Tuple.Create("0,1", "D"c, 3))
            ElseIf isValid({i(0, 1), i(1, 0), i(2, 0)}) Then
                Return Tuple.Create(True, Tuple.Create("0,1", "U"c, 3))
            ElseIf isValid({i(0, 2), i(1, 1), i(2, 1)}) Then
                Return Tuple.Create(True, Tuple.Create("0,2", "U"c, 3))
            End If
        End If

        Return Tuple.Create(False, Tuple.Create("None", "."c, 0))
    End Function
End Module

这是我使用的元组类。
顺便说一句：我将它从 C# 转换为 VB.NET，来自 StackOverflow

Imports System.Collections.Generic

Public Class Tuple(Of T1, T2, T3)
    Inherits Tuple(Of T1, T2)
    Implements IEqualityComparer(Of Tuple(Of T1, T2, T3))

    Private _third As T3

    Public Sub New(ByVal item1 As T1, ByVal item2 As T2, ByVal item3 As T3)
        MyBase.New(item1, item2)
        _third = item3
    End Sub

    Public Property Item3() As T3
        Get
            Return _third
        End Get
        Private Set(ByVal value As T3)
            _third = value
        End Set
    End Property

    Public Overloads Function Equals(ByVal x As Tuple(Of T1, T2, T3), ByVal y As Tuple(Of T1, T2, T3)) As Boolean Implements IEqualityComparer(Of Tuple(Of T1, T2, T3)).Equals
        Return EqualityComparer(Of T1).[Default].Equals(x.Item1, y.Item1) AndAlso EqualityComparer(Of T2).[Default].Equals(x.Item2, y.Item2) AndAlso EqualityComparer(Of T3).[Default].Equals(x.Item3, y.Item3)
    End Function

    Public Overrides Function Equals(ByVal obj As Object) As Boolean
        Return TypeOf obj Is Tuple(Of T1, T2, T3) AndAlso Equals(Me, DirectCast(obj, Tuple(Of T1, T2, T3)))
    End Function

    Public Overloads Function GetHashCode(ByVal obj As Tuple(Of T1, T2, T3)) As Integer Implements IEqualityComparer(Of Tuple(Of T1, T2, T3)).GetHashCode
        Return EqualityComparer(Of T1).[Default].GetHashCode(Item1) Xor EqualityComparer(Of T2).[Default].GetHashCode(Item2) Xor EqualityComparer(Of T3).[Default].GetHashCode(Item3)
    End Function

    Public Shared Shadows Operator =(ByVal left As Tuple(Of T1, T2, T3), ByVal right As Tuple(Of T1, T2, T3)) As Boolean
        If DirectCast(left, Object) Is Nothing AndAlso DirectCast(right, Object) Is Nothing Then
            Return True
        End If

        Return left.Equals(right)
    End Operator

    Public Shared Shadows Operator <>(ByVal left As Tuple(Of T1, T2, T3), ByVal right As Tuple(Of T1, T2, T3)) As Boolean
        If DirectCast(left, Object) Is Nothing AndAlso DirectCast(right, Object) Is Nothing Then
            Return False
        End If

        Return Not left.Equals(right)
    End Operator
End Class

Public Class Tuple(Of T1, T2)
    Implements IEqualityComparer(Of Tuple(Of T1, T2))

    Public Property Item1() As T1
        Get
            Return _first
        End Get
        Private Set(ByVal value As T1)
            _first = value
        End Set
    End Property
    Private _first As T1

    Public Property Item2() As T2
        Get
            Return _second
        End Get
        Private Set(ByVal value As T2)
            _second = value
        End Set
    End Property
    Private _second As T2

    Public Sub New(ByVal item1 As T1, ByVal item2 As T2)
        _first = item1
        _second = item2
    End Sub

    Public Overloads Function Equals(ByVal x As Tuple(Of T1, T2), ByVal y As Tuple(Of T1, T2)) As Boolean Implements IEqualityComparer(Of Tuple(Of T1, T2)).Equals
        Return EqualityComparer(Of T1).[Default].Equals(x.Item1, y.Item1) AndAlso EqualityComparer(Of T2).[Default].Equals(x.Item2, y.Item2)
    End Function

    Public Overrides Function Equals(ByVal obj As Object) As Boolean
        Return TypeOf obj Is Tuple(Of T1, T2) AndAlso Equals(Me, DirectCast(obj, Tuple(Of T1, T2)))
    End Function

    Public Overloads Function GetHashCode(ByVal obj As Tuple(Of T1, T2)) As Integer Implements IEqualityComparer(Of Tuple(Of T1, T2)).GetHashCode
        Return EqualityComparer(Of T1).[Default].GetHashCode(Item1) Xor EqualityComparer(Of T2).[Default].GetHashCode(Item2)
    End Function

    Public Shared Operator =(ByVal left As Tuple(Of T1, T2), ByVal right As Tuple(Of T1, T2)) As Boolean
        If DirectCast(left, Object) Is Nothing AndAlso DirectCast(right, Object) Is Nothing Then
            Return True
        End If

        Return left.Equals(right)
    End Operator

    Public Shared Operator <>(ByVal left As Tuple(Of T1, T2), ByVal right As Tuple(Of T1, T2)) As Boolean
        If DirectCast(left, Object) Is Nothing AndAlso DirectCast(right, Object) Is Nothing Then
            Return False
        End If

        Return Not left.Equals(right)
    End Operator
End Class

Public MustInherit Class Tuple
    <DebuggerStepThrough()> _
    Public Shared Function Create(Of T1, T2)(ByVal first As T1, ByVal second As T2) As Tuple(Of T1, T2)
        Return New Tuple(Of T1, T2)(first, second)
    End Function

    <DebuggerStepThrough()> _
    Public Shared Function Create(Of T1, T2, T3)(ByVal first As T1, ByVal second As T2, ByVal third As T3) As Tuple(Of T1, T2, T3)
        Return New Tuple(Of T1, T2, T3)(first, second, third)
    End Function

End Class

运行该应用程序会给出以下输出：

INPUT:
   |  A  B  C  D  E  F  G  H
---+------------------------
  1|  1  3  2  4  1  1  2  1
  2|  1  2  5  3  2  1  3  4
  3|  2  1  5  4  3  2  5  4
  4|  3  5  1  5  2  4  1  2
  5|  4  2  5  1  5  2  4  2
  6|  2  3  2  2  5  1  3  1
  7|  2  1  5  4  3  2  5  4
  8|  3  5  1  3  2  4  1  2


SOLUTION:
Move B4 R for a match of 4
Move D4 L for a match of 4
Move B3 L for a match of 3
Move B5 D for a match of 3
Move C3 D for a match of 3
Move C5 U for a match of 3
Move D4 D for a match of 3
Move E4 R for a match of 3
Move F3 L for a match of 3

该程序可以与任何板尺寸配合使用。该程序基于我在游戏中搜索匹配的方式（我认为这是暴力）。

编辑
看来求解器无法在第一个宝石上找到匹配项（请参见下面的示例）。

5, 2, 5
2, 5, 3
1, 5, 4

如果该算法应用于上面的示例，则不会找到匹配项。

我现在已经解决了这个问题。现在有一个 IsMatchOnFirst() 方法来处理这些情况。
请参阅更新后的代码以了解更改。

Answer 2

您希望在一行中包含三个（或更多）数字，因此请执行以下操作：

• 对于每个找到的行，在一行中扫描两个（或更多）相同的数字
• ，检查两端的邻居是否包含会增加的元素 如果你发现了一些东西
• ，你就可以移动并完成了

该行邻域的定义如下：

    0
   0x0   x is the central point, 0 are the neighbours.
    0

例如

_____
__0__   0 represents the line found
__0__
_X___   X represents the element that would augment the line.
_____