最近在上《最優(yōu)化理論》這一門課，課后老師布置一道課后作業(yè)---“使用啟發(fā)式搜索算法求解9*9數(shù)獨問題”英上。采用“回溯算法”和“啟發(fā)式搜索算法”兩種算法進行求解并進行比較，回溯法用C++實現(xiàn)啤覆，啟發(fā)式方法用python實現(xiàn)苍日。
1數(shù)獨規(guī)則及題目
數(shù)獨的規(guī)則：
-
填入空格（即下圖數(shù)獨中值為0的格子）中的數(shù)滿足使每一行、每一列窗声、每一個宮內的均含有數(shù)字1-9且不重復相恃。
數(shù)獨題目
2使用回溯算法求解
(1) 思路：
對于給定的數(shù)獨按照從左到右從上到下的順序進行搜索求解空格的值，對每一個空格首先取出空格處的值(假設每一個空格處的初始值為0)賦給變量m笨觅，然后令m=m+1拦耐。判斷m是否大于9，若大于9則將空格處的值賦0然后退回到前一個空格见剩；若不大于9則繼續(xù)判斷m是否滿足數(shù)獨規(guī)則杀糯，若滿足規(guī)則將此時的值m添入空格并移動到下一個空格，若不滿足規(guī)則就令m=m+1,繼續(xù)判斷m是否大于9苍苞。直到填完最后一個空格則求解完成固翰。
(2)具體的流程圖如下：
回溯法流程圖
(3)代碼實現(xiàn)如下：
代碼結構：
初始化函數(shù)-InitiFun
判段當前值是否滿足數(shù)獨規(guī)則函數(shù)-DetermValue
求解函數(shù)-Reslove
顯示結果的函數(shù)-ShowResult
- 函數(shù)的頭文件-headfile.h
#pragma once
#include<vector>
std::vector<std::pair<int, int>> InitiFun(int(*Sokudu)[9], int&NumofZero);//初始化函數(shù)
int DetermValue(int x, int y, int m, int(*Soduku)[9]);//判斷函數(shù)
int Reslove(int(*Sokudu)[9], std::vector<std::pair<int, int>>&Coord, int&NumofZero, int&Count);//求解函數(shù)
void ShowResult(int(*ResultSokudu)[9], int result);//顯示函數(shù)
- 函數(shù)的源碼-source.cpp
#include"pch.h"
#include<iostream>
#include"headfile.h"
//判斷是否滿足數(shù)獨的規(guī)則
int DetermValue(int x, int y, int m, int(*Soduku)[9])
{
int x0, y0;
x0 = x / 3;
y0 = y / 3;
//橫向判斷是否滿足規(guī)則
for (int i = 0; i < 9; i++)
{
if (m == Soduku[x][i])
return 0;
}
//縱向判斷是否滿足規(guī)則
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;
}
//初始化函數(shù)返回所有空格處的位置
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;
}
//求解數(shù)獨
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;
}
//顯示數(shù)獨的結果
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 << "數(shù)獨無解\n";
}
- 主函數(shù)-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為需要填空的總數(shù),Count記錄總的走的步數(shù)
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 << "迭代的次數(shù)為" << Count << "\n"
<<"需要填寫的數(shù)字個數(shù)為"<<NumofZero<<"\n";
ShowResult(Sokudu, result);
}
(4)求解結果
求解結果
3啟發(fā)式搜索算法求解
(1)思路
我們在手算數(shù)獨的時候一般先算出所有空格的候選數(shù)，然后找到候選數(shù)個數(shù)最少的位置開始搜索羹呵，如果在開始時存在一個空格的候選數(shù)個數(shù)為一骂际，那么這個數(shù)一定為該空格處的值。所以我們在每一步中按照候選數(shù)的個數(shù)最少的路徑開始搜索担巩，這樣會在一定程度上減少搜索的次數(shù)方援。
具體步驟如下：
- 判斷Sokudu是否有空格
- 若有空格則求出所有空格處的候選數(shù)
找到候選數(shù)個數(shù)最小的空格没炒，判斷最小的候選數(shù)個數(shù)是否為零涛癌，若最小的候選數(shù)個數(shù)不為零則取出該候選數(shù)的第一項賦給該空格，并將取出第一項后剩下的候選數(shù)以及該空格的位置分別記錄下來分別保存到PopList列表及PopCoord列表的尾部送火，然后繼續(xù)判斷Sokudu是否有空格拳话。若最小的候選數(shù)個數(shù)為零，則判斷PopList列表的最后一項是否為空种吸，若為空則刪除PopList列表PopCoord列表的最后一項弃衍，接著判斷PopList列表的最后一項是否為空。若不為空則取出Poplist列表最后一項的的第一項賦給PopCoord最后一項位置處對應的數(shù)獨的值坚俗，然后繼續(xù)判斷Sokudu是否有空格镜盯。 - 若無空格則輸出結果
(2)具體流程圖
啟發(fā)式搜索算法流程圖
(3)代碼
代碼結構：
計算所有空格的位置及個數(shù)-Locat_Zero
計算所有空格的候補數(shù)列表-Compute_Cadida
計算最小候選數(shù)個數(shù)的位置-Find_Min
求解數(shù)獨函數(shù)-Solve_Sokudu
顯示結果函數(shù)-Show_Result
- sokudu.py
import array
def Locat_Zero(Sokudu):
#計算所有空格的位置及個數(shù)
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):
#計算所有空格的候補數(shù)列表
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):
#找到最小的候選數(shù)個數(shù)的位置
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):
#計算需要填空的坐標及個數(shù):坐標列表:Coord,個數(shù):Count
Coord,Count=Locat_Zero(Sokudu)
TotalCount=0
#彈出的候選數(shù)列表
PopCandidaList=[]
#彈出的坐標列表
PopCoordList=[]
while Count:
#計算需要填空的候補列表:Candidalist
CandidaList=Compute_Cadida(Coord,Count,Sokudu)
#計算最小的候選數(shù)個數(shù)的位置
Min,MinIndex,MinCoord=Find_Min(CandidaList,Coord,Count)
if Min==0:
while len(PopCandidaList[-1])==0:
#上一個空格的坐標
x=PopCoordList[-1][0]
y=PopCoordList[-1][1]
#還原當前節(jié)點值
Sokudu[x][y]=0
Count=Count+1
Coord.append(PopCoordList[-1])
#刪除當前節(jié)點坐標及候選數(shù)列表
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位置處的候選數(shù)刪除候選數(shù)的第一項后放到彈出來的候選數(shù)列表中
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)結果
總的迭代步數(shù)為：444
計算結果
