Soduku puzzle solver

Please support our C++ advertiser: Intel Parallel Studio Home
Thread Solved

•
•
Join Date: Sep 2006
Posts: 2
Reputation: Zabby is an unknown quantity at this point 
Solved Threads: 0
Zabby Zabby is offline Offline
Newbie Poster

Soduku puzzle solver

 
0
  #1
Sep 27th, 2006
Hi is there anyone willing enough to help me solve my problem. I'm using both Dev C++ 5 in windows and g++ in Linux to compile this code but was unable to do it successfully. Can any one help mi pliz

C++ Syntax (Toggle Plain Text) 
  1.  
  2. #include <cstdlib> 
  3. #include <iostream> 
  4.    using namespace std; 
  5. // note: sky 1905 puzzle 
  6.    int g[]={5,0,6,0,2,0,9,0,3, 
  7.          0,0,8,0,0,0,5,0,0, 
  8.          0,0,0,0,0,0,0,0,0, 
  9.          6,0,0,2,8,5,0,0,9, 
  10.          0,0,0,9,0,3,0,0,0, 
  11.          8,0,0,7,6,1,0,0,4, 
  12.          0,0,0,0,0,0,0,0,0, 
  13.          0,0,4,0,0,0,3,0,0, 
  14.          2,0,1,0,5,0,6,0,7}; 
  15.  
  16.    long m[108]; 
  17.    long r[10]; 
  18.    int p; 
  19.    bool FirstSolution; 
  20.    int Solutions; 
  21.    long sg[81][81]; 
  22.    int sp=0; 
  23.     void rarray () 
  24.    { 
  25.    // Populate r[] table with values. 
  26.       r[0]=0  ; r[1]=2  ; r[2]=4  ; r[3]=8  ; r[4]=16; 
  27.       r[5]=32 ; r[6]=64 ; r[7]=128; r[8]=256; r[9]=512; 
  28.    } 
  29.     void PrintGrid() 
  30.    { 
  31.       printf("\n"); 
  32.       int i=0; 
  33.       while (i<81) 
  34.       { 
  35.          printf( "%d",g[i]); 
  36.          if (((i+1)%9)==0) { printf("\n");  } 
  37.          i++; 
  38.       } 
  39.       printf("\n"); 
  40.    } 
  41.     void or_horizontal() { 
  42.    // Create Horizontal Masks by OR-ing 2^(grid values) together, 
  43.    // via a lookup table for speed. 
  44.       int p;                                            
  45.       int q; 
  46.       int i = 0; 
  47.       while (i < 9) { 
  48.          p = 81 + i; 
  49.          q = 9 * i; 
  50.          m[p] = r[g[q]] |  r[g[q+1]] |  r[g[q+2]] |  r[g[q+3]] |  r[g[q+4]] |  r[g[q+5]] |  r[g[q+6]] |  r[g[q+7]] |  r[g[q+8]]; 
  51.          i++; 
  52.       } 
  53.    } 
  54.     void or_verticals() { 
  55.    // Create Vertical Masks by OR-ing 2^(grid values) together, 
  56.    // via a lookup table for speed. 
  57.       int p; 
  58.       int q; 
  59.       int i = 0; 
  60.       while (i < 9) { 
  61.          p =90 + i; 
  62.          m[p] = r[g[i]] | r[g[9+i]] |  r[g[18+i]] |  r[g[27+i]] |  r[g[36+i]] |  r[g[45+i]] |  r[g[54+i]] |  r[g[63+i]] |  r[g[72+i]]; 
  63.          i++; 
  64.       } 
  65.    } 
  66.     void or_clusters() { 
  67.    // Create Cluster Masks by OR-ing 2^(grid values) together, 
  68.    // via a lookup table for speed. 
  69.       m[ 99] = r[g[ 0]] | r[g[ 1]] | r[g[ 2]] | r[g[ 9]] | r[g[10]] | r[g[11]] | r[g[18]] | r[g[19]] | r[g[20]] ; 
  70.       m[100] = r[g[ 3]] | r[g[ 4]] | r[g[ 5]] | r[g[12]] | r[g[13]] | r[g[14]] | r[g[21]] | r[g[22]] | r[g[23]] ; 
  71.       m[101] = r[g[ 6]] | r[g[ 7]] | r[g[ 8]] | r[g[15]] | r[g[16]] | r[g[17]] | r[g[24]] | r[g[25]] | r[g[26]] ; 
  72.       m[102] = r[g[27]] | r[g[28]] | r[g[29]] | r[g[36]] | r[g[37]] | r[g[38]] | r[g[45]] | r[g[46]] | r[g[47]] ; 
  73.       m[103] = r[g[30]] | r[g[31]] | r[g[32]] | r[g[39]] | r[g[40]] | r[g[41]] | r[g[48]] | r[g[49]] | r[g[50]] ; 
  74.       m[104] = r[g[33]] | r[g[34]] | r[g[35]] | r[g[42]] | r[g[43]] | r[g[44]] | r[g[51]] | r[g[52]] | r[g[53]] ; 
  75.       m[105] = r[g[54]] | r[g[55]] | r[g[56]] | r[g[63]] | r[g[64]] | r[g[65]] | r[g[72]] | r[g[73]] | r[g[75]] ; 
  76.       m[106] = r[g[57]] | r[g[58]] | r[g[59]] | r[g[66]] | r[g[67]] | r[g[68]] | r[g[75]] | r[g[76]] | r[g[78]] ; 
  77.       m[107] = r[g[60]] | r[g[61]] | r[g[62]] | r[g[69]] | r[g[70]] | r[g[71]] | r[g[78]] | r[g[79]] | r[g[80]] ; 
  78.  
  79.    } 
  80.  
  81.     void or_squares() { 
  82.    // Create individual masks by OR-ing Horizontal Mask, Vertical Mask and Cluser Mask. 
  83.       m[ 0]=m[81] | m[90] | m[ 99]; m[ 1]=m[81] | m[91] | m[ 99]; m[ 2]=m[81] | m[92] | m[ 99]; 
  84.       m[ 3]=m[81] | m[93] | m[100]; m[ 4]=m[81] | m[94] | m[100]; m[ 5]=m[81] | m[95] | m[100]; 
  85.       m[ 6]=m[81] | m[96] | m[101]; m[ 7]=m[81] | m[97] | m[101]; m[ 8]=m[81] | m[98] | m[101]; 
  86.       m[ 9]=m[82] | m[90] | m[ 99]; m[10]=m[82] | m[91] | m[ 99]; m[11]=m[82] | m[92] | m[ 99]; 
  87.       m[12]=m[82] | m[93] | m[100]; m[13]=m[82] | m[94] | m[100]; m[14]=m[82] | m[95] | m[100]; 
  88.       m[15]=m[82] | m[96] | m[101]; m[16]=m[82] | m[97] | m[101]; m[17]=m[82] | m[98] | m[101]; 
  89.       m[18]=m[83] | m[90] | m[ 99]; m[19]=m[83] | m[91] | m[ 99]; m[20]=m[83] | m[92] | m[ 99]; 
  90.       m[21]=m[83] | m[93] | m[100]; m[22]=m[83] | m[94] | m[100]; m[23]=m[83] | m[95] | m[100]; 
  91.       m[24]=m[83] | m[96] | m[101]; m[25]=m[83] | m[97] | m[101]; m[26]=m[83] | m[98] | m[101]; 
  92.       m[27]=m[84] | m[90] | m[102]; m[28]=m[84] | m[91] | m[102]; m[29]=m[84] | m[92] | m[102]; 
  93.       m[30]=m[84] | m[93] | m[103]; m[31]=m[84] | m[94] | m[103]; m[32]=m[84] | m[95] | m[103]; 
  94.       m[33]=m[84] | m[96] | m[104]; m[34]=m[84] | m[97] | m[104]; m[35]=m[84] | m[98] | m[104]; 
  95.       m[36]=m[85] | m[90] | m[102]; m[37]=m[85] | m[91] | m[102]; m[38]=m[85] | m[92] | m[102]; 
  96.       m[39]=m[85] | m[93] | m[103]; m[40]=m[85] | m[94] | m[103]; m[41]=m[85] | m[95] | m[103]; 
  97.       m[42]=m[85] | m[96] | m[104]; m[43]=m[85] | m[97] | m[104]; m[44]=m[85] | m[98] | m[104]; 
  98.       m[45]=m[86] | m[90] | m[102]; m[46]=m[86] | m[91] | m[102]; m[47]=m[86] | m[92] | m[102]; 
  99.       m[48]=m[86] | m[93] | m[103]; m[49]=m[86] | m[94] | m[103]; m[50]=m[86] | m[95] | m[103]; 
  100.       m[51]=m[86] | m[96] | m[104]; m[52]=m[86] | m[97] | m[104]; m[53]=m[86] | m[98] | m[104]; 
  101.       m[54]=m[87] | m[90] | m[105]; m[55]=m[87] | m[91] | m[105]; m[56]=m[87] | m[92] | m[105]; 
  102.       m[57]=m[87] | m[93] | m[106]; m[58]=m[87] | m[94] | m[106]; m[59]=m[87] | m[95] | m[106]; 
  103.       m[60]=m[87] | m[96] | m[107]; m[61]=m[87] | m[97] | m[107]; m[62]=m[87] | m[98] | m[107]; 
  104.       m[63]=m[88] | m[90] | m[105]; m[64]=m[88] | m[91] | m[105]; m[65]=m[88] | m[92] | m[105]; 
  105.       m[66]=m[88] | m[93] | m[106]; m[67]=m[88] | m[94] | m[106]; m[68]=m[88] | m[95] | m[106]; 
  106.       m[69]=m[88] | m[96] | m[107]; m[70]=m[88] | m[97] | m[107]; m[71]=m[88] | m[98] | m[107]; 
  107.       m[72]=m[89] | m[90] | m[105]; m[73]=m[89] | m[91] | m[105]; m[74]=m[89] | m[92] | m[105]; 
  108.       m[75]=m[89] | m[93] | m[106]; m[76]=m[89] | m[94] | m[106]; m[77]=m[89] | m[95] | m[106]; 
  109.       m[78]=m[89] | m[96] | m[107]; m[79]=m[89] | m[97] | m[107]; m[80]=m[89] | m[98] | m[107]; 
  110.    } 
  111.  
  112.     void or_masks() { 
  113.    // Perform masks 
  114.       or_horizontal(); 
  115.       or_verticals(); 
  116.       or_clusters(); 
  117.       or_squares(); 
  118.    } 
  119.     bool not_impossible() { 
  120.    // Check grid to see if it is impossible. 
  121.    // If a square is empty but has a mask of 1022, then the grid is impossible. 
  122.       int i=0; 
  123.       bool s=true; 
  124.       while ((i<81) && (s=true)) { 
  125.          if ((m[i]==1022) && (g[i]==0)) { 
  126.             s=false;  
  127.          } 
  128.          i++; 
  129.       } 
  130.       return s; 
  131.    } 
  132.     bool fullgrid() { 
  133.       int i=0; 
  134.       bool s=true; 
  135.       while ((i<81) && (s==true)) 
  136.       { 
  137.          if (g[i]==0)  { s=false ;  } 
  138.          i++; 
  139.       }    
  140.       return s; 
  141.    } 
  142.     void findsingles() { 
  143.    // Find Squares that can only be one value. 
  144.       int i=0; 
  145.       while (i<81) 
  146.       { 
  147.          if (g[i]==0) // Is square empty? 
  148.          { 
  149.             switch (m[i])  //What's it mask? 
  150.             { 
  151.                case  510: g[i]=9; 
  152.                   break; 
  153.                case  766: g[i]=8; 
  154.                   break; 
  155.                case  894: g[i]=7; 
  156.                   break; 
  157.                case  958: g[i]=6; 
  158.                   break; 
  159.                case  990: g[i]=5; 
  160.                   break; 
  161.                case 1006: g[i]=4; 
  162.                   break; 
  163.                case 1014: g[i]=3; 
  164.                   break; 
  165.                case 1018: g[i]=2; 
  166.                   break; 
  167.                case 1020: g[i]=1; 
  168.                   break; 
  169.                default: 
  170.                   break; 
  171.             }    
  172.             or_masks(); 
  173.          } 
  174.          i++; 
  175.       } 
  176.    } 
  177.  
  178.     void stack() 
  179.    { 
  180.    //printf("stack "); 
  181.       sp++; 
  182.       sg[sp][ 0]=g[ 0]; sg[sp][ 1]=g[ 1]; sg[sp][ 2]=g[ 2]; sg[sp][ 3]=g[ 3]; sg[sp][ 4]=g[ 4]; sg[sp][ 5]=g[ 5]; 
  183.       sg[sp][ 6]=g[ 6]; sg[sp][ 7]=g[ 7]; sg[sp][ 8]=g[ 8]; sg[sp][ 9]=g[ 9]; sg[sp][10]=g[10]; sg[sp][11]=g[11]; 
  184.       sg[sp][12]=g[12]; sg[sp][13]=g[13]; sg[sp][14]=g[14]; sg[sp][15]=g[15]; sg[sp][16]=g[16]; sg[sp][17]=g[17]; 
  185.       sg[sp][18]=g[18]; sg[sp][19]=g[19]; sg[sp][20]=g[20]; sg[sp][21]=g[21]; sg[sp][22]=g[22]; sg[sp][23]=g[23]; 
  186.       sg[sp][24]=g[24]; sg[sp][25]=g[25]; sg[sp][26]=g[26]; sg[sp][27]=g[27]; sg[sp][28]=g[28]; sg[sp][29]=g[29]; 
  187.       sg[sp][30]=g[30]; sg[sp][31]=g[31]; sg[sp][32]=g[32]; sg[sp][33]=g[33]; sg[sp][34]=g[34]; sg[sp][35]=g[35]; 
  188.       sg[sp][36]=g[36]; sg[sp][37]=g[37]; sg[sp][38]=g[38]; sg[sp][39]=g[39]; sg[sp][40]=g[40]; sg[sp][41]=g[41]; 
  189.       sg[sp][42]=g[42]; sg[sp][43]=g[43]; sg[sp][44]=g[44]; sg[sp][45]=g[45]; sg[sp][46]=g[46]; sg[sp][47]=g[47]; 
  190.       sg[sp][48]=g[48]; sg[sp][49]=g[49]; sg[sp][50]=g[50]; sg[sp][51]=g[51]; sg[sp][52]=g[52]; sg[sp][53]=g[53]; 
  191.       sg[sp][54]=g[54]; sg[sp][55]=g[55]; sg[sp][56]=g[56]; sg[sp][57]=g[57]; sg[sp][58]=g[58]; sg[sp][59]=g[59]; 
  192.       sg[sp][60]=g[60]; sg[sp][61]=g[61]; sg[sp][62]=g[62]; sg[sp][63]=g[63]; sg[sp][64]=g[64]; sg[sp][65]=g[65]; 
  193.       sg[sp][66]=g[66]; sg[sp][67]=g[67]; sg[sp][68]=g[68]; sg[sp][69]=g[69]; sg[sp][70]=g[70]; sg[sp][71]=g[71]; 
  194.       sg[sp][72]=g[72]; sg[sp][73]=g[73]; sg[sp][74]=g[74]; sg[sp][75]=g[75]; sg[sp][76]=g[76]; sg[sp][77]=g[77]; 
  195.       sg[sp][78]=g[78]; sg[sp][79]=g[79]; sg[sp][80]=g[80];          
  196.    } 
  197.     void unstack() 
  198.    { 
  199.       g[ 0]=sg[sp][ 0]; g[ 1]=sg[sp][ 1]; g[ 2]=sg[sp][ 2]; g[ 3]=sg[sp][ 3]; g[ 4]=sg[sp][ 4]; g[ 5]=sg[sp][ 5]; 
  200.       g[ 6]=sg[sp][ 6]; g[ 7]=sg[sp][ 7]; g[ 8]=sg[sp][ 8]; g[ 9]=sg[sp][ 9]; g[10]=sg[sp][10]; g[11]=sg[sp][11]; 
  201.       g[12]=sg[sp][12]; g[13]=sg[sp][13]; g[14]=sg[sp][14]; g[15]=sg[sp][15]; g[16]=sg[sp][16]; g[17]=sg[sp][17]; 
  202.       g[18]=sg[sp][18]; g[19]=sg[sp][19]; g[20]=sg[sp][20]; g[21]=sg[sp][21]; g[22]=sg[sp][22]; g[23]=sg[sp][23]; 
  203.       g[24]=sg[sp][24]; g[25]=sg[sp][25]; g[26]=sg[sp][26]; g[27]=sg[sp][27]; g[28]=sg[sp][28]; g[29]=sg[sp][29]; 
  204.       g[30]=sg[sp][30]; g[31]=sg[sp][31]; g[32]=sg[sp][32]; g[33]=sg[sp][33]; g[34]=sg[sp][34]; g[35]=sg[sp][35]; 
  205.       g[36]=sg[sp][36]; g[37]=sg[sp][37]; g[38]=sg[sp][38]; g[39]=sg[sp][39]; g[40]=sg[sp][40]; g[41]=sg[sp][41]; 
  206.       g[42]=sg[sp][42]; g[43]=sg[sp][43]; g[44]=sg[sp][44]; g[45]=sg[sp][45]; g[46]=sg[sp][46]; g[47]=sg[sp][47]; 
  207.       g[48]=sg[sp][48]; g[49]=sg[sp][49]; g[50]=sg[sp][50]; g[51]=sg[sp][51]; g[52]=sg[sp][52]; g[53]=sg[sp][53]; 
  208.       g[54]=sg[sp][54]; g[55]=sg[sp][55]; g[56]=sg[sp][56]; g[57]=sg[sp][57]; g[58]=sg[sp][58]; g[59]=sg[sp][59]; 
  209.       g[60]=sg[sp][60]; g[61]=sg[sp][61]; g[62]=sg[sp][62]; g[63]=sg[sp][63]; g[64]=sg[sp][64]; g[65]=sg[sp][65]; 
  210.       g[66]=sg[sp][66]; g[67]=sg[sp][67]; g[68]=sg[sp][68]; g[69]=sg[sp][69]; g[70]=sg[sp][70]; g[71]=sg[sp][71]; 
  211.       g[72]=sg[sp][72]; g[73]=sg[sp][73]; g[74]=sg[sp][74]; g[75]=sg[sp][75]; g[76]=sg[sp][76]; g[77]=sg[sp][77]; 
  212.       g[78]=sg[sp][78]; g[79]=sg[sp][79]; g[80]=sg[sp][80]; 
  213.  
  214.       sp--; 
  215.    } 
  216.  
  217.     void AddToSolutions() 
  218.    { 
  219.  
  220.       Solutions++; 
  221.       printf("\n%d ={",Solutions); 
  222.       PrintGrid(); 
  223.       printf("}\n"); 
  224.    } 
  225.     bool validSelection(int value,int pos) 
  226.    { 
  227.    //printf("%d",(m[gv] & r[gp]) == 0); 
  228.       return( (m[pos] & r[value]) == 0); 
  229.    } 
  230.  
  231.  
  232.  
  233. void SolveThis() 
  234. { 
  235. // if ((FirstSolution=true) && (Solutions>0))  { return; } 
  236.  if (not_impossible()==false) { return; } 
  237.  if (p<=80) { 
  238.     or_masks(); 
  239.   findsingles(); 
  240.  
  241.   while ((g[p] != 0) && (p < 81)) { ++p; } 
  242.   if (g[p]==0) { 
  243.      printf("%d ",p); 
  244.    for (int v=1;v<10;v++) { 
  245.     if (validSelection(v,p)==true) { 
  246.      stack(); 
  247.      g[p]=v; 
  248.      or_masks(); 
  249.      findsingles(); 
  250.       ++p; 
  251.       SolveThis(); 
  252.       --p; 
  253.       unstack(); 
  254.       or_masks(); 
  255.      } 
  256.     } 
  257.   } 
  258.  } 
  259.  else 
  260.  { 
  261.   if (fullgrid()==true) { 
  262.   AddToSolutions();     } 
  263.  } 
  264. } 
  265.  
  266.  
  267.  
  268.     int main(int argc, char *argv[]) 
  269.    { 
  270.       rarray(); 
  271.       printf("Sudoko Solver\n"); 
  272.    // printf("= %d",g[0]); 
  273.       PrintGrid(); 
  274.       p=0; 
  275.       FirstSolution=false; 
  276.    //Solutions=0; 
  277.  
  278.       or_masks(); 
  279.       SolveThis(); 
  280.       system("PAUSE"); 
  281.       return EXIT_SUCCESS; 
  282.    }
Reply With Quote Quick reply to this message  
•
•
Join Date: Jun 2005
Posts: 1,496
Reputation: WolfPack has a spectacular aura about WolfPack has a spectacular aura about WolfPack has a spectacular aura about 
Solved Threads: 104
Moderator
WolfPack's Avatar
WolfPack WolfPack is offline Offline
Mentally Challenged Mod.

Re: Soduku puzzle solver

 
0
  #2
Sep 27th, 2006
What were the compile errors? Give the error messages and the lines where the error occured. Don't give the line numbers. We can't count.
バルサミコ酢やっぱいらへんで
Reply With Quote Quick reply to this message  
•
•
Join Date: Sep 2006
Posts: 2
Reputation: Zabby is an unknown quantity at this point 
Solved Threads: 0
Zabby Zabby is offline Offline
Newbie Poster

Re: Soduku puzzle solver

 
0
  #3
Sep 27th, 2006
•
•
•
•
Originally Posted by WolfPack View Post
What were the compile errors? Give the error messages and the lines where the error occured. Don't give the line numbers. We can't count.

I got the problem figured out. I forgot to include the <stdio.h> library. The problem was an implicit declaration of the function printf(....).
Thanks alot for the immediate response. The program is now running.
Last edited by Zabby; Sep 27th, 2006 at 4:00 am.
Reply With Quote Quick reply to this message  
•
•
Join Date: Sep 2006
Posts: 21
Reputation: risby is an unknown quantity at this point 
Solved Threads: 0
risby's Avatar
risby risby is offline Offline
Newbie Poster

Re: Soduku puzzle solver

 
1
  #4
Sep 27th, 2006
•
•
•
•
Originally Posted by Zabby View Post
Hi is there anyone willing enough to help me solve my problem. I'm using both Dev C++ 5 in windows and g++ in Linux to compile this code but was unable to do it successfully. Can any one help mi pliz 

 
    bool not_impossible() { 
   // Check grid to see if it is impossible. 
   // If a square is empty but has a mask of 1022, then the grid is impossible. 
      int i=0; 
      bool s=true; 
      while ((i<81) && (s=true)) { 
         if ((m[i]==1022) && (g[i]==0)) { 
            s=false;  
         } 
         i++; 
      } 
      return s; 
   }
I presume this should be a test for equality rather than an assignment.
Good judgment comes from experience, and a lot of that comes from bad judgment.
Reply With Quote Quick reply to this message  
Reply

Quick Reply to Thread
This thread has been marked solved.
Perhaps start a new thread instead?
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Similar Threads
Other Threads in the C++ Forum
Thread Tools Search this Thread



Tag cloud for C++
api application array arrays based beginner binary bmp c++ c/c++ calculator char char* class classes code coding compile compiler console conversion convert count data database delete deploy developer display dll dynamiccharacterarray email encryption error file format forms fstream function functions game generator givemetehcodez graph homeworkhelp iamthwee ifstream image input int java lib list loop looping loops map math matrix memory multiple newbie news number numbertoword output pointer problem program programming project python random read recursion recursive reference return rpg simple sorting spoonfeeding string strings struct template templates text tree url variable vector video visual visualstudio win32 windows winsock wordfrequency wxwidgets
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC