USACO Checker Challenge

[polska]

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?

[HappyHippyHippo]

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 ???

[polska]

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

[HappyHippyHippo]

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

[polska]

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 July 25, 2012 at 09:03 PM by polska

[HappyHippyHippo]

o problema é conhecido, mas prontos ... agora é resolver-lo ..

agora ... não sei qual a flexibilidade das soluções espelhadas e rodadas no resultado pretendido

Edited July 25, 2012 at 09:05 PM by HappyHippyHippo

[mogers]

É 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.

[Warrior]

É 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..

[polska]

Eu estou tentando xD

[polska]

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 ??

[pmg]

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.

[polska]

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.

[pmg]

Repara que tens 15 diagonais "esquerdas" e outras tantas "direitas".

Nao basta verificar apenas as diagonais grandes.

[polska]

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 August 17, 2012 at 12:06 AM by polska

[HappyHippyHippo]

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;
}

[polska]

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))

[pmg]

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]
|-|#|-|-|-|*|
|-|-|#|-|-|-|
|-|-|-|#|-|-|
|-|-|-|-|#|-|

[polska]

hum.. certo, já entendi. Vou tentar resolver, obrigado 🙂

Edited August 17, 2012 at 11:47 AM by polska

[polska]

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 August 17, 2012 at 01:51 PM by polska

[pmg]

Em vez de canRow[linha] usa canDiagonalEsq[linha + coluna] e parecido para a outra diagonal.