数独游戏求解：解法适用于任意阶数的数独

02月

329 0 0

　　2）9阶（可填数字范围1~9，宫格3阶）

　　3）16阶（可填数字范围1~16，宫格4阶）

　　*见附录

　　1、数独的表示

　　对于N阶数独可以用一个N*N的二维数组表示

　　1）数独阶数GridRank=N

　　2）宫格阶数SubGridRank=Sqrt(N)

　　3）数独包含宫的阶数SubGridIncludeRank=Sqrt(N)

　　4）可填最大数字MaxValue=N

　　5）可填最小数字MinValue=1

Public Class SudokuClass
Public Property Rank As Integer 数独的阶数
Get
Return GridRank
End Get
Set(ByVal value As Integer)
GridRank = value
SubGridRank = CType(Math.Sqrt(value), Integer)
SubGridIncludeRank = SubGridRank
DataMaxValue = value
DataMinValue = 1
End Set
End Property
Public Property GridData As Integer?(,) 数独的数据
Private GridRank As Integer 数独的阶数
Private SubGridRank As Integer 子数独(宫)的阶数
Private SubGridIncludeRank As Integer 数独包含子数独(宫)的阶数
Private DataMaxValue As Integer 数独可填最大数值
Private DataMinValue As Integer 数独可填最小数值
<summary>
实例化一个指定阶数的数独类
</summary>
<param name=nRank>指定的阶数</param>
Public Sub New(nRank As Integer)
Me.Rank = nRank
End Sub
End Class

　　2）VB.NET类 C#类(在线工具转换，仅供参考）

Public Class SudokuClass
- Public Property Rank As Integer 数独的阶数
  - Get
    - Return GridRank
      - End Get
        Set(ByVal value As Integer)
        GridRank = value
        SubGridRank = CType(Math.Sqrt(value), Integer)
        SubGridIncludeRank = SubGridRank
        DataMaxValue = value
        DataMinValue = 1
        End Set
        End Property
        Public Property GridData As Integer?(,) 数独的数据
        Private GridRank As Integer 数独的阶数
        Private SubGridRank As Integer 子数独(宫)的阶数
        Private SubGridIncludeRank As Integer 数独包含子数独(宫)的阶数
        Private DataMaxValue As Integer 数独可填最大数值
        Private DataMinValue As Integer 数独可填最小数值
        <summary>
        实例化一个指定阶数的数独类
        </summary>
        <param name=nRank>指定的阶数</param>
        Public Sub New(nRank As Integer)
        Me.Rank = nRank
        End Sub
        
        Public Function GenerateInitialNumbers() As Integer?(,)
        ReDim GridData(GridRank - 1, GridRank - 1)
        For i = 0 To GridRank - 1
        For j = 0 To GridRank - 1
        GridData(i, j) = 0 暂无初始数字生成规则，请从数独文件导入
        Next
        Next
        Return GridData 返回一个空白数独
        End Function
        
        Public Function IsImpossible(ByVal Numbers As Integer?(,)) As Boolean
        Dim temp As Integer?
        For i = 0 To GridRank - 1
        For j = 0 To GridRank - 1
        If Not Numbers(i, j) = 0 Then
        temp = Numbers(i, j)
        Numbers(i, j) = 0
        If GetExisting(Numbers, i, j, CInt(temp)) Then Numbers(i, j) = temp : Return True
        Numbers(i, j) = temp
        End If
        Next
        Next
        Return False
        End Function
        Public Function IsWin(ByVal Numbers As Integer?(,)) As Boolean
        For i = 0 To GridRank - 1
        For j = 0 To GridRank - 1
        If Not Numbers(i, j).HasValue Then Return False 出现空格
        Next
        Next
        Dim TempInt As New List(Of Integer)
        判断行重复
        For i = 0 To GridRank - 1
        TempInt.Clear()
        For j = 0 To GridRank - 1
        TempInt.Add(CInt(Numbers(i, j)))
        Next
        If IsDuplicate(TempInt.ToArray) Then Return False
        Next
        判断列重复
        For j = 0 To GridRank - 1
        TempInt.Clear()
        For i = 0 To GridRank - 1
        TempInt.Add(CInt(Numbers(i, j)))
        Next
        If IsDuplicate(TempInt.ToArray) Then Return False
        Next
        判断宫格重复
        For i = 0 To GridRank - 1 Step SubGridRank
        For j = 0 To GridRank - 1 Step SubGridRank
        TempInt.Clear()
        For i2 = 0 To SubGridRank - 1
        For j2 = 0 To SubGridRank - 1
        TempInt.Add(CInt(Numbers(i + i2, j + j2)))
        Next
        Next
        If IsDuplicate(TempInt.ToArray) Then Return False
        Next
        Next
        Return True
        End Function
        <summary>
        判断一个序列是否有重复数字
        </summary>
        <param name=Numbers></param>
        <returns></returns>
        Private Function IsDuplicate(ByVal Numbers() As Integer) As Boolean
        Array.Sort(Numbers)
        If Numbers.Length > 1 Then
        For i = 0 To Numbers.Length - 2
        If Numbers(i) = Numbers(i + 1) Then Return True
        Next
        End If
        Return False
        End Function
        <summary>
        返回指定位置的所有可填数字的序列
        </summary>
        <param name=Numbers>原数组</param>
        <param name=gX>指定的位置的X值，从0开始</param>
        <param name=gY>指定的位置的Y值，从0开始</param>
        <returns></returns>
        Public Function GetEnabledNum(ByVal Numbers As Integer?(,), gX As Integer, gY As Integer) As Integer()
        Dim NumList As New List(Of Integer)
        For i = DataMinValue To DataMaxValue
        If GetExisting(Numbers, gX, gY, i) = False Then NumList.Add(i)
        Next
        Return NumList.ToArray
        End Function
        递归求解数独
        Private Function GetValue(ByVal gData As Integer?(,)) As List(Of Integer?(,))
        Dim ResultList As New List(Of Integer?(,))
        Dim i, j As Integer
        Dim tempPoint As Point = getStartPoint(gData)
        i = tempPoint.X : j = tempPoint.Y
        If i >= 0 AndAlso j >= 0 Then
        For value = DataMinValue To DataMaxValue
        If GetExisting(gData, i, j, value) = False Then
        gData(i, j) = value
        GetValue(gData)
        gData(i, j) = 0

标签：魔兽开发经验爬坑游戏开发者开发技术游戏开发论坛

你还没有登录，请先登录或注册！

还没有人评论，欢迎说说您的想法！