Алгоритм проверки судоку в переполнении стека
В настоящее время я работаю над алгоритмом, чтобы найти все числа с 9 цифрами, используя числа 1-9 без повторов. Я проверяю теорию, которая у меня есть, что фильтрация чисел как таковая сделает более эффективную проверку судоку.
Код, который я реализовал, делает следующее. Он использует цикл for для мест 1-9 в числе, таких что (a) (b) (c) (d) (e) (f) (g) (h) (i) = ###### ###.
Моя теория состоит в том, что, проверяя, равна ли сумма чисел (a-i) 45, произведение a через i равно 9! и что сумма инверсий a-i равна примерно 2.828968 (или 1 + 1/2 + 1/3 … 1/9)
Проблема в том, что после того, как я отфильтрую 9-значные числа по сумме инверсий a-i, число возможных 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;
}
Решение
Теперь, когда я вымыл глаза, увидев так много петель, я бы сказал, что кандидат:
if(inverseSum==correctInverseSum)
doubleОни не совсем представимы, поэтому вам придется проверять равенство с помощью небольшого эпсилона. Что-то вроде:
if (fabs(inverseSum - correctInverseSum) < std::numeric_limits<double>::epsilon())
Вам нужно будет #include <limits>,
Другие решения
Вам понадобится некоторая устойчивость к ошибкам при проверке:
if(fabs(inverseSum-correctInverseSum) < 1e-6) count++
Или умножьте на 9!
b*c*d*e*f*g*h*i + a*c*d*e*f*g*h*i ...
(один недостающий фактор в каждом слагаемом сумме). Тогда вы можете использовать целочисленную арифметику вместо чисел с плавающей точкой.
Давайте проведем быстрый эксперимент: попробуем вычислить обратную сумму от большой к маленькой и в обратном порядке:
#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
Проблема в том, что значения не являются точными, и добавление двух из этих неточных значений приводит к некоторой ошибке. Часто ошибка не имеет большого значения, но попытка сравнить результаты для идентификации не сработает: в зависимости от порядка операций используются разные операнды с разными округленными результатами.
Старая поговорка, но, пожалуйста: не повторяйся.
Держите это сухим.
Когда вы обнаружите, что пишете такой код, вы должны спросить себя, зачем мне повторяться таким образом.
Есть много других вариантов.
1 — рекурсия. освоиться с концепцией.
2 — оператор мода для i = от 0 до 100 r = i% 10, c = i / 10
3 — переоценка проблемы. Вы пытаетесь решить проблему, которая сложнее, чем необходимо
Разве вы не слышали о std :: bitset? Вам нужно только девять бит, чтобы проверить, что, вероятно, в пределах вашего бюджета.
Я намеревался немного попрактиковаться с шаблонами с переменными числами, поэтому я написал это для вас: (Эксперты 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 / ая это ΣJ (Πя я) / АJ все разделены на Πя я; вы уже вычисляете знаменатель, поэтому нужно только вычислить числитель, максимальное значение которого равно 99. Но, тем не менее, битовое решение кажется мне намного проще.