Eu estou até com vergonha de dizer isso, mas escrevi um programa que tenta todas as
jogadas possíveis e vê se tem solução...
Supondo que eu tenha entendido direito a configuração triangular que o Haroldo pediu:
0
1 2
3 4 5
6 7 8 9
10 11 12 13 14
Meu programa disse que não tem solução, não importa onde o buraco vazio comece.
Claro que essa técnica exaustiva só funciona para tabuleiros pequenos como esse...
Coloquei o computador do meu pai (1.2 GHz) para
rodar com o de 33 posições, vamos ver o que acontece... Provavelmente amanhã de manhã
eu vou desistir ;)
Caso alguém se interesse, aqui está o código... Para testar com outro tabuleiro mude
as coisas no começo. Este aqui está com o
tabuleiro triangular.
- Juliana
/* @BEGIN_OF_SOURCE_CODE */
#include <stdio.h>
#define TAMANHO_TABULEIRO 15
#define NUMERO_JOGADAS 24
/*tabuleiro:
0
1 2
3 4 5
6 7 8 9
10 11 12 13 14
*/
/* jogada: casa inicial, casa do meio, casa final */
int jogadas[NUMERO_JOGADAS][3] =
{
{ 0, 1, 3}, { 1, 3, 6}, { 2, 4, 7}, { 3, 6,10},
{ 3, 4, 5}, { 3, 1, 0}, { 4, 7,11}, { 5, 8,12},
{ 5, 4, 3}, { 6, 3, 1}, { 6, 7, 8}, { 7, 4, 2},
{ 7, 8, 9}, { 8, 7, 6}, { 9, 8, 7}, {10, 6, 3},
{10,11,12}, {11, 7, 4}, {11,12,13}, {12,11,10},
{12, 8, 5}, {12,13,14}, {13,12,11}, {14,13,12}
};
/* o caminho até a posição vencedora terá 13 passos,
porque é o número de peças que precisam ser comidas */
/* a posicao 0 guarda a casa de origem, a posição 1
guarda a casa de destino */
int caminho[TAMANHO_TABULEIRO - 2][2];
int j; /* em qual passo estamos */
int t[TAMANHO_TABULEIRO]; /* o tabuleiro */
void passo();
void main()
{
int i;
int k;
for (k=0;k<TAMANHO_TABULEIRO;k++)
{
printf("casa vazia = %d\n\n",k);
for (i=0;i<TAMANHO_TABULEIRO;i++) t[i] = 1;
t[k] = 0; /* a casa que começa vazia */
j = 0;
passo();
}
}
/* função recursiva de backtracking */
void passo()
{
int i,k;
for (i=0;i<NUMERO_JOGADAS;i++) /* para cada jogada que existe */
{
/* dá pra fazer essa jogada agora? */
if ( t[jogadas[i][0]] == 1 &&
t[jogadas[i][1]] == 1 &&
t[jogadas[i][2]] == 0 )
{
/* faz a jogada */
t[jogadas[i][0]] = 0;
t[jogadas[i][1]] = 0;
t[jogadas[i][2]] = 1;
caminho[j][0] = jogadas[i][0];
caminho[j][1] = jogadas[i][2];
j++;
if (j==TAMANHO_TABULEIRO - 2) /* é uma posição final? */
{ /* sim: imprime o caminho */
printf("caminho:\n");
for (k=0;k<TAMANHO_TABULEIRO - 2;k++)
printf("%4d%4d\n",caminho[k][0],caminho[k][1]);
printf("\n");
} else
passo(); /* não: continua */
/* desfaz a jogada */
t[jogadas[i][0]] = 1;
t[jogadas[i][1]] = 1;
t[jogadas[i][2]] = 0;
j--;
}
}
}
/* @END_OF_SOURCE_CODE */
----- Original Message -----
From: "Nicolau C. Saldanha" <[EMAIL PROTECTED]>
To: <[EMAIL PROTECTED]>
Sent: Friday, April 05, 2002 6:06 PM
Subject: [obm-l] Re: [obm-l] Re: [obm-l] resta um -táticas" ajuda "
On Fri, Apr 05, 2002 at 05:55:06PM -0300, Juliana Freire wrote:
> "Como determinar" eu não sei...
> Na verdade não tenho a menor idéia de qual a lógica por trás disto,
> mas quando eu era criança uma vez meu avô conseguiu resolver sem
> querer, e eu decorei a solução.
> Vamos numerar as casas do tabuleiro assim:
>
> 1 2 3
> 4 5 6
> 7 8 9 10 11 12 13
> 14 15 16 17 18 19 20
> 21 22 23 24 25 26 27
> 28 29 30
> 31 32 33
O volume 2 do livro Winning Ways de Berlekamp, Conway e Guy
tem um monte de coisa sobre este jogo.
Um problema extra pouco conhecido é deixar só um com o buraco
inicial em qualquer posição dada, devendo o último pino ficar
na posição do buraco inicial.
Tem também o problema da OBM de provar que, começando com o buraco
no centro, o último pino *deve* ficar em uma das posições 2, 14, 17,
20 ou 32.
[]s, N.
[]s, N.
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <[EMAIL PROTECTED]>
=========================================================================
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <[EMAIL PROTECTED]>
=========================================================================
