Решить хроматическую головоломку

35

У наших друзей в Puzzling.SE была опубликована следующая загадка: всегда ли эта хроматическая головоломка разрешима? Эдгар Г. Вы можете сыграть здесь .

Объяснение головоломки

Учитывая m x nсетку с плитками трех разных цветов, вы можете выбрать любые две соседние плитки , если их цвета разные . Эти две плитки затем преобразуются в третий цвет, то есть в один цвет, не представленный этими двумя плитками. Загадка решается, если все плитки имеют одинаковый цвет . По-видимому, можно доказать, что эта головоломка всегда разрешима, если ни одна из них mне nделится на 3.

8x8 трехцветная головоломка

Конечно, это требует алгоритма решения. Вы напишите функцию или программу, которая решает эту головоломку. Обратите внимание, что функции с «побочными эффектами» (т. Е. Вывод включен, stdoutа не в каком-то неудобном возвращаемом значении типа данных) явно разрешены.

Ввод, вывод

Вход будет m x nматрица , состоящая из целых чисел 1, 2и 3(или 0, 1, 2если это удобно). Вы можете принять этот вход в любом нормальном формате. Как mи nявляются >1и не делится на 3. Можно считать загадку не решена

Затем вы решите головоломку. Это будет включать в себя повторный выбор двух смежных плиток для «преобразования» (см. Выше). Вы будете выводить две координаты этих тайлов для каждого шага, который предпринял ваш алгоритм решения. Это также может быть в любом нормальном формате вывода. Вы можете выбирать между индексированием ваших координат на основе 0 и 1, а также в первую очередь индексировать строки или столбцы. Пожалуйста, укажите это в своем ответе, однако.

Ваш алгоритм должен работать в течение разумного времени в исходном случае 8x8. Грубое форсирование полностью запрещено, т. Е. Ваш алгоритм должен выполняться O(k^[m*(n-1)+(m-1)*n])с kколичеством шагов, необходимых для решения. Однако решение не обязательно должно быть оптимальным. Доказательство, приведенное в связанном вопросе, может дать вам представление о том, как это сделать (например, сначала сделать все столбцы, используя только вертикально смежные плитки, а затем сделать все строки)

Контрольные примеры

В этих тестовых случаях координаты основаны на 1, и строки индексируются первыми (например, MATLAB / Octave и, возможно, многие другие).

Input: 
[1 2]
Output: (result: all 3's)
[1 1],[1,2]


Input:
[ 1 2
  3 1 ]
Output: (result: all 1's)
[1 1],[2 1]        (turn left column into 2's)
[2 1],[2 2]        (turn right column into 3's)
[1 1],[1 2]        (turn top row into 1's)
[2 1],[2 2]        (turn bottom row into 1's)

Input:
[1 2 3 2
 3 2 1 1]

Output: (result: all 3's)
[1 1],[1 2] 
[1 3],[1 4] 
[1 2],[1 3] 
[1 1],[1 2] 
[1 2],[1 3] 
[1 1],[1 2]
[1 3],[1 4]
[2 1],[2 2]
[1 1],[2 1]
[1 2],[2 2]
[1 3],[2 3]
[1 4],[2 4]

При желании я могу опубликовать пастбин более крупных тестовых случаев, но я думаю, что этого должно быть достаточно.

Sanchises
источник
Я хотел бы увидеть версию этого кода, где цель состоит в том, чтобы решить ряд головоломок с наименьшим количеством ходов.
Mego
@ Мего, я определенно обдумал это. Тем не менее, я боюсь, что это превратится в DFS или BFS, который будет работать вечно ; или, чтобы предотвратить это, набор смутных ограничений (например, «должен работать в течение часа», который отдает предпочтение людям с большим компьютером или который потребует от меня тестирования всех решений). И, кроме того, текущая задача имеет нулевое количество ответов, поэтому я сомневаюсь, что еще более сложная версия, требующая эвристики и т. Д., Окажется более популярной ... Но, возможно, если эта задача наберет обороты, я могу опубликовать такую ​​же задачу, как у вас. описать.
Санчиз
Я думаю, что я попытаюсь сделать это в Lua, но это может быть дольше, чем ваше 324-
байтовое
@ Katenkyo Только один способ узнать! Я с нетерпением жду вашего решения.
Санчиз
Вам придется немного подождать с грустью, вы предотвратили грубое решение, поэтому мне нужно найти решение, короткое в lua: p
Katenkyo

Ответы:

5

Рубин, 266 байт

Более или менее всего лишь порт решения Octave, за исключением того, что сначала решаются строки, а не столбцы. Ввод - это массив массивов, с внутренними массивами, являющимися строками. Выходные ходы есть [row, column, row, column]. Тестирование

->m{t=->v{v.size*v.inject(:+)%3}
s=->a,x,r{g=t[a]
(q=(r=0..a.size-2).find{|i|a[i]!=a[i+1]&&g!=a[i]}||r.find{|i|a[i]!=a[i+1]}
a[q,2]=[t[a[q,2]]]*2
p r ?[x,q,x,q+1]:[q,x,q+1,x])while[]!=a-[g]}
m.size.times{|i|s[m[i],i,1]}
m=m.shift.zip *m
m.size.times{|i|s[m[i],i,p]}}

Неуправляемый с объяснением

->m{                                  # Start lambda function, argument `m`
  t=->v{v.size*v.inject(:+)%3}        # Target color function
  s=->a,x,r{                          # Function to determine proper moves
                                      #   a = row array, x = row index, r = horizontal
    g=t[a]                            # Obtain target color
    (
      q=(r=0..a.size-2).find{|i|      # Find the first index `i` from 0 to a.size-2 where...
        a[i]!=a[i+1]                  # ...that element at `i` is different from the next...
        &&g!=a[i]                     # ...and it is not the same as the target color
      } || r.find{|i|a[i]!=a[i+1]}    # If none found just find for different colors
      a[q,2]=[t[a[q,2]]]*2            # Do the color flipping operation
      p r ?[x,q,x,q+1]:[q,x,q+1,x]    # Print the next move based on if `r` is truthy
    ) while[]!=a-[g]}                 # While row is not all the same target color, repeat
m.size.times{|i|                      # For each index `i` within the matrix's rows...
  s[m[i],i,1]                         # ...run the solving function on that row
                                      #   (`r` is truthy so the moves printed are for rows)
}
m=m.shift.zip *m                      # Dark magic to transpose the matrix
m.size.times{|i|s[m[i],i,p]}}         # Run the solving function on all the columns now
                                      #   (`r` is falsy so the moves printed are for columns)
Значение чернил
источник
Интересно видеть, что порт между двумя языками, не относящимися к гольфу, все еще может иметь значение ~ 20%. Не могли бы вы добавить краткое объяснение? (Особенно строка 3 - я в тайне надеюсь, что смогу использовать это в своем ответе, поскольку intersectэто такое громоздкое ключевое слово)
Sanchises
@sanchises объяснение было добавлено. Что касается intersect, я не знаю, сможете ли вы исправить это, как работает мой, потому что Ruby в findосновном работает с функциями, а ваше functionключевое слово столь же громоздко.
Чернила стоимости
Я действительно мог бы использовать ваш метод для find- спасибо! Тем не менее, близко к тому, чтобы
побить
13

Октава, 334 313 байтов

Поскольку проблема может показаться немного сложной, я представляю свое собственное решение. Я формально не доказал, что этот метод работает (я полагаю, что это сводится к доказательству того, что алгоритм никогда не застрянет в цикле), но пока он работает отлично, выполняя тестовые примеры 100x100 в течение 15 секунд. Обратите внимание, что я решил использовать функцию с побочными эффектами, а не функцию, которая возвращает все координаты, поскольку это сэкономило мне несколько байтов. Координаты являются основными строками, основаны на 1 и отформатированы как row1 col1 row2 col2. Цвета ввода таковы, что 0,1,2это работает лучше mod, за счет использования, numelа не nnz. Версия для гольфа: Edit: сохранил еще несколько байтов, используя технику из ответа Кевина Лау.

function P(p)
k=0;[m,n]=size(p);t=@(v)mod(sum(v)*numel(v),3);for c=1:n
p(:,c)=V(p(:,c));end
k=1;for r=1:m
p(r,:)=V(p(r,:));end
function a=V(a)
while any(a-(g=t(a)))
isempty(q=find(diff(a)&a(1:end-1)-g,1))&&(q=find(diff(a),1));
a([q q+1])=t(a([q q+1]));if k
disp([r q r q+1])
else
disp([q c q+1 c])
end;end;end;end

Пример GIF алгоритма решения:

введите описание изображения здесь

Безголовая версия:

function solveChromaticPuzzle(p)
[m,n]=size(p);                           % Get size
t=@(v)mod(sum(v)*numel(v),3);            % Target colour function
for c=1:n                                % Loop over columns
    p(:,c)=solveVec(p(:,c));             % Solve vector
end
for r=1:m                                % Loop over rows
    p(r,:)=solveVec(p(r,:));
end
    function a=solveVec(a)               % Nested function to get globals
        g=t(a);                          % Determine target colour
        while(any(a~=g))                 % While any is diff from target...
            % Do the finding magic. Working left-to-right, we find the
            % first pair that can be flipped (nonzero diff) that does not
            % have the left colour different from our goal colour
            q=min(intersect(find(diff(a)),find(a~=g)));
            if(isempty(q))               % In case we get stuck...
                q=find(diff(a),1);       % ... just flip the first possible
            end;
            a([q q+1])=t(a([q q+1]));    % Do the actual flipping.
            if(exist('r'))               % If we're working per row
                disp([r q r q+1])        % Print the pair, using global row
            else
                disp([q c q+1 c])        % Print the pari, using global col
            end
        end
    end
end
Sanchises
источник
Только что заметил, но меня зовут не Кенни Лау ... это еще один пользователь, и мое имя пользователя специально говорит, что я не Кенни
Value Ink
7

Луа, 594 575 559 байт

Внимание! До того, как я закончу с этим гольфом, еще много работы! Я должен быть в состоянии принять это до 500 байт, по крайней мере. На данный момент это первое решение, которое сработало, и я все еще работаю над ним.

Я предоставлю полное объяснение, как только я закончу.

function f(t)s=#t a=","for i=1,s do p=t[i]for i=1,s
do p.Q=p.Q and p.Q+p[i]or p[i]end p.Q=(p.Q*#p)%3 for i=1,s do for j=1,#p-1 do
x=p[j]y=p[j+1]u=x~=y and(p.S and p.R==p.S or x~=p.Q)v=(x+y)*2p[j]=u and v%3or x
p[j+1]=u and v%3or y print(i..a..j,i..a..j+1)end
p.R=p.S p.S=table.concat(p)end end
for i=1,s do Q=Q and Q+t[i][1]or t[i][1]end Q=(Q*s)%3 for i=1,s
do for j=1,s-1 do p=t[j]q=t[j+1]x=p[1]y=q[1]u=x~=y and(S and R==S or x~=Q)v=(x+y)*2
for k=1,#p do p[k]=u and v%3or x q[k]=u and v%3or y
print(j..a..k,j+1..a..k)end Y=Y and Y..x or x end
R=S S=Y end end
Katenkyo
источник
5

Ржавчина, 496 495 байт

К сожалению, я не могу победить OP, но для ответа Rust я вполне доволен бай-счетом.

let s=|mut v:Vec<_>,c|{
let p=|v:&mut[_],f,t|{
let x=|v:&mut[_],i|{
let n=v[i]^v[i+1];v[i]=n;v[i+1]=n;
for k in f..t+1{print!("{:?}",if f==t{(k,i,k,i+1)}else{(i,k,i+1,k)});}};
let l=v.len();let t=(1..4).find(|x|l*x)%3==v.iter().fold(0,|a,b|a+b)%3).unwrap();
let mut i=0;while i<l{let c=v[i];if c==t{i+=1;}else if c==v[i+1]{
let j=if let Some(x)=(i+1..l).find(|j|v[j+1]!=c){x}else{i-=1;i};x(v,j);}else{x(v,i);}}t};
p(&mut (0..).zip(v.chunks_mut(c)).map(|(i,x)|{p(x,i,i)}).collect::<Vec<_>>(),0,c-1usize)};

Ввод: вектор чисел, а также количество столбцов. Например

s(vec!{1,2,1,3},2);

выходы

 (row1,col1,row2,col2)

в командной строке.

Сначала я решаю каждую строку, а затем - полученный столбец только один раз, но печатаю шаги для всех столбцов. Так что это на самом деле довольно эффективно :-P.

С форматированием:

let s=|mut v:Vec<_>,c|{  
    let p=|v:&mut[_],f,t|{     // solves a single row/column
        let x=|v:&mut[_],i|{   // makes a move and prints it 
            let n=v[i]^v[i+1]; // use xor to calculate the new color
            v[i]=n;
            v[i+1]=n;
            for k in f..t{
                print!("{:?}",if f==t{(k,i,k,i+1)}else{(i,k,i+1,k)});
            }
        };
        let l=v.len();
        // find target color
        // oh man i am so looking forward to sum() being stabilized
        let t=(1..4).find(|x|(l*x)%3==v.iter().fold(0,|a,b|a+b)%3).unwrap();
        let mut i=0;
        while i<l{
            let c=v[i];
            if c==t{             // if the color is target color move on
                i+=1;
            }else if c==v[i+1]{ // if the next color is the same
                                // find the next possible move
                let j=if let Some(x)=(i+1..l).find(|j|v[j+1]!=c){x}else{i-=1;i};
                x(v,j);
            }else{              // colors are different so we can make a move
                x(v,i);         
            }
        }
        t
    };
    // first solve all rows and than sovle the resulting column c times 
    p(&mut (0..).zip(v.chunks_mut(c)).map(|(i,x)|p(x,i,i)).collect::<Vec<_>>(),0,c-1usize)
};

Изменить: теперь возвращает цвет решения, которое спасает меня точка с запятой ^^

зазубренный
источник
5

Befunge , 197 368 696 754 байта


(да, я занимаюсь гольфом с обратным кодом, чем больше байтов, тем лучше)


Я думал, что это может быть проблемой, чтобы написать этот алгоритм в Befunge и что это может быть весело

Я хотел бы, чтобы это была общественная программа, поэтому, если кто-то хочет работать над этим, пожалуйста, сделайте это.

В конце концов, пока я все сделал один, так что я закончу сам (это почти сделано)


Что еще сделано: код в форме тролля

&:19p&:09p:v:p94g92g90  <
 v94+1:g94&_$59g1+59p1-:|
 >p59gp1-: ^    vp95g93$<
v94\-1<v:g<     >  v
>g:1+v^_$v^90p94g92<
v5p94<   3>1+59p   ^
>9gg+\:^ %g   v93:g95<           v3_2         v
v1pg95g94<^95<>g-v>$v^           v ^-%3*2\gg9<
>9g39g+59g-1-|v-1_^ #^pg95+g92g90<1_09g:29g+5^
       ;  >  >  09g:29g+59gg\3%-# !^v         <
          ^p95<                  ^  <
     v  p96-1+g90g92<
     v                  p95_@
            >59g1+:39g-19g-^
     v    >p 79g:59gg\1+59gp$$$$$29g49pv
    > p59g^ |<<<<<<<<<<<<<<<<<<!-g96g94<
>:79^>29g49p>69g1+59gg49g:59gg\1+49p- v
^\-\6+gg95+1\g< v         !-g96:<-1g94_^
>"]",52*,::59g^v_::1+59gg\59gg-v^ <
^ .-g93g95,.-g<>:69g- v  v-g96:_1+^
>+" [,]",,,\29^       >#v_$:49g2-v
^1:.-g93g95,.-g92\,"[ ":<        <

(да, это тролль, поверь мне)


По сути, он читает массив и вычисляет движение, которое нужно выполнить, чтобы решить строки, учитывая входные данные как

(number of rows) (number of columns) 1 2 3 1 1 3 2 1 2 ....

(весь массив передается в виде списка [row1, row2, row3,…])

вывод

[col row],[col',row']
[col2 row2],[col2',row2']
...

строки и столбцы оба начинаются с 0.


Теперь, когда строки решены, это почти сделано! Ура!


Пояснение: (будет обновлено позже)

образ

Итак, есть 5 основных частей:

  • Первый, зеленый, читает строку ввода и записывает одну строку массива
  • Второй, оранжевый, переходит к следующему ряду массива.
  • Третий, в синем, суммирует ряд
  • Четвертый, ярко-розовый, берет модуль 3 суммы, сохраняет его справа от соответствующего ряда и переходит к следующему ряду.
  • Наконец, в красном, часть, которая вычисляет целевой цвет от ранее вычисленного числа. Эта часть действительно тупая и, вероятно, должна быть переписана, но я не понял, как мне это удастся (передал от 197 байтов до 368 только с этой частью)

Серые части - инициализация


Вот более глубокое объяснение модуля, который находит объединяемые блоки (кстати, здесь это кодируется)

                                       B
            @                          v
            |                  !-g96g94<
ENTRY>29g49p>69g1+59gg49g:59gg\1+49p- v
                v         !-g96:<-1g94_^
               v_::1+59gg\59gg-v^ <
               >:69g- v  v-g96:_1+^
                      >#v_$:49g2-v
                    CALL<        <

Часть CALL - это когда указатель инструкции собирается в другой модуль, чтобы объединиться в блоки. Он возвращается к этому модулю через запись «B»

Вот некоторый псевдокод: (currentx связан с чтением массива) Для:

    69g1+59gg  // read target color
    49g:59gg\1+49p // read current color and THEN shift the currentx to the next box
    if ( top != top ){  // if the current color is bad
        49g1-          //  put the current place  (or currentx - 1) in the stack
        While:
            if ( :top != 69g ){   // if you didn't reach the end of the list
                ::1+              // copy twice, add 1
                if ( 59gg == \59gg ){ // if the next color is the same than current
                   1+                // iterate
                   break While;
                }
            }

        : // copies j (the previous raw iterator)
        if ( top == 69g ){  // if you reached the end of the row (which mean you can't swap with the color after that point)
            $:              // discard j's copy and copy target
            49g2-           // put the place just before the color change on the stack
            combine_with_next;
        } else {
            combine_with_next;
        }
        29g49p   // back to the beginning of the row (there was some changes int the row)
    }

    if ( 49g != 69g ) // if you didn't reach the end of the list
        break For:

Обратите внимание, что если вы хотите проверить его, вам нужно будет поставить некоторое конечное пространство и завершающие новые строки, чтобы было достаточно места для хранения массива, если вы хотите использовать интерпретацию, которую я связал. 22 + количество строк на входе в качестве конечных строк и 34 + количество столбцов в качестве конечных пробелов в одной строке должно быть в порядке.

Maliafo
источник
Просто любопытно, почему это не конкурирует?
Value Ink
Из-за этой части: «Я бы хотел, чтобы это была общественная программа». Я думал, что буду немного обманывать в противном случае
Малиафо
У меня результат 197 байт, вы работаете под windows? (а считать только \r\nвместо \n?)
Катенкё
Хм, я думаю, что я скопировал вставил некоторые трейлинг при подсчете байтов, спасибо
Малиафо
Если в конце я буду единственным, кто это сделал, я удалю упоминание, но надеюсь, что не буду
Малиафо
2

C, 404 байта

Мой первый код гольф, я очень доволен тем, как это получилось. Хотя это заняло слишком много времени. Это не полностью стандартный C, только то, что скомпилируется в gcc без специальных флагов (и игнорирует предупреждения). Так что там есть вложенная функция. Функция fпринимает измерения mи в nкачестве своих первых аргументов, а в качестве третьего аргумента принимает (int-указатель) массив массива m× n(индексируется сначала по строкам). Другие аргументы - это фиктивные аргументы, вам не нужно их передавать, они просто предназначены для сохранения байтов при объявлении переменных. Он записывает каждую измененную пару в формат STDOUT в формате row1,col1:row1,col1;с точкой с запятой, разделяющей пары. Использует индексирование на основе 0.

#define A a[i*o+p
#define B A*c
f(m,n,a,i,j,o,p,b,c,d)int*a;{
int t(x){printf("%d,%d:%d,%d;",b?i:c+x,b?c+x:i,b?i:c+1+x,b?c+1+x:i);}
o=n;p=b=1;for(;~b;b--){
for(i=0;i<m;i++){c=j=0;
for(;j<n;)c+=A*j++];d=c*n%3;
for(j=0;j<n-1;j++) 
while(A*j]^d|A*j+p]^d){
for(c=j;B]==B+p];c++);
if(c<n-2&B]==d&2*(B+p]+A*(c+2)])%3==d)
B+p]=A*(c+2)]=d,t(1);else
B]=B+p]=2*(B]+B+p])%3,
t(0);}}o=m;p=m=n;n=o;o=1;}}

Я использовал немного другой алгоритм, чем OP для решения отдельных строк / столбцов. Это выглядит примерно так (псевдокод):

for j in range [0, rowlength):
    while row[j] != targetCol or row[j+1] != targetCol:
        e=j
        while row[e] == row[e+1]:
            e++             //e will never go out of bounds
        if e<=rowLength-3 and row[e] == targetCol 
                and (row[e+1] != row[e+2] != targetCol):
            row.changeColor(e+1, e+2)
        else:
            row.changeColor(e, e+1)

for(;~b;b--) выполнении цикла ровно в два раза, на втором проходе он решает столбцы вместо строк. Это делается путем замены nи mи изменения значений oи, pкоторые используются в арифметике указателей для обращения к массиву.

Вот версия, которая не разглажена, с тестовой основной и печатает весь массив после каждого хода (нажмите ввод для шага 1 хода):

#define s(x,y)b?x:y,b?y:x
#define A a[i*o+p
#define B A*e
f(m,n,a,i,j,o,p,b,c,d,e)int*a;{

    int t(x){
        printf("%d,%d:%d,%d;\n",s(i,e+x),s(i,e+1+x));
        getchar();
        printf("\n");
        for(int i2=0;i2<(b?m:n);i2++){
            for(int j2=0;j2<(b?n:m);j2++){
                printf("%d ",a[i2*(b?n:m)+j2]);
            }
            printf("\n");
        }
        printf("\n");
    }

    printf("\n");
    b=1;
    for(int i2=0;i2<(b?m:n);i2++){
        for(int j2=0;j2<(b?n:m);j2++){
            printf("%d ",a[i2*(b?n:m)+j2]);
        }
        printf("\n");
    }
    printf("\n");

    o=n;p=1;
    for(b=1;~b;b--){
        for(i=0;i<m;i++){
            c=0;
            for(j=0;j<n;j++) c+= a[i*o+p*j];
            d=0;
            d = (c*n)%3;
            for(j=0;j<n-1;j++) {
                while(a[i*o+p*j]!=d||a[i*o+p*j+p]!=d){
                    for(e=j;a[i*o+p*e]==a[i*o+p*e+p];e++);
                    if(e<=n-3 && a[i*o+p*e]==d 
                            && 2*(a[i*o+p*e+p]+a[i*o+p*(e+2)])%3==d){
                        a[i*o+p*e+p]=a[i*o+p*(e+2)]=d;
                        t(1);
                    }else{
                        a[i*o+p*e]=a[i*o+p*e+p] = 2*(a[i*o+p*e]+a[i*o+p*e+p])%3;
                        t(0);
                    }
                }
            }
        }
        o=m;p=m=n;n=o;o=1;
    }
}

main(){
    int g[11][11] = 
    {
        {0,2,1,2,2,1,0,1,1,0,2},
        {2,1,1,0,1,1,2,0,2,1,0},
        {1,0,2,1,0,1,0,2,1,2,0},
        {0,0,2,1,2,0,1,2,0,0,1},
        {0,2,1,2,2,1,0,0,0,2,1},
        {2,1,1,0,1,1,2,1,0,0,2},
        {1,0,2,1,0,1,0,2,2,1,2},
        {0,0,2,1,2,0,1,0,1,2,0},
        {1,2,0,1,2,0,0,2,1,2,0},
        {2,1,1,0,1,1,2,1,0,0,2},
        {0,2,1,0,1,0,2,1,0,0,2},
    };
    #define M 4
    #define N 7
    int grid[M][N];
    for(int i=0;i<M;i++) {
        for(int j=0;j<N;j++) {
            grid[i][j] = g[i][j];
        }
    }
    f(M,N,grid[0],0,0,0,0,0,0,0,0);
};
Norg74
источник
Просто из любопытства: почему вы выбрали другой алгоритм (с точки зрения экономии байтов)?
Санчиз
1
Я думаю, что это более интересно, когда люди придумывают разные решения, и из некоторых быстрых тестов я предположил, что эти два метода будут примерно одинаковыми по количеству байтов. Я, наверное, тоже попробую ваш алгоритм и посмотрю, смогу ли я понизиться.
Norg74
Размещать это здесь, потому что у меня нет достаточно представителей, чтобы прокомментировать вопрос. Будет ли правильным использовать грубую силу для каждой строки, а затем для каждого столбца в отдельности? Технически это не «полный перебор» и должен быть ниже, чем указанный предел сложности по времени. Я действительно подумывал сделать это.
Norg74
Упоминание о грубом принуждении должно было усилить замечание «разумного времени», поэтому воспринимайте его как t «O (...). Я знаю, что между грубой силой и разумным алгоритмом есть серая область, поэтому используйте свое собственное суждение о том, чувствуете ли вы, что он работает над решением головоломки, или это просто небольшая модификация DFS или BFS, которые, так сказать, не зависят от «прогресса» ,
Санчиз