Решить проблему числа Аристотеля

21

Головоломка чисел Аристотеля - это задача заполнения каждой из 19 ячеек в гексагональной сетке уникальным целым числом от 1 до 19 таким образом, чтобы сумма по каждой оси составляла 38.

Вы можете изобразить игровое поле в следующем виде:

аристотелевская сетка

И загадка, по сути, является решением следующего набора из пятнадцати уравнений:

((a + b + c) == 38 && (d + e + f + g) == 38 && (h + i + j + k + l) == 
   38 && (m + n + o + p) == 38 && (q + r + s) == 38 && (a + d + h) == 
   38 && (b + e + i + m) == 38 && (c + f + j + n + q) == 
   38 && (g + k + o + r) == 38 && (l + p + s) == 38 && (c + g + l) == 
   38 && (b + f + k + p) == 38 && (a + e + j + o + s) == 
   38 && (d + i + n + r) == 38 && (h + m + q) == 38)

Где каждая переменная является уникальным числом в наборе {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19}.

Существует множество возможных решений и 19!возможных комбинаций целых чисел, поэтому наивная грубая сила будет непрактичной.

Правила:

  1. Нет жесткого кодирования ответа или поиска ответа в другом месте; ваш код должен найти его самостоятельно
  2. Скорость не имеет значения, но вы должны показать свои результаты, поэтому код, выполнение которого занимает 1000 лет, вам не поможет
  3. Найти все ответы
  4. Относитесь к ответам, которые идентичны при ротации, как к идентичным
  5. Вычтите 5% от общего количества байтов, если вы выводите результаты в привлекательной соте
  6. Побеждает несколько байтов
Майкл Стерн
источник
Отличный вопрос, с нетерпением жду возможности найти решение.
ProgrammerDan
Считаете ли вы повернутые ответы уникальными? Например, предположим, что a, b, c = 1, 18, 19 индексирует конкретное решение, если мы установим c, g, l = 1, 18, 19 и все другие значения «повернуты» для соответствия, считаете ли вы это уникальным решение?
ProgrammerDan
@ProgrammerDan Вращенные ответы идентичны. Я уточню.
Майкл Стерн
1
Шестиугольник имеет больше симметрий, чем просто повороты. А как насчет ответов, которые идентичны при сочетании вращения и отражения?
Питер Тейлор
Заинтересован, чтобы увидеть решение этой проблемы с помощью самоорганизующихся карт.
Муравей Р

Ответы:

3

Haskell 295 289

import Data.List
t=38
y a b=[max(19-b)(a+1)..19]
w=y 0 t
x=filter((==w).sort)$[[a,b,c,d,e,f,g,h,i,t-a-e-o-s,k,l,m,t-d-i-r,o,p,q,r,s]|a<-[1..14],c<-y a a,l<-y a c,s<-y a l,q<-y a s,h<-y c q,e<-w,let{f=t-g-e-d;i=t-b-e-m;o=t-r-k-g;k=t-p-f-b;b=t-a-c;g=t-l-c;p=t-l-s;r=t-q-s;m=t-q-h;d=t-a-h}]

Еще один аналогичный ответ, использующий арифметику для получения промежуточных гексов. В отличие от других решений, я не проверяю, чтобы эти суммы были> 0, достаточно проверить, что отсортированные гексы равны диапазону [1..19]. a, c и h ограничены, так что разрешены только повернутые / отраженные решения. Решение появляется через несколько секунд, затем идет минута или около того, пока он решает, что больше нет.

Использование в ghci:

ghci> x
[[3,19,16,17,7,2,12,18,1,5,4,10,11,6,8,13,9,14,15]]

Отредактировано, чтобы побрить несколько символов. 'y 0 t' производит [1..19].

bazzargh
источник
1
На самом деле я делаю то же самое в своем ответе на C :) Черт, как я мог не видеть, что Haskell - идеальный инструмент для работы: P +1
Niklas B.
Я пропускаю ваш x>0чек, потому что я сортирую список, включающий в себя негативы, вместо увеличения массива? С другой стороны, я должен ограничить диапазоны (мои y a b), чтобы заставить Haskell работать, что стоит мне несколько символов. Но обязательно должен быть другой язык со встроенной сортировкой, который побьет меня, работая так же (глядя на вас, Mathematica).
bazzargh,
Да, сортировка в C, к сожалению, не так проста, как в Haskell. Проблема с Mathematica заключается в том, что он не скомпилирован и, таким образом, чертовски медленен :(
Никлас Б.
Я всегда делаю это в Хаскеле для практики, даже если другой язык будет лучше.
bazzargh,
Я на самом деле программирую Haskell как побочную работу, поэтому я озадачен тем, что мне даже не пришло в голову использовать его здесь: D Это действительно великолепный язык, даже в реальном / нечистом мире
Никлас Б.
10

Ява (1517–75,85) = 1441,15 ( 1429–71,45) = 1357,55 (1325–66,25 ) = 1258,75

Это было весело

Печатает все уникальные решения с зеркальным отображением и вращением, в приятной соте (следовательно, 5% снижение)

Время работы: ~ 0,122 с (122 миллисекунды) на моем 4-летнем ноутбуке.

Гольф-код ( редактирование показало, что я тупо повторял свои printfs, уменьшил их до одного printf для максимального гольфа) ( новое редактирование Сокращенные вызовы для установки функций в умные меньшие функции, некоторые другие микрооптимизации):

import java.util.*;class A{boolean c(Set<Integer>u,int z){return!u.contains(z);}Set<Integer>b(Set<Integer>c,int...v){Set<Integer>q=new HashSet<Integer>(c);for(int x:v)q.add(x);return q;}void w(){Set<Integer>U,t,u,v,w,y,z;int a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,X,Z;X=20;Z=38;for(a=1;a<X;a++)for(b=1;b<X;b++)if(b!=a)for(c=1;c<X;c++)if(c!=a&&c!=b&&a+b+c==Z){U=b(new HashSet<Integer>(),a,b,c);for(d=1;d<X;d++)if(c(U,d))for(h=1;h<X;h++)if(h!=d&&c(U,h)&&a+d+h==Z){t=b(U,a,b,c,d,h);for(m=1;m<X;m++)if(c(t,m))for(q=1;q<X;q++)if(q!=m&&c(t,q)&&h+m+q==Z){u=b(t,m,q);for(r=1;r<X;r++)if(c(u,r))for(s=1;s<X;s++)if(s!=r&&c(u,s)&&q+r+s==Z){v=b(u,r,s);for(p=1;p<X;p++)if(c(v,p))for(l=1;l<X;l++)if(l!=p&&c(v,l)&&s+p+l==Z){w=b(v,p,l);for(g=1;g<X;g++)if(c(w,g)&&l+g+c==Z)for(e=1;e<X;e++)if(e!=g&&c(w,e))for(f=1;f<X;f++)if(f!=e&&f!=g&&c(w,f)&&d+e+f+g==Z){y=b(w,g,e,f);for(i=1;i<X;i++)if(c(y,i))for(n=1;n<X;n++)if(n!=i&&c(y,n)&&d+i+n+r==Z&&b+e+i+m==Z){z=b(y,i,n);for(o=1;o<X;o++)if(c(z,o))for(k=1;k<X;k++)if(k!=o&&c(z,k)&&m+n+o+p==Z&&r+o+k+g==Z&&b+f+k+p==Z)for(j=1;j<X;j++)if(c(z,j)&&j!=o&&j!=k&&a+e+j+o+s==Z&&c+f+j+n+q==Z&&h+i+j+k+l==Z){System.out.printf("%6d%4d%4d\n\n%4d%4d%4d%4d\n\n%2d%4d%4d%4d%4d\n\n%4d%4d%4d%4d\n\n%6d%4d%4d\n\n",a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s);return;}}}}}}}}}public static void main(String[]a){(new A()).w();}}

Грубая сила устарела, но умное использование факта, что существует только очень маленький набор решений, привело меня к ответу, основанному на итерациях, где в каждом цикле итерации я рассматриваю только целые числа, которые еще не были «назначены». Я использую Java HashSet для получения O (1) поиска для чисел, которые использовались ранее. Наконец, существует ровно 12 решений, но когда вы не учитываете как ротацию, так и зеркалирование, это сводится к одному уникальному решению, поэтому, когда встречается первое решение, я распечатываю его и завершаю. Посмотрите мой код с меньшим количеством игр в github, чтобы получить более четкое представление о том, как я подхожу к этому решению.

Наслаждайтесь!

ProgrammerDan
источник
Ну, вы лежите в своем спойлере, есть больше разных решений, поэтому ваш ответ неверен.
ST3
Сильное утверждение, можете ли вы подтвердить это собственным ответом, чтобы доказать это? Я конечно не знаю ни о какой преднамеренной лжи в моем спойлере.
ProgrammerDan
поэтому, когда первое решение встречается, я распечатываю его и прекращаю действие правила №. 3 рассказывает рассказывает, чтобы найти все ответы. Там 19, как сказал OP, не уверен, действительно ли это 19, но я сталкивался с подобной задачей раньше, поэтому знайте, что есть больше, чем один.
ST3
Вам нужно прочитать весь мой спойлер. Я нашел 12 решений. Затем вам нужно прочитать все комментарии, прилагаемые к вопросу. ОП говорит, что ответы, которые равны по вращению, эквивалентны и должны быть пропущены. Другой человек спросил, следует ли пропустить ответы, равные по зеркальному отражению. Хотя до настоящего времени ОП не ответил на этот запрос, и мое, и все другие решения на сегодняшний день предполагают, что ответ «да». Следовательно, мое решение является полностью полным, полностью точным, и здесь нет «лжи». Однако, если вы хотите увидеть все 12 решений, удалите return;утверждение.
ProgrammerDan
Наконец, это код гольф. Учитывая, что добавление произвольного return;оператора увеличивает длину моего кода на 7, было бы безумно добавить его, если бы верный ответ включал все 12 решений, которые являются просто повернутыми / зеркальными версиями друг друга. Хотя нельзя исключать безумия, в этом случае добавление return;было преднамеренным и, как я описал, основывалось на полном диалоге вопросов и комментариев , который вы должны позаботиться о рассмотрении, прежде чем бросать обвинения. Благодарность!
ProgrammerDan
8

C 366 байт ( C ++ 541 450 )

#define R(i)for(int i=19;i;--i)
#define X(x)if(x>0&&!V[x]++)
#define K(X)X(a)X(b)X(c)X(d)X(e)X(f)X(g)X(h)X(i)X(j)X(k)X(l)X(m)X(n)X(o)X(p)X(q)X(r)X(s)
Q(x){printf("%d ",x);}
T=38,V[99];main(){R(h)R(c)R(s)R(a)R(l)R(q)R(e){int d=T-a-h,b=T-a-c,g=T-c-l,p=T-l-s,r=T-q-s,m=T-h-q,f=T-g-e-d,i=T-b-e-m,n=T-d-i-r,o=T-p-n-m,k=T-g-o-r,j=T-h-i-k-l;R(C)V[C]=0;K(X)K(+Q),exit(0);}}

Компилировать с gcc -std=c99 -O3.

Печатает все уникальные решения по модулю поворота и зеркалирования, в формате a b c d ..., по одному на строку.

Время выполнения: 0,8 секунды на моем компьютере.

Мы перечисляем клетки в порядке h -> c -> s -> a -> l -> q -> e для максимальной отсеченности. Фактически вышеприведенная версия просто пытается каждые 20 ^ 7 назначений для этих переменных. Тогда мы можем вычислить все остальные ячейки. Существует только одно уникальное решение по модулю вращения / зеркального отображения. На Github можно найти более старую версию, менее подходящую для игры в гольф и примерно в 20 раз быстрее (из-за обрезки) C ++.

Никлас Б.
источник
Я люблю в основном арифметический подход здесь. Браво! +1
ProgrammerDan
1

Matlab: 333 320 символов

Это довольно тупой подход почти грубой силы, который не использует рекурсию. Он создает частичные решения z, которые выводятся в конце. Каждый столбец является решением; элементы перечислены z сверху вниз. Время работы 1-2 часа.

z=[];
a='abc adh hmq qrs spl lgc defg beim mnop dinr rokg pkfb hijkl aejos cfjnq';while a[k,a]=strtok(a);n=length(k);x=nchoosek(1:19,n)';s=[];for t=x(:,sum(x)==38)s=[s,perms(t)'];end
m=0.*s;m(19,:)=0;m(k(1:n)-96,:)=s(1:n,:);y=[];for p=m for w=z m=[];l=w.*p~=0;if p(l)==w(l) y(:,end+1)=w+p.*(~l);end
end
end
z=[m,y];end
z

Бег изнутри Matlab:

>> aristotle;
>> z(:,1)

ans =

    9
   11
   18
   14
    6
    1
   17
   15
    8
    5
    7
    3
   13
    4
    2
   19
   10
   12
   16
intx13
источник