1

Olá, estou desenvolvendo um pequeno trabalho onde preciso através do algoritmo A* solucionar um puzzle, mais precisamente este puzzle:

inserir a descrição da imagem aqui


Basicamente consiste em deslizar as peças para o espaço em branco a fim de deixá-las em ordem (ou no estado desejado).

Exemplo: https://www.proprofs.com/games/puzzle/sliding/

Porém antes de iniciar a resolução, preciso verificar se o mesmo é solucionável, já pesquisei mas não consigo entender porque a contagem de inversões garante isso, e o que é essas inversões.

A parte onde vou verificar isto é essa:

function countInversions(array) {
    // Contar inversões
    // TODO
}

console.log(tiles);
return countInversions(tiles) % 2 == 0;

Vi que o resultado é adquirido através da contagem das inversões e depois capturando o modulo por 2, no caso pra descobrir se o resultado é ímpar ou par, por isso já adicionei ao código.

A configuração da grid do jogo é um array contendo a sequência de números.

Ex.

[5, 3, 2, 1, 4, 6, 8, 7, ""]

1 Resposta 1

3

A fórmula determinante para checar a solucionabilidade é referente à Paridade de uma permutação ou em inglês Parity of a permutation.
Que resumidamente calcula a quantidade de inversões necessárias para ordenar certa sequência numérica, determinado por Possível a quantidade de inversões pares e Impossível a quantidade de inversões ímpares.

E realmente existe uma forma de checar se é solucionável ou não.

2|8|3
-+-+-
1|6|4
-+-+-
7| |5

Escrevendo de forma linear teremos: 2,8,3,1,6,4,7,5 ignore os espaços em branco.

Agora precisamos encontrar o número de inversões contando os números depois de cada campo que precedem ao número analisado.

A soma das inversões determina se é solucionável ou não. Inversões pares é solucionável, ímpares não.

Seguindo seu exemplo, passando casa por casa:

2 tem como precedente 1 - 1 inversão.
8 tem como precedentes 3,1,6,4,7,5 - 6 inversões.
3 tem como precedente 1 - 1 inversão.
1 não tem precedentes - 0 inversões.
6 tem como precedentes 4,5 - 2 inversões.
4 não tem precedentes - 0 inversões.
7 não tem precedentes - 0 inversões.
5 não tem precedentes - 0 inversões.

Total de inversões 1+6+1+2 = 10 (Número par). Puzzle Solucionável.

Já esse caso:

1|2|3
-+-+-
4|5|6
-+-+-
 |8|7

Não é solucionável pois o número de inversão é 1 (ímpar).
Pois 1,2,3,4,5,6 não tem precedentes.
8 tem 7 como precedente - 1 inversão.
7 não tem precedente.

fonte

3
  • A questão de descobrir o ímpar e par eu entendi, a maior dúvida que tenho agora é relacionado a por que isso garante que o problema é solucionável, algo mais formal. Obrigado pela resposta!
    – MSLacerda
    2/10/2018 às 14:09
  • 1
    @matheussoareslacerda editado a resposta 2/10/2018 às 14:19
  • 1
    Era exatamente isso cara, valeu!
    – MSLacerda
    2/10/2018 às 14:23

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .