Saber todas las combinaciones posibles de un tablero

[aguml]

Hola amigos, hoy he estado ayudando en la tarea de mates a la peque y la verdad es que el ejercicio no lo entiendo ni yo pero de él me ha surgido una duda. El ejercicio decía algo asi:

Pablo tiene 4 fichas y las quiere colocar en una cuadricula de 4 filas por 4 columnas de manera que con coincidan en fila, ni en columna, ni en diagonal. Dibuja todas las combinaciones posibles.

Yo como un tonto he dibujado la cuadricula y con 4 garbanzos he intentado colocar las fichas de manera que ninguna coincidiera con otra en la misma fila, o en la misma columna, o en la misma diagonal. Deduje que es imposible o al menos yo no vi la manera. Entonces se me ocurrió que quizás se refiere a que no pueden estar todas alineadas ni en una fila, ni en una columna, ni en una diagonal. Es poco probable que sea este caso porque es una niña de 9 años y creo que podrían ser muchas combinaciones así que que ponga lo que le parezca y ya veremos cuando lo corrijan pero este último planteamiento que he dado me gustaría saber como resolverlo en C. ¿alguien sabría explicar como hay que plantear esto o que formula matemática se usa o algo?

[xKuZz]

Para resolver problemas de este tipo hay muchas técnicas variadas de búsqueda en espacio de estados que dan solución al problema (búsquedas en anchura, profundidad, algoritmos genéticos) o técnicas algorítmicas de backtracking o branch & bound suelen ser útiles. Probablemente backtracking sea la más apropiada para el problema.

No obstante, el número de tableros posibles para 4 fichas si consideramos una representación con un vector de 4 enteros en el que el índice es la fila y el valor es la columna y en los valores aparece cada valor del 1 al 4 una única vez se reduce a comprobar todas las permutaciones de esos cuatro números y determinar cuáles son factibles, y 4! = 4 * 3 * 2 = 24 tableros se comprueba en un momentillo. Por tanto hacerlo por fuerza bruta no es ningún problema. En C++:

Código C++:

#include <algorithm>
#include <iostream>
#include <set>
#include <tuple>
#include <vector>
 
using namespace std;
 
bool esFactible(const vector<int>& fichas) {
    set<int> diagonal_descendente;
    set<int> diagonal_ascendente;
    bool unico = true;
    for (unsigned i = 0; i < fichas.size(); ++i) {
        // Si dos valores fila - columna coinciden indican que estamos en
        // la misma diagonal descendente
        tie(ignore, unico) =diagonal_descendente.insert(i-fichas[i]);
        if (!unico)
            return false;
 
        // Si dos valores fila + columna coinciden indican que estamos en
        // la misma diagonal ascendente
        tie(ignore, unico) = diagonal_ascendente.insert(i+fichas[i]);
        if (!unico)
            return false;
    }
 
    // Si no ocurre nada de eso es una solución porque no hay encuentros
    // diagonales y la modelización del espacio de estados evita que haya
    // columnas o filas iguales
    return true;
}
 
int main() {
    // Representación del tablero
    // Índice -> Filas -1
    // Valor -> Columnas
    vector<int> fichas {1, 2, 3, 4};
 
    // A permutar
    do {
        if (esFactible(fichas)) {
            cout << "SOLUCION" << endl;
            for (unsigned i = 0; i < fichas.size(); ++i)
                cout << "Fila " << i+1 << "\t Columna" << fichas[i] << endl;
            cout << endl << endl;
        }
    } while (next_permutation(fichas.begin(),fichas.end()));
 
}
 

Que me devuelve como solución dos únicos tableros que cumplen eso si no lo he hecho mal que creo que no.

Fila 1 Columna2
Fila 2 Columna4
Fila 3 Columna1
Fila 4 Columna3


SOLUCION
Fila 1 Columna3
Fila 2 Columna1
Fila 3 Columna4
Fila 4 Columna2

Hay un problema muy similar a este que es el problema de las 8 reinas y que se resolvería de la misma manera (eso sí la fuerza bruta cuanto más grande es el tablero menos recomendable). Infórmate sobre éstos que te he comentado y te dará para rato y una manera de encontrar la solución más apropiada que comprobarlo todo y aunque este problema haya sido resuelto aquí con esta fuerza bruta cutre la búsqueda en el espacio de estados en un tema denso e interesante si te gustan este tipo de problemas.

[aguml]

y 4! = 4 * 3 * 2 = 24 tableros

No entiendo eso que dices hay..
Por otro lado lo pedía en C porque de C++ no entiendo tanto y por ejemplo eso que haces aqui:

Código PHP:

      set<int> diagonal_descendente;
    set<int> diagonal_ascendente;
    bool unico = true;
    for (unsigned i = 0; i < fichas.size(); ++i) {
        // Si dos valores fila - columna coinciden indican que estamos en
        // la misma diagonal descendente
        tie(ignore, unico) =diagonal_descendente.insert(i-fichas[i]);
        if (!unico)
            return false;
 
        // Si dos valores fila + columna coinciden indican que estamos en
        // la misma diagonal ascendente
        tie(ignore, unico) = diagonal_ascendente.insert(i+fichas[i]);
        if (!unico)
            return false;
    } 
   

SI como dices que lo de las ocho reinas es igual, voy a buscar info por la red a ver si encuentro algo donde se explique con mucha claridad.

[eferion]

4! Lo dice porque la primera ficha puede estar en cualquiera de las 4 filas, mientras que la segunda ficha puede estar únicamente en tres filas (no puede coincidir con la fila ocupada por la primera ficha). Con el mismo planteamiento se deduce que la tercera ficha únicamente puede estar colocada en 2 posibles filas y la cuarta ya no tiene elección.

Estas condiciones te dan 4*3*2*1=4!=24 posibles combinaciones.

Si tuviese en cuenta a la vez las columnas entonces el número de posibles combinaciones crece hasta las 576 combinaciones, 24^2.

Un saludo

[xKuZz]

Perdona, no toco mucho el C sin el ++, jeje.
el 4! hace referencia 4 factorial que es el número de permutaciones sin repeticiones posibles sin repetición de {1,2,3,4}, como te ha indicado eferion

El esquema de fuerza bruta usado es el siguiente:

Para cada permutación de {1,2,3,4}
Si es factible, lo muestro como solución por pantalla.

Una permutación es factible si: (Esto es fácil de comprobar con papel y boli)
La resta de su fila menos su columna es única en el array de diagonales descendentes.
La suma de su fila más su columna es única en el array de diagonales ascedentes.

Puesto que los índices del array indican los valores de la fila y son únicos y del 1 al 4 nunca va a haber dos fichas en la misma fila.

Puesto que los valores para cada permutación son siempre los mismos que los iniciales pero en orden diferente, van de 1 a 4 y son únicos, los valores del array representan las columnas y son únicos.

¿Así lo entiendes mejor?

Saludos.

[aguml]

Lo del factorial no me acabo de enterar pero eso es porque nunca los di en el cole (o falte ese dia) jejeje. La verdad es que ahí estoy muy perdido aunque que encantan las matemáticas.
Lo otro ya me ha quedado claro.

A ver si me entero, el factorial es el producto de todos los valores enteros desde 1 a n y como aquí va de 1 a 4 es 1*2*3*4=24.
Eso sería solo para las filas pero si quisiera realmente saber cuantas combinaciones realmente hay serian:
(!n)^2
Cómo hay 4 filas y cuatro columnas y dos diagonales tendríamos ya de entrada un descarte de 10 combinaciones.
¿El truco aquí está en que sólo usamos un array unidmensional y con eso se reducen las posibles combinaciones de (!n)^2 a !n ?
Mañana si puedo lo intentaré hacer en c a ver que sale. Ya vi el de las 8 reinas en c pero usando recursividad y la verdad es que la recursividad y yo nos llevamos muy mal así que quiero codearlo sin ella jejeje.

[aguml]

Bueno amigos, he encontrado este código en C que usa recursividad: http://elvex.ugr.es/decsai/c/problemas/reinas/reinas2.c
Estoy intentando pasarlo a no recursivo y me tiene loco porque no veo el modo de hacerlo. El caso es que, como dije, la recursividad y yo somos enemigos declarados y me pierdo cuando intento entender una funcion recursiva por muy sencilla que sea jajaja. Aqui está lo que llevo:

Código C:

// Problema de las N reinas
// ------------------------
 
// Algoritmo recursivo
//
// 0. Obviamente, colocaremos una reina en cada fila
//
// 1. Se coloca una reina en una casilla de su fila y,
//    a continuación, se intentan colocar las reinas restantes.
//
// 2. Si las demás reinas no se pueden colocar con éxito,
//    probamos a colocar la reina actual en otra columna.
//
// Caso base: Cuando no quedan reinas por colocar.
 
 
#include <stdio.h>
#include <stdlib.h>
 
// Constantes simbólicas
 
#define TRUE  1
#define FALSE 0
 
 
// Comprobar si una reina está bien colocada
// -----------------------------------------
// La reina de la fila i está bien colocada si no está
// en la columna ni en la misma diagonal que cualquiera
// de las reinas de las filas anteriores
//
// Parámetros
//   fila   - Fila de la reina cuya posición queremos validar
//   reinas - Vector con las posiciones de las reinas
//   n      - Número de reinas
 
 
int comprobar (int fila, int reinas[], int n) 
{
  int i;
 
  for (i=0; i<fila; i++)
      if (  ( reinas[i]==reinas[fila] )                      // Misma columna
         || ( abs(fila-i) == abs(reinas[fila]-reinas[i]) ) ) // Misma diagonal
         return FALSE;
 
  return TRUE;
}
 
 
// Mostrar el tablero con las reinas
// ---------------------------------
// Parámetros:
//   reinas - Vector con las posiciones de las distintas reinas
//   n      - Número de reinas
 
void mostrarTablero (int reinas[], int n)
{
  int i,j;
 
  for (i=0; i<n; i++) {
 
      for (j=0; j<n; j++) {
 
          if (reinas[i]==j)
             printf("#");
          else
             printf("-");
      }
 
      printf(" %d %d\n",i,reinas[i]);
  }
 
  printf("\n");
}
 
 
// Colocación de una reina
// -----------------------
// Parámetros
//   fila   - Fila de la reina que queremos colocar
//   reinas - Vector con las posiciones de las reinas
//   n      - Número de reinas
 
int colocarReina (int fila, int reinas[], int n)
{
  int ok = FALSE;
 
  if (fila<n) {
 
     // Quedan reinas por colocar
 
         // Comprobamos si la posición 
         // de la reina actual es válida
 
         if (comprobar(fila,reinas,n)) {
 
            // Si es así, intentamos colocar
            // las reinas restantes
            ok = TRUE;
         }
  
  } else {
 
     // No quedan reinas por colocar (solución)
 
     mostrarTablero(reinas,n);
  }
 
  return ok;
}
 
 
 
// Mostrar información acerca del uso del programa
// -----------------------------------------------
// Parámetro:
//   programa - Nombre del programa
 
void mostrarAyuda (char *programa)
{
  printf("Instrucciones:\n");
  printf("-------------\n\n");
  printf("Al princicio nos pide el numero de reinas que deseamos colocar en el tablero.\n");
  printf("El numero de reinas sera igual a las dimensiones del tablero, osea que\n");
  printf("el tablero tendra un tamaño de nReinas x nReinas.\n");
  printf("El valor minimo permitido es 4 y el maximo es 10.\n");
}
 
// Programa principal
// ------------------
 
int main (int argc, char *argv[])
{
  int *reinas;  // Vector con las posiciones de las reinas de cada fila
  int nreinas;  // Número de reinas
  int i;        // Contador
  int fila;
  int nposibles,probados=0;
 
  // Obtener el número de reinas
  printf("Introduce el numero de reinas: ");
  scanf("%d",&nreinas);
 
  if(nreinas >=4 && nreinas <=10){
      // Colocar las reinas en el tablero
 
      // Crear vector dinámicamente
      reinas = (int*) malloc ( nreinas*sizeof(int) );
 
      // Inicializar vector:
      // (inicialmente, ninguna reina está colocada)
      for (i=0; i<nreinas; i++)
          reinas[i] = -1;
 
      //Obtener el numero de combinaciones posibles
      for(i=1,nposibles=1;i<=nreinas;i++)
         nposibles *= i;
 
      // Colocar reinas
      do{
         fila=0;
         for (reinas[fila]=0; reinas[fila]<nreinas; reinas[fila]++) {
            if(colocarReina(fila,reinas,nreinas) == TRUE){
               fila++;
            }else{
               break;
            }
         }
         probados++;
      }while(nposibles > probados);
 
      // Liberar memoria
      free (reinas);
  } else {
      mostrarAyuda(argv[0]);
  }
  return 0;
}
 

¿Podriais echarme una mano diciendome que debo cambiar y sobre todo explicarme que hago mal?

[eferion]

Lo cierto es que me parece un ejercicio un tanto raro para 8 años... es más un rompecabezas que un ejercicio jejeje

[aguml]

pues si porque con 9 años no la veo con ecuaciones en matematicas jajaja. Es raro y creo que la idea seria que hiciera como yo, coger una cuadricula y con unas fichas hacerlo a mano para ver si se podia o no y cuales. Para esa edad no le veo utilidad matematica, es mas, supongo que seria un problema matematico de al menos 4º de la eso o bachillerato.
Tambien estoy intentando convertir el codigo de xKuZz a C pero es que no se como traducir las lineas que usa tie porque no tengo ni idea de que hace eso y lo que veo por la red habla de tuplas que no se ni que es .

[eferion]

std::set es un contenedor en el que los elementos están ordenados, en este caso por orden ascendente. El método insert te devuelve en un paquete (tupla) un iterador a la posición del elemento y un booleano que indica si el elemento ha sido insertado (true) o si ya existía (false). Lo que hace tie es separar esos dos valores (iterador,booleano). En este caso tie separa los elementos del paquete y los almacena en las variables que le facilitas como parámetro. El iterador no nos interesa para nada, por lo que lo almacenamos en ignore que es algo parecido a un cubo de la basura de la stl para datos que no te interesan mientras que el segundo parámetro, que indica si el valor se ha insertado en el contenedor o si ya existía lo amacena en la variable unico.

Lo que hace el algoritmo de xKuZz es insertar en el set los resultados de sumar o restar (según el caso) la fila y columna de cada ficha. Si el contenedor no tenía ese valor ya almacenado almacenará en unico un true y un false en caso contrario. Si consigues meter todos los resultados y no se repite ninguno (siempre recibes true) es que has podido ubicar las 4 fichas cumpliendo los requisitos planteados.

Un saludo.

[aguml]

Bueno, tirando del codigo de y con vuestras explicaciones he llegado a esto:

Código C:

#include <stdio.h>
#include <stdlib.h>
 
/* next lexicographical permutation */
int perm(int *a, int n) {
#   define swap(i, j) {t = a[i]; a[i] = a[j]; a[j] = t;}
    int k, l, t;
 
    /* 1. Find the largest index k such that a[k] < a[k + 1]. If no such
          index exists, the permutation is the last permutation. */
    for (k = n - 1; k && a[k - 1] >= a[k]; k--);
    if (!k--) return 0;
 
    /* 2. Find the largest index l such that a[k] < a[l]. Since k + 1 is
       such an index, l is well defined */
    for (l = n - 1; a[l] <= a[k]; l--);
 
    /* 3. Swap a[k] with a[l] */
    swap(k, l);
 
    /* 4. Reverse the sequence from a[k + 1] to the end */
    for (k++, l = n - 1; l > k; l--, k++)
        swap(k, l);
    return 1;
#   undef swap
}
 
int Diagonal(unsigned *len,int **diagonal,int n)
{
   unsigned j,ok=1;
 
   if(*len == 0){
      *diagonal=(int*)malloc(sizeof(int));
      (*diagonal)[0]=n;
      (*len)++;
   }else{
      for(j=0;j<*len;j++)
         if((*diagonal)[j]==n){
            ok=0;
            break;
         }
      if(ok==1){
         (*len)++;
         *diagonal=(int*)realloc(*diagonal,*len * sizeof(int));
         (*diagonal)[*len-1]=n;
      }
   }
   return ok;
}
 
int esFactible(const int fichas[],unsigned nreinas) {
   int *diagonal_descendente=NULL;
   int *diagonal_ascendente=NULL;
   unsigned i;
   unsigned len_desc=0,len_asc=0;
   int retval=1;
 
   for (i = 0; i < nreinas; ++i) {
      // Si dos valores fila - columna coinciden indican que estamos en
      // la misma diagonal descendente
      if(Diagonal(&len_desc,&diagonal_descendente,i-fichas[i])==0){
         retval=0;
         break;
      }
     
      // Si dos valores fila + columna coinciden indican que estamos en
      // la misma diagonal ascendente
      if(Diagonal(&len_asc,&diagonal_ascendente,i+fichas[i])==0){
         retval=0;
         break;
      }
   }
   free(diagonal_descendente);
   free(diagonal_ascendente);
   diagonal_descendente=NULL;
   diagonal_ascendente=NULL;
     
   // Si no ocurre nada de eso es una solución porque no hay encuentros
   // diagonales y la modelización del espacio de estados evita que haya
   // columnas o filas iguales
   return retval;
}
 
void mostrarAyuda (void)
{
  printf("Instrucciones:\n");
  printf("-------------\n\n");
  printf("Al princicio nos pide el numero de reinas que deseamos colocar en el tablero.\n");
  printf("El numero de reinas sera igual a las dimensiones del tablero, osea que\n");
  printf("el tablero tendra un tamaño de nReinas x nReinas.\n");
  printf("El valor minimo permitido es 4 y el maximo es 10.\n");
}
 
void RepresentarFilaTablero(int size,int posReina)
{
   int i;
 
   for(i=0;i<size;i++)
      if(i!= posReina-1)
         printf("O ");
      else
         printf("X ");
}
 
int main() {
   // Representación del tablero
   // Índice -> Filas -1
   // Valor -> Columnas
   int *reinas;
   unsigned i;
   unsigned nreinas=4;
   int nPermutas=0,nSoluciones=0;
 
   do{
      // Obtener el número de reinas
      printf("Introduce el numero de reinas: ");
      scanf("%d",&nreinas);
 
      if(nreinas <4 || nreinas >10){
         mostrarAyuda();
         system("PAUSE");
         system("CLS");
      }
   }while(nreinas < 4 || nreinas > 10);
 
   // Colocar las reinas en el tablero
   // Crear vector dinámicamente
   reinas = (int*) malloc ( nreinas * sizeof(int) );
 
   // Inicializar vector:
   // (inicialmente, ninguna reina está colocada)
   for (i=0; i<nreinas; i++)
      reinas[i] = i+1;
 
   printf("\n");
 
   // A permutar
   do {
 
      if (esFactible(reinas,nreinas)) {
         printf("SOLUCION (%d):\n",++nSoluciones);
         for (i = 0; i < nreinas; ++i){
            RepresentarFilaTablero(nreinas,reinas[i]);
            printf("  ->  Fila %d\t Columna %d\n",i+1, reinas[i]);
         }
         printf("\n");
         if(nSoluciones % 10 == 0){
            system("PAUSE");
            system("CLS");
         }
      }
      nPermutas++;
   } while(perm(reinas,nreinas));
   printf("En un total de %d combinaciones, se encontraron %d soluciones validas.\n",nPermutas,nSoluciones);
   free(reinas);
   system("PAUSE");
   return 0;
}
 

Creo que funciona correctamente pero la funcion de permutar la saqué de internet y realmente no tengo ni idea de como funciona dicha funcion pero funciona jajaja. Si pudieran explicarme como funciona ya que con los comentarios que trae no me acabo de enterar.
Y tambien sigo interesado en hacer funcionar sin recursividad el otro codigo que os puse por si podeis ayudarme a arreglarlo. Gracias de antemano por toda la ayuda.

[leosansan]

Bueno, bueno, volviendo a que el problema se plantea para una niña de 9 añitos creo que la solución ha de ser algo más sencilla.

Para empezar a colocar los garbanzos de aguml sobre la cuadrícula de 4x4 tacharía las diagonales (es obvio pero si tienes duda inténtalo) y así colocaría el primer garbanzo en (0,1). Ahora tacharía el resto de la fila y columna así como sus diagonales (en realidad una sola más) y quedaría algo como esto:



Como se ve ya solo queda un hueco en la segunda línea, coloco el segundo garbanzo y tacho el resto de su línea, columna y diagonal (uf que pesado estoy, en realidad se tacha una sola casilla) y ya nos queda:



¡Voilá¡, ya solo quedan dos casillas donde van los garbanzos tres y cuatro.
La otra solución se puede obtener de forma similar empezando con el (0,2) o, para nosotros que no para la niña. aplicando simetría respecto a la diagonal principal.

Y aguml. entre tú, yo, en C con una cuadrícula tan pequeña pasaría de permutaciones y de todo el aparataje logístico del C++que nosotros no tenemos. Casi me quedaría con esto:

Código C++:

#include<stdio.h>
 
int main()  {
    int i, j, a[4][4]={0};
  for (i=0; i<4; i++)
    for (j=0; j<4; j++){
      if (i==j ||(i+j==3)){
          a[i][j]=1 ;
          continue;
      }
      if (a[i][j]==0){
        a[j][i]=1;
        printf ("(%2d , %2d) ---- (%2d , %2d)\n",i ,j ,j, i);
        break ;
      }
    }
  return 0 ;
}
 

Código C++:

( 0 ,  1) ---- ( 1 ,  0)
( 1 ,  3) ---- ( 3 ,  1)
( 2 ,  0) ---- ( 0 ,  2)
( 3 ,  2) ---- ( 2 ,  3)
 
Process returned 0 (0x0)   execution time : 0.006 s
Press any key to continue.
 

Después de más de un año sin tocar un teclado estoy algo oxidado pero creo que salvo pifia mayúscula valga y os guste lo que propongo

[eferion]

Cuánto tiempo sin saber de ti leosansan. Me alegra tenerte de vuelta

[leosansan]

Iniciado por eferion

Cuánto tiempo sin saber de ti leosansan. Me alegra tenerte de vuelta

¡¡¡ La alegría es mutua fenómeno ¡¡¡¡

[aguml]

Pues leon sanan, creo que lo que explicas en las cuadrículas seria lo que se esperaba que hicieran pero me dijo que no explicaron nada y que cuando han resuelto en la pizarra simplemente puso los resultados sin más explicación. Con profesores así mal les ira a lo que se supone es el futuro.
Toda la demás parafernalia era por trastear e intentarlo resolver codeándo y hacerlo más flexible que un 4x4.
¿esa lógica de tachar las diagonales vale tamaños mayores o es solo para 4x4?

[eferion]

No es tachar las diagonales sino todos los espacios prohibidos... y te debería valer para cualquier tipo de tablero

[aguml]

Por cierto, si hoy trae el libro y el cuaderno les haré una foto a la parte del libro y como quedó en el cuaderno para que opinen si eso es tarea de mates o no para una niña de 9 años.