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]>
=========================================================================
