最近在上《最优化理论》这一门课，课后老师布置一道课后作业---“使用启发式搜索算法求解9*9数独问题”。采用“回溯算法”和“启发式搜索算法”两种算法进行求解并进行比较，回溯法用C++实现，启发式方法用python实现。
1数独规则及题目
数独的规则：
-
填入空格（即下图数独中值为0的格子）中的数满足使每一行、每一列、每一个宫内的均含有数字1-9且不重复。
数独题目
2使用回溯算法求解
(1) 思路：
对于给定的数独按照从左到右从上到下的顺序进行搜索求解空格的值，对每一个空格首先取出空格处的值(假设每一个空格处的初始值为0)赋给变量m，然后令m=m+1。判断m是否大于9，若大于9则将空格处的值赋0然后退回到前一个空格；若不大于9则继续判断m是否满足数独规则，若满足规则将此时的值m添入空格并移动到下一个空格，若不满足规则就令m=m+1,继续判断m是否大于9。直到填完最后一个空格则求解完成。
(2)具体的流程图如下：
回溯法流程图
(3)代码实现如下：
代码结构：
初始化函数-InitiFun
判段当前值是否满足数独规则函数-DetermValue
求解函数-Reslove
显示结果的函数-ShowResult
- 函数的头文件-headfile.h
#pragma once
#include<vector>
std::vector<std::pair<int, int>> InitiFun(int(*Sokudu)[9], int&NumofZero);//初始化函数
int DetermValue(int x, int y, int m, int(*Soduku)[9]);//判断函数
int Reslove(int(*Sokudu)[9], std::vector<std::pair<int, int>>&Coord, int&NumofZero, int&Count);//求解函数
void ShowResult(int(*ResultSokudu)[9], int result);//显示函数
- 函数的源码-source.cpp
#include"pch.h"
#include<iostream>
#include"headfile.h"
//判断是否满足数独的规则
int DetermValue(int x, int y, int m, int(*Soduku)[9])
{
int x0, y0;
x0 = x / 3;
y0 = y / 3;
//横向判断是否满足规则
for (int i = 0; i < 9; i++)
{
if (m == Soduku[x][i])
return 0;
}
//纵向判断是否满足规则
for (int i = 0; i < 9; i++)
{
if (m == Soduku[i][y])
return 0;
}
//宫内判断是否满足条件
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
if (m == Soduku[x0 * 3 + i][y0 * 3 + j])
return 0;
}
}
return 1;
}
//初始化函数返回所有空格处的位置
std::vector<std::pair<int, int>> InitiFun(int(*Sokudu)[9], int&NumofZero)
{
//定义局部的vector故不能返回vector的引用
std::vector<std::pair<int, int>>Coord;
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
if (Sokudu[i][j] == 0)
{
Coord.push_back(std::make_pair(i, j));
NumofZero++;
}
}
}
return Coord;
}
//求解数独
int Reslove(int(*Sokudu)[9], std::vector<std::pair<int, int>>&Coord, int&NumofZero, int&Count)
{
int i = 0;
int X, Y, M;
while (i < NumofZero&&i >= 0)
{
X = Coord[i].first;
Y = Coord[i].second;
M = Sokudu[X][Y];
while (1)
{
M++;
if (M > 9)
{
Sokudu[X][Y] = 0;
i--;
Count++;
break;
}
else
{
if (DetermValue(X, Y, M, Sokudu))
{
Sokudu[X][Y] = M;
i++;
Count++;
break;
}
}
}
}
return i;
}
//显示数独的结果
void ShowResult(int(*ResultSokudu)[9], int result)
{
if (result != -1)
{
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
std::cout << ResultSokudu[i][j] << "\t";
}
std::cout << "\n";
}
}
else
std::cout << "数独无解\n";
}
- 主函数-sodukumain.cpp
#include "pch.h"
#include <iostream>
#include"headfile.h"
int main()
{
int Sokudu[9][9] =
{
{0,0,5,3,0,0,0,0,0},
{8,0,0,0,0,0,0,2,0},
{0,7,0,0,1,0,5,0,0},
{4,0,0,0,0,5,3,0,0},
{0,1,0,0,7,0,0,0,6},
{0,0,3,2,0,0,0,8,0},
{0,6,0,5,0,0,0,0,9},
{0,0,4,0,0,0,0,3,0},
{0,0,0,0,0,9,7,0,0}
};
//NumofZero为需要填空的总数,Count记录总的走的步数
int i=0, NumofZero=0, Count=0;
//进行初始化
std::vector<std::pair<int,int>>Coord = InitiFun(Sokudu, NumofZero);
//进行计算
int result = Reslove(Sokudu, Coord, NumofZero, Count);
std::cout << "迭代的次数为" << Count << "\n"
<<"需要填写的数字个数为"<<NumofZero<<"\n";
ShowResult(Sokudu, result);
}
(4)求解结果
求解结果
3启发式搜索算法求解
(1)思路
我们在手算数独的时候一般先算出所有空格的候选数，然后找到候选数个数最少的位置开始搜索，如果在开始时存在一个空格的候选数个数为一，那么这个数一定为该空格处的值。所以我们在每一步中按照候选数的个数最少的路径开始搜索，这样会在一定程度上减少搜索的次数。
具体步骤如下：
- 判断Sokudu是否有空格
- 若有空格则求出所有空格处的候选数
找到候选数个数最小的空格，判断最小的候选数个数是否为零，若最小的候选数个数不为零则取出该候选数的第一项赋给该空格，并将取出第一项后剩下的候选数以及该空格的位置分别记录下来分别保存到PopList列表及PopCoord列表的尾部，然后继续判断Sokudu是否有空格。若最小的候选数个数为零，则判断PopList列表的最后一项是否为空，若为空则删除PopList列表PopCoord列表的最后一项，接着判断PopList列表的最后一项是否为空。若不为空则取出Poplist列表最后一项的的第一项赋给PopCoord最后一项位置处对应的数独的值，然后继续判断Sokudu是否有空格。 - 若无空格则输出结果
(2)具体流程图
启发式搜索算法流程图
(3)代码
代码结构：
计算所有空格的位置及个数-Locat_Zero
计算所有空格的候补数列表-Compute_Cadida
计算最小候选数个数的位置-Find_Min
求解数独函数-Solve_Sokudu
显示结果函数-Show_Result
- sokudu.py
import array
def Locat_Zero(Sokudu):
#计算所有空格的位置及个数
Count=0
Coord=[]
for X in range(9):
for Y in range(9):
if Sokudu[X][Y]==0:
CoordXY=[]
CoordXY.append(X)
CoordXY.append(Y)
Coord.append(CoordXY)
Count=Count+1
return Coord,Count
def Compute_Cadida(Coord,Count,Sokudu):
#计算所有空格的候补数列表
CandidaList=[]
for i in range(Count):
Num=[1,2,3,4,5,6,7,8,9]
x=Coord[i][0]
y=Coord[i][1]
x0=int(x/3)
y0=int(y/3)
for j in range(9):
if Sokudu[x][j] in Num:
Num.remove(Sokudu[x][j])
for k in range(9):
if Sokudu[k][y] in Num:
Num.remove(Sokudu[k][y])
for m in range(3):
for n in range(3):
if Sokudu[x0*3+m][y0*3+n] in Num:
Num.remove(Sokudu[x0*3+m][y0*3+n])
CandidaList.append(Num)
return CandidaList
def Find_Min(CandidaList,Coord,Count):
#找到最小的候选数个数的位置
NumofCandida=[]
for i in range(Count):
temp=len(CandidaList[i])
NumofCandida.append(temp)
Min=min(NumofCandida)
MinIndex=NumofCandida.index(Min)
return Min,MinIndex,Coord[MinIndex]
def Solve_Sokudu(Sokudu):
#计算需要填空的坐标及个数:坐标列表:Coord,个数:Count
Coord,Count=Locat_Zero(Sokudu)
TotalCount=0
#弹出的候选数列表
PopCandidaList=[]
#弹出的坐标列表
PopCoordList=[]
while Count:
#计算需要填空的候补列表:Candidalist
CandidaList=Compute_Cadida(Coord,Count,Sokudu)
#计算最小的候选数个数的位置
Min,MinIndex,MinCoord=Find_Min(CandidaList,Coord,Count)
if Min==0:
while len(PopCandidaList[-1])==0:
#上一个空格的坐标
x=PopCoordList[-1][0]
y=PopCoordList[-1][1]
#还原当前节点值
Sokudu[x][y]=0
Count=Count+1
Coord.append(PopCoordList[-1])
#删除当前节点坐标及候选数列表
del PopCoordList[-1]
del PopCandidaList[-1]
#更改上一个空格位置处的值
x=PopCoordList[-1][0]
y=PopCoordList[-1][1]
Sokudu[x][y]=PopCandidaList[-1][0]
del PopCandidaList[-1][0]
TotalCount=TotalCount+1
else:
#更改MinCoord位置处空格的值
x=MinCoord[0]
y=MinCoord[1]
Sokudu[x][y]=CandidaList[MinIndex][0]
#取出MinCoord位置处的候选数删除候选数的第一项后放到弹出来的候选数列表中
PopCandida=CandidaList.pop(MinIndex)
del PopCandida[0]
PopCandidaList.append(PopCandida)
#取出MinCoord的位置放到弹出来的坐标列表中
PopCoord=Coord.pop(MinIndex)
PopCoordList.append(PopCoord)
Count=Count-1
TotalCount=TotalCount+1
return Sokudu,TotalCount
def Show_Result(Sokudu):
for i in range(9):
print(Sokudu[i])
- sukudumain.py
from numpy import*
from soduku import*
Sokudu=[
[0,0,5,3,0,0,0,0,0],
[8,0,0,0,0,0,0,2,0],
[0,7,0,0,1,0,5,0,0],
[4,0,0,0,0,5,3,0,0],
[0,1,0,0,7,0,0,0,6],
[0,0,3,2,0,0,0,8,0],
[0,6,0,5,0,0,0,0,9],
[0,0,4,0,0,0,0,3,0],
[0,0,0,0,0,9,7,0,0]]
Solve,TotalCount=Solve_Sokudu(Sokudu)
print("solve:")
Show_Result(Solve)
print(TotalCount)
(4)结果
总的迭代步数为：444
计算结果
