Écrire une réponse @ Prise2Tete

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

	Forum » Enigmes Mathématiques » Echecs 8 Écrire une réponse Attention : Aucun indice ou demande d'aide concernant les énigmes de Prise2Tete n'est accepté sur le forum ! Rends-toi sur le cercle des sages si tu as besoin d'aide ! Tout nouveau message ou sujet ne respectant pas cette règle sera supprimé, merci. Rédige ton message Nom Courriel \| \| \| \| Upload \| Aide Message [quote=gasole]J'ai un truc raisonnable. Par raisonnable, s'entend : qui ne revient pas, de près ou de loin, à essayer toutes les possibilités via un test qui nécessite un temps de calcul exponentiel. J'ai un test quadratique. En s'autorisant des valeurs négatives, on va "pousser" les valeurs non nulles vers la droite d'abord (elles n'occuperont plus que 2 colonnes), puis vers le bas (il restera 2 lignes de 2 colonnes). "Pousser vers la droite" consiste à poser des pièces sur les deux cases de droite d'une case non nulle, de façon à ce que sa voisine lui soit égale... et recommencer jusqu'à atteindre le bord droit. Au total, on constate que ça revient à faire la somme des cases paires, et à soustraire cette somme à la somme de la première (la 1) et la dernière (la 7) case impaire. Ensuite, on fait pareil, mais verticalement. On se retrouve au pire avec un carré 2x2 de pièces, pour lequel il est facile de conclure. Ce n'est évidemment pas optimal en nombre de pièces posées... Exemple : 3,2,0,0 va devenir 0,0,1,0 (= on a posé 1 pièces en case 2 et 3 et ramassé 1 et 2) 0,1,0,1 va devenir 0,0,-1,1 (= on a posé -1 pièce en case 2 et 3) Formellement, l'échiquier est une matrice aij en l'occurrence 8x8. Pour chaque ligne i, on calcule b la matrice à 2 colonnes et 8 lignes telle que : bi1 = ai1 + a7i - (ai2+ai4+ai6) et bi2 = ai8 Pour chaque colonne j, on calcule c la matrice à 2 colonnes et 2 lignes telle que : c1j = bi1+bi7- (bi2+bi4+bi6) et c2j=b8j Il nous reste un carré c11, c12, c21, c22. On peut tout enlever si c12+c21 = c11 + c22. NB : la complexité de ce test est en O(n^2) --------------------------- Condition suffisante c'est sûr, mais nécessaire? En y réfléchissant, s'il y a une solution, ma méthode aboutira, mais pas simple à expliquer... C'est dû au fait que l'ordre dans lequel on pousse vers la droite ou vers le bas ne change rien à la conclusion. PS : on peut éviter les valeurs négatives si nécessaire en ajoutant suffisamment de pièces sur le jeu.[/quote] Options Ne pas convertir les émoticônes sur ce message Sécurité Répondez à la devinette suivante : Le père de toto a trois fils : Tim, Tam et ? Retour Résumé de la discussion Vasimolo 05-03-2011 00:47:10 Bonsoir à tous La série lancée par gasole dans le forum logique m'a donné envie de reprendre celle que j'avais commencée il y a quelques temps . Je rappelle qu'il n'est pas nécessaire de connaître les règles du jeu , ici l'échiquier sert uniquement de terrain pour se détendre . On place des piles de pièces de 1€ sur les cases d'un échiquier , chaque pile pouvant contenir 0 , 1 , 2 , ... pièces . On suppose en plus qu'on dispose d'une réserve suffisante de pièces de 1€ pour s'adonner au jeu suivant ... On peut poser ou enlever une pièce sur deux cases voisines ( partageant un même côté ) et ceci autant de fois que l'on veut dans l'espoir de vider l'échiquier . Un exemple avec initilement 10 pièces placées ( on a utilisé 4 pièces supplémentaires ) . Peut-on toujours vider l'échiquier et si non dans quels cas celà est-il possible et comment ??????? Merci d'avance pour la participation Vasimolo PS : C'est un problème personnel , la solution est donc assez simple Pied de page des forums P2T basé sur PunBB Screenshots par Robothumb © Copyright 2002–2005 Rickard Andersson
Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact