byte[] Mp = null;int cMp = 10;
// Try elementsint success = 0;
for (int y = 0; y < 9; y++)
{for (int x = 0; x < 9; x++)
{// Is this spot unused?if (m_sudoku[y, x] == 0)
{// Set M of possible solutionsbyte[] M = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
// Remove used numbers in the vertical directionfor (int a = 0; a < 9; a++)
M[m_sudoku[a, x]] = 0;
// Remove used numbers in the horizontal directionfor (int b = 0; b < 9; b++)
M[m_sudoku[y, b]] = 0;
// Remove used numbers in the sub square.int squareIndex = m_subSquare[y, x];for (int c = 0; c < 9; c++)
{
point p = m_subIndex[squareIndex, c];
M[m_sudoku[p.x, p.y]] = 0;
}
int cM = 0;// Calculate cardinality of Mfor (int d = 1; d < 10; d++)
cM += M[d] == 0 ? 0 : 1;
// Is there more information in this spot than in the best yet?if (cM < cMp)
{
cMp = cM;
Mp = M;
xp = x;
yp = y;
}
for (int i = 1; i < 10; i++)
{if (Mp[i] != 0)
{
m_sudoku[yp, xp] = Mp[i];if (Solve())
success++;else break;
// Restore to original state.m_sudoku[yp, xp] = 0;
// More than one solution found?if (success > 1)return false;
}
}
}
}
}
return success == 1;
-----------------------------------------------
/* SU DOKU */
#include
void main()
{
int k[9][9],K[9][9];
int i,j,i1,j1,i2,j2;
int error,temp;
int count=0;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
K[i][j]=0;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
{
cin>>K[i][j];
k[i][j]=K[i][j];
}
cout<<"O.K.? (Enter 0 if OK, 1 to update): ";
cin>>error;
if(error==0)
goto matrixvalidation;
matrixupdation:
while(1)
{
cout<<"Enter Row, Col, Revised number:(0 to exit) ";
cin>>i;
if(i==0)break;
cin>>j>>temp;
if(i>0&&j>0&&temp>=0&&i<10&&j<10&&temp<10)
{
K[i-1][j-1]=temp;
k[i-1][j-1]=temp;
}
else
cout<<"Enter row/column 1 to 9 & number 0 to 9 only.
";
}
matrixvalidation:
cout<<"
Input matrix:
";
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
cout<<<" ";
cout<<"
";
}
for(i=0;i<9;i++)
for(j=0;j<9;j++)
if(k[i][j]<0||k[i][j]>9)
{
cout<<"
"<<<" "<<<" "<
cout<<"
Input matrix error.";
cout<<"
Numbers should be 1 to 9 only.
";
goto matrixupdation;
}
for(i=0;i<9;i++)
for(j=0;j<9;j++)
{
if(k[i][j]==0)continue;
error=0;
for(i1=0;i1<9;i1++)
if(i!=i1&&k[i][j]==k[i1][j])
{
error=1;
i2=i1;
j2=j;
}
for(j1=0;j1<9;j1++)
if(j!=j1&&k[i][j]==k[i][j1])
{
error=1;
i2=i;
j2=j1;
}
for(i1=0;i1<9;i1++)
for(j1=0;j1<9;j1++)
if((i!=i1||j!=j1)&&i/3==i1/3&&j/3==j1/3&&k[i][j]==k[i1][j1])
{
error=1;
i2=i1;
j2=j1;
}
if(error)
{
cout<<"
"<<<" "<<<" "<
cout<<"
"<<<" "<<<" "<
cout<<"
Input matrix error.";
cout<<"
A number has been repeated in the same row, col or
block.
";
goto matrixupdation;
}
}
/* Logic starts: */
for(i=0;i<9;i++)
for(j=0;j<9;j++)
{
if(K[i][j]>0) goto chksol;
for(k[i][j]++;k[i][j]<=9;k[i][j]++)
{
error=0;
for(i1=0;i1<9;i1++)
if(i!=i1&&k[i][j]==k[i1][j])error=1;
for(j1=0;j1<9;j1++)
if(j!=j1&&k[i][j]==k[i][j1])error=1;
for(i1=0;i1<9;i1++)
for(j1=0;j1<9;j1++)
if((i!=i1||j!=j1)&&i/3==i1/3&&j/3==j1/3&&k[i][j]==k[i1][j1])
error=1;
if(error==0)break;
}
if(k[i][j]>9)
{
k[i][j]=0;
do
{
if(i==0&&j==0)goto nomoresol;
if(j>0)j--;else{j=8;i--;}
}while(K[i][j]>0);
j--;
}
chksol: if(i==8&&j==8)
{
cout<<"
Solution: "<<++count<<"
";
for(i1=0;i1<9;i1++)
{
for(j1=0;j1<9;j1++)
cout<<<" ";
cout<<"
";
}
if(count==50)
{
cout<<"
Too many solutions.
Not checking for more
solutions.
";
return;
}
while(K[i][j]>0)
{
if(i==0&&j==0)goto nomoresol;
if(j>0)j--;else{j=8;i--;}
}
k[i][j]=0;
do
{
if(i==0&&j==0)goto nomoresol;
if(j>0)j--;else{j=8;i--;}
}while(K[i][j]>0);
j--;
}
}
nomoresol:
if(count>0)
cout<<"
No more solutions.
";
else
cout<<"No solution.
";
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Hi Lone,
here is an algorithm that solves any soduko problem known as
a backtracking algorithm. I wrote this program on my way back
from italy while my wife was driving. I checked it with some
samples I found on the internet. Now, I am seeking for new
algorthims.
Have a good time …
Detlef
********************************** **************************
*** Dipl.- Inf. Detlef Hafer
*** D-91058 Erlangen (Germany)
********************************** ***************************
#include
#include
#define BACK -1
#define FORWARD 1
#define NSIZE 9
int F[NSIZE][NSIZE];
#if _DEBUG
static int M[NSIZE][NSIZE] = { {1, 6, 4, 0, 0, 0, 0, 0, 2},
{2, 0, 0, 4, 0, 3, 9, 1, 0},
{0, 0, 5, 0, 8, 0, 4, 0, 7},
{0, 9, 0, 0, 0, 6, 5, 0, 0},
{5, 0, 0, 1, 0, 2, 0, 0, 8},
{0, 0, 8, 9, 0, 0, 0, 3, 0},
{8, 0, 9, 0, 4, 0, 2, 0, 0},
{0, 7, 3, 5, 0, 9, 0, 0, 1},
{4, 0, 0, 0, 0, 0, 6, 7, 9} };
#endif
static BOOL findnumber (int z, int s)
{
int u = (z/3)*3;
int v = (s/3)*3;
int m = F[z][s];
F[z][s] = 0;
for (int t = m+1; t <= NSIZE; t++)
{
for (int i = 0; i < NSIZE; i++)
{
div_t q = div(i,3);
if ((F[i][s] == t) || (F[z][i] == t) || F[u+q.quot][v+q.rem] == t)
break;
}
if (i == NSIZE )
{
F[z][s] = t;
return TRUE;
}
}
return FALSE;
}
BOOL soduko (void)
{
BOOL bFix[NSIZE][NSIZE];
int r = FORWARD;
#if _DEBUG
memcpy(F, M, sizeof(M));
#endif
for (int i = 0; i < NSIZE; i++)
for (int j = 0; j < NSIZE; j++)
bFix[i][j] = (F[i][j] != 0);
i = 0;
while ( (i >= 0) && (i < NSIZE*NSIZE) )
{
div_t q = div(i,NSIZE);
int z = q.quot;
int s = q.rem;
if ( ! bFix[z][s])
{
if ( ! findnumber(z,s))
r = BACK;
else
r = FORWARD;
}
i += r;
}
if ( i < 0)
{
// no solution
return FALSE;
}
return TRUE;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////
#include #include using namespace std;
class SudokuBoard;
void printB(SudokuBoard sb);
typedef unsigned int uint;
const uint MAXVAL = 9;
const uint L = 9;
const uint C = 9;
const uint S = L * C;
const uint ZONEL = 3;
const uint ZONEC = 3;
const uint ZONES = ZONEL * ZONEC;
const uint lineElements[L][C] = {
{ 0, 1, 2, 3, 4, 5, 6, 7, 8}, { 9, 10, 11, 12, 13, 14, 15, 16, 17}, {18, 19, 20, 21, 22, 23, 24, 25, 26}, {27, 28, 29, 30, 31, 32, 33, 34, 35}, {36, 37, 38, 39, 40, 41, 42, 43, 44}, {45, 46, 47, 48, 49, 50, 51, 52, 53}, {54, 55, 56, 57, 58, 59, 60, 61, 62}, {63, 64, 65, 66, 67, 68, 68, 70, 71}, {72, 73, 74, 75, 76, 77, 78, 79, 80}}; const uint columnElements[C][L] = {
{ 0, 9, 18, 27, 36, 45, 54, 63, 72}, { 1, 10, 19, 28, 37, 46, 55, 64, 73}, { 2, 11, 20, 29, 38, 47, 56, 65, 74}, { 3, 12, 21, 30, 39, 48, 57, 66, 75}, { 4, 13, 22, 31, 40, 49, 58, 67, 76}, { 5, 14, 23, 32, 41, 50, 59, 68, 77}, { 6, 15, 24, 33, 42, 51, 60, 69, 78}, { 7, 16, 25, 34, 43, 52, 61, 70, 79}, { 8, 17, 26, 35, 44, 53, 62, 71, 80}}; const uint zoneElements[S / ZONES][ZONES] = {
{ 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, 68, 70, 71, 78, 79, 80}}; class SudokuBoard {
public:
SudokuBoard() : filledIn(0) { for (uint i(0); i < S; ++i) table[i] = usedDigits[i] = 0; } virtual ~SudokuBoard() { } int const at(uint l, uint c) { // Returns the value at line l and row c if (isValidPos(l, c)) return table[l * L + c]; else return -1; } void set(uint l, uint c, uint val) { // Sets the cell at line l and row c to hold the value val if (isValidPos(l, c) && ((0 < val) && (val <= MAXVAL))) { if (table[l * C + c] == 0) ++filledIn; table[l * C + c] = val; for (uint i = 0; i < C; ++i) // Update lines usedDigits[lineElements[l][i]] |= 1<for (uint i = 0; i < L; ++i) // Update columns
usedDigits[columnElements[c][i]] |= 1<<val; int z = findZone(l * C + c); for (uint i = 0; i < ZONES; ++i) // Update columns usedDigits[zoneElements[z][i]] |= 1< } } void solve() {try { // This is just a speed boost
scanAndSet(); // Logic approach goBruteForce(); // Brute force approach } catch (int e) { // This is just a speed boost } } void scanAndSet() { int b; bool changed(true); while (changed) { changed = false; for (uint i(0); i < S; ++i) if (0 == table[i]) // Is there a digit already written?if ((b = bitcount(usedDigits[i])) == MAXVAL - 1) { // If there's only one digit I can place in this cell, do
int d(1); // Find the digit while ((usedDigits[i] & 1< 0) ++d; set(i / C, i % C, d); // Fill it in changed = true; // The board has been changed so this step must be rerun } else if (bitcount(usedDigits[i]) == MAXVAL) throw 666; // Speed boost } } void goBruteForce() { int max(-1); // Find the cell with the _minimum_ number of posibilities (i.e. the one with the largest number of /used/ digits) for (uint i(0); i < S; ++i) if (table[i] == 0) // Is there a digit already written? if ((max == -1) || (bitcount(usedDigits[i]) > bitcount(usedDigits[max]))) max = i; if (max != -1) { for (uint i(1); i <= MAXVAL; ++i) // Go through each possible digit if ((usedDigits[max] & 1< SudokuBoard temp(*this); // Create a new board temp.set(max / C, max % C, i); // Complete the attempt temp.solve(); // Solve it if (temp.getFilledIn() == S) { // If the board was completely solved (i.e. the number of filled in cells is S) for (uint j(0); j < S; ++j) // Copy the board into this one set(j / C, j % C, temp.at(j / C, j % C)); return; // Break the recursive cascade } } } } uint getFilledIn() { return filledIn; } private: uint table[S]; uint usedDigits[S]; uint filledIn; bool const inline isValidPos(int l, int c) { return ((0 <= l) && (l < (int)L) && (0 <= c) && (c < (int)C)); } uint const inline findZone(uint off) { return ((off / C / ZONEL) * (C / ZONEC) + (off % C / ZONEC)); } uint const inline bitcount(uint x) { uint count(0); for (; x; ++count, x &= (x - 1)); return count; }}; void printB(SudokuBoard sb) { cout << " | ------------------------------- |" << endl; for (uint i(0); i < S; ++i) { if (i % 3 == 0) cout << " |"; cout << " " << sb.at(i / L, i % L); if (i % C == C - 1) { if (i / C % 3 == 2) cout << " |" << endl << " | -------------------------------"; cout << " |" << endl; } } cout << endl;} int main(int argc, char *argv[]) { SudokuBoard sb; ifstream fin("sudoku4.in"); int aux; for (uint i(0); i < S; ++i) { fin >> aux; sb.set(i / L, i % L, aux); } fin.close(); printB(sb); sb.solve(); printB(sb); return 0;}///////////////////////////////////////////////////////////////////////////////////////////////////////////
Webdesign Erlangen Mehrjährige Erfahrungen, technische Expertisen und unsere Kreativität sind das Sprungbrett für Ihr Vorhaben.
ReplyDeleteWir von Thorit.net freuen uns auf eine erfolgreiche Zusammenarbeit! Webdesign Erlangen Benutzen Sie einfach unser Kontaktformular
oder senden Sie uns gerne auch eine direkte Email an: info@thorit.net. Mehr Infos finden Sie hier Webdesign Erlangen