Portanto, sua tarefa é pegar um bloco 3x3 -em que os espaços em branco são médios e *os espaços preenchidos, por exemplo:

-**
-*-
*-*

e reorganize o bloco para que ele *forme um X, assim:

*-*
-*-
*-*

Entrada: quadrados 3x3 como acima, eles podem ser de 3 linhas, uma matriz ou como você desejar.

Saída: a menor quantidade de movimentos para reorganizar em um X. Cada movimento está invertendo 2 caracteres que estão tocando e são horizontais um do outro, verticais um do outro ou diagonal um do outro. Se não for possível, retorne qualquer saída impossível, por exemplo 999ou -4242. 5é o menor número desse tipo.

Casos de teste:

1) Saída: 1

-**
-*-
*-*

2) Saída: -1

-*-
-*-
*-*

3) Saída: 3

---
-**
***

4) Saída: 0

*-*
-*-
*-*

Você pode substituir os caracteres em branco e não em branco, mas lembre-se de incluir qual é qual em sua postagem

Code Golf

Lembre-se de que este é o código de golfe, o código mais curto vence!

Python 3 , 104 78 bytes

lambda n:-(sum(n)!=5)or sum(n[1::2])+n[4]*(max(n,n[6:],n[::3],n[2::3])>=[1]*3)

Experimente online!

Edit: Aplicadas as sugestões de @Jonathan Allan e @ xnor para reduzir drasticamente a contagem de bytes.

A entrada é uma lista de cadeias de comprimento 9 com zeros e uns, sendo os *s.

Aqui estão algumas observações:

• Nós nunca precisamos mover as estrelas já nas células corretas. Qualquer estrela extraviada tem 5 células circundantes que não podem ser bloqueadas de uma só vez (caso contrário, a resposta já é -1).
• O custo de cada estrela extraviada é 1 ou 2 e é 2 somente se estiver cercado por três estrelas corretamente colocadas.
• O custo para cada estrela extraviada é independente uma da outra.

Portanto, primeiro testamos se a sequência possui cinco e depois contamos as seguintes coisas:

• O número de estrelas mal colocadas (= umas com índices ímpares)
• O número de estrelas deslocada de custo 2 (= células em 0124, 0346, 2458, 4678sendo todos os)
  • Fatore como n[4]sendo um e teste cada ser de extração de intervalo '111'.
  • Como essa estrela é no máximo uma, podemos usar com segurança em maxvez de sum.

Geléia , 26 bytes

5ḶḤd3ạŒ!Ṁ€€ḅ1Ṃ
T’d3Ç-L=5Ɗ?

Experimente online!

Tome uma lista simples como entrada.

Pena que Jelly não tem "índices de verdade multidimensionais" ... T€ṭ€"JẎtambém funciona, mas leva mais 1 byte.

Algoritmo: Existem 5 posições de bloco atuais e 5 destinos (destinos), o algoritmo tenta cada um dos 5! correspondendo e produza a soma mínima da distância Chebyshev [origem, destino].

Haskell , 176 132 126 126 104 bytes

w=0:1:w
m a|sum a/=5=5|1>0=sum$[a!!4|3<-sum.map(a!!)<$>[[0,1,2],[0,3,6],[2,5,8],[6,7,8]]]++zipWith(*)a w

Experimente online!

Leva uma lista de números inteiros com 1 como o caractere não em branco. Soma o número de quadrados indexados pares diferentes de zero e adiciona 1 se algum dos padrões de movimento duplo for encontrado (quadrado central e coluna / linha da aresta completamente preenchida). Acho que a última parte é um pouco inútil, provavelmente poderia ser muito melhorada em relação a esse método de força bruta. Retorna 5 (uma saída impossível) em uma entrada impossível.

Python 2 , 194 192 bytes

from itertools import*
f=lambda l,k=0:-(sum(l)!=5)or[1,0]*4!=l[:-1]and k<4and-~min(f(l[:a]+[l[b]]+l[a+1:b]+[l[a]]+l[b+1:],k+1)for a,b in combinations(range(9),2)if max(b/3-a/3,abs(a%3-b%3))<2)

Experimente online!

JavaScript (ES6), 123 bytes

Recebe a entrada como um número inteiro de 9 bits. Resolve o enigma aplicando ingenuamente as regras, que provaram não ser a abordagem mais curta.

f=(n,k=b=-1)=>n^341?k>2?b:[3,6,9,10,17,18,20,34,36].map(m=>[1,8,8].map(M=>(x=n&(m*=M))&-x^x||f(n^m,k+1)))|b:!~b|k<b?b=k+1:b

Experimente online!

Comentado

f = (                           // f = recursive function taking:
  n,                            //   n = input
  k =                           //   k = number of moves, initialized to -1
  b = -1                        //   b = best result so far, initialized to -1
) =>                            //
  n ^ 341 ?                     // if n does not match the target pattern:
    k > 2 ?                     //   if we've already done more than 3 moves:
      b                         //     we're not going to find a solution -> abort
    :                           //   else:
      [3,6,9,10,17,18,20,34,36] //     for each swap bitmask m
      .map(m =>                 //     and
      [1,8,8]                   //     for each multiplier M:
      .map(M =>                 //       apply the multiplier to m and
        (x = n & (m *= M))      //       apply the final bitmask to n -> this gives x
        & -x                    //       isolate the least significant bit of x
        ^ x ||                  //       if it's the only bit set,
        f(n ^ m, k + 1)         //       then swap the bits and make a recursive call
      )) | b                    //     end of both map() loops; return b
  :                             // else:
    !~b | k < b ? b = k + 1 : b //   this is a solution in k+1 moves: update b

Nota : Este código realiza alguns movimentos ilegais além do topo do tabuleiro quando m é multiplicado por 64. Mas eles são simplesmente ignorados, pois não podem levar a uma solução mais curta que a melhor solução legal.

Abaixo estão as 9 máscaras de troca de base e o padrão de destino. O canto superior esquerdo é o bit mais significativo.

000  000  001  001  010  010  010  100  100     101
011  110  001  010  001  010  100  010  100     010 (341)
(3)  (6)  (9)  (10) (17) (18) (20) (34) (36)    101

Geléia , 26 bytes

“ċȤ‘ḤB;U$=a¥;Ḋm2ƊẠ€SɓSn5Nȯ

Experimente online!

Um link monádico.

Quão?

Inspirado pela resposta Python de Bubbler ; Golfed para atender Jelly ...

“ċȤ‘ḤB;U$=a¥;Ḋm2ƊẠ€SɓSn5Nȯ - Link: length 9 list of ones & zeros, X
“ċȤ‘                       - list of code-page indices     = [232,154]
    Ḥ                      - double                        = [464,308]
     B                     - to binary     = [[1,1,1,0,1,0,0,0,0],[1,0,0,1,1,0,1,0,0]]
        $                  - last two links as a monad:
       U                   -   upend       = [[0,0,0,0,1,0,1,1,1],[0,0,1,0,1,1,0,0,1]]
      ;                    -   concatenate = [[1,1,1,0,1,0,0,0,0],[1,0,0,1,1,0,1,0,0],[0,0,0,0,1,0,1,1,1],[0,0,1,0,1,1,0,0,1]]
           ¥               - last two links as a dyad:
          a                -   logical AND (vectorises)
         =                 -   equal? (vectorises)
                Ɗ          - last three links as a monad:
             Ḋ             -   dequeue X (remove leftmost element)
               2           -   literal two
              m            -   modulo slice (keeps the "edge-elements") 
            ;              - concatenate
                 Ạ€        - all? for €ach (edge-elements: no-op
                           -                else: 1 for any cost-2 element 0 otherwise)
                   S       - sum
                    ɓ      - new dyadic chain ^that on the right; X on the left
                     S     - sum X
                       5   - literal five
                      n    - not equal?
                        N  - negate (-1 if not exactly 5 1s, 0 otherwise)
                         ȯ - logical OR with right

JavaScript, 85 bytes

s=>/^0*(10*){5}$/.test(s)*s.match(/(?=1.(..)*$|^1(..)?11.1|1.11(..)?1$)|$/g).length-1

Este é um porto regular da resposta de Bubbler .

Insira como uma sequência de 0/1.

f=
s=>/^0*(10*){5}$/.test(s)*s.match(/(?=1.(..)*$|^1(..)?11.1|1.11(..)?1$)|$/g).length-1

document.write('<table>'+('<tr>'+'<td><label><input type=checkbox><span></span></label>'.repeat(3)).repeat(3)+'</table>');
document.write('Answer: <output id=o></output>');
U=()=>o.value=f(ii.map(i=>i.checked?1:0).join``);
ii=[...document.querySelectorAll('input')];
ii.forEach((i,p)=>{
i.checked=!(p%2);
i.oninput=U;
});
U()

label{display:block;position:relative;overflow:hidden;width:20px;height:20px;}
input{position:absolute;top:-200%;}
input~span{width:100%;height:100%;display:block;border:1px solid black;box-sizing:border-box;}
input:focus~span{border-color:red;}
input:checked~span{background:#ace;}

Stax , 23 22 bytes

Ç╙╤Ü┤└åVτ┐├Y-²▼░█∩¡3ëâ

Execute e depure

Este programa utiliza uma variedade de [0, 1] como entrada e retorna um número inteiro de movimentos ou uma sequência vazia, se nenhuma solução for possível.

Considere estes índices para a grade

0 1 2
3 4 5
6 7 8

• Se não houver exatamente 5 1 s na entrada, não haverá solução; portanto, não produzimos saída.
• Os centros de cada lado estão nas posições incorretas. Estes são os índices 1, 3, 5 e 7. Somando a distância para cada1 dessas posições produzirá o resultado final.
• Para cada 1um em uma posição incorreta, sua distância é 1 ou 2. Serão 2 se estiver cercado por outros 1s. Por exemplo, se houver 1s nos índices [0, 1, 2, 4], a distância para o incorreto 1é 2.

• Com isso em mente, considere esse pseudocódigo para obter a distância contribuída para o resultado pelo índice 1.

  1. Leia 4 bits dos índices [1, 0, 2, 4]. Isso coloca a posição incorreta na posição mais significativa.
  2. Converta esses bits em um número bde 0 a 15.
  3. Quando 0 <= b <= 7a distância é 0. Quando 8 <= b <= 14a distância é 1. Quando b == 15a distância é 2. Isso pode ser calculado usando a divisão inteira por b * 2 / 15.

Portanto, a distância total pode ser calculada repetindo esse processo 4 vezes e girando a grade no meio.

1#5=4*  if the number of 1s is 5, then 4, else 0
D       repeat the rest of the program that many times
  x     push the value in the x register, which is initially the input
  3/    split into 3 rows
  rM    rotate 90 degrees
  $X    flatten back into single array, and save the "rotated" array in the X register
  A|2E  get the digits of 2^10 i.e. [1,0,2,4]
  @     read the bits from the current rotation at indices [1,0,2,4]
  :b    convert bits to integer
  H15/  double, then divide by 2
  +     add to running total

Execute este

Excel, 86 81 bytes

=SUM(B1,A2,B3,C2)+B2*(AND(A1:A3)+AND(A1:C1)+AND(C1:C3)+AND(A3:C3))/(SUM(A1:C3)=5)

Antigo: quando a saída 'impossível' era-1

=IF(SUM(A1:C3)=5,SUM(B1,A2,B3,C2)+B2*(AND(A1:A3)+AND(A1:C1)+AND(C1:C3)+AND(A3:C3)),-1)

Usa 1para entrada preenchida e 0vazia, dentro do intervalo A1:C3. É possível jogar golfe ainda mais se pudermos retornar valores diferentes de -1"impossível". Retorna um #DIV/0!erro em grades impossíveis

Opera na mesma lógica que a resposta Python do Bubbler .