很菜的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