fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <cctype>
  5. #include <algorithm>
  6. #include <valarray>
  7.  
  8. using namespace std;
  9.  
  10. /*
  11. 数独を総当りで解く関数を2つ作成 
  12.  
  13. 1, forを使用したもの 
  14. 2, 再起を使用したもの 
  15.  
  16. ・1～9の数字を使用 
  17. ・盤面は9*9マス(3*3のブロックが9つ) 
  18. ・縦 + 横 + ブロック(3*3)において数字が重複しないようにする 
  19. ・問題が不正な(問題の時点で重複があった)場合問題が不正と出力 
  20. ・問題に空行が見つかった場合はその行の値を全て無しとみなす 
  21. ・読み込みが9行未満で終了した場合はそれ以降の行も値を無しとみなす 
  22. ・解が100個以上見つかった場合は100個目を出力 
  23. ・解が見つからなかった場合は解無しと出力 
  24.  
  25. 問題の受け取りはテキストから一行ずつ 
  26. 各行につき9文字+改行 
  27. 値を指定しない場合はドット'.'を指定する 
  28. */
  29.  
  30. template <int N = 3, class Num = int, Num InvalidValue = -1, Num Empty = 0 >
  31. struct Sudoku {
  32.     static const int kBaseSize        = N;
  33.     typedef Num number_type;
  34.  
  35.     static const number_type kInvalidValue = InvalidValue;
  36.     static const number_type kEmpty        = Empty;
  37.  
  38.     typedef Sudoku<kBaseSize,number_type,kInvalidValue,kEmpty> this_type;
  39.  
  40.     typedef vector<number_type> SVector;
  41.     typedef valarray<number_type> SArray;
  42.     typedef vector<SArray> SAVector;
  43.  
  44.     SArray table;
  45.  
  46.     Sudoku() : table(0,N*N*N*N) {}
  47.     Sudoku(const this_type& r) : table(r.table) {}
  48.     Sudoku(number_type* aProblem) : table(aProblem,N*N*N*N) {}
  49.     Sudoku(SVector aProblem) : table(aProblem.data(),N*N*N*N) {}
  50.  
  51.     bool checkPointForRange(int x, int y){
  52.         return ! ( x < 0 || N*N <= x || y < 0 || N*N <= y );
  53.     }
  54.  
  55.     SAVector relatedCompartmentsOf(int x, int y){
  56.         if( !checkPointForRange(x,y) )
  57.             return SAVector();
  58.  
  59.         int Y_ = (int)(y/N); // avoid optimization
  60.         int X_ = (int)(x/N); // avoid optimization
  61.         SAVector coms;
  62.         // x axis
  63.         coms.emplace_back( table[ gslice(y*N*N + 0,       {1,   N*N},{N*N,1}) ] );
  64.         // y axis
  65.         coms.emplace_back( table[ gslice(0     + x,       {N*N, 1  },{N*N,1}) ] );
  66.         // n*n square
  67.         coms.emplace_back( table[ gslice(Y_*N*N*N + X_*N, {N,   N  },{N*N,1}) ] );
  68.         return coms;
  69.     }
  70.  
  71.     SVector candidatesOf(int x, int y){
  72.         bool has[N*N +1] = {false};
  73.         SAVector coms = relatedCompartmentsOf(x,y);
  74.  
  75.         if( coms.empty() ) return SVector();
  76.  
  77.         for_each(coms.begin(),coms.end(), [&has](SArray& a){
  78.             for_each(begin(a),end(a), [&has](number_type& a){ has[a] = true; });
  79.         });
  80.  
  81.         SVector candidates;
  82.         for( int i = 1; i < (N*N+1); i++ )
  83.             if( ! has[i] )
  84.                 candidates.emplace_back(i);
  85.         return candidates;
  86.     }
  87.  
  88. private:
  89.     bool hasOverlap_(SArray& a){
  90.         bool has[N*N +1] = {false};
  91.         for(int i = 0; i < N*N; i++ ){
  92.             if( a[i] == kEmpty ) continue;
  93.             if( has[ a[i] ] ) return true;
  94.             has[ a[i] ] = true;
  95.         }
  96.         return false;
  97.     }
  98.  
  99. public:
  100.     bool isOverlapOn( int x, int y ){
  101.         SAVector coms = relatedCompartmentsOf(x,y);
  102.         return !coms.empty() &&
  103.             any_of(coms.begin(),coms.end(),
  104.                 [&](SArray& a){ return hasOverlap_(a); });
  105.     }
  106.  
  107.     bool hasOverlap(){
  108.         for( int y = 0, x = 0; y < N*N; x++, y++ ){
  109.             if( isOverlapOn((int)(y/N) + (x%N)*N, y) ){
  110.                 return true;
  111.             }
  112.         }
  113.         return false;
  114.     }
  115.  
  116.     bool set( int x, int y, number_type value ){
  117.         if( !checkPointForRange(x,y) ||
  118.             ( ( value < 1 || N*N < value ) && value != kEmpty )
  119.         )
  120.             return false;
  121.  
  122.         table[y*N*N + x] = value;
  123.         return true;
  124.     }
  125.  
  126.     number_type get( int x, int y ){
  127.         return ( checkPointForRange(x,y) ) ?
  128.             table[y*N*N + x]: kInvalidValue;
  129.     }
  130.  
  131.     bool isEmpty( int x, int y ){
  132.         return get(x,y) == kEmpty;
  133.     }
  134.  
  135.     bool setEmpty( int x, int y ){
  136.         return set(x,y,kEmpty);
  137.     }
  138.  
  139.     static number_type getEmptyValue(){ return kEmpty; }
  140.  
  141.     ostream& show(ostream& os){
  142.         string s(N*N+1,0);
  143.         for( int i = 0; i < N*N; i++ ){
  144.             SArray v = table[ gslice(i*N*N,{1,N*N},{1,1}) ];
  145.             v += (number_type)('0');
  146.             copy( begin(v), end(v), s.begin() );
  147.             replace( begin(s), end(s), '0', ' ' );
  148.             os << s << endl;
  149.         }
  150.         return os;
  151.     }
  152.     ostream& show(){
  153.         return show(cout);
  154.     }
  155. };
  156.  
  157. template <int n = 3>
  158. struct Solver {
  159.     typedef Sudoku<n> Su;
  160.     typedef typename Su::SVector SVector ;
  161.     typedef typename Su::number_type SNumber ;
  162.  
  163.     static const int nn = n*n;
  164.  
  165.     struct Helper {
  166.         int x;
  167.         int y;
  168.         bool succeed;
  169.         Su problem;
  170.         Su current;
  171.         vector<Su> answers;
  172.  
  173.         Helper(Su& probSrc):
  174.             x(0), y(0),
  175.             succeed(true),
  176.             problem(probSrc),
  177.             current(problem)
  178.         {
  179.             if(fixed()) moveNext();
  180.         }
  181.  
  182.  
  183.         bool move(int i, int it){
  184.             int cx = x;
  185.             int cy = y;
  186.             do if( ! problem.checkPointForRange(x+=i,0) ){
  187.                 if( ! problem.checkPointForRange(0,y+=i) ){
  188.                     y = cy; x = cx;
  189.                     return succeed = false;
  190.                 }
  191.                 x = it;
  192.             } while ( fixed() );
  193.             return succeed = true;
  194.         }
  195.  
  196.         bool fixed()       { return !problem.isEmpty(x,y); }
  197.         bool moveNext()    { return move(1, 0);    }
  198.         bool movePrev()    { return move(-1,nn-1); }
  199.         bool moveFailed()  { return !succeed; }
  200.         int linearIndex()  { return y*nn + x; }
  201.  
  202.  
  203.         SVector candidate(){ return current.candidatesOf(x,y); } 
  204.         bool set(SNumber i){ return current.set(x,y,i); } 
  205.         bool setEmpty()    { return current.setEmpty(x,y); } 
  206.         SNumber get()      { return current.get(x,y); } 
  207.  
  208.         void pushAnswer()  { answers.push_back(current); }
  209.         int sizeAnswers()  { return answers.size(); }
  210.     };
  211.  
  212.     bool readAndSolve(){
  213.         vector<int> N(nn*nn,Su::getEmptyValue());
  214.         auto N_it = N.begin();
  215.         string s;
  216.  
  217.         for( int i = 0; getline(cin,s) && i < n*n; i++ ){
  218.             if( s.empty() ){
  219.                 N_it += nn;
  220.                 continue;
  221.             }
  222.             if( s.length() != n*n ){
  223.                 cout << "error: invalid length of line. len = "
  224.                      << s.length() << endl << s << endl;
  225.                 return false;
  226.             }
  227.             std::replace(s.begin(),s.end(),'.','0');
  228.             if( ! all_of(s.begin(),s.end(),::isdigit) ){
  229.                 cout << "error: invalid char at line." << s << endl;
  230.                 return false;
  231.             }
  232.             N_it = std::transform(s.begin(),s.end(),N_it,
  233.                 [](char& c){ return (int)(c - '0'); });
  234.         }
  235.  
  236.         Su problem(N);
  237.  
  238.         cout << "Problem" << endl;
  239.         problem.show();
  240.         if( problem.hasOverlap() ){
  241.             cout << "Problem has overlap." << endl;
  242.             return false;
  243.         }
  244.  
  245.         Helper h1(problem);
  246.         cout << endl << "<< for loop >>" << endl;
  247.         getAnswersByForLoop(h1,100);
  248.         showAnswer(h1.answers);
  249.  
  250.         Helper h2(problem);
  251.         cout << endl << "<< rec. call >>" << endl;
  252.         getAnswersByRecursiveCall(h2,100);
  253.         showAnswer(h2.answers);
  254.  
  255.         return true;
  256.     }
  257.  
  258.     void showAnswer( vector<Su>& answers ){
  259.         if( answers.empty() ){
  260.             cout << "No answers were found." << endl;
  261.         } else {
  262.             cout << answers.size() << " answers were found." << endl;
  263.             cout << "The last one is below." << endl;
  264.             answers.back().show();
  265.         }
  266.     }
  267.  
  268.     void getAnswersByForLoop(Helper& h, int limit ){
  269.  
  270.         // max = n^5 * sizeof SNumber
  271.         for( SVector cands[nn*nn]; !h.moveFailed(); ){
  272.             // forward
  273.             {
  274.                 SVector& cd = cands[h.linearIndex()];
  275.                 // entered next empty element.
  276.                 if( cd.empty() )
  277.                     cd = h.candidate();
  278.  
  279.                 // if no candidates, goto backward process.
  280.                 if( !cd.empty() ){
  281.                     h.set( cd.back() );
  282.  
  283.                     // it could have moved to the next empty element.
  284.                     if( h.moveNext() ) continue;
  285.  
  286.                     // or it is the answer.  
  287.                     h.pushAnswer();
  288.  
  289.                     if( h.sizeAnswers() >= limit ){
  290.                         cout << "Limit exceeds: too many answers. aborted." << endl;
  291.                         return;
  292.                     }
  293.                     // goto backward process.
  294.                 }
  295.             }
  296.  
  297.             // backward
  298.             // if prev() is false, then completed. (current is the first element.)
  299.             while( h.movePrev() ){
  300.                 // search candidate.
  301.                 SVector& cdc = cands[h.linearIndex()];
  302.  
  303.                 // current value is the last candidate.
  304.                 if( cdc.empty() || cdc.front() == h.get() ) {
  305.                     // there are no answers exist along with this path.
  306.                     h.setEmpty();
  307.                     cdc.clear();
  308.                 } else {
  309.                     cdc.pop_back();
  310.                     break;
  311.                 }
  312.             }
  313.         }
  314.     }
  315.  
  316.     void getAnswersByRecursiveCall(Helper& h, int limit ){
  317.         for( auto cd: h.candidate() ){
  318.             h.set(cd);
  319.             if( h.moveNext() )
  320.                 getAnswersByRecursiveCall(h,limit);
  321.             else {
  322.                 h.pushAnswer();
  323.                 if( h.sizeAnswers() >= limit )
  324.                     cout << "Limit exceeds: too many answers. aborted." << endl;
  325.             }
  326.  
  327.             if( h.sizeAnswers() >= limit )
  328.                 return;
  329.  
  330.             h.setEmpty();
  331.         }
  332.         h.movePrev();
  333.     }
  334. };
  335.  
  336. int main() {
  337.     Solver<3>().readAndSolve();
  338.     return 0;
  339. }
  340.  
  341.  
  342.  
Success #stdin #stdout 0.04s 3452KB
comments (?)
stdin 
1........
2........
...3....4
.......1.
....9....
.....7...
.8.......
.........
.........
stdout 
Problem
1        
2        
   3    4
       1 
    9    
     7   
 8       
         
         

<< for loop >>
Limit exceeds: too many answers. aborted.
100 answers were found.
The last one is below.
198764532
243985761
765321984
976852413
854193627
312647859
581279346
629438175
437516298

<< rec. call >>
Limit exceeds: too many answers. aborted.
100 answers were found.
The last one is below.
134256789
257489136
698371254
325648917
471592368
869137542
983765421
742813695
516924873
https://ideone.com/2bLzS9
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!