數獨求解演算法

最近又重新翻出了數獨，然後解傳說中最難數獨沒解開（半小時），就萌生了計算機求解的想法。背景交代完畢，然後就開始了苦逼的編碼過程。

知乎上找了半天都是DLX，DFS，剪枝...也找到了一些源碼看，我就鬱悶了一個9*9的方格而已需要用到這麼複雜的演算法嗎？

於是自己嘗試寫了一個簡單的迭代+RCB方式求解，用我們筆記本（i5-3230）沒遇到50ms沒解出來的。就記錄下來，給大家分享。

BTW，我看了DLX的介紹，說是坐標跳轉和跳舞一樣優美，而我想法是9*9的格子而已我要程序怎麼跳就怎麼跳，直接就預設好路徑所以肯定比DLX快。

代碼寫出來時間理想就沒做優化了，下面貼個代碼。我知道看別人代碼是最麻煩的事情了，有誰願意做優化的就看下吧。

#include "stdafx.h"#include <stdlib.h>#include <windows.h>//寫死路徑，坐標按我說的跳！char blockPt[9*9] = { 0, 1, 2, 9,10,11,18,19,20, 3, 4, 5,12,13,14,21,22,23, 6, 7, 8,15,16,17,24,25,26, 27,28,29,36,37,38,45,46,47, 30,31,32,39,40,41,48,49,50, 33,34,35,42,43,44,51,52,53, 54,55,56,63,64,65,72,73,74, 57,58,59,66,67,68,75,76,77, 60,61,62,69,70,71,78,79,80};char blockPt2[9*9] = { 0,0,0,1,1,1,2,2,2, 0,0,0,1,1,1,2,2,2, 0,0,0,1,1,1,2,2,2, 3,3,3,4,4,4,5,5,5, 3,3,3,4,4,4,5,5,5, 3,3,3,4,4,4,5,5,5, 6,6,6,7,7,7,8,8,8, 6,6,6,7,7,7,8,8,8, 6,6,6,7,7,7,8,8,8};void printSD(char *a){ if( NULL == a) { printf("fail to calculate!
"); return; } int i,j; for(i = 0;i<9;i++) { for(j=0;j<9;j++) { printf("%d",a[9*i+j]); if( j == 8 ) { printf("
"); break; } if( (『+1)%3 == 0 ) printf(" "); } if( (i+1)%3 == 0 ) printf("
"); } printf("============
");}class Sudoku{public: Sudoku() { m_bInited = false; init(); } ~Sudoku() { destory(); } void inputSudoku(char *src) //初始化 { insertNum1st(src); } char *calcSudoku(){ //計算並返回答案 int iRet,iResult = 0; do{ iRet = iResult = calcAbleRCB(); if( iResult<0 ) return NULL; iResult = setPtAble1(); if( iResult<0 ) return NULL; iRet += iResult; }while(iRet); // return (char*)m_srcMap; if( !chkFullAll() ){ int i,p,v; char *b=NULL; p = getTryPt(); for(i=0;i<9;i++){ if(m_ptAble[p][i] != 0 ){ v = m_ptAble[p][i]; m_srcMap[p] = v; Sudoku newSDK; //printf("Try:setMap(p=%d,v=%d) able%d%d%d%d%d%d%d%d%d%d
",p,v,m_ptAble[p][0],m_ptAble[p][1],m_ptAble[p][2],m_ptAble[p][3],m_ptAble[p][4],m_ptAble[p][5],m_ptAble[p][6],m_ptAble[p][7],m_ptAble[p][8],m_ptAble[p][9]); newSDK.inputSudoku((char*)m_srcMap); b = newSDK.calcSudoku(); if(b){ memcpy(m_srcMap,b,sizeof(m_srcMap[0])*9*9); break; } else{ m_ptAble[p][9]--; m_ptAble[p][i]=0; //newSDK.doBack(); m_srcMap[p] = 0; //printf("Try:setMap(p=%d,v=%d) failed!!
",p,v); } if( 0 == m_ptAble[p][9]) return NULL; } } return b; //if( NULL == b) // return NULL; } return (char*)m_srcMap; } char *getOneSudoku(); //獲取一個數獨題private: bool m_bInited; unsigned char m_srcMap[9*9]; unsigned char m_ptAble[9*9][10]; //每個點的可能值，1則確定填入 unsigned char m_unitAbleR[9][9][10]; //i行中數字j可能的位置k unsigned char m_unitAbleC[9][9][10]; unsigned char m_unitAbleB[9][9][10]; void init() { if(m_bInited) return; int i,j,k; memset(m_srcMap,0,sizeof(char)*9*9); //初始化所有able表， for(i=0;i<9;i++){ for(j=0;j<9;j++){ for(k=0;k<10;k++){ m_ptAble[i*9+j][k] = k+1; m_unitAbleR[i][j][k] = k+1; m_unitAbleC[i][j][k] = k+1; m_unitAbleB[i][j][k] = k+1; } m_ptAble[i*9+j][9] = 9; m_unitAbleR[i][j][9] = 9; m_unitAbleC[i][j][9] = 9; m_unitAbleB[i][j][9] = 9; } } m_bInited = true; } void destory() { ; } int insertNum1st(char*a) { init(); int p,v,iRet = 0; for(p=0;p<9*9;p++) { v = a[p]; if(v<0 || v>9) return -1; else if( v!=0 ){ setPt(p,v,0); if(unitDelAbleR(p,v)<0) return -1; if(unitDelAbleC(p,v)<0) return -1; if(unitDelAbleB(p,v)<0) return -1; } else m_srcMap[p] = 0; } return 0; } void setPt(int p,char v,bool back = 1) { m_srcMap[p] = v; memset(m_ptAble[p],0,sizeof(m_ptAble[p][0])*9); m_ptAble[p][v - 1] = v; m_ptAble[p][9] = 1; } int unitDelAbleR(int p,char v) { int i,j,t,m,n,iRet=0; i=p/9;j=p%9; for(t=0;t<9;t++){ if(m_srcMap[i*9+t]==m_srcMap[p] && i*9+t!=p){ //printf("Err:unitDelAbleR(p=%d,p1=%d,v=%d) same NUM
",p,i*9+t,v); return -1; } if( t!=v && m_ptAble[p][9]>1 && m_unitAbleR[i][t][j]!=0){ m_unitAbleR[i][t][j]=0; switch(--m_unitAbleR[i][t][9]){ case -2: case -1: case 0://printf("Err:unitDelAbleR(p=%d,v=%d)
",p,v); return -1; case 1:{ for(m=n=0;m<9;m++){ n += m_unitAbleR[i][t][m]; } //printf("get:unitDelAbleR(p=%d,v=%d)
",p,v); setPt(i*9+n-1,t); iRet++; }break; default: break; } } } return iRet; } int unitDelAbleC(int p,char v) { int i,j,t,m,n,iRet=0; i=p/9;j=p%9; for(t=0;t<9;t++){ if(m_srcMap[j+t*9]==m_srcMap[p] && j+t*9!=p){ //printf("Err:unitDelAbleC(p=%d,p1=%d,v=%d) same NUM
",p,j+t*9,v); return -1; } if( t!=v && m_ptAble[p][9]>1 && m_unitAbleC[j][t][i]!=0){ m_unitAbleC[j][t][i]=0; switch(--m_unitAbleC[j][t][9]){ case -2: case -1: case 0://printf("Err:unitDelAbleC(p=%d,v=%d)
",p,v); return -1; case 1:{ for(m=n=0;m<9;m++){ n += m_unitAbleC[j][t][m]; } //printf("get:unitDelAbleC(p=%d,v=%d)
",p,v); setPt(i+(n-1)*9,t); iRet++; }break; default: break; } } } return iRet; } int unitDelAbleB(int p,char v) { int i,j,t,m,n,iRet=0; i=blockPt2[p]; for(j=0;j<9;j++) { if(p==blockPt[i*9+j]) break; } if(9 == j) return -1; for(t=0;t<9;t++){ if( blockPt[i*9+t] == 17) int aaaa=22; if(m_srcMap[blockPt[i*9+t]]==m_srcMap[p] && p!=blockPt[i*9+t]){ //判斷v值沒有在unit內其他位置出現 //printf("Err:unitDelAbleB(p=%d,p1=%d,v=%d) same NUM
",p,blockPt[i*9+t],v); return -1; } if( t!=v-1 && m_ptAble[p][9]>1 && m_unitAbleB[i][t][j]!=0){ m_unitAbleB[i][t][j]=0;//刪除當前block內，其他數字不會在j位置 switch(--m_unitAbleB[i][t][9]){ case -2: case -1: case 0: //printf("Err:unitDelAbleB(p=%d,v=%d)
",p,v); return -1; case 1:{ for(m=n=0;m<9;m++){ n += m_unitAbleB[i][t][m]; } //printf("get:unitDelAbleB(p=%d,v=%d)
",p,v); setPt(blockPt[i*9+n-1],t); iRet++; }break; default: break; } } } //刪除pt所在Row涉及到的BAble m=p/9;n=p%9; //srcMap中（x,y）,,i,j BlockAble(x,y) if(v == 5) int as=2; if(i%3 == 0){ //0,3,6塊 //Row if(m_unitAbleB[i+1][v-1][j/3*3+0]!=0){ m_unitAbleB[i+1][v-1][j/3*3+0] = 0; m_unitAbleB[i+1][v-1][9]--; } if(m_unitAbleB[i+1][v-1][j/3*3+1]!=0){ m_unitAbleB[i+1][v-1][j/3*3+1] = 0; m_unitAbleB[i+1][v-1][9]--; } if(m_unitAbleB[i+1][v-1][j/3*3+2]!=0){ m_unitAbleB[i+1][v-1][j/3*3+2] = 0; m_unitAbleB[i+1][v-1][9]--; } if(m_unitAbleB[i+2][v-1][j/3*3+0]!=0){ m_unitAbleB[i+2][v-1][j/3*3+0] = 0; m_unitAbleB[i+2][v-1][9]--; } if(m_unitAbleB[i+2][v-1][j/3*3+1]!=0){ m_unitAbleB[i+2][v-1][j/3*3+1] = 0; m_unitAbleB[i+2][v-1][9]--; } if(m_unitAbleB[i+2][v-1][j/3*3+2]!=0){ m_unitAbleB[i+2][v-1][j/3*3+2] = 0; m_unitAbleB[i+2][v-1][9]--; } //Col } else if(i%3 == 1){ //1,4,7塊 if(m_unitAbleB[i+1][v-1][j/3*3+0]!=0){ m_unitAbleB[i+1][v-1][j/3*3+0] = 0; m_unitAbleB[i+1][v-1][9]--; } if(m_unitAbleB[i+1][v-1][j/3*3+1]!=0){ m_unitAbleB[i+1][v-1][j/3*3+1] = 0; m_unitAbleB[i+1][v-1][9]--; } if(m_unitAbleB[i+1][v-1][j/3*3+2]!=0){ m_unitAbleB[i+1][v-1][j/3*3+2] = 0; m_unitAbleB[i+1][v-1][9]--; } if(m_unitAbleB[i-1][v-1][j/3*3+0]!=0){ m_unitAbleB[i-1][v-1][j/3*3+0] = 0; m_unitAbleB[i-1][v-1][9]--; } if(m_unitAbleB[i-1][v-1][j/3*3+1]!=0){ m_unitAbleB[i-1][v-1][j/3*3+1] = 0; m_unitAbleB[i-1][v-1][9]--; } if(m_unitAbleB[i-1][v-1][j/3*3+2]!=0){ m_unitAbleB[i-1][v-1][j/3*3+2] = 0; m_unitAbleB[i-1][v-1][9]--; } } else{ //2，5，8塊 if(m_unitAbleB[i-1][v-1][j/3*3+0]!=0){ m_unitAbleB[i-1][v-1][j/3*3+0] = 0; m_unitAbleB[i-1][v-1][9]--; } if(m_unitAbleB[i-1][v-1][j/3*3+1]!=0){ m_unitAbleB[i-1][v-1][j/3*3+1] = 0; m_unitAbleB[i-1][v-1][9]--; } if(m_unitAbleB[i-1][v-1][j/3*3+2]!=0){ m_unitAbleB[i-1][v-1][j/3*3+2] = 0; m_unitAbleB[i-1][v-1][9]--; } if(m_unitAbleB[i-2][v-1][j/3*3+0]!=0){ m_unitAbleB[i-2][v-1][j/3*3+0] = 0; m_unitAbleB[i-2][v-1][9]--; } if(m_unitAbleB[i-2][v-1][j/3*3+1]!=0){ m_unitAbleB[i-2][v-1][j/3*3+1] = 0; m_unitAbleB[i-2][v-1][9]--; } if(m_unitAbleB[i-2][v-1][j/3*3+2]!=0){ m_unitAbleB[i-2][v-1][j/3*3+2] = 0; m_unitAbleB[i-2][v-1][9]--; } } if(i<3){ //0,1,2塊 if(m_unitAbleB[i+3][v-1][j%3+0]!=0){ m_unitAbleB[i+3][v-1][j%3+0] = 0; m_unitAbleB[i+3][v-1][9]--; } if(m_unitAbleB[i+3][v-1][j%3+3]!=0){ m_unitAbleB[i+3][v-1][j%3+3] = 0; m_unitAbleB[i+3][v-1][9]--; } if(m_unitAbleB[i+3][v-1][j%3+6]!=0){ m_unitAbleB[i+3][v-1][j%3+6] = 0; m_unitAbleB[i+3][v-1][9]--; } if(m_unitAbleB[i+6][v-1][j%3+0]!=0){ m_unitAbleB[i+6][v-1][j%3+0] = 0; m_unitAbleB[i+6][v-1][9]--; } if(m_unitAbleB[i+6][v-1][j%3+3]!=0){ m_unitAbleB[i+6][v-1][j%3+3] = 0; m_unitAbleB[i+6][v-1][9]--; } if(m_unitAbleB[i+6][v-1][j%3+6]!=0){ m_unitAbleB[i+6][v-1][j%3+6] = 0; m_unitAbleB[i+6][v-1][9]--; } } else if(i<6){ if(m_unitAbleB[i+3][v-1][j%3+0]!=0){ m_unitAbleB[i+3][v-1][j%3+0] = 0; m_unitAbleB[i+3][v-1][9]--; } if(m_unitAbleB[i+3][v-1][j%3+3]!=0){ m_unitAbleB[i+3][v-1][j%3+3] = 0; m_unitAbleB[i+3][v-1][9]--; } if(m_unitAbleB[i+3][v-1][j%3+6]!=0){ m_unitAbleB[i+3][v-1][j%3+6] = 0; m_unitAbleB[i+3][v-1][9]--; } if(m_unitAbleB[i-3][v-1][j%3+0]!=0){ m_unitAbleB[i-3][v-1][j%3+0] = 0; m_unitAbleB[i-3][v-1][9]--; } if(m_unitAbleB[i-3][v-1][j%3+3]!=0){ m_unitAbleB[i-3][v-1][j%3+3] = 0; m_unitAbleB[i-3][v-1][9]--; } if(m_unitAbleB[i-3][v-1][j%3+6]!=0){ m_unitAbleB[i-3][v-1][j%3+6] = 0; m_unitAbleB[i-3][v-1][9]--; } } else{ if(m_unitAbleB[i-6][v-1][j%3+0]!=0){ m_unitAbleB[i-6][v-1][j%3+0] = 0; m_unitAbleB[i-6][v-1][9]--; } if(m_unitAbleB[i-6][v-1][j%3+3]!=0){ m_unitAbleB[i-6][v-1][j%3+3] = 0; m_unitAbleB[i-6][v-1][9]--; } if(m_unitAbleB[i-6][v-1][j%3+6]!=0){ m_unitAbleB[i-6][v-1][j%3+6] = 0; m_unitAbleB[i-6][v-1][9]--; } if(m_unitAbleB[i-3][v-1][j%3+0]!=0){ m_unitAbleB[i-3][v-1][j%3+0] = 0; m_unitAbleB[i-3][v-1][9]--; } if(m_unitAbleB[i-3][v-1][j%3+3]!=0){ m_unitAbleB[i-3][v-1][j%3+3] = 0; m_unitAbleB[i-3][v-1][9]--; } if(m_unitAbleB[i-3][v-1][j%3+6]!=0){ m_unitAbleB[i-3][v-1][j%3+6] = 0; m_unitAbleB[i-3][v-1][9]--; } } return iRet; } int setPtAble1() { int p,v,iRet=0; int i,j,k; for(p=0;p<9*9;p++){ v = m_srcMap[p]; for(k=0;k<9&&v>0;k++){ i=p/9;j=p%9; //Row if(p!=i*9+k && m_ptAble[i*9+k][v-1]!=0){ m_ptAble[i*9+k][v-1] = 0; m_ptAble[i*9+k][9]--; if(0 == m_ptAble[i*9+k][9]){ return -1; } } //Col if(p!=k*9+j && m_ptAble[k*9+j][v-1]!=0){ m_ptAble[k*9+j][v-1] = 0; m_ptAble[k*9+j][9]--; if(0 == m_ptAble[k*9+j][9]){ return -1; } } //block i=blockPt2[p]; for(v=0;v<9;v++) if(p==blockPt[i*9+v]) j=v; v = m_srcMap[p]; if(p!=blockPt[i*9+k] && m_ptAble[blockPt[i*9+k]][v-1]!=0){ m_ptAble[blockPt[i*9+k]][v-1] = 0; m_ptAble[blockPt[i*9+k]][9]--; if(0 == m_ptAble[blockPt[i*9+k]][9]){ return -1; } } } } return iRet; } int chkFullAll() { int iRet = 1; for(int p=0;p<9*9;p++) if(m_srcMap[p] == 0) return 0; return iRet; } int chkRCB() { int i,j,k,p,v,iRet = 0; for(p=0;p<9*9;p++){ if( m_ptAble[p][9] == 1 && m_srcMap[p] == 0){ //for(k=v=0;k<9;k++) // v += m_ptAble[p][k]; //setPt(p,v); for(k=0;k<9;k++) if(m_ptAble[p][k]) break; setPt(p,m_ptAble[p][k]); //printf("get:chkRCB(p=%d,v=%d) able k=%d
",p,m_ptAble[p][k],k); iRet++; } } for(i=0;i<9;i++){ for(j=0;j<9;j++){ //Row if(m_unitAbleR[i][j][9]==1 ){ for(k=v=0;k<9;k++) v += m_unitAbleR[i][j][k]; if(m_srcMap[i*9+v-1]==0){ printf("get:chkRCB(p=%d,v=%d) Row setPt(p=%d,v=%d)
",p,v,i*9+v-1,j+1); setPt(i*9+v-1,j+1); iRet++; } } //Col if(m_unitAbleC[i][j][9]==1 ){ for(k=v=0;k<9;k++) v += m_unitAbleC[i][j][k]; if(m_srcMap[i+(v-1)*9]==0){ //printf("get:chkRCB(p=%d,v=%d) Col setPt(p=%d,v=%d)
",p,v,i+(v-1)*9,j+1); setPt(i+(v-1)*9,j+1); iRet++; } } //Block if(m_unitAbleB[i][j][9]==1 ){ for(k=v=0;k<9;k++) v += m_unitAbleB[i][j][k]; if(m_srcMap[blockPt[i*9+v-1]]==0){ //printf("get:chkRCB(p=%d,v=%d) Blk setPt(p=%d,v=%d)
",p,v,blockPt[i*9+v-1],j+1); setPt(blockPt[i*9+v-1],j+1); iRet++; } } } } return iRet; } int calcAbleRCB() { int p,v,iResult,iRet = 0; iRet = setPtAble1(); if(iRet<0) return -1; iResult = chkRCB( ); if(iResult<0) return -1; iRet += iResult; for(p=0;p<9*9;p++) { v = m_srcMap[p]; if(v<0 || v>9) return -1; else if( v!=0 ){ //setPt(p,v); iResult = unitDelAbleR(p,v); if(iResult<0) return -1; iRet += iResult; iResult = unitDelAbleC(p,v); if(iResult<0) return -1; iRet += iResult; iResult = unitDelAbleB(p,v); if(iResult<0) return -1; iRet += iResult; } } return 0; } int getTryPt() { int i,j; for(i=2;i<9;i++) { for(j=0;j<9*9;j++) { if(m_ptAble[j][9] == i) return j; } } return -1; } };int main(int argc, char* argv[]){ char a0[]={ 0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0}; char a1[]={ 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}; char a2[]={ 0,9,5,0,0,8,0,0,0, 0,0,2,0,0,6,7,0,0, 0,4,0,0,0,0,0,0,5, 0,5,0,0,2,0,0,0,7, 0,6,0,0,5,0,0,2,0, 4,0,0,0,7,0,0,8,0, 2,0,0,0,0,0,0,4,0, 0,0,6,1,0,0,3,0,0, 0,0,0,3,0,9,2,5,0}; char ac[]={ 5,3,0,0,7,0,0,0,0, 6,0,0,1,9,5,0,0,0, 0,9,8,0,0,0,0,6,0, 8,0,0,0,6,0,0,0,3, 4,0,0,8,0,3,0,0,1, 7,0,0,0,2,0,0,0,6, 0,6,0,0,0,0,2,8,0, 0,0,0,4,1,9,0,0,5, 0,0,0,0,8,0,0,7,9}; char a[]={ 0,0,0,1,0,0,2,6,0, 7,0,0,0,3,0,0,0,0, 3,0,2,0,8,0,4,0,0, 0,0,0,4,0,8,0,0,1, 0,3,5,0,0,0,9,4,0, 2,0,0,3,0,5,0,0,0, 0,0,6,0,5,0,7,0,9, 0,0,0,0,4,0,0,0,8, 0,5,7,0,0,9,0,0,0}; Sudoku sdk; printSD(ac); unsigned long time1 = GetTickCount(); printf("beg tick %dms
",time1); sdk.inputSudoku(ac); char *b = sdk.calcSudoku(); unsigned long time2 = GetTickCount(); printf("end tick %dms
",time2); int aa = time2-time1; printSD(b); printf("used time %dms
",time2-time1); return 0;}

推薦閱讀：