C++中的数独检查器算法

Question

我目前正在研究一种算法，使用数字1-9来查找所有带有9位数字的数字，而没有任何重复。我正在测试一个我认为过滤数字的理论，因为这样可以创建一个更有效的数独检查器。

我实现的代码执行以下操作。 （a）（b）（c）（d）（e）（f）（g）（h）（i）= ###### ###。

我的理论是，通过检查数字（a-i）的和是否等于45，a到i的乘积等于9！并且ai的逆和的总和等于大约2.828968（或1 + 1/2 + 1/3 ... 1/9）

问题是我过滤了9位数字ai的逆数的总和，可能的9位数字预测的数量小于9！ （可能的实际数量）。我不确定它为什么会过滤这么多，但它所捕捉的数字没有任何重复（这很好）。

我的想法是，我玩双打的方式搞乱了算法。

这里是我的代码：

#include <iostream> 
#include <iomanip> 

using namespace std; 

int main() 
{ 
    int product; 
    int sum; 
    int count=0; 
    double inverseSum; 
    double correctInverseSum=(1.0/1.0)+(1.0/2.0)+(1.0/3.0)+(1.0/4.0)+(1.0/5.0)+ 
(1.0/6.0)+(1.0/7.0)+(1.0/8.0)+(1.0/9.0); 
     for(double a=1.0; a<10.0; a++){ 
      for(double b=1.0; b<10.0; b++){ 
       for(double c=1.0; c<10.0; c++){ 
       for(double d=1.0; d<10.0; d++){ 
        for(double e=1.0; e<10.0; e++){ 
         for(double f=1.0; f<10.0; f++){ 
          for(double g=1.0; g<10.0; g++){ 
           for(double h=1.0; h<10.0; h++){ 
            for(double i=1.0; i<10.0; i++){ 
             product=a*b*c*d*e*f*g*h*i; 
             sum=a+b+c+d+e+f+g+h+i; 
             if(product==9*8*7*6*5*4*3*2*1 && sum==45){ 
              inverseSum=(1.0/a)+(1.0/b)+(1.0/c)+(1.0/d)+ 
              (1.0/e)+(1.0/f)+(1.0/g)+(1.0/h)+(1.0/i); 
              if(inverseSum==correctInverseSum) 
              { 
               count++; 
              } 
             } 
            } 
           } 
          } 
         } 
        } 
       } 
      } 
     } 
    } 
    cout<<"This is the count:"<<count<<endl; 
    return 0; 
} 

Answer 1

现在，我看到这么多的for循环后洗我的眼睛，我想说的候选人是：

if(inverseSum==correctInverseSum) 

double s为不完全可代表的，所以你必须检查使用一个小epsilon平等。喜欢的东西：

if (fabs(inverseSum - correctInverseSum) < std::numeric_limits<double>::epsilon()) 

你需要#include <limits>。

Answer 2

你将需要在检查一些容错：

if(fabs(inverseSum-correctInverseSum) < 1e-6) count++ 

另外，通过乘以9！你在每学期的总和得到

b*c*d*e*f*g*h*i + a*c*d*e*f*g*h*i ... 

（一人失踪因素）。然后你可以使用整数算术代替浮点数。

Answer 3

让我们运行一个快速实验：让我们试着计算逆之和由大变小，并以相反的顺序：

#include <algorithm> 
#include <numeric> 
#include <iostream> 
#include <iterator> 
#include <vector> 

struct generator 
{ 
    generator(): d_value() {} 
    double operator()() { return 1.0/++this->d_value; } 
    double d_value; 
}; 

int main() 
{ 
    std::vector<double> values; 
    std::generate_n(std::back_inserter(values), 9, generator()); 
    double ordered(std::accumulate(values.begin(), values.end(), 0.0)); 
    double reversed(std::accumulate(values.rbegin(), values.rend(), 0.0)); 
    std::cout << "ordered=" << ordered << " " 
       << "reversed=" << reversed << " " 
       << "difference=" << (reversed - ordered) << " " 
       << "\n"; 
} 

如果这其中确切的数学，显然这应该产生相同的总和。毕竟，它们是同一套价值观。不幸的是，事实证明，这些值并不完全相同。下面是输出它显示我：

ordered=2.82897 reversed=2.82897 difference=4.44089e-16 

的问题是，该值不准确，将两个这些非精确值的介绍了一些错误。通常，错误并不重要，但是尝试比较标识的结果将不起作用：取决于操作的顺序，涉及具有不同舍入结果的不同操作数。

Answer 4

古老的谚语，但请：不要重复自己。

保持干燥。

当你发现自己写这样的代码时，你应该问自己为什么我需要用这种方式重复自己。

还有很多其他的选择。

1 - 递归。让自己对这个概念感到满意。

2 - mod运算符对于i = 0至100 R = I 10％，C = 1/10

3 - 重新评估的问题。您试图解决比所需更难的问题

Answer 5

您是否听说过std :: bitset？您只需要9位验证，这可能在您的预算内。

我一直想获得一些实践与可变参数模板，所以我写了这个给你：（C++ 11名专家，随时把它撕得粉碎）

#include <bitset> 
#include <iostream> 

template<unsigned long i> 
bool test_helper(std::bitset<i> seen) { 
    return seen.count() == i; 
} 

template<unsigned long i, typename T, typename... Args> 
bool test_helper(std::bitset<i> seen, T arg1, Args... args) { 
    return test_helper(seen.set(arg1 - 1), args...); 
} 

template<typename... Args> 
bool test(Args... args) { 
    return test_helper(std::bitset<sizeof... (Args)>(), args...); 
} 

template<unsigned long size, bool done = false> 
struct Counter { 
    template<typename ... Args> 
    unsigned long operator()(Args... args) { 
    unsigned long count = 0; 
    for (int a = 1; a < 10; ++a) 
     count += Counter<size, size == sizeof...(Args)+1>()(a, args...); 
    return count; 
    } 
}; 

template<unsigned long i> 
struct Counter<i, true> { 
    template<typename ... Args> 
    unsigned long operator()(Args... args) { 
    return test(args...); 
    } 
}; 

int main(int argc, char** argv) { 
    std::cout << Counter<9>()() << std::endl; 
    return 0; 
} 

如果你真的坚持使用复杂的启发式，你也可以通过有理算术得到一些经验来计算你的逆和。它应为1清楚总和/一个_我是Σ _Ĵ（Π _我  一个_我）/一个_Ĵ所有由Π _我  一个_我划分;你已经在计算分母了，所以只需计算分子，它的最大值是9 。但是，尽管如此，这个糟糕的解决方案似乎对我来说简单得多。