很菜的Sodoku Solver

其实是模拟了手工填写数独的方法，用的排除法。这个代码的不足在于没有怎么规划，其实board::pencilMark()完全可以做成按行、列、正方形顺序将所有的方格的pencil mark全部填好。稍加改动，可以解１６*１６或８*８的数独。

  1. using namespace std;
  2.  
  3. class cell
  4. {
  5. private:
  6.     int number;
  7.     int pencil;
  8. public:
  9.     bool getPencil(int num);
  10.     bool setPencil(int num);
  11.     bool isHavingPencil(void);
  12.     int  getAllPencil(void);
  13.     bool erasePencil(int num);
  14.     int  getNumber(void);
  15.     bool fillNumber(int num);
  16.     bool initCell(int num);
  17.     bool clearPencil(void);
  18. protected:
  19. };
  20.  
  21. bool cell::getPencil(int num)
  22. {
  23.     return (pencil & (1<<num))?true:false;
  24. }
  25.  
  26. bool cell::setPencil(int num)
  27. {
  28.     if(!num)
  29.         return true;
  30.     if(pencil & (1<<num))
  31.         ;
  32.     else
  33.         pencil += (1<< num);
  34.     return true;
  35. }
  36.  
  37. bool cell::isHavingPencil(void)
  38. {
  39.     return pencil?true:false;
  40. }
  41.  
  42. int  cell::getAllPencil(void)
  43. {
  44.     return pencil;
  45. }
  46.  
  47. bool cell::erasePencil(int num)
  48. {
  49.     if(!num)    //Meet zero
  50.         return true;
  51.     if(pencil & (1 << num))
  52.         pencil -= 1<< num;
  53.     return true;
  54. }
  55.  
  56. int  cell::getNumber(void)
  57. {
  58.     return number;
  59. }
  60.  
  61. bool cell::fillNumber(int num)
  62. {
  63.     number = num;
  64.     clearPencil();
  65.     return true;
  66. }
  67.  
  68. bool cell::initCell(int num)
  69. {
  70.     number = num;
  71.     pencil = num?0:((1 << 10) - 2);
  72.     return true;
  73. }
  74.  
  75. bool cell::clearPencil(void)
  76. {
  77.     pencil = 0;
  78.     return true;
  79. }
  80.  
  81. class board
  82. {
  83. private:
  84.     cell boardCells[10][10];
  85.     int blankCell;
  86.     int cellSolved;
  87. public:
  88.     bool solveOneStep(void);
  89.     bool pencilMark(int x, int y);
  90.     bool decideNumber(void);
  91.     void printBoard(void);
  92.     bool readCell(void);
  93. protected:
  94.  
  95. };
  96.  
  97. void getSquare(const int x, const int y, int & left, int & top)
  98. {
  99.     static int coordinates[]={0,1,1,1,4,4,4,7,7,7};
  100.     left = coordinates[x];
  101.     top = coordinates[y];
  102.     return;
  103. }
  104.  
  105. bool board::pencilMark(int x, int y) //True for having pencil mark, false for not.
  106. {
  107.     int linearPointer, sqLinePointer, sqColumnPointer, sqLeft, sqTop;
  108.     int reading;
  109.  
  110.     if(!(boardCells[x][y].getNumber())) //Blank Cell.
  111.     {
  112.         boardCells[x][y].initCell(0);   //Initialize pencil marks.
  113.         //Line
  114.         for(linearPointer = 1; linearPointer <= 9; linearPointer ++)
  115.         {
  116.             if (linearPointer == y)
  117.                 continue;
  118.             reading = boardCells[x][linearPointer].getNumber();
  119.             if (reading)
  120.                 boardCells[x][y].erasePencil(reading);
  121.         }
  122.    
  123.         //Column
  124.         for(linearPointer = 1; linearPointer <= 9; linearPointer ++)
  125.         {
  126.             if (linearPointer == x)
  127.                 continue;
  128.             reading = boardCells[linearPointer][y].getNumber();
  129.             if (reading)
  130.                 boardCells[x][y].erasePencil(reading);
  131.         }
  132.        
  133.         //Square
  134.         getSquare(x, y, sqLeft, sqTop);
  135.         for(sqLinePointer = 0; sqLinePointer < 3; sqLinePointer ++)
  136.         {
  137.             if (x - sqLeft == sqLinePointer)
  138.                 continue;
  139.             for(sqColumnPointer = 0; sqColumnPointer < 3; sqColumnPointer ++)
  140.             {
  141.                 if(y - sqTop == sqColumnPointer)
  142.                     continue;
  143.                 reading = boardCells[sqLeft + sqLinePointer][sqTop + sqColumnPointer].getNumber();
  144.                 if(reading)
  145.                     boardCells[x][y].erasePencil(reading);
  146.             }
  147.         }
  148.     }
  149.     else
  150.         return true;
  151.     return boardCells[x][y].isHavingPencil();
  152. }
  153.  
  154. bool board::decideNumber(void) //True for progress, false for no.
  155. {
  156.     int x, y, marks;
  157.     bool retlog;
  158.  
  159.     cellSolved = 0;
  160.  
  161.     //Calculate pencil marks.
  162.     for(x = 1; x <= 9; x++)
  163.     {
  164.         for(y = 1; y <= 9; y++)
  165.         {
  166.             retlog = pencilMark(x, y);
  167.             if(!retlog)
  168.                 goto noSolution;
  169.         }
  170.     }
  171.  
  172.     //Search for single pencil mark.
  173.     for(x = 1; x <= 9; x++)
  174.     {
  175.         for(y = 1; y<= 9; y++)
  176.         {
  177.             if(boardCells[x][y].getNumber()) //Already have number
  178.                 continue;
  179.             marks = boardCells[x][y].getAllPencil();
  180.             if(!(marks & (marks - 1))) // Only have one number.
  181.             {
  182.                 switch(marks)
  183.                 {
  184.                 case 2:
  185.                     boardCells[x][y].initCell(1);break;
  186.                 case 4:
  187.                     boardCells[x][y].initCell(2);break;
  188.                 case 8:
  189.                     boardCells[x][y].initCell(3);break;
  190.                 case 16:
  191.                     boardCells[x][y].initCell(4);break;
  192.                 case 32:
  193.                     boardCells[x][y].initCell(5);break;
  194.                 case 64:
  195.                     boardCells[x][y].initCell(6);break;
  196.                 case 128:
  197.                     boardCells[x][y].initCell(7);break;
  198.                 case 256:
  199.                     boardCells[x][y].initCell(8);break;
  200.                 case 512:
  201.                     boardCells[x][y].initCell(9);break;
  202.                 default:
  203.                     cout << "ERROR! ";
  204.                 }
  205.                 blankCell--;
  206.                 cellSolved++;
  207.             }
  208.         }
  209.     }
  210.     if(cellSolved)
  211.         return true;
  212.    
  213.     int searchNum;
  214.     int markCount;
  215.     int lastPos, lastSqX, lastSqY;
  216.     int linearIndex, sqRowIndex, sqColumnIndex, sqLeft, sqTop;
  217.     //Search for only candidates.
  218.          
  219.     //By Row
  220.     for(x = 1; x <= 9; x++)
  221.     {
  222.         for(searchNum = 1; searchNum <= 9; searchNum ++)
  223.         {
  224.             markCount = 0;
  225.             lastPos = 0;
  226.             for(linearIndex = 1; linearIndex <= 9; linearIndex++)
  227.             {
  228.                 if(boardCells[x][linearIndex].getPencil(searchNum))
  229.                 {
  230.                     markCount ++;
  231.                     lastPos = linearIndex;
  232.                 }                   
  233.             }
  234.             if(markCount == 1)
  235.             {
  236.                 boardCells[x][lastPos].initCell(searchNum);
  237.                 goto foundSolution;
  238.             }
  239.         }
  240.     }
  241.  
  242.     //By Column
  243.     for(y = 1; y <= 9; y++)
  244.     {
  245.         for(searchNum = 1; searchNum <= 9; searchNum ++)
  246.         {
  247.             markCount = 0;
  248.             lastPos = 0;
  249.             for(linearIndex = 1; linearIndex <= 9; linearIndex++)
  250.             {
  251.                 if(boardCells[linearIndex][y].getPencil(searchNum))
  252.                 {
  253.                     markCount ++;
  254.                     lastPos = linearIndex;
  255.                 }                   
  256.             }
  257.             if(markCount == 1)
  258.             {
  259.                 boardCells[lastPos][y].initCell(searchNum);
  260.                 goto foundSolution;
  261.             }
  262.         }
  263.     }
  264.    
  265.     //By Square
  266.     for(sqLeft = 1; sqLeft < 9; sqLeft += 3)
  267.     {
  268.         for(sqTop = 1; sqTop < 9; sqTop += 3)
  269.         {
  270.             for(searchNum = 1; searchNum <= 9; searchNum ++)
  271.             {
  272.                 markCount = 0;
  273.                 lastSqX = 0, lastSqY = 0;
  274.                 for(sqRowIndex = 0; sqRowIndex < 3; sqRowIndex ++)
  275.                 {
  276.                     for(sqColumnIndex = 0; sqColumnIndex < 3; sqColumnIndex++)
  277.                     {
  278.                         if(boardCells[sqLeft + sqRowIndex][sqTop + sqColumnIndex].getPencil(searchNum))
  279.                         {
  280.                             markCount ++;
  281.                             lastSqX = sqRowIndex, lastSqY = sqColumnIndex;
  282.                         }
  283.                     }
  284.                 }
  285.                 if(markCount == 1)
  286.                 {
  287.                     boardCells[sqLeft + lastSqX][sqTop + lastSqY].initCell(searchNum);
  288.                     goto foundSolution;
  289.                 }
  290.             }
  291.         }
  292.     }
  293.            
  294.     if(blankCell)   //Not solved yet.
  295.         cout << "Cannot solve. " << endl;
  296.     return false;
  297.  
  298. foundSolution:
  299.     cellSolved ++;
  300.     blankCell --;
  301.     return true;
  302.    
  303. noSolution:
  304.     cout << "No Solution!!" << endl;
  305.     return false;
  306.    
  307. }
  308.  
  309. bool board::solveOneStep(void)
  310. {
  311.     int x, y;
  312.     for(x = 1; x <= 9; x++)
  313.         for(y = 1; y<= 9; y++)
  314.             pencilMark(x,y);
  315.     return decideNumber();
  316. }
  317.  
  318. bool board::readCell(void)
  319. {
  320.     int x, y, recv;
  321.     blankCell = 0;
  322.     for(x = 1; x <= 9; x++)
  323.         for(y = 1; y <= 9; y++)
  324.         {
  325.             cin >> recv;
  326.             boardCells[x][y].initCell(recv);
  327.             if(recv==0)
  328.                 blankCell++;
  329.         }
  330.     return true;
  331. }
  332.  
  333. void board::printBoard(void)
  334. {
  335.     int x, y, num;
  336.     num = 0;
  337.     for(x = 1; x <= 9; x++)
  338.     {
  339.         for(y = 1; y <= 9; y++)
  340.         {
  341.             num = boardCells[x][y].getNumber();
  342.             cout << " " << num;
  343.         }
  344.         cout << "\n";
  345.     }
  346. }
  347.  
  348. int _tmain(void)
  349. {
  350.         board game;
  351.     int counter = 0;
  352.    
  353.     cout << "VIKTOR\'S SODUKU SOLVER VER 1.00A SEPT 7, 2008\n";
  354.     cout << "Input soduku, 0 for blank\n";
  355.    
  356.     game.readCell();
  357.     cout << "Your initial soduku is: \n\n";
  358.     game.printBoard();
  359.  
  360.     while(game.solveOneStep())
  361.     {
  362.         counter ++;
  363.     /*DEBUG CODE
  364.         cout << "The " << counter << " step of soduku is: \n\n";
  365.         game.printBoard();
  366.     */
  367.     }
  368.  
  369.     cout << "Your soduku is solved after " << counter << " steps as follows: \n" ;
  370.     game.printBoard();
  371.    
  372.     return 0;
  373. }
  374.  
  375.  

C soduku solver 数独 c++ 排除法 很菜 Comments(1) Sep 09, 2008 12:46:32 AM

VC++ 2005里CFile类ReadHuge和WriteHuge废了

统一转入Read()和Write()，望周知。

 

The process of atmospheric scattering, deflects light rays from a straight path and thus causes blurring or haziness. It affects the blue end of the visible spectrum more than the red end, and consequently the blue waveband is not used in many remote-sensing systems.

C VC++ 2005 ReadHuge WriteHuge Obsolute 废 旧 蓝光 波段 blue Waveband Comments(2) May 31, 2008 10:01:28 PM