这是我2006年写的Sukodu 计算程序,可以求解大部分问题. 有些难题不能完成填空.
int gData[LENGTH]= { //hard, unsolved 2,0,0, 0,8,0, 6,0,7, 0,0,0,0,0,0,0, 0,3,6, 9,0,0, 0,0,0, 0,0,0,0,0,0,0, 0,0,0, 0,0,0, 0,1,0, 0,0,0,0,0,0,0, 0,0,0, 0,3,4, 0,0,5, 0,0,0,0,0,0,0, 0,0,4, 6,0,5, 1,0,0, 0,0,0,0,0,0,0, 7,0,0, 2,9,0, 0,0,0, 0,0,0,0,0,0,0, 0,8,0, 0,0,0 ,0,0,0, 0,0,0,0,0,0,0, 0,7,0, 0,0,6, 8,3,0, 0,0,0,0,0,0,0, 1,0,2, 0,4,0, 0,0,0, 0,0,0,0,0,0,0//192};
#include "assert.h"#include // Header File For Windows#include // Header File For Standard Input / Output#include // Header File For The OpenGL32 Library#include // Header File For The GLu32 Library#include // Header File For The Glaux Library#include #include using namespace std;#define SQURE 3#define WIDTH 9#define LENGTH WIDTH * 16enum{ BLOCKREGION =1, ROWREGION = 2, COLREGION};#include "puzzle.h"//sudoku puzzle solver class by jesse sun 2006class Solve{public: int mBlockData[WIDTH * 3][WIDTH]; int mBoard[LENGTH]; int mBoardMask[LENGTH]; //int mRowSum[WIDTH]; //int mColSum[WIDTH]; int mBlockSum[WIDTH * 3]; int GetIndex(int row, int col) { return (row > 4; col = index & 0xf; } //initialize data mask and region void Init() { for (int row = 0; row >bit) & 0x1; } int FindAviBit(int mask, vector *pArray = NULL)//Count available number { int count = 0; int data = mask; for (int bit = 0; bit >= 1) { if ((data & 0x1) == 0) { count ++; if (pArray) pArray->push_back(bit + 1); } } return count; } //Only one number available at a cell. int FindOnlyNumberForCell() { for (int row = 0; row bitarray; int count = FindAviBit(mBoardMask[index], &bitarray); if (count == 1) { mBoard[index ] = bitarray[0]; return index; } } } return -1; } //number not available for the row void MaskDataRow(int row, int data) { int index = GetIndex(row, 0); for (int col = 0; col & rArray) { for (int i = 0; i >= 1) { if ((mask & 0x1) ==0)//a number is missing in this block { vector array; SearchAvlPosition(BlockPos, bit, array); if (array.size() == 1) { Data = bit + 1; return array[0]; } } } return -1; } //Find the only number available for a region, row, col int ThinkOneBlock() { int index = -1; for (int block = 0; block = 0) { mBoard[index] = bit; return index; } } return -1; }#define USE //SubGroup, Hidden Twin exclusion rule, naked twin exclusion bool Discovery() { bool change = false; for (int bit = 0; bit 7 --- 1 // 7 is impossible at lower left corner bool IsSpecialXwing(int Number, int BlockFlag) { bool change = false; //return change; vector > pos_arrays; vector pos_count; int start = WIDTH; if (BlockFlag == ROWREGION) start = WIDTH; else start = WIDTH * 2; for (int block = start; block array; SearchAvlPosition(mBlockData[block], Number, array); pos_arrays.push_back(array); pos_count.push_back(array.size()); } int i; for (i = 0; i 3 || j == i || pos_count[j] == 0) continue; for (int k = 0; k bitarray; int avl = FindAviBit(mask, &bitarray); if (avl != 2) continue; IndextoRowCol(index, row, col); int cornerindex, nakedindex; if (IsSameRowCol(row, col, pos_arrays[i], BlockFlag, cornerindex)) { int mask = mBoardMask[cornerindex]; vector bitarrayc; avl = FindAviBit(mask, &bitarrayc); if (avl != 2) continue; int row0, col0; int rown, coln; IndextoRowCol(cornerindex, row0, col0); if (BlockFlag ==ROWREGION) { rown = row0; coln= col; row0 = row; nakedindex = GetIndex(row, col0); } else { rown = row; coln = col0; col0 = col; nakedindex = GetIndex(row0, col); } int bit1 = (bitarray[0] - 1 == Number) ? bitarray[1] -1: bitarray[0]-1; int bit2 = (bitarrayc[0] -1 == Number) ? bitarrayc[1] -1: bitarrayc[0]-1; if (bit1==bit2) continue; if (IsTwinNumber(row0, col0, bit1, bit2, rown, coln)) { //if they are naked TWIN int index1; if (BlockFlag ==ROWREGION) index1 = GetIndex(i, col); else index1 = GetIndex(row, i); Print(); ReSetBit(mBoardMask[index1], Number, change); char buf[200]; sprintf(buf, "postion %x can not be %d because of n=%x c=%xspecial %d %d", index1, Number+1, nakedindex, cornerindex, bit1+1, bit2+1); PrintLog(buf); } } } } } return change; } bool IsTwinNumber(int row, int col, int bit1, int bit2, int rown, int coln) { int index= GetIndex(row, col); int mask = ~((1 bitarrayc; int avl = FindAviBit(mBoardMask[index], &bitarrayc); if (avl != 2) return false; int bit3, bit4; bool ok = false; for (int i = 0; i & pos1, int BlockFlag, int &rOtherIndex) { for (int i = 0; i 3 // the lower left 3 is impossible, cause it will lead a unsolvable 69 position bool SearchSpecialGroup(int *BlockPos, int mask, int BlockFlag) { bool change = false; for (int bit = 0; bit >=1) { if ((mask & 0x1) != 0)//a number is missing in this block continue; vector array; int size = SearchAvlPosition(BlockPos, bit, array); if (size arrayother; int size2 = SearchAvlPosition(mBlockData[block], bit, arrayother); if (size2 bitarray1; int mask = mBoardMask[array[i]]; int avl = FindAviBit(mask, &bitarray1); vector bitarray2; mask = mBoardMask[array[j]]; avl = FindAviBit(mask, &bitarray2); for (k = 0; k array; SearchAvlPosition(mBlockData[block], bit, array); for (int n = 0; n & pos1, vector& pos2, vector& pos3, vector& Rows, vector& Cols) { set rows; set cols; for (int i = 0; i ::iterator it; for (it = rows.begin(); it != rows.end(); it++) { Rows.push_back(*it); } for (it = cols.begin(); it != cols.end(); it++) { Cols.push_back(*it); } return true; } else return false; } bool ExcluseXwing(vector& rows, vector& cols, int Number, int BlockFlag, bool& change) { { //find a XWing, vector rowsmask; rowsmask.resize(WIDTH, false); for (int i = 0; i > pos_arrays; vector pos_count; int start = WIDTH; if (BlockFlag == ROWREGION) start = WIDTH; else start = WIDTH * 2; for (int block = start; block array; SearchAvlPosition(mBlockData[block], Number, array); pos_arrays.push_back(array); pos_count.push_back(array.size()); } int i; for (i = 0; i tmp; vector rows, cols; if (IsXWing(2, pos_arrays[i], pos_arrays[j], tmp, rows, cols)) { //Exclulde rowcol if (BlockFlag != ROWREGION) ExcluseXwing(cols, rows, Number, BlockFlag, change); else ExcluseXwing(rows, cols, Number, BlockFlag, change); } } } for (i = 0; i 3 || pos_count[i] == 0) continue; for (int j = i + 1; j 3 || pos_count[j] == 0) continue; for (int k = j + 1; k 3) continue; vector rows, cols; if (IsXWing(3, pos_arrays[i], pos_arrays[j], pos_arrays[k], rows, cols)) { if (BlockFlag != ROWREGION) ExcluseXwing(cols, rows, Number, BlockFlag, change); else ExcluseXwing(rows, cols, Number, BlockFlag, change); } } } } if (change) { char buf[200] = ""; sprintf(buf, "Xwing Found Number = %d", Number+1); PrintLog(buf); } return change; } //sub group exclusion bool SearchSubGroup(int *BlockPos, int mask, int BlockFlag) { bool change = false; for (int bit = 0; bit >= 1) { if ((mask & 0x1) == 0)//a number is missing in this block { vector array; int size = SearchAvlPosition(BlockPos, bit, array); if (size >= 2 && size bitarray; int avl = FindAviBit(mask, &bitarray); if (avl != 2 && avl != 3 ) continue; vector array; for (int j = i + 1; j array; int avl = SearchAvlPosition(BlockPos, i, array); if (avl != 2 && avl != 3) continue; vector numbers; for (int j = i + 1; j array2; int avl2 = SearchAvlPosition(BlockPos, j, array2); if (avl2 != avl) continue; //does number i & j have same position in the block if ((array[0]== array2[0] && array[1]== array2[1]) && (avl == 2 || (array[2]== array2[2]))) {//find hidden twins numbers.push_back(j); } } if ( avl == numbers.size() + 1) { int j = numbers[0]; int tnwmask = ~((1= 0) { bfirst = true; int data = mBoard[index]; if (data) { int row, col; IndextoRowCol(index, row, col); MaskData(row, col, data); char buf[200]; sprintf(buf, "Gird %0x is number %d", index, data); PrintLog(buf); } } } while(index >= 0); return; } Solve() { Init(); PrintLog(NULL); MaskData(); ThinkAll(); Print(); } void PrintLog(char *info) { char *att = "at"; if (info == NULL) att = "wt"; FILE * fp = fopen("c:\\output.txt", att); if (fp == NULL) return; if (info) fprintf(fp, "%s\n", info); fclose(fp); } void Print() { FILE * fp = fopen("c:\\output.txt", "at"); for (int row = 0; row array; int count = FindAviBit(mask, &array); for (int i = 0; i ));>)>));>));>))>\glaux.h>\glu.h>\gl.h>
