Jump to content

USACO Checker Challenge


polska
 Share

Recommended Posts

Boas pessoal, bem, em algum problema do 1.5 tinha que encravar e parece que foi neste 😄 , eu percebo o que tenho que fazer e que devo implementar uma DFS, mas confundo sempre quando vou fazer as funções e fico sem saber como resolver o problema...

Temos que descobrir de quantas maneiras possíveis podemos encaixar os checkers no tabuleiro todos em colunas diferentes e não na mesma diagonal.. Eu percebo bem o que pede o problema, mas não conssigo implementar a solução, acabo por me perder na recursividade e apago a solução, estou a fazer grande trapalhada mesmo basicamente 😄 . Alguém me pode dar uma ajudinha?

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Link to comment
Share on other sites

estás a falar do problema das 8 raínhas ???

o algoritmo é semelhante a encontrar o caminho dentro de um labirinto ... já te faz lembrar algo ???

Sim, esse problema.

Encontrar um caminho dentro de um labirinto é uma pesquisa em profundidade... Eu percebo isso, mas bloqueio na hora de implementar neste problema

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Link to comment
Share on other sites

tens 8 peças e uma matrix NxN

- verificação se existe peças a colocar

- se sim

- para cada posição da matrix não preenchida

- colocar uma peça

- se a posição for válida

- recursividade com menos uma peça a colocar

- se não, continuar o ciclo

- se fim do ciclo

- retornar solução inválida

- se não

- retornar solução valida

IRC : sim, é algo que ainda existe >> #p@p
Link to comment
Share on other sites

tens 8 peças e uma matrix NxN

- verificação se existe peças a colocar

- se sim

- para cada posição da matrix não preenchida

- colocar uma peça

- se a posição for válida

- recursividade com menos uma peça a colocar

- se não, continuar o ciclo

- se fim do ciclo

- retornar solução inválida

- se não

- retornar solução valida

Neste caso não temos 8 peças.. temos o 6 <= N <= 13 , que é para o tabuleiro.. Tenho é de preencher com rainhas.

Examine the 6x6 checkerboard below and note that the six checkers are arranged on the board so that one and only one is placed in each row and each column, and there is never more than one in any diagonal. (Diagonals run from southeast to northwest and southwest to northeast and include all diagonals, not just the major two.)

Column

1 2 3 4 5 6

-------------------------

1 | | O | | | | |

-------------------------

2 | | | | O | | |

-------------------------

3 | | | | | | O |

-------------------------

4 | O | | | | | |

-------------------------

5 | | | O | | | |

-------------------------

6 | | | | | O | |

-------------------------

The solution shown above is described by the sequence 2 4 6 1 3 5, which gives the column positions of the checkers for each row from 1 to 6: ROW 1 2 3 4 5 6 COLUMN 2 4 6 1 3 5

This is one solution to the checker challenge. Write a program that finds all unique solution sequences to the Checker Challenge (with ever growing values of N). Print the solutions using the column notation described above. Print the the first three solutions in numerical order, as if the checker positions form the digits of a large number, and then a line with the total number of solutions.

Edited by polska

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Link to comment
Share on other sites

É normal as pessoas empancarem neste problema e a resolução necessita de algum trabalho em cima para ser eficiente.

Mas este também é daqueles problemas chave que vale mesmo muito a pena tentar resolver sozinho (pelo menos até ao N <= 12, o N = 13 é um pouco mais dificil), nem que se demore 1 semana ou mais. Por isso, para já não vou dar dicas, mas depois podes discutir as ideias que tens para o resolver.

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Link to comment
Share on other sites

É normal as pessoas empancarem neste problema e a resolução necessita de algum trabalho em cima para ser eficiente.

Mas este também é daqueles problemas chave que vale mesmo muito a pena tentar resolver sozinho (pelo menos até ao N <= 12, o N = 13 é um pouco mais dificil), nem que se demore 1 semana ou mais. Por isso, para já não vou dar dicas, mas depois podes discutir as ideias que tens para o resolver.

x2.

Lembro-me que na altura tive que meter uma quantidade enorme de optimizações nisto..

Acho que pior só o cryptcowgraphy..

Link to comment
Share on other sites

Bem, voltei a resolução deste problema e tentei fazer a função recursiva, mas cheguei a uma dúvida, este é o meu código:

#include <stdio.h>

int max, ans = 0;
int tabuleiro[13][13], canRow[13] = {0};


void colocaRainhas(int col)
{
//!condição de paragem
if(col == max-1)
{
	//!..
	return;
}

//!processamento
for(int linha=0; linha<max; linha++)
{
	if(!canRow[linha] && canPlace(row, col))
	{
		canRow[linha] = 1;
	}
}
}



int main()
{
//!input
scanf("%d", &max);

//!processamento
colocaRainhas(0);

return 0;
}

Eu adicionei o vector canRow para me indicar se uma determinada linha do tabuleiro esta livre (confesso que vi isto numa hint dada no enunciado), agora a minha dúvida é nesta condição:

if(!canRow[linha] && canPlace(row, col))

A função canPlace, não será tão simples como !canRow[linha] && tabuleiro[row][col]!=1 ??

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Link to comment
Share on other sites

A função canPlace, não será tão simples como !canRow[linha] && tabuleiro[row][col]!=1 ??

Para cada posicao tens que testar se a linha esta vazia, se a coluna esta vazia, e se as duas diagonais estao vazias.

So podes colocar uma rainha na posicao, por exemplo, [4][2] se todos as posicoes [*][2], [4][*], e as diagonais ([5][3], [6][4], [7][5], ... [5][1], [5][0], ..., [3][1], ..., [3][3], [2][4], ...) estiverem vazias.

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Link to comment
Share on other sites

Para cada posicao tens que testar se a linha esta vazia, se a coluna esta vazia, e se as duas diagonais estao vazias.

So podes colocar uma rainha na posicao, por exemplo, [4][2] se todos as posicoes [*][2], [4][*], e as diagonais ([5][3], [6][4], [7][5], ... [5][1], [5][0], ..., [3][1], ..., [3][3], [2][4], ...) estiverem vazias.

Então eu podia cirar também um array canCol com a mesma função que o canRow mas para colunas, e fazia uma função para testar as diagonais, uma função recursiva, tipo :

!canRow[linha] && tabuleiro[row][col]!=1 && !diagonal_principal && !diagonal_secundaria

Isto separando tudo, não se colocando tudo na mesma função não será mais fácil.

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Link to comment
Share on other sites

Pois, eu pensei que eram apenas as grandes..

Eu agora tenho praticamente tudo, só falta mesmo as diagonais, não haverá maneira de eu calcular o início de uma diagonal esquerda e direita de uma dada posição de rainha? Por exemplo, se a rainha estivesse na posição 4,2 , eu passava á função a posição 2,0 , que era o início da diagonal "principal" de 4,2 e passava a posição 1,5, que era o início da diagonal "secundaria" de 4,2 .. Eu já tentei alguns cálculos mas ainda não cheguei lá, e eu estou a tentar isto porque se eu passo 4,2 á função, tenho que calcular para a frente e para trás a partir dessa posição para verificar a diagonal :s .

Edited by polska

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Link to comment
Share on other sites

tenho uma solução mais simples para pensares :

como terás no máximo N peças num tabuleiro NxN, logo só terás N passos.

com uma lista de N matrizes, podes gravar os passos para criar uma solução.

se em cada posição da matriz poderes teres os valores :

> 0 = livre

> 1 = ocupado

> -1 = não permitido

basta teres este código (não está completo mas dá para o gasto)

// int ** = matriz
// int *** = lista de matrizes

void copiar_matrix(int ** dest, int ** src, int N)
{
 /* copiar a matriz */
}

void colocar_rainha(int ** matrix, int linha, int coluna)
{
 /* marcar as novas posição como inválidas
  * - na linha da nova peça  (valor : -1)
  * - na coluna da nova peça (valor : -1)
  * - nas diagonais da peça  (valor : -1)
  * - posição da nova rainha (valor :  1)
  */
}

int dfs(int *** solucao, int N, int passo)
{
 int i, j;

 if (passo == N)
 {
   // solução do problema
   return 1;
 }

 /* ciclo de todas as posições para ver onde se pode tentar colocar uma rainha */
 for (int i; i < N; i++)
 {
   for (int j; j < N; j++)
   {
     /* verificar se é possível colocar a rainha na posição (i,j) */
     if (solucao[passo][i]{j] == 0)
     {
       /* gravar o estado do passo actual para o seguinte */
       copiar_matrix(solucao[passo+1], solucao[passo], N); 

       /* marcar as novas posição como inválidas */
       colocar_rainha(solucao[passo+1], i, j);

       /* procurar o resto da solução */
       if (dfs(solucao, N, passo+1))
         return 1;
     }
   }
 }

 /* solução não foi encontrada */
 return 0;
}

int main()
{
 int *** solucao = NULL;

 /* alocar a lista de matrizes */
 /* colocar 0 em todos os elementos da primeira matriz */

 if (dfs(solucao, N, 0))
 {
   /* a solução está na última matrix nas células com valor 1 */
 }

 /* libertar memória */

 return 0;
}
IRC : sim, é algo que ainda existe >> #p@p
Link to comment
Share on other sites

tenho uma solução mais simples para pensares :

como terás no máximo N peças num tabuleiro NxN, logo só terás N passos.

com uma lista de N matrizes, podes gravar os passos para criar uma solução.

se em cada posição da matriz poderes teres os valores :

> 0 = livre

> 1 = ocupado

> -1 = não permitido

basta teres este código (não está completo mas dá para o gasto)

// int ** = matriz
// int *** = lista de matrizes

void copiar_matrix(int ** dest, int ** src, int N)
{
 /* copiar a matriz */
}

void colocar_rainha(int ** matrix, int linha, int coluna)
{
 /* marcar as novas posição como inválidas
  * - na linha da nova peça  (valor : -1)
  * - na coluna da nova peça (valor : -1)
  * - nas diagonais da peça  (valor : -1)
  * - posição da nova rainha (valor :  1)
  */
}

int dfs(int *** solucao, int N, int passo)
{
 int i, j;

 if (passo == N)
 {
   // solução do problema
   return 1;
 }

 /* ciclo de todas as posições para ver onde se pode tentar colocar uma rainha */
 for (int i; i < N; i++)
 {
   for (int j; j < N; j++)
   {
     /* verificar se é possível colocar a rainha na posição (i,j) */
     if (solucao[passo][i]{j] == 0)
     {
       /* gravar o estado do passo actual para o seguinte */
       copiar_matrix(solucao[passo+1], solucao[passo], N);

       /* marcar as novas posição como inválidas */
       colocar_rainha(solucao[passo+1], i, j);

       /* procurar o resto da solução */
       if (dfs(solucao, N, passo+1))
         return 1;
     }
   }
 }

 /* solução não foi encontrada */
 return 0;
}

int main()
{
 int *** solucao = NULL;

 /* alocar a lista de matrizes */
 /* colocar 0 em todos os elementos da primeira matriz */

 if (dfs(solucao, N, 0))
 {
   /* a solução está na última matrix nas células com valor 1 */
 }

 /* libertar memória */

 return 0;
}

Eu percebi a solução que me explicaste, mas eu queria agora tentar acabar a minha, só falta mesmo a verificação das diagonais de uma posição.. Eu podia assinalar as diagonais a -1 ou fazer uma função que me verificasse se elas não contêm nenhuma rainha... Mas foi como eu disse, se eu tenho uma matrix de 6*6 e por exemplo, tenho de verificar ou assinalar as diagonais da posição (4,2), tenho que andar para trás e para a frente no tabuleiro a assinalar ou a verificar.. E isso não é nada eficiente..

Eu tenho isto:

#include <stdio.h>

int max, ans = 0;
int tabuleiro[13][13], canRow[13] = {0}, canCol[13] = {0};

void printSol(int row, int col)
{
if(row == max)
	return;

if(tabuleiro[row][col] == 1)
{
	printf("%d", col);
	printSol(row+1, 0);
}
else
	printSol(row, col+1);
}

void colocaRainhas(int coluna)
{
//! condição de paragem
if(coluna == max)
{
	if(ans < 3)
	{
		printSol(0,0);
		printf("\n");
	}
	ans++;
	return;
}

//! processamento
for(int linha=0; linha<max; linha++)
{
	if(!canRow[linha] && !canCol[coluna])
	{
		//! marca linha e coluna como usada
		//! coloca rainha no tabuleiro
		canRow[linha] = 1;
		canCol[coluna] = 1;
		tabuleiro[linha][coluna] = 1;

		//! continua processamento
		colocaRainhas(coluna+1); 

		//! desmarca linha e coluna
		//! retira rainha do tabuleiro
		tabuleiro[linha][coluna] = 0;
		canCol[coluna] = 0;
		canRow[linha] = 0;
	}
}
}

int main()
{
//! input
scanf("%d", &max);

//! processamento
colocaRainhas(0);

//! resultado, soluções totais
printf("%d\n", ans);

return 0;
}

só falta mesmo acabar esta condição if(!canRow[linha] && !canCol[coluna]) com a verificação das diagonais: if(!canRow[linha] && !canCol[coluna] && diagonais(row,col))

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Link to comment
Share on other sites

Assim como tens os arrays canRow e canCol podes arranjar os arrays canDiagEsq[0], canDiagEsq[1], ..., canDiagEsq[2N-1] e o mesmo para canDiagDir.

Ha duas formulas muito simples que mapeiam a posicao que queres verificar em cada uma das diagonais

canDiagEsq[linha + coluna]

canDiagDir[N-linha + coluna]

|-|-|-|*|-|-|    * canDiagEsq[3]
|-|-|*|-|-|-|    # canDiagEsq[7]
|-|*|-|-|-|#|
|*|-|-|-|#|-|
|-|-|-|#|-|-|
|-|-|#|-|-|-|

|-|-|-|*|-|-|    * canDiagDir[8]
|#|-|-|-|*|-|    # canDiagDir[4]
|-|#|-|-|-|*|
|-|-|#|-|-|-|
|-|-|-|#|-|-|
|-|-|-|-|#|-|

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Link to comment
Share on other sites

uma dúvida @pmg, eu já criei os arrays, e inicializei-os a 0..

Quando tenho de testar uma posição, como devo colocar nos parenteses em : !canDiagonalEsq[] && !canDiagonalDir[] ?

Eu fiz uns calculos e em alguns casos resultava quando colocava Linha+coluna no DiagonalEsq e linha-coluna no DiagonalDir, mas não em todos os casos... :s

Já agora, posso estar a entender mal, mas as diagonais direitas começam a contar no canto inferior esquerdo ma matrix e as esquerdas no superior :b

Edited by polska

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.