[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[obm-l] Re: [obm-l] resta um -táticas" ajuda "

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" <nicolau@sucuri.mat.puc-rio.br>
To: <obm-l@mat.puc-rio.br>
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 é <nicolau@mat.puc-rio.br>
=========================================================================


=========================================================================
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 é <nicolau@mat.puc-rio.br>
=========================================================================