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

一元 · 发表于 2016-2-17 11:55:36

　　GameRes游资网授权发布文/ExperDot

　　0、数独简介

　　数独（すうどく，Sūdoku）是一种运用纸、笔进行演算的逻辑游戏。以九阶数独为例，玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，不重复。

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

　　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

复制代码

　　6）任意阶数独的表示（N≠K2,K>1,K∈Z）

　　任意阶数独仅有一个宫，所以数独阶数和宫阶数相等。以7阶为例，设置GridRank=7,SubGridRank=7,SubGridIncludeRank=1即可。

　　2、数独的求解

　　采用回溯法，直接寻找到一个空白格，尝试填入所有可能的数字，继续填下一个空白格，直至填满或者不能继续填入为止（不符合规则）。

　　1）寻找空白格

　　空白格的选择至关重要，当一个格子的限制越多,也就是可填入数字越少时，优先选择该空白格。这样做可以大大降低递归填格子的次数。

'查找当前空白格(最佳格)
Private Function getStartPoint(ByRef data As Integer?(,)) As Point
Dim gPoint As Point
Dim tempValue As Integer
Dim maxValue As Integer
'查找限制最多的空白格
For i = 0 To GridRank - 1
For j = 0 To GridRank - 1
If data(i, j) = 0 Then
tempValue = 0
For k = 0 To GridRank - 1
If data(i, k) > 0 Then tempValue += 1
If data(k, j) > 0 Then tempValue += 1
If data((i \ SubGridIncludeRank) * SubGridIncludeRank + k \ SubGridIncludeRank, (j \ SubGridIncludeRank) * SubGridIncludeRank + (k Mod SubGridIncludeRank)) > 0 Then tempValue += 1
Next
If tempValue > maxValue Then
maxValue = tempValue
gPoint.X = i
gPoint.Y = j
End If
End If
Next
Next
If maxValue > 0 Then
Return gPoint
Else
gPoint.X = -1
gPoint.Y = -1
Return gPoint
End If
End Function

复制代码

　　当确定空白格后就需要向其中填入数字了，一一筛选出符合规则的数字。规则就是格子当前行，当前列，当前宫不能有相同数值出现。

'判断同行同列同宫是否已经存在
Private Function GetExisting(ByRef data As Integer?(,), ByVal gX As Integer, ByVal gY As Integer, ByVal gValue As Integer) As Boolean
For k = 0 To GridRank - 1
If data(gX, k) = gValue OrElse data(k, gY) = gValue OrElse data((gX \ SubGridIncludeRank) * SubGridIncludeRank + k \ SubGridIncludeRank, (gY \ SubGridIncludeRank) * SubGridIncludeRank + (k Mod SubGridIncludeRank)) = gValue Then
Return True
End If
Next
Return False
End Function

复制代码

　　2）回溯法求解

　　简单的递归调用即可。

'递归求解数独
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
End If
Next
Else
'新增一个结果
ResultList.Add(gData)
End If
Return ResultList
End Function

复制代码

　　3）其他

　　判断一个序列（数组）中是否有重复数字

''' <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

复制代码

　　判断数独是否填写完毕，无空白格且所有格子填入的数字符合规则

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

复制代码

　　判断当前数独是否符合规则，检查每一个非空白格的数字的同行、同列、同宫是否重复。

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

复制代码

　　附录

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

　　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
End If
Next
Else
'新增一个结果
ResultList.Add(gData)
End If
Return ResultList
End Function
'查找当前空白格(最佳格)
Private Function getStartPoint(ByRef data As Integer?(,)) As Point
Dim gPoint As Point
Dim tempValue As Integer
Dim maxValue As Integer
'查找限制最多的空白格
For i = 0 To GridRank - 1
For j = 0 To GridRank - 1
If data(i, j) = 0 Then
tempValue = 0
For k = 0 To GridRank - 1
If data(i, k) > 0 Then tempValue += 1
If data(k, j) > 0 Then tempValue += 1
If data((i \ SubGridIncludeRank) * SubGridIncludeRank + k \ SubGridIncludeRank, (j \ SubGridIncludeRank) * SubGridIncludeRank + (k Mod SubGridIncludeRank)) > 0 Then tempValue += 1
Next
If tempValue > maxValue Then
maxValue = tempValue
gPoint.X = i
gPoint.Y = j
End If
End If
Next
Next
If maxValue > 0 Then
Return gPoint
Else
gPoint.X = -1
gPoint.Y = -1
Return gPoint
End If
End Function
'判断同行同列同宫是否已经存在
Private Function GetExisting(ByRef data As Integer?(,), ByVal gX As Integer, ByVal gY As Integer, ByVal gValue As Integer) As Boolean
For k = 0 To GridRank - 1
If data(gX, k) = gValue OrElse data(k, gY) = gValue OrElse data((gX \ SubGridIncludeRank) * SubGridIncludeRank + k \ SubGridIncludeRank, (gY \ SubGridIncludeRank) * SubGridIncludeRank + (k Mod SubGridIncludeRank)) = gValue Then
Return True
End If
Next
Return False
End Function
End Class

复制代码

using Microsoft.VisualBasic;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Data;
using System.Diagnostics;
public class SudokuClass
{
public int Rank {
//数独的阶数
get { return GridRank; }
set {
GridRank = value;
SubGridRank = Convert.ToInt32(Math.Sqrt(value));
SubGridIncludeRank = SubGridRank;
DataMaxValue = value;
DataMinValue = 1;
}
}
public int?[,] GridData { get; set; }
//数独的数据
//数独的阶数
private int GridRank;
//子数独(宫)的阶数
private int SubGridRank;
//数独包含子数独(宫)的阶数
private int SubGridIncludeRank;
//数独可填最大数值
private int DataMaxValue;
//数独可填最小数值
private int DataMinValue;
/// <summary>
/// 实例化一个指定阶数的数独类
/// </summary>
/// <param name="nRank">指定的阶数</param>
public SudokuClass(int nRank)
{
this.Rank = nRank;
}
public int?[,] GenerateInitialNumbers()
{
GridData = new Nullable<int>[GridRank, GridRank];
for (i = 0; i <= GridRank - 1; i++) {
for (j = 0; j <= GridRank - 1; j++) {
GridData[i, j] = 0;
//暂无初始数字生成规则，请从数独文件导入
}
}
return GridData;
//返回一个空白数独
}
public bool IsImpossible(int?[,] Numbers)
{
int? temp = default(int?);
for (i = 0; i <= GridRank - 1; i++) {
for (j = 0; j <= GridRank - 1; j++) {
if (!(Numbers[i, j] == 0)) {
temp = Numbers[i, j];
Numbers[i, j] = 0;
if (GetExisting(ref Numbers, i, j, Convert.ToInt32(temp))){Numbers[i, j] = temp;return true;}
Numbers[i, j] = temp;
}
}
}
return false;
}
public bool IsWin(int?[,] Numbers)
{
for (i = 0; i <= GridRank - 1; i++) {
for (j = 0; j <= GridRank - 1; j++) {
if (!Numbers[i, j].HasValue)
return false;
//出现空格
}
}
List<int> TempInt = new List<int>();
//判断行重复
for (i = 0; i <= GridRank - 1; i++) {
TempInt.Clear();
for (j = 0; j <= GridRank - 1; j++) {
TempInt.Add(Convert.ToInt32(Numbers[i, j]));
}
if (IsDuplicate(TempInt.ToArray()))
return false;
}
//判断列重复
for (j = 0; j <= GridRank - 1; j++) {
TempInt.Clear();
for (i = 0; i <= GridRank - 1; i++) {
TempInt.Add(Convert.ToInt32(Numbers[i, j]));
}
if (IsDuplicate(TempInt.ToArray()))
return false;
}
//判断宫格重复
for (i = 0; i <= GridRank - 1; i += SubGridRank) {
for (j = 0; j <= GridRank - 1; j += SubGridRank) {
TempInt.Clear();
for (i2 = 0; i2 <= SubGridRank - 1; i2++) {
for (j2 = 0; j2 <= SubGridRank - 1; j2++) {
TempInt.Add(Convert.ToInt32(Numbers[i + i2, j + j2]));
}
}
if (IsDuplicate(TempInt.ToArray()))
return false;
}
}
return true;
}
/// <summary>
/// 判断一个序列是否有重复数字
/// </summary>
/// <param name="Numbers"></param>
/// <returns></returns>
private bool IsDuplicate(int[] Numbers)
{
Array.Sort(Numbers);
if (Numbers.Length > 1) {
for (i = 0; i <= Numbers.Length - 2; i++) {
if (Numbers[i] == Numbers[i + 1])
return true;
}
}
return false;
}
/// <summary>
/// 返回指定位置的所有可填数字的序列
/// </summary>
/// <param name="Numbers">原数组</param>
/// <param name="gX">指定的位置的X值，从0开始</param>
/// <param name="gY">指定的位置的Y值，从0开始</param>
/// <returns></returns>
public int[] GetEnabledNum(int?[,] Numbers, int gX, int gY)
{
List<int> NumList = new List<int>();
for (i = DataMinValue; i <= DataMaxValue; i++) {
if (GetExisting(ref Numbers, gX, gY, i) == false)
NumList.Add(i);
}
return NumList.ToArray();
}
//递归求解数独
private List<int?[,]> GetValue(int?[,] gData)
{
List<int?[,]> ResultList = new List<int?[,]>();
int i = 0;
int j = 0;
Point tempPoint = getStartPoint(ref gData);
i = tempPoint.X;
j = tempPoint.Y;
if (i >= 0 && j >= 0) {
for (value = DataMinValue; value <= DataMaxValue; value++) {
if (GetExisting(ref gData, i, j, value) == false) {
gData[i, j] = value;
GetValue(gData);
gData[i, j] = 0;
}
}
} else {
//新增一个结果
ResultList.Add(gData);
}
return ResultList;
}
//查找当前空白格(最佳格)
private Point getStartPoint(ref int?[,] data)
{
Point gPoint = default(Point);
int tempValue = 0;
int maxValue = 0;
//查找限制最多的空白格
for (i = 0; i <= GridRank - 1; i++) {
for (j = 0; j <= GridRank - 1; j++) {
if (data[i, j] == 0) {
tempValue = 0;
for (k = 0; k <= GridRank - 1; k++) {
if (data[i, k] > 0)
tempValue += 1;
if (data[k, j] > 0)
tempValue += 1;
if (data[(i / SubGridIncludeRank) * SubGridIncludeRank + k / SubGridIncludeRank, (j / SubGridIncludeRank) * SubGridIncludeRank + (k % SubGridIncludeRank)] > 0)
tempValue += 1;
}
if (tempValue > maxValue) {
maxValue = tempValue;
gPoint.X = i;
gPoint.Y = j;
}
}
}
}
if (maxValue > 0) {
return gPoint;
} else {
gPoint.X = -1;
gPoint.Y = -1;
return gPoint;
}
}
//判断同行同列同宫是否已经存在
private bool GetExisting(ref int?[,] data, int gX, int gY, int gValue)
{
for (k = 0; k <= GridRank - 1; k++) {
if (data[gX, k] == gValue || data[k, gY] == gValue || data[(gX / SubGridIncludeRank) * SubGridIncludeRank + k / SubGridIncludeRank, (gY / SubGridIncludeRank) * SubGridIncludeRank + (k % SubGridIncludeRank)] == gValue) {
return true;
}
}
return false;
}
}

复制代码

相关阅读：对弈类游戏的人工智能设计(4)——游戏AI的落地

账号		自动登录	找回密码
密码			立即注册

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

相关帖子