Répondre à la discussion
Affichage des résultats 1 à 11 sur 11

Othello



  1. #1
    RomVi

    Othello


    ------

    Bonjour

    Voici une petite énigme que j'ai imaginé cet après midi. Par avance je m'excuse si elle est déjà connue sous une autre forme ; je n'ai pas la prétention d'être le 1er à avoir pensé à ce genre de problème...

    On a 9 jetons du jeu Othello sur un jeu en 3x3 placés comme sur mon dessin en pièce jointe, les règles de base du jeu ne sont pas prises en compte. Le but est de tous les placer sur la face blanche, mais chaque fois que l'on retourne un jeton tous les jetons contigus (par un coté ou un coin) sont également retournés.

    Existe il une possibilité de tous les placer du coté blanc ?
    Questions subsidiaires :
    - Si oui, en combien de coups minimum
    - Existe il une combinaison de départ ne permettant pas d'obtenir le résultat voulu.

    A vous de jouer

    -----
    Images attachées Images attachées

  2. Publicité
  3. #2
    mohamed02

    Re : Othello

    J'arrive seulement à avoir 3 jetons noirs ! C'est difficile de gagner !

  4. #3
    RomVi

    Re : Othello

    Merci pour ta participation mohamed02

    Tu dois pouvoir arriver à faire mieux que ça, essayes d'alterner un coté et l'autre.

  5. #4
    lafurlane

    Re : Othello

    Bonjour,
    je suis arrivée en 5 mouvements, un peu par hasard, peut on faire mieux?

  6. A voir en vidéo sur Futura
  7. #5
    Resartus

    Re : Othello

    Bonjour,
    Je ne vais pas spoiler ton jeu, mais juste signaler qu'il s'agit d'un puzzle de la catégorie des "lights out puzzles", où on dispose de lampes allumées ou eteintes, et d'interrupteurs qui permutent l'état de plusieurs lampes à la fois. Il faut finir avec "tout éteint".

    La résolution mathématique est intéressante (mais d'assez haut niveau), et utilise des calculs avec des matrices mais sur un corps fini : le corps Z/ZZ.
    Les interrupteurs sont des transformations linéaires de l'espace vectoriel des n lampes, et selon la dimension de l'espace engendré par ces transformations, soit on peut eteindre toute configuration, soit il y a des configurations qu'on ne peut pas eteindre.... Il y a alors des familles distinctes de configurations, et on peut passer d'une configuration à toute autre de la même famille, mais pas changer de famille. Pour résoudre, il faut être au départ dans la même famille que "tout éteint".

    Pour ceux que cela interesse :http://mathworld.wolfram.com/LightsOutPuzzle.html
    Dernière modification par Resartus ; 21/11/2016 à 11h34.
    Why, sometimes I've believed as many as six impossible things before breakfast

  8. #6
    RomVi

    Re : Othello

    En effet le principe est assez proche, je ne connaissais pas ces "lights out puzzles", la seule différence étant que les règles semblent légèrement différentes (retournement des jetons contigus par une arête).
    Pour mon problème il existe une méthode de résolution "mathématique" simple, niveau 1ere ou terminale technique.

  9. Publicité
  10. #7
    CM63

    Re : Othello

    Bonjour,

    Ma méthode est de rechercher des règles d'invariance, ou au contraire de retournement du genre:
    - si on retourne les 4 pions des coins, cela laisse invariant tous les autres.

  11. #8
    Deedee81
    Modérateur

    Re : Othello

    Salut,

    Citation Envoyé par CM63 Voir le message
    Ma méthode est de rechercher des règles d'invariance, ou au contraire de retournement du genre:
    - si on retourne les 4 pions des coins, cela laisse invariant tous les autres.
    C'est ainsi que je l'envisageais (pour simplifier la recherche). Je n'ai malheureusement pas eut le temps de me pencher dessus.
    Exemple : chaque retournement retourne le jeton central, il faut donc un nombre total de retournement impair.
    Keep it simple stupid

  12. #9
    Médiat

    Re : Othello

    Bonjour,

    Une méthode un peu bourrin consiste à écrire des équations dans , par exemple(en numérotant les cases de 1 à 9 en partant du haut à gauche) en notant le retournement de la case , on obtient
    La case 1 ne doit pas changer
    La case 2 ne doit pas changer
    d'où on tire :


    etc.

    Et du coup je peux affirmer que 5 est le minimum

     Cliquez pour afficher
    Dernière modification par Médiat ; 22/11/2016 à 08h33.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  13. #10
    Médiat

    Re : Othello

    Question subsidiaire :
    Trouver les configurations de départ telles que la solution soit de jouer une et une seule fois tous les jetons noirs et exclusivement ceux ci (il y en a plusieurs)
    Trouver les configurations de départ telles que la solution soit de jouer une et une seule fois tous les jetons blancs et exclusivement ceux ci (je n'en ai pas trouvé jusqu'à présent)
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  14. #11
    _Goel_

    Re : Othello

    Bonsoir,

    Je regarde les types de mouvements possibles : ils sont au nombre de 3 :
    - On retourne un carré de 4 jetons (en retournant le jeton du coin)
    - On retourne un rectangle de 6 jetons (en retournant un jeton entre 2 coins)
    - On retourne tous les jetons (en retournant le jeton du centre)

    A l'inverse :
    - le jeton d'un coin est influencé que par lui-même et les 4 jetons environnants soit 4 jetons
    - le jeton entre 2 coins est influencé par 6 jetons
    - le jeton du milieu est influencé par tous les autres jetons

    on a 2^9 = 512 combinaisons possible
    Retourner 2 fois le même jeton est inutile (même si c'est pas d'affilée). Donc on a un max de 9 retournements de jetons (+jetons adjacents) à effectuer pour atteindre n'importe quelle position finale
    soit 2^9 = 512 positions finales max atteignables avec une position de départ donnée.

    Par effet de symétrie, on ne peut étudier que 8 positions finales à partir d'une position initiale :
    - ex : position initiale = tout blanc
    - positions à étudier = un L de 3 cases, dont une est le centre, avec toutes les combinaisons possible (3 cases = 8 positions) toutes les autres cases ayant leur jeton qui bouge pas.

    Donc déjà on a un maximum théorique de 8 familles de configurations indépendante (être dans une famille nous permet pas d'aller dans une configuration de l'autre famille)

    On peut identifier une combinaison ainsi : C1=R1+R2+R5 (Statut de la case 1 si retournement retourner les jetons des cases 1, 2 et 5)
    On peut définir le statut final d'un jeton en fonction de la combinaison de retournement : ex : la case 1 (coin supérieur gauche) = f(R1, R2, R4, R5) (Retourner les autres jetons n'influe pas sur la case 1)

    Pour cela on peut définir un système d'équation :

    Ri & Ci appartiennent à {0,1}

    C1 = (-1)^(R1+R2+R4+R5)
    C2 = (-1)^(R1+R2+R3+R4+R5+R6)
    ...
    C5 = (-1)^(R1+R2+R3+R4+R5+R6+R7+R8+R9 )
    ...
    C9 = (-1)^(R5+R6+R8+R9)


    Si on revient à notre L d'étude (disons C1, C2, C5) on a donc à étudier (et résoudre) les 8 systèmes de 9 équations avec C1, C2, C5 = {0,1} et les Ci restants = 0

    On peut transformer le système d'équation de :
    C1 = (-1)^(R1+R2+R4+R5)
    en
    R1+R2+R4+R5 = 2.n1+s1
    "ni" est, pour une case i, un entier quelconque compris entre 0 et 2 pour un coin, 0 et 3 pour une case entre 2 coins, et 0 et 4 pour la case centrale
    "si" est, pour une case i, le statut s de la case i (1 pour retourné donc noir, 0 pour blanc)

    Exemple pour un L avec toutes les cases retournées (noires) :
    R1+R2+R4+R5 = 2.n1 +1
    R1+R2+R3+R4+R5+R6 = 2.n2 +1
    R2+R3+R5+R6 = 2.n3
    R1+R2+R4+R5+R7+R8 = 2.n4
    R1+R2+R3+R4+R5+R6+R7+R8+R9 = 2.n5 +1
    R2+R3+R5+R6+R8+R9 = 2.n6
    R4+R5+R7+R8 = 2.n7
    R4+R5+R6+R7+R8+R9 = 2.n8
    R5+R6+R8+R9 = 2.n9

    Bref...
    Merci excel...
    Toutes les combinaisons de L sont atteignables à partir d'une position donnée, donc ça fait 1 famille.
    Donc on a 512 positions différentes, 512 positions atteignables, 512 combinaisons de retournement. donc chaque combinaison de retournement conduit à un une position différente. Ce qui limite à 9 le nombre de retournement maximal (auquel cas tous les jetons sont conservés sauf celui du milieu)

    Solution au pb : Retourner les jetons 1, 3, 5, 6 et 7.
    Le succès c'est d'être capable d'aller d'échec en échec sans perdre son enthousiasme

Discussions similaires

  1. Othello en C
    Par pyine dans le forum Programmation et langages, Algorithmique
    Réponses: 1
    Dernier message: 02/03/2015, 17h44
  2. Jeu othello en C
    Par aymannblal dans le forum Programmation et langages, Algorithmique
    Réponses: 4
    Dernier message: 26/01/2014, 20h28
  3. [Enigme] Othello rencontre la logique
    Par GradJ dans le forum Science ludique : la science en s'amusant
    Réponses: 4
    Dernier message: 26/05/2013, 16h11
  4. Problème C, mini-projet/othello
    Par yasyes_2000 dans le forum Logiciel - Software - Open Source
    Réponses: 2
    Dernier message: 20/04/2006, 00h14