Open Source Your Knowledge, Become a Contributor

Technology knowledge has to be shared and made accessible for free. Join the movement.

Create Content

Inversion en croix

Difficulté : Extrême (100%) Origine : Projet Euler n°331

NxN disques sont placés sur un grille carrée. Chaque disque a une face blanche et une face noire.

A chaque tour, on peut choisir un disque et tourner alors tous les disques de la même ligne et colonne : Il y a donc 2N-1 disques retournés. Le jeu fini quand tous les disques montrent la face blanche. Voici un exemple de jeu sur une grille 5x5.

Jeu

On peut prouver que 3 est le nombre minimum de tours pour finir le jeu.

Le disque en bas à gauche de la grille a pour coordonnées (0,0), celui en bas à droite (N-1,0) et en haut à gauche (0,N-1).

On pose Cn la configuration de la grille avec NxN disques suivante : Un disque de coordonnées (x,y) vérifiant (N1)2x2+y2N2 montre sa face noire. Sinon, il montre sa face blanche. C5 est l'exemple ci-dessus.

On pose T(N) le nombre minimal de tours pour finir le jeu qui commence à la configuration CN ou 0 si la configuration CN n'a pas de solution. On a T(5)=3. On peut montrer que T(10)=29 et T(1 000)=395253.

Trouver i=331T(2ii)

On affichera le résultat avec print.

Remarque : Si vous trouvez une solution qui met moins de 50 sec pour s'exécuter, je suis très intéressé !

Inversion en croix
1
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Open Source Your Knowledge: become a Contributor and help others learn. Create New Content