数独解题算法 能快速求解任意难度数独

#include <string.h> #include <malloc.h> #include "shutOut.h" #include "guess.h" #include "infer.h" #include "types.h" void initTable(Table *pTable) { int ix = 0; for( ; ix < SIZE; ++ix ) { pTable->shutOutTable[ix] = 0; pTable->shuDuTable[ix] = '0'; } pTable->ensureValCnt = 0; pTable->guessIx = SIZE; pTable->guessVal = 0; pTable->pre = NULL; } int shuDuTableCheck(ShuDuTable shuDuTable) { int ix = 0; int iy = 0; int rx = 0; int ry = 0; int x = 0; int y = 0; int mask = 0; char c = '0'; /*row check*/ for( iy = 0; iy < WIDE; ++iy ) { for ( ix = 0; ix < WIDE; ++ix ) { c = shuDuTable[ iy*WIDE + ix ]; if ( c != '0' ) { if ( CHECKBIT(mask,CHARTOINT(c) ) != 0 ) { #ifdef TEST printf("ROW:%d error!\n",iy+1); #endif return ERROR; } SETBIT(mask,CHARTOINT(c)); } } mask = 0; } /*column check*/ for( ix = 0; ix < WIDE; ++ix ) { for ( iy = 0; iy < WIDE; ++iy ) { c = shuDuTable[ iy*WIDE + ix ]; if ( c != '0' ) { if ( CHECKBIT(mask,CHARTOINT(c)) != 0 ) { #ifdef TEST printf("COLUMN:%d error!\n",ix+1); #endif return ERROR; } SETBIT(mask,CHARTOINT(c)); } } mask = 0; } /*round check*/ for( ix = 0; ix < WIDE; ++ix ) { y = ix / ROUNDWIDE * ROUNDWIDE; for( ry = y; ry < (y + ROUNDWIDE); ++ry ) { x = ix % ROUNDWIDE * ROUNDWIDE; for ( rx = x; rx < (x + ROUNDWIDE); ++rx ) { c = shuDuTable[ ry*WIDE + rx ]; if ( c != '0' ) { if ( CHECKBIT(mask,CHARTOINT(c)) != 0 ) { #ifdef TEST printf("ROUND:%d error!\n",ix+1); #endif return ERROR; } SETBIT(mask,CHARTOINT(c)); } } } mask = 0; } return OK; } int ensureValCnt(Table *pTable) { int ix = 0; int cnt = 0; for( ix = 0; ix < SIZE; ++ix ) { if ( pTable->shuDuTable[ix] != '0' ) ++cnt; } pTable->ensureValCnt = cnt; return OK; } int freeResource(Table **ppTable) { Table *pTable = (*ppTable); Table *pTempTable; while(1) { if( pTable->pre == NULL ) { (*ppTable) = pTable; return OK; } pTempTable = pTable; pTable = pTable->pre; free(pTempTable); } } int shuDu(Table **pTable) { bool shutOutSucceed = true; bool inferSucceed = true; int shutResult = UNDONE; INDEX ix = 0; ShutOutTable shutOutTable = (*pTable)->shutOutTable; ShuDuTable shuDuTable = (*pTable)->shuDuTable; int *cnt = &((*pTable)->ensureValCnt); while( (*pTable)->ensureValCnt < SIZE ) { shutOutSucceed = false; inferSucceed = false; printf("starting shutOut...\n"); for ( ix = 0; ix < SIZE; ++ix ) { if ( shutOut(shutOutTable,shuDuTable,ix) == ERROR ) continue; shutResult = shutOutEnsureVal(shutOutTable,shuDuTable,cnt,ix); if ( ERROR == shutResult ) { if ( guessFailDeal(pTable) == ERROR ) return ERROR; ix = 0; } if ( OK == shutResult ) { shutOutSucceed = true; inferSucceed = true; } } if ( false == shutOutSucceed ) { printf("starting infer...\n"); for( ix = 0; ix < SIZE; ++ix ) { if ( inferEnsureVal(shutOutTable,shuDuTable,ix,cnt) == OK ) { inferSucceed = true; break; } } } if ( false == inferSucceed ) { printf("starting guess...\n"); if ( newGuess(pTable) == ERROR ) return ERROR; shutOutTable = (*pTable)->shutOutTable; shuDuTable = (*pTable)->shuDuTable; cnt = &((*pTable)->ensureValCnt); } } return OK; }