Schaakbord probleem

[sgoku01]

Je hebt een schaakbord van N*N aantal vakjes.
Op dat schaakbord moet je N aantal Koninginnen plaatsen zonder dat ze elkaar bedreigen (horizontaal, verticaal, diagonaal).

Dus op een schaakbord van 5*5 moet je 5 Koninginnen plaatsen.

Bestaat er een formule/manier om het aantal mogelijkheden uit te reken bij een bepaalde N?

[illch84]

1....
..2..
....3
.4...
...5.

Linksboven kan. Spiegeling zorgt ervoor dat de 2e ook kan in 2 richtingen. De middelste kan ook.

Geinig probleempje. Je kunt de sequentie willekeurig veranderen, alsmede de orientatie van de hele opzet.

4 richtingen.
5! sequenties.

Dus ik gok op 4 * 5! .. maar dat is een beetje gebaseerd op intuitie. De rest laat ik maar over aan de knappe hoofden op dit forum

[Just Johan]

N -> f

1 -> 1
2 -> 0
3 -> 0
4 -> 2
5 -> 10
6 -> 4
7 -> 40
8 -> 92
9 -> 352
10 -> 724
11 -> 2680
12 -> 14200
13 -> 73712

volgens m'n zelfgeschreven programmaatje; een mooi verband zie ik hier niet zo gauw, misschien later, misschien niet. (ik denk trouwens niet dat het simpel met faculteiten kan want 73712 heeft een priemfactor 271)

- edit - wat wel grappig is aan 73712 is: 73712 = 271*272 en 272 = 16 * 17

[Just Johan]

illch84 schreef:

1....
..2..
....3
.4...
...5.

Je kunt de sequentie willekeurig veranderen

nee, want wanneer je de 2e en 3e kolom omwisselt staan zowel de 1 en 2 als de 4 en 5 op een zelfde diagonale lijn.

[illch84]

Just Johan schreef:
nee, want wanneer je de 2e en 3e kolom omwisselt staan zowel de 1 en 2 als de 4 en 5 op een zelfde diagonale lijn.

Ik doelde meer op welke dame waar staat

Als je daar geen rekening mee zou houden, is het aantal mogelijkheden bij verre niet zo groot als jij denkt.

Op het moment dat je de opstelling draait, krijg je namelijk de andere samenstellingen voor ogen. Elke mogelijke oplossing staat in die ene opstelling, mits je er anders naar kijkt.

Of ken jij een andere?

[Just Johan]

illch84 schreef:
Ik doelde meer op welke dame waar staat

Als je daar geen rekening mee zou houden, is het aantal mogelijkheden bij verre niet zo groot als jij denkt.

Op het moment dat je de opstelling draait, krijg je namelijk de andere samenstellingen voor ogen. Elke mogelijke oplossing staat in die ene opstelling, mits je er anders naar kijkt.

Of ken jij een andere?

ja okay maar het is vrij triviaal dat als je de dames van elkaar gaat onderscheiden je n! keer zoveel mogelijkheden krijgt, dus die laten we maar weg lijkt me.

inclusief alle draaiingen en spiegelingen vond ik deze 10 oplossingen voor N=5:

type A:
*....
..*..
....*
.*...
...*.

....*
..*..
*....
...*.
.*...

...*.
.*...
....*
..*..
*....

.*...
...*.
*....
..*..
....*

type B:
*....
...*.
.*...
....*
..*..

....*
.*...
...*.
*....
..*..

..*..
*....
...*.
.*...
....*

..*..
....*
.*...
...*.
*....

type C:
.*...
....*
..*..
*....
...*.

...*.
*....
..*..
....*
.*...

[Just Johan]

illch84 schreef:
Als je daar geen rekening mee zou houden, is het aantal mogelijkheden bij verre niet zo groot als jij denkt.

nee?

[sgoku01]

Just Johan schreef:
volgens m'n zelfgeschreven programmaatje; [/B]

Mag ik dat programaatje eens zien?

[Just Johan]

sgoku01 schreef:
Mag ik dat programaatje eens zien?

jahoor. in checker.in moet het getal n staan; maak het niet te groot anders gaat het jaren duren de array die alle oplossingen bijhoudt staat nu ingesteld op net groot genoeg voor n=13; (degene waar ik dit voor schreef wilde de eerste paar oplossingen gesorteerd dus vandaar deze omweg)

/*

     by  Johan de Ruiter - jdrsoft@worldonline.nl
 
*/

#include <iostream.h>
#include <stdio.h>

int oplossing[75000][13];
int aantaloplossing=0;
int n;


//swaps two solutions in list
void wissel(int a, int b)
{
  int i, temp;
  for(i=0;i<n;i++)
  {
    temp=oplossing[a][i];
    oplossing[a][i]=oplossing[b][i];
    oplossing[b][i]=temp;
  }
}


//sorts only first three solutions
void sorteernieuwe()
{
  bool gevonden=false;
  bool zoeknog;
  int i=-1,j;
  while(!gevonden && i<3)
  {
    i++;
    zoeknog=true;
    for(j=0;j<n && zoeknog;j++)
    {
      if(oplossing[aantaloplossing-1][j]!=oplossing[i][j])
      {
        zoeknog=false;
        if(oplossing[aantaloplossing-1][j]<oplossing[i][j])
        {
          gevonden=true;
          wissel(aantaloplossing-1,i);
        }
      }
    }
  }
}


void plakvolgende(int huidig[13], int aantalhuidig)
{
  int i;
  bool mag=true;

  //controle
  for(i=0;i<aantalhuidig-1;i++)
  {
    if((huidig[i]==huidig[aantalhuidig-1])|| //horizontaal
       (aantalhuidig-1-i==huidig[aantalhuidig-1]-huidig[i]||
        aantalhuidig-1-i==huidig[i]-huidig[aantalhuidig-1]))
      mag=false;
  }
    
  if(mag)
  {
    if(aantalhuidig<n) //nog een erbij proberen
      for(huidig[aantalhuidig]=1;huidig[aantalhuidig]<=n;huidig[aantalhuidig]++)
        plakvolgende(huidig,aantalhuidig+1);
    else  //toevoegen
    {
      for(i=0;i<n;i++)
        oplossing[aantaloplossing][i]=huidig[i];
      aantaloplossing++;
      sorteernieuwe();

      if(huidig[0]<=n/2)
      {
        for(i=0;i<n;i++)
          oplossing[aantaloplossing][i]=n+1-huidig[i];
        aantaloplossing++;
        sorteernieuwe();
      }
    }
  }
}


int main()
{
  FILE *invoer;
  FILE *uitvoer;

  invoer = fopen("checker.in", "r");
  uitvoer = fopen("checker.out", "w");
   
  fscanf(invoer, "%d", &n);

  int huidig[13];
  int aantalhuidig=0;
  
  int c;
  for(c=1;c<=n/2;c++)
  {
    huidig[0]=c;
    plakvolgende(huidig,1);
  }
  if(n%2==1)
  {
    huidig[0]=n/2+1;
    plakvolgende(huidig,1);
  }
  
  int a,b;
  for(a=0;a<3;a++)
  {
    for(b=0;b<n;b++)
    {
      fprintf(uitvoer, "%d", oplossing[a][b]);
      if(b<n-1)
        fprintf(uitvoer, " ");
    }
    fprintf(uitvoer, "\n");
  }
    

  fprintf(uitvoer, "%d\n", aantaloplossing);
 
  fclose(invoer);
  fclose(uitvoer);

  return 0;
}

[Just Johan]

oh btw, de uitvoer bestaat uit reeksen getallen die de alleen x-positie aangeven van de volgende koningin die vanzelfsprekend op de volgende y-coordinaat staat (of omgekeerd als je wilt)