Matlab 编程实现数独的求解（一） |
您所在的位置：网站首页 › 数独游戏技巧和思路有哪些 › Matlab 编程实现数独的求解（一） |
Matlab 编程实现数独的求解（一）
|
数独是什么？这个我就直接从网上粘一段吧。 数独是一种风靡全球的智力游戏，也称为Sudoku，Number Place。正规的数独题目需要保证每个题目仅有一个解。 数独规则 标准数独由9行，9列共81的小格子构成。 分别在格子中填入1到9的数字，并满足下面的条件。 每一行都用到1,2,3,4,5,6,7,8,9每一列都用到1,2,3,4,5,6,7,8,9每3×3的格子都用到1,2,3,4,5,6,7,8,9 很多人多玩过数独，这个游戏简单但比较有趣，今天我试着用编程来解决这个问题，其实从大学时我就尝试过这个问题。那时候在参加大学生数学建模，好像第一次接触数独就是看到有一年美国大学生数学建模竞赛的试题就是有关数独的。因为美国大学生数学建模竞赛的试题一般是当前比较热点和比较前沿的综合型问题，而数独作为一道赛题，可见还是比较受大众欢迎的。因为当时也在学习Matlab,因此曾尝试用Matlab 编程来解决，当时基本实现了简单数独的求解，因为我想完全自己实现因此也没过网上有关求解数独的实现程序，请允许我当年有一颗年少而又自信和略有倔强的心。虽然几经周折，断断续续的写了代码，也基本简单实现了数独求解，但程序比较繁杂，后面有些其他事，比较难的数独求解程序也没写，再到后来这事就搁着没搞了，因此这个程序一直放在电脑里，去年整理文件又发现了这个，弄了一下，因为工作忙又搁置了，哎，拖延症害的。这段时间又在整理文件，又发现了这个事，因此抽了点时间来做个小的了结吧，顺便写个博客。 我先总体说一下求解思路，此程序主要利用了： 一、数独的基本规则(见上面数独规则)，然后求取三个方向(行、列、块或宫格)候选数的交集； 二、唯一数法，某个位置上的数在行、列、块或宫格具有唯一性，那么在其余两个方向(行、列、块或宫格)上要去除这个唯一数； 三、二连数， 当一个单元（行、列、宫）的某两个数字仅可能在某两格时，我们称这两个格为这两个数的数对。数对出现在宫称为宫数对；数对出现在行列成为行列数对。用候选数法的观点去看，数对有两种，一种是在同单元内其中两格有相同的双候选数，一看就明白，因此称为显性数对（Naked Pair），另一种是，同单元内有两个候选数占用了相同的两格，该两格因为还有其它候选数很难辨认，因此称为隐性数对（Hidden Pair）。 数独的解法这个网站：http://www.sudokufans.org.cn/forums/topic/69/ 说的比较全也很好。 此程序使用的是Matlab语言，其实那种语言，关系倒也不大，算法和思路才最重要的，当然这个游戏带来的快乐才是最最重要的。使用这个语言主要一是原先代码是Matlab的，二是Matlab 对这个做集合运算非常方便，不需自己编写过多的程序。下面就直接上代码得了，程序上有注解，只要熟悉Matlab语言的童鞋看懂没晒大问题的。 程序如下： 一、按基本规则处理然后求交集。 %%2017/11/12 by DengQi(DQ) %本程序是按照数独基本规则对每个位置可能候选数进行筛选，主要是在行列块上做交集 %进行上述筛选后的候选数只有少数几个数了，因此后续操作就简化了很多 function [PossibleData,PossibleDataNum] = BaseRule(Data) [m,n]=size(Data); BaseNumber=1:9; PossibleData=cell(m,n); PossibleDataNum=zeros(m,n); for i=1:m for j=1:n %原先有数的地方就不需对其操作 if Data(i,j)==0 %先沿着x方向 RowData={setdiff(BaseNumber,Data(i,:))}; %再沿着y方向 ColumnData={setdiff(BaseNumber,Data(:,j))}; %在3x3小块中 BlockX= (1+3*floor((i-1)/3)):(3+3*floor((i-1)/3)); BlockY= (1+3*floor((j-1)/3)):(3+3*floor((j-1)/3)); BlockData={setdiff(BaseNumber,Data(BlockX,BlockY))}; %求取三个方向数据的交集 Temp1=intersect(RowData{:},ColumnData{:}); Temp2=intersect(Temp1,BlockData{:}); PossibleData(i,j)={Temp2}; PossibleDataNum(i,j)=length(Temp2); end end end end 二、唯一数法。 %%2018/01/14 by DengQi(DQ) 修正了交集后只有一个数的情况 function [Data,PossibleData,PossibleDataNum,DataChange]=Row_Col_Block_DataUnique(Data,PossibleData,PossibleDataNum) %% 如果当前单元可能数据中有一个在行或列或小块中具有唯一性，那么当前单元的数据就是这个唯一性数据 DataChange=false; g=1:9; h=1:9; for i=1:9 for j=1:9 %此数据所在块坐标 BlockX= (1+3*floor((i-1)/3)):(3+3*floor((i-1)/3)); BlockY= (1+3*floor((j-1)/3)):(3+3*floor((j-1)/3)); if PossibleDataNum(i,j)==1 UniqueData=cell2mat(PossibleData(i,j)); Data(i,j)= UniqueData; DataChange=true; PossibleData(i,j)={[]}; PossibleDataNum(i,j)=0; [TempPossibleData,TempPossibleDataNum] =ExcludeRow_Col_BlockSame(PossibleData,PossibleDataNum,... UniqueData,i,j,BlockX,BlockY); PossibleData=TempPossibleData; PossibleDataNum=TempPossibleDataNum; elseif PossibleDataNum(i,j)>1 %% 行cell中数据唯一 ExceptItselfColIndex=setdiff(h,j); ExceptItselfRowCellData=cell2mat(PossibleData(i,ExceptItselfColIndex)); RowUniqueData=setdiff(PossibleData{i,j},ExceptItselfRowCellData); if length(RowUniqueData)==1 Data(i,j)= RowUniqueData; DataChange=true; PossibleData(i,j)={[]}; PossibleDataNum(i,j)=0; [TempPossibleData,TempPossibleDataNum] =ExcludeRow_Col_BlockSame(PossibleData,PossibleDataNum,... RowUniqueData,i,j,BlockX,BlockY); PossibleData=TempPossibleData; PossibleDataNum=TempPossibleDataNum; continue;%在行中唯一，在行列和块中其他地方去除后这个唯一数后，没必要在进行下面程序的操作，因为它是唯一的 end %% 列cell中数据唯一 ExceptItselfRowIndex=setdiff(g,i); ExceptItselfColCellData=cell2mat(PossibleData(ExceptItselfRowIndex,j)'); ColUniqueData=setdiff(PossibleData{i,j},ExceptItselfColCellData); if length(ColUniqueData)==1 Data(i,j)=ColUniqueData; DataChange=true; PossibleData(i,j)={[]}; PossibleDataNum(i,j)=0; [TempPossibleData,TempPossibleDataNum] =ExcludeRow_Col_BlockSame(PossibleData,PossibleDataNum,... ColUniqueData,i,j,BlockX,BlockY); PossibleData=TempPossibleData; PossibleDataNum=TempPossibleDataNum; continue; end %% 块中唯一 if mod(i,3) BlockRowIndex=mod(i,3); else BlockRowIndex=3; end if mod(j,3) BlockColIndex=mod(j,3); else BlockColIndex=3; end Block=PossibleData(BlockX,BlockY);%取出则个小块数据 Block(BlockRowIndex,BlockColIndex)={[]};%先去掉当前格子中的数据 ExceptItselfBlockCellData=cell2mat(Block(:)'); BlockUniqueData=setdiff(PossibleData{i,j}, ExceptItselfBlockCellData); if length(BlockUniqueData)==1 Data(i,j)=BlockUniqueData; DataChange=true; PossibleData(i,j)={[]}; PossibleDataNum(i,j)=0; [TempPossibleData,TempPossibleDataNum] =ExcludeRow_Col_BlockSame(PossibleData,PossibleDataNum,... BlockUniqueData,i,j,BlockX,BlockY); PossibleData=TempPossibleData; PossibleDataNum=TempPossibleDataNum; continue; end end end end end 三、二连数法。 %%2017/11/13 by DengQi(DQ) function [Data,PossibleData,PossibleDataNum,DataChange] = Row_Col_Block_DataTwoSame(Data,PossibleData,PossibleDataNum) DataChange=false; [m,n]=size(PossibleData); %% 在行中查找具有2个且相同的数据，那么在这两个位置上的数据 %只可能是2个数据中的一个，其他位置则无此数据，在其他位置干掉他们 for i=1:m for j=1:n if PossibleDataNum(i,j)==2 RowTwoCount=1; for g=j+1:n if PossibleDataNum(i,g)==2 Temp=intersect(PossibleData{i,j},PossibleData{i,g}); if length(Temp)==2 RowTwoCount=RowTwoCount+1; break; end end end if RowTwoCount==2 for h=1:9 if (PossibleDataNum(i,h))&&(h~=j)&&(h~=g) ExcludeTwoData=setdiff(PossibleData{i,h},PossibleData{i,j}); PossibleData(i,h)={ExcludeTwoData}; PossibleDataNum(i,h)=length(ExcludeTwoData); DataChange=true; end end end end end%j end%i %% 在列中查找具有2个且相同的数据，那么在这两个位置上的数据 %只可能是2个数据中的一个，其他位置则无此数据，在其他位置干掉他们 for j=1:n for i=1:m if PossibleDataNum(i,j)==2 ColTwoCount=1; for h=i+1:m if PossibleDataNum(h,j)==2 Temp=intersect(PossibleData{i,j},PossibleData{h,j}); if length(Temp)==2 ColTwoCount=ColTwoCount+1; break; end end end if ColTwoCount==2 for g=1:9 if (PossibleDataNum(g,j))&&(g~=i)&&(g~=h) ExcludeTwoData=setdiff(PossibleData{g,j},PossibleData{i,j}); PossibleData(g,j)={ExcludeTwoData}; PossibleDataNum(g,j)=length(ExcludeTwoData); DataChange=true; end end end end end%i end%j %% 在3x3小块中查找具有2个且相同的数据，那么在这两个位置上的数据 %只可能是2个数据中的一个，其他位置则无此数据，在其他位置干掉他们 for i=1:m for j=1:n if PossibleDataNum(i,j)==2 BlockXIndex= (1+3*floor((i-1)/3)):(3+3*floor((i-1)/3)); BlockYIndex= (1+3*floor((j-1)/3)):(3+3*floor((j-1)/3)); BlockTwoCount=1; Blockg=0; Blockh=0; TempPossibleData=PossibleData{i,j}; PossibleData(i,j)={[]}; PossibleDataNum(i,j)=0; for BlockX=BlockXIndex for BlockY=BlockYIndex if (PossibleDataNum(BlockX,BlockY)==2) Temp=intersect(TempPossibleData,PossibleData{BlockX,BlockY}); if length(Temp)==2 BlockTwoCount=BlockTwoCount+1; PossibleData(BlockX,BlockY)={[]}; PossibleDataNum(BlockX,BlockY)=0; Blockg=BlockX; Blockh=BlockY; break; end end end end if BlockTwoCount==2 for g=BlockXIndex for h=BlockYIndex if PossibleDataNum(g,h) ExcludeTwoData=setdiff(PossibleData{g,h},TempPossibleData); PossibleData(g,h)={ExcludeTwoData}; PossibleDataNum(g,h)=length(ExcludeTwoData); DataChange=true; end end end PossibleData(Blockg,Blockh)={TempPossibleData}; PossibleDataNum(Blockg,Blockh)=2; end PossibleData(i,j)={TempPossibleData}; PossibleDataNum(i,j)=2; end end end%j end%i 除了上面三个核心程序，还有一个公共程序和主函数，其中公共程序主要用于： 当某个格子上的数确定后，执行删掉其所在行列以及宫格中的相同的数。 %%2017/11/13 by DengQi(DQ) function [PossibleData,PossibleDataNum] =ExcludeRow_Col_BlockSame(PossibleData,PossibleDataNum,RegionUniqueData,i,j,BlockX,BlockY) %在行中其他地方去除这个唯一的数据 for x=1:9 if PossibleDataNum(i,x) PrePossibleData=PossibleData{i,x}; PreDataNum=length(PrePossibleData); CurData=setdiff(PrePossibleData,RegionUniqueData); CurDataNum=length(CurData); if (PreDataNum-CurDataNum)==1 PossibleData(i,x)={CurData}; PossibleDataNum(i,x)=PossibleDataNum(i,x)-1; end end end %在列中其他地方去除这个唯一的数据 for y=1:9 if PossibleDataNum(y,j) PrePossibleData=PossibleData{y,j}; PreDataNum=length(PrePossibleData); CurData=setdiff(PrePossibleData,RegionUniqueData); CurDataNum=length(CurData); if (PreDataNum-CurDataNum)==1 PossibleData(y,j)={CurData}; PossibleDataNum(y,j)=PossibleDataNum(y,j)-1; end end end %在块中其他地方去除这个唯一的数据 for g=BlockX for h=BlockY if PossibleDataNum(g,h) PrePossibleData=PossibleData{g,h}; PreDataNum=length(PrePossibleData); CurData=setdiff(PrePossibleData,RegionUniqueData); CurDataNum=length(CurData); if (PreDataNum-CurDataNum)==1 PossibleData(g,h)={CurData}; PossibleDataNum(g,h)=PossibleDataNum(g,h)-1; end end end end end 主函数如下： %%2018/01/14 by DengQi(DQ) clc; clear; close all; close all; Data=xlsread('SudouM1.xls'); %% 初次操作 %使用基本规则行列块元素唯一性 [PossibleData,PossibleDataNum]= BaseRule(Data); Count=0; DataChange1=true; DataChange2=true; while (DataChange1||DataChange2) Count=Count+1; %当前cell中的元素在行列块元素唯一性 [Data,PossibleData,PossibleDataNum,DataChange1]=Row_Col_Block_DataUnique(Data,PossibleData,PossibleDataNum); [Data,PossibleData,PossibleDataNum,DataChange2] = Row_Col_Block_DataTwoSame(Data,PossibleData,PossibleDataNum); end 下面来找几个实例来用程序测试一下吧。 首先进入这个数独网站：http://cn.sudokupuzzle.org/ ,然后选择初级题目如下：
为了方便我把这道题的答案也在此附上，答案如下：
下面利用我写的程序求解一下，首先把题目数据存放在excel或txt,空缺的数据填0，我在此使用excel，如下：
程序求解结果如下：
对比结果没问题，求解正确。
下面我们在选一个中级的求解一下看看。
中级求解答案：
程序求解结果：
求解不全，来看一下没求解出来为止的候选数吧，候选数都对着啦
由上可见，此程序还不完善，这主要是由于程序包含的解法不全造成的，比如没有三连数法等，但上面的程序在求解数独大体思路上有很大指示作用和意义，按照这个大方向走就没错。因此后续把：http://www.sudokufans.org.cn/forums/topic/69/上所说方法加进去，问题就可解决了。由于最近没啥时间，因此暂时就写到这里吧，后面有时间在跟进完善吧，我把上面这些程序传到了这里：
http://download.csdn.net/download/lingyunxianhe/10205393 如果觉得粘贴麻烦的话可以去这里下载。
|
【本文地址】
今日新闻 |
推荐新闻 |