Le problème des n dames optimitation

Saule · 26-02-2022 10:32:03

Bonjours/Bonsoir,

J'ai u a faire ré-cament a faire a ce problème, avec un plateaux de 10*10.
L’idée pour ce qui ne connaisse pas ce problème, c'est de placer n dames(d’échec) dans un échiquier de n*n, sans quel puise se toucher en un coup.
Je devais donc coder un programme qui trouve toutes le solution a ce problème, j'ai donc coder un petit code en C qui trouve les 724 solution a ce problème.
Je viens bien sur pas ici sans but, un ami a moi a remarquer que les solution sont modifiable facilement pour en obtenir d'autres :

(Les chiffre sont la lignes et l'emplacement des chiffre est la colonne.)
0257948136
6318497520

C'est assez basic comme méthode mais en cherchant un peu on a trouver un truc un peu plus puissant.
L'idée est de faire 9 - x sur tout les chiffre trouver.

0257948136
9742051863

L'idée est simple a comprendre, comme il est pas important de prendre en compte les casse blanche est noir dans ce problème on peut tout simplement retourner la plateaux pour avoir une autre solution.
C'est très puissant car ça divise par 2 le nombre de solution a trouver pour avoir les 724 solution.

Je pense qu'il est possible de réduire beaucoup, beaucoup plus le nombre de solution à avoir pour en déduire les 724.
J'aimerait bien savoir, a quel point on peu réduire le nombre de solutions a trouver, pour avoir toutes les solution.

Voici la liste des 724 solution à ce problème :

Saule · 26-02-2022 10:36:41

Le code C en question :

#include <unistd.h>

void  ft_putchar(char c)

{

  write(1, &c, 1);

}

//i - ligne = colone (le i % 10 peut etre un equivalent)

//nombre max de diago gauche = colone

//nombre max de diago droite = 9 - colone

//nombre max de deplacement bas = 9 - ligne / 10

void  push_pull_queens(int *tab, int i, int ligne, int state)

{

  int x;

  int t;

  x = 0;

  t = i + 10;

  while (++x <= 9 - ligne / 10)

  {

    tab[t] += (2 * state);

    t += 10;

  }

  x = 0;

  t = i + 9;

  while (++x <= i - ligne && x <= 9 - ligne / 10)

  {

    tab[t] += (2 * state);

    t += 9;

  }

  x = 0;

  t = i + 11;

  while (++x <= 9 - (i - ligne) && x <= 9 - ligne / 10)

  {

    tab[t] += (2 * state);

    t += 11;

  }

}

void  result_print(int *tab, int *res)

{

  int q;

  q = 0;

  while (q < 100)

  {

    if (tab[q] == 1)

      ft_putchar(q % 10 + '0');

    q++;

  }

  ft_putchar('\n');

  q = 0;

  while (q < 100)

  {

    if (tab[q] == 1)

      ft_putchar(9 - q % 10 + '0');

    q++;

  }

  ft_putchar('\n');

  (*res) += 2;

  return ;

}

void  solve(int *tab, int *res, int q, int ligne)

{

  int i;

  if (q == 10)

  {

    result_print(tab, res);

    return ;

  }

  i = ligne;

  while (i < ligne + 10)

  {

    if (tab[i] == 0)

    {

      tab[i] = 1;

      push_pull_queens(tab, i, ligne, 1);

      solve(tab, res, q + 1, ligne + 10);

      push_pull_queens(tab, i, ligne, -1);

      tab[i] = 0;

    }

    i++;

  }

  return ;

}

int ft_ten_queens_puzzle(void)

{

  int tab[100];

  int res;

  int i;

  i = 0;

  res = 0;

  while (i < 100)

  {

    if (i > 4 && i < 10)

      tab[i++] = 2;

    else

      tab[i++] = 0;

  }

  solve(tab, &res, 0, 0);

  return (res);

}

Bernard-maths · 26-02-2022 10:54:59

Bonjour !

J'imagine que les chiffres 0 à 9 désignent ... par ex 0257948136 : ligne 0, colonne 0 ; ligne 2, colonne 2 ; ligne 3, colonne 5 ; ligne 4, colonne 7 ; etc ... ?

Cela me rappelle une fois où on me demandait comment faire une grille de Sudoku ... Plutôt que de faire ça, qui est difficile, j'ai proposé de "tricher" en modifiant une grille donnée !

Par permutation, décalage, symétrie, rotation ... il est possible de fabriquer quelques millions de grilles, apparement différentes !

Peut-être peux-tu chercher dans ce genre de combine ...

Bernard-maths

Dernière modification par Bernard-maths (26-02-2022 10:56:37)

Saule · 26-02-2022 12:15:51

Bernard-maths a écrit :

J'imagine que les chiffres 0 à 9 désignent ... par ex 0257948136 : ligne 0, colonne 0 ; ligne 2, colonne 2 ; ligne 3, colonne 5 ; ligne 4, colonne 7 ; etc ... ?
Cela me rappelle une fois où on me demandait comment faire une grille de Sudoku ... Plutôt que de faire ça, qui est difficile, j'ai proposé de "tricher" en modifiant une grille donnée !
Par permutation, décalage, symétrie, rotation ... il est possible de fabriquer quelques millions de grilles, apparement différentes !
Peut-être peux-tu chercher dans ce genre de combine ...

Oui, le 0 c'est la ligne 1, c'est juste que je commence a compté a 0.
si on commence a compter a 1 pour 0257948136 ça fait : ligne 1, colonne 1 ; ligne 2, colonne 3 ; ligne 3, colonne 6 ; ligne 4, colonne 8 ;

C'est exactement ça je cherche a trouver toutes les possibilité avec le moins de possibilité possible par permutation/décalage/symétrie/rotation... ou tout t’autre idée.

Forum de mathématiques - Bibm@th.net

#1 26-02-2022 10:32:03

Le problème des n dames optimitation

#2 26-02-2022 10:36:41

Re : Le problème des n dames optimitation

#3 26-02-2022 10:54:59

Re : Le problème des n dames optimitation

#4 26-02-2022 12:15:51

Re : Le problème des n dames optimitation

Réponse rapide

Pied de page des forums