# Klotski

Klotski (do polonês klocki—blocos de madeira) é um quebra-cabeça de blocos deslizantes que se acredita ter se originado no início do século XX. O nome pode se referir a um layout específico de dez blocos, ou em um sentido mais global, para se referir a todo um grupo de quebra-cabeças de blocos deslizantes semelhantes, onde o objetivo é mover um bloco específico para algum local predefinido.

## Regras

Como outros quebra-cabeças de blocos deslizantes, várias peças de blocos de tamanhos diferentes são colocadas dentro de uma caixa, que geralmente é do tamanho 4×5. Entre os blocos, existe um especial (geralmente o maior) que deve ser movido para uma área especial designada pelo tabuleiro de jogo. O jogador não tem permissão para remover blocos e só pode deslizar blocos horizontalmente e verticalmente. Objetivos comuns são resolver o quebra-cabeça com um número mínimo de movimentos ou em um período mínimo de tempo.

## Nomeação

A referência mais antiga conhecida do nome Klotski é originária da versão do computador para Windows 3.1 da ZH Computing em 1991, que também foi incluída no Microsoft Windows Entertainment Pack. O quebra-cabeça deslizante já havia sido registrado e vendido sob nomes diferentes por décadas, incluindo Psychoteaze Square Root, Intreeg, e Ego Buster. Não se conhecia um nome amplamente usado para a categoria de quebra-cabeças deslizantes descrita antes da aparição de Klotski.

## História

Um precursor significativo do quebra-cabeça Klotzki é o quebra-cabeça do século 19, com quinze quadrados de madeira que foram reorganizados. O quebra-cabeça 15 teve imensa popularidade nos países ocidentais durante o final do século XIX. Por essa época, surgiram patentes de quebra-cabeças usando blocos de formas diferentes. Henry Walton registrou a Patente E.U.A. 516 035 em 1893 para um quebra-cabeça deslizante de retângulos de forma idêntica, que, segundo Edward Hordern, é o primeiro quebra-cabeça deslizante conhecido com blocos retangulares. Frank E. Moss registrou a Patente E.U.A. 668 386 em 1900 para um quebra-cabeça deslizante de seis quadrados e quatro retângulos, que é uma das primeiras ocorrências conhecidas de quebra-cabeça deslizante com blocos não iguais.
Lewis W. Hardy obteve os direitos autorais de um jogo chamado Pennant Puzzle em 1909, fabricado pela OK Novelty Co., Chicago. O objetivo deste quebra-cabeça é idêntico ao Klotski, e apenas seus blocos e arranjos padrão são diferentes. Hardy também registrou a Patente E.U.A. 1 017 752 em 1907, que trata de um quebra-cabeça de blocos deslizantes semelhante ao Pennant Puzzle, mas com uma combinação ligeiramente diferente de blocos e um objetivo diferente - não apenas o maior bloco deve ser movido para um local específico, mas todos dos outros blocos também deve obter uma configuração específica. A patente foi concedida em 1912.
John Harold Fleming obteve patente para um quebra-cabeça em 1934 na Inglaterra, com configuração quase idêntica à descrita nesta página. O quebra-cabeça em questão tem os mesmos blocos e o posicionamento quase idêntico ao Miosótis, apenas que o único bloco horizontal 2 × 1 é colocado na parte inferior, em vez de abaixo do bloco 2 × 2. A patente incluiu uma solução de 79 etapas.
Diz-se que o jogo já era conhecido no Japão por volta do 10º ano do período Shōwa, ou seja, por volta de 1935.$^[$O primeiro relato de ocorrência de Klotski na China é na província de Shaanxi, onde Lín Dé Kuān, da Universidade Politécnica do Noroeste, notou crianças em uma aldeia jogando uma versão de Klotski feita com pedaços de papel em 1938. Os primeiros livros sobre Klotski padrão foram escritos pelo professor chinês Jiāng Cháng Yīng da Northwestern Polytechnical University em 1949, em seu livro 科学 消遣. (tradução em inglês: Science Passime) Este livro foi republicado como 科学思维锻炼与消遣. [S.l.: s.n.] ISBN 7-5612-0971-1 (tradução: Treinamento mental e passatempo)
Ainda não se sabe qual versão do quebra-cabeça é a original. Existem muitas afirmações confusas e conflitantes, e vários países afirmam ser a origem final deste jogo.

## Resolução

O número mínimo de jogadas para o quebra-cabeça original é 81, que é verificado pelo computador como o mínimo absoluto para o layout inicial padrão, se você considerar deslizar uma única peça para qualquer posição acessível como uma única jogada.
A primeira solução publicada de 81 etapas é de Martin Gardner, na edição de fevereiro de 1964 da Scientific American. No artigo, ele discutiu os seguintes quebra-cabeças (com o código de classificação Edward Hordern entre parênteses): Pennant Puzzle (C19), L'Âne Rouge (C27d), Line Up the Quinties (C4), Ma's Puzzle (D1) e uma forma de Stotts 'Quebra-cabeça de tigre bebê (F10).
Para as primeiras soluções publicadas (solução não ótima), atualmente conhecida é do educador chinês Xǔ Chún Fǎng, em seu livro 數學 漫談. (tradução: Petiscos da Matemática; Kāi Mínɡ Shū Diàn, março de 1952) Sua solução envolve 100 etapas.

## Variação

Existem várias variações deste jogo, algumas com nomes específicos para a cultura de certos países, outras com diferentes arranjos de blocos.
Ainda não se sabe se essas variações se afetaram e como.

### Outros nomes

As seguintes variações têm basicamente o mesmo layout e disposição dos blocos, variando apenas em nome (humano, animal ou outros), geralmente com algum tipo de história por trás dos nomes. É completamente desconhecido se eles compartilham a mesma origem, embora isso seja altamente possível, pois são idênticos um ao outro.

#### Huarong Dao

Huarong Dao (também chamado Caminho Huarong ou Trilha Huarong, nome chinês: 華容道) é a variação chinesa, baseada em uma história fictícia no romance histórico Romance dos Três Reinos sobre o senhor da guerra Cao Cao recuando pela Trilha Huarong (atualmente Jianli County, Jingzhou, Hubei) após sua derrota na Batalha dos Penhascos Vermelhos no inverno de 208/209 dC durante o final da Dinastia Han Oriental . Ele encontrou um general inimigo, Guan Yu, que estava guardando o caminho e esperando por ele. Guan Yu poupou Cao Cao e permitiu que o último passasse pela Trilha Huarong por conta do generoso tratamento que recebeu de Cao no passado. O maior bloco do jogo é chamado "Cao Cao".

#### Filha na caixa

O quebra-cabeça de madeira A Filha na Caixa (nome japonês: hakoiri musume 箱入り娘 ) mostra uma "jovem inocente que não conhece nada do mundo" presa em um prédio. A peça maior é chamada de "filha" e outros blocos recebem nomes de outros membros da família (como pai, mãe e assim por diante).
Outra variação japonesa usa os nomes de peças de shogi .

#### L'âne rouge

Na França, é conhecido como L'âne rouge. Apresenta um burro vermelho (a maior peça) tentando escapar de um labirinto de cercas e canetas para chegar às cenouras. No entanto, não há registro conhecido e documentado de sua primeira existência na França.

#### Khun Chang Khun Phaen

Esta é uma variação da Tailândia. Khun Phaen é um personagem famoso da lenda tailandesa, e o jogo recebeu o nome do épico poema Khun Chang Khun Phaen, no qual o personagem está preso. O jogo mostra Khun Phaen saindo da prisão superando suas nove sentinelas.
Há uma pequena diferença entre Khun Chang Khun Phaen e o layout padrão - os dois blocos 1 × 1 do meio são movidos para o fundo. Fora isso, todos os outros blocos são iguais. A origem dessa variação é desconhecida.

### Outros arranjos de blocos

Nesse contexto, o arranjo "básico" é assumido como sendo uma área 4 × 5, da seguinte maneira:
* Na coluna da esquerda, dois blocos 1 × 2 com um bloco 1 × 1 abaixo.
* Na coluna da direita, dois blocos 1 × 2 com um bloco 1 × 1 abaixo.
* Nas duas colunas do meio, um bloco 2 × 2 na parte superior, com um bloco 2 × 1 horizontal abaixo, dois blocos 1 × 1 abaixo, deixando um espaço 2 × 1 vazio na parte inferior.
Isso é usado globalmente como o jogo "básico" de Klotski. É codificado C27d na classificação Hordern de jogos de quebra-cabeça deslizante.

#### Pennant Puzzle

Codificado como C19 na classificação Hordern, é o primeiro copyright em 1909 por Lewis. W. Hardy nos Estados Unidos. A Standard Trailer Co. possui direitos autorais sob o nome Dad's Puzzler em 1926 (também nos EUA). Seu arranjo é diferente:
* A localização padrão de todos os blocos é diferente de Klotski. Por exemplo, o maior bloco quadrado fica no canto superior esquerdo.
* Está na área 4 × 5, com uma 2 × 2, duas 1 × 2, quatro 2 × 1, duas peças 1 × 1.
* A saída do bloco não está no meio, mas no canto inferior esquerdo.
Fora isso, as regras do jogo são as mesmas que Klotski. O número mínimo de movimentos para resolver o quebra-cabeça é 59.

#### Ma's Puzzle

Ma's Puzzle tem direitos autorais da Standard Trailer Co. em 1927. Foi o primeiro quebra-cabeça deslizante a usar formas não retangulares. Seu objetivo é unir suas 2 peças em forma de L, em qualquer lugar ou no canto superior direito do tabuleiro.

### Versão computadorizada

A primeira versão gráfica conhecida do Klotski foi criada para Windows pela ZH Computing em 1991. Mais tarde, no mesmo ano, foi incluído no terceiro Microsoft Windows Entertainment Pack. Muitas versões do Klotski seguiram, disponíveis gratuitamente ou comercialmente. Por exemplo, um está incluído no ambiente de desktop da GNOME.