#include <stdio.h>

#define SZ  3

enum {VIDE, TOTO, TITI};
struct partie
{
    int grille[SZ][SZ];
    int victoires[2];
    int partiesNulles;
    int pions;
};



int testerLignes(struct partie *p)
{
    int i, j;
    for(i = 0; i < SZ; i++)
    {
        for(j = 1; p->grille[i][0] && j < SZ; j++)
            if(p->grille[i][j] != p->grille[i][0])
                break;
        if(j == SZ)
            return p->grille[i][0];
    }

    return 0;
}


int testerColonnes(struct partie *p)
{
    int i, j;
    for(i = 0; i < SZ; i++)
    {
        for(j = 1; p->grille[0][i] && j < SZ; j++)
            if(p->grille[j][i] != p->grille[0][i])
                break;
        if(j == SZ)
            return p->grille[0][i];
    }
    return 0;
}


int testerDiagonale1(struct partie *p)
{
    int i;
    for(i = 1; p->grille[0][0] && i < SZ; i++)
        if(p->grille[i][i] != p-> grille[0][0])
            return 0;
    return p->grille[0][0];
}


int testerDiagonale2(struct partie *p)
{
    int i;
    for(i = 1; p->grille[SZ - 1][0] && i < SZ; i++)
        if(p->grille[SZ - 1 - i][i] != p->grille[SZ - 1][0])
            return 0;
    return p->grille[SZ - 1][0];
}


int evaluer(struct partie *p)
{
    int i;
    int res;

    int(*f[])(struct partie *p) =
    {
        testerLignes,
        testerColonnes,
        testerDiagonale1,
        testerDiagonale2
    };

    for(i = 0; i < sizeof f / sizeof *f; i++)
    {
        res = f[i](p);
        if(res)
        {
            p->victoires[res - 1]++;
            return 1;
        }
    }

    if(p->pions == SZ * SZ)
        p->partiesNulles++;

    return 0;
}

void jouer(struct partie *p, int joueurCourant)
{
    int i, j;

    if(evaluer(p))
        return;

    for(i = 0; i < SZ; i++)
        for(j = 0; j < SZ; j++)
            if(p->grille[i][j] == 0)
            {
                p->grille[i][j] = joueurCourant;
                p->pions++;
                jouer(p, 1 - joueurCourant + 2);
                p->grille[i][j] = VIDE;
                p->pions--;
            }
}


int main(void)
{
    struct partie p = {0};

    jouer(&p, TOTO);

    printf("Toto    ->  %d\n", p.victoires[0]);
    printf("Titi    ->  %d\n", p.victoires[1]);
    printf("Nulles  ->  %d\n", p.partiesNulles);
    printf("Total   ->  %d\n", p.victoires[0] +
                                p.victoires[1] +
                                p.partiesNulles);

    return 0;
}

Toto    ->  131184
Titi    ->  77904
Nulles  ->  46080
Total   ->  255168

Process returned 0 (0x0)   execution time : 0.500 s
Press any key to continue.

import psyco
psyco.full()

class Joueur:
    def __init__(self):
        self.gain = 0
        self.nulle = 0

class Partie:
    voisins = {1: ((2, 3), (4, 7), (5, 9)), 2: ((1, 3), (5, 8)),
               3: ((2, 1), (5, 7), (6, 9)), 4: ((7, 1), (5, 6)),
               5: ((9, 1), (2, 8), (3, 7), (4, 6)), 6: ((3, 9), (5,
               4)), 7: ((4, 1), (5, 3), (8, 9)), 8: ((2, 5), (9, 7)),
               9: ((5, 1), (5, 8), (6, 3))}

    def __init__(self, *joueurs):
        self.joueur = joueurs[0]
        self.non_joueur = joueurs[1]
        self.plateau = dict.fromkeys(range(1, 10), None)
        self.libres = range(1, 10)

    def jouer(self, c):
        self.plateau[c] = self.joueur
        self.libres.remove(c)

    def retirer(self, c):
        self.plateau[c] = None
        self.libres.append(c)

    def gagner(self, c):
        for v in Partie.voisins[c]:
            if self.plateau[v[0]] == self.plateau[v[1]] == self.joueur:
                return 1
        return 0

def f(p):
    libres = p.libres[:]
    joueur = p.joueur
    non_joueur = p.non_joueur
    if libres:
        for c in libres:
            p.jouer(c)
            if p.gagner(c):
                joueur.gain += 1
            else:
                (p.joueur, p.non_joueur) = (p.non_joueur, p.joueur)
                f(p)
            p.joueur = joueur
            p.non_joueur = non_joueur
            p.retirer(c)
    else:
        p.joueur.nulle += 1
        p.non_joueur.nulle += 1

(j1, j2) = (Joueur(), Joueur())
p = Partie(j1, j2)

f(p)
z = (j1.gain, j2.gain, j1.nulle)
zz = '%-15s : %6s\n'
print (zz * 4)[:-1] % ('Titi gagne', z[0], 'Toto gagne', z[1],
                       'Parties nulles', z[2], 'Nombre parties', sum(z))

candide@~$ time python partiesMorpion.py 
Titi gagne      : 130644
Toto gagne      :  76584
Parties nulles  :  48960
Nombre parties  : 256188

real    0m5.339s
user    0m5.320s
sys     0m0.016s

candide@~$ time ./x
Toto    ->  131184
Titi    ->  77904
Nulles  ->  46080
Total   ->  255168

real    0m0.049s
user    0m0.048s
sys     0m0.000s
candide@~$

with Ada.Text_IO;
use Ada.Text_IO;

procedure Morpion is

   Nc : constant Integer := 3;

   type Joueur is (VIDE, TOTO, TITI);
   type Une_Grille is array (1..Nc,1..Nc) of Joueur;

   type Partie is record
     Grille : Une_Grille;
     Toto_Gagne, Titi_Gagne, Match_Nul : Integer;
   end record;

   function Test_Ligne(G : Une_Grille) return Joueur;
   function Test_Colone(G : Une_Grille) return Joueur;
   function Test_Diagonale(G : Une_Grille) return Joueur;
   function Match_Nul(G : Une_Grille) return Boolean;
   procedure Evaluer(P : in out Partie; Fin : out Boolean);
   procedure Jouer(P : in out Partie; J1 : Joueur);

   function Test_Ligne(G : Une_Grille) return Joueur is
   begin
      for N in G'Range(1) loop
         if G(N,1) /= VIDE and G(N,1) = G(N,2) and G(N,2) = G(N,3) then
            return G(N,1);
         end if;
      end loop;
      return VIDE;
   end Test_Ligne;

   function Test_Colone(G : Une_Grille) return Joueur is
   begin
      for N in G'Range(2) loop
         if G(1,N) /= VIDE and G(1,N) = G(2,N) and G(2,N) = G(3,N) then
            return G(1,N);
         end if;
      end loop;
      return VIDE;
   end Test_Colone;

   function Test_Diagonale(G : Une_Grille) return Joueur is
      C : Joueur := G(2,2);
   begin
      if C /= VIDE then
         if (C = G(1,1) and C = G(3,3)) or (C = G(1,3) and C = G(3,1)) then
           return C;
         end if;
      end if;
      return VIDE;
   end Test_Diagonale;

   function Match_Nul(G : Une_Grille) return Boolean is
   begin
      for I in G'Range(1) loop
         for J in G'Range(2) loop
            if G(I,J) = VIDE then
               return FALSE;
            end if;
         end loop;
      end loop;
      return TRUE;
   end Match_Nul;

   procedure Evaluer(P : in out Partie; Fin : out Boolean) is
      Gagnant : Joueur := VIDE;
   begin
      Gagnant := Test_Ligne(P.Grille);
      if (Gagnant = TOTO) then
         P.Toto_Gagne := P.Toto_Gagne + 1;
         Fin := TRUE;
         return ;
      elsif (Gagnant = TITI) then
         P.Titi_Gagne := P.Titi_Gagne + 1;
         Fin := TRUE;
         return ;
      end if;

      Gagnant := Test_Colone(P.Grille);
      if (Gagnant = TOTO) then
         P.Toto_Gagne := P.Toto_Gagne + 1;
         Fin := TRUE;
         return ;
      elsif (Gagnant = TITI) then
         P.Titi_Gagne := P.Titi_Gagne + 1;
         Fin := TRUE;
         return ;
      end if;

      Gagnant := Test_Diagonale(P.Grille);
      if (Gagnant = TOTO) then
         P.Toto_Gagne := P.Toto_Gagne + 1;
         Fin := TRUE;
         return ;
      elsif (Gagnant = TITI) then
         P.Titi_Gagne := P.Titi_Gagne + 1;
         Fin := TRUE;
         return ;
      end if;

      Fin := Match_Nul(P.Grille);

      if Fin then
         P.Match_Nul := P.Match_Nul + 1;
      end if;

   end Evaluer;

   procedure Jouer(P : in out Partie; J1 : Joueur) is
      Fin : Boolean;
      J2 : Joueur;
   begin
      Evaluer(P, Fin);

      if Fin then
         return ;
      end if;

      if J1 = TOTO then
         J2 := TITI;
      else
         J2 := TOTO;
      end if;

      for I in P.Grille'Range(1) loop
         for J in P.Grille'Range(2) loop
            if P.Grille(I,J) = VIDE then
               P.Grille(I,J) := J1;
               Jouer(P,J2);
               P.Grille(I,J) := VIDE;
            end if;
         end loop;
      end loop;
   end Jouer;

   P : Partie := ((others => (others => VIDE)),0,0,0);
begin
   Jouer(P, TOTO);
   Put_Line("Victoire de Toto : " & Integer'Image(P.Toto_Gagne));
   Put_Line("Victoire de Titi : " & Integer'Image(P.Titi_Gagne));
   Put_Line("Match nul : " & Integer'Image(P.Match_Nul));
   Put_Line("Total : " & Integer'Image(P.Toto_Gagne + P.Titi_Gagne + P.Match_Nul));
end Morpion;

candide@~$ time python partiesMorpion.py 
Titi gagne      : 130644
Toto gagne      :  76584
Parties nulles  :  48960
Nombre parties  : 256188
 
real    0m5.339s
user    0m5.320s
sys     0m0.016s

candide@~$ time ./x
Toto    ->  131184
Titi    ->  77904
Nulles  ->  46080
Total   ->  255168

real    0m0.049s
user    0m0.048s
sys     0m0.000s
candide@~$

class Joueur:
    def __init__(self):
        self.gain=0
        self.nulle=0

class Partie:
    voisins={
    1:((2,3), (4,7), (5,9)), 
    2:((1,3), (5,8)),
    3:((2,1), (5,7), (6,9)), 
    4:((7,1), (5,6)),
    5:((9,1), (2,8), (3,7), (4,6)),
    6:((3,9), (5,4)),
    7:((4,1), (5,3), (8,9)),
    8:((2,5), (9,7)),
    9:((5,1), (7,8), (6,3))
    }
    
    def __init__(self, *joueurs):
        self.joueur=joueurs[0]
        self.non_joueur=joueurs[1]
        self.plateau=dict.fromkeys(range(1,10), None)
        self.libres=range(1,10)

    def jouer(self, c):
        self.plateau[c]=self.joueur
        self.libres.remove(c)
    
    def retirer(self, c):
        self.plateau[c]=None
        self.libres.append(c)

    def gagner(self, c):
        for v in Partie.voisins[c]:
            if self.plateau[v[0]]==self.plateau[v[1]]==self.joueur:
                return 1
        return 0

def f(p):
    libres=p.libres[:]
    joueur=p.joueur
    non_joueur=p.non_joueur
    if libres:
        for c in libres:
            p.jouer(c)
            if p.gagner(c):
                joueur.gain+=1
            else:
                p.joueur, p.non_joueur= p.non_joueur, p.joueur
                f(p)
            p.joueur=joueur
            p.non_joueur=non_joueur
            p.retirer(c)
    else:
        p.joueur.nulle+=1
        p.non_joueur.nulle+=1
        
j1, j2= Joueur(), Joueur()
p=Partie(j1,j2)

f(p)
z=(j1.gain,j2.gain, j1.nulle)
zz="%-15s : %6s\n"
print (zz*4)[:-1] %("Toto gagne",z[0], "Titi gagne",z[1], "Parties nulles", z[2],"Nombre parties", sum(z))

candide@~$ python partiesMorpion.py 
Toto gagne      : 131184
Titi gagne      :  77904
Parties nulles  :  46080
Nombre parties  : 255168
candide@~$

#include <stdio.h>

#define N 3
#define VIDE 2

typedef
  struct {
  int t[N][N];
  int j;
  int gains[2];
  int nulles;
  int remplies;
} Partie;

int gagner(Partie * p)
{
  int (*t)[N] = p->t;
#define LIG(i) (t[i][0]!=VIDE && t[i][0]==t[i][1] && t[i][0]==t[i][2])
#define COL(j) (t[0][j]!=VIDE && t[0][j]==t[1][j] && t[0][j]==t[2][j])
  return LIG(0) || LIG(1) || LIG(2) || COL(0) || COL(1) || COL(2)
    || (t[0][0] != VIDE && t[0][0] == t[1][1] && t[0][0] == t[2][2])
    || (t[0][2] != VIDE && t[0][2] == t[1][1] && t[0][2] == t[2][0]);
}

void compter(Partie * p)
{
  int (*t)[N] = p->t, j = p->j;
  int lin, col;

  for (lin = 0; lin < N; lin++)
    for (col = 0; col < N; col++)
      if (t[lin][col] == VIDE)
        {
          t[lin][col] = p->j;
          p->remplies++;
          if (gagner(p))
            (p->gains)[j]++;
          else if (p->remplies < N * N)
            {
              p->j = 1 - p->j;
              compter(p);
              p->j = 1 - p->j;
            }
          else
            (p->nulles)++;
          p->remplies--;
          t[lin][col] = VIDE;
        }
}

int main(void)
{
  Partie p = { 0 };
  int i;
  int *z = &(p.t[0][0]);

  for (i = 0; i < N * N; i++)
    z[i] = VIDE;
  compter(&p);
  printf("%d\n", p.gains[0] + p.gains[1] + p.nulles);
  return 0;
}

255168

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N       3
#define MAX_P   9

typedef struct _partie {
  char tab[N][N];
  int toto, titi, nul;
  int nb_pions;
} partie;

enum JOUEURS {
  RIEN, TOTO, TITI
};

int verifie(char (*tab)[N]) {
  int i;
  
  for (i = 0; i < N; i++) {
    if (tab[i][0] != RIEN &&
        tab[i][0] == tab[i][1] && tab[i][1] == tab[i][2])
      return tab[i][0];
    if (tab[0][i] != RIEN &&
        tab[0][i] == tab[1][i] && tab[1][i] == tab[2][i])
      return tab[0][i];
  }
  if (tab[0][0] != RIEN &&
      tab[0][0] == tab[1][1] && tab[1][1] == tab[2][2])
    return tab[0][0];
  if (tab[2][0] != RIEN &&
      tab[2][0] == tab[1][1] && tab[1][1] == tab[0][2])
    return tab[2][0];
  return RIEN;
}

int jouerCoup(partie * p, int tour, int lig, int col) {
  if (p->tab[lig][col] != RIEN)
    return 0;
  p->tab[lig][col] = tour;
  p->nb_pions++;
  return 1;
}

void delCoup(partie * p, int lig, int col) {
  p->tab[lig][col] = RIEN;
  p->nb_pions--;
}

int evalue(partie * p, int ret) {
  int res = 1;
  
  if (p->nb_pions == MAX_P && ret == RIEN)
    p->nul++;
  else if (ret == TOTO)
    p->toto++;
  else if (ret == TITI)
    p->titi++;
  else
    res = 0;
  return res;
}

void jouerParties(partie * p, int tour) {
  int lig, col;
  
  if (p->nb_pions > 4) {
    int tmp = verifie(p->tab);
    if (evalue(p, tmp))
      return;
  }
  
  for (lig = 0; lig < N; lig++) {
    for (col = 0; col < N; col++) {
      if (!jouerCoup(p, tour, lig, col))
        continue;
      jouerParties(p, (tour == TOTO ? TITI : TOTO));
      delCoup(p, lig, col);
    }
  }
}

#define N_COUPS 3

void jouer3Coups(partie * p) {
  int coups[N_COUPS][2] = { { 0, 0 }, { 1, 0 }, { 1, 1 } };
  int mult[N_COUPS] = { 4, 4, 1 };
  partie p3;
  int i;
  
  for (i = 0; i < N_COUPS; i++) {
    memset(&p3, 0, sizeof p3);
    jouerCoup(&p3, TOTO, coups[i][0], coups[i][1]);
    jouerParties(&p3, TITI);
    p->toto += (p3.toto * mult[i]);
    p->titi += (p3.titi * mult[i]);
    p->nul += (p3.nul * mult[i]);
  }
}

int main(void) {
  int total;
  partie p;
  
  memset(&p, 0, sizeof p);
  /* jouerParties(&p, TOTO); */
  jouer3Coups(&p);
  total = p.toto + p.titi + p.nul;
  
  printf("Toto  : %d\n", p.toto);
  printf("Titi  : %d\n", p.titi);
  printf("Null  : %d\n", p.nul);
  printf("Total : %d\n", total);
  return EXIT_SUCCESS;
}

/*--------------- RECHERCHE DU NOMBRE TOTAL DE PARTIES DE MORPION RÉALISABLES ---------*/
/* 
   L'algorithme est un backtracking qui examine tous les coups possibles
   depuis le plateau vide. Autrement dit, au début, toto peut joueur en case 
   1, 2, 3, etc jusqu'à 9. Puis en fonction de ce qu'a joué toto, titi peut 
   joueur en case 2,3, etc et ainsi de suite.


   L'algorithme est implémentée par une fonction récursive appelée
   compter(). On appelle état du jeu, la connaissance -- de l'état du
   plateau (sans l'ordre de placement) -- du joueur j qui a le trait. Le
   principe de recherche du nb total de parties est le suivant : à partir
   d'un état donné E du jeu, l'ensemble de tous les états suivants
   possibles est obtenu en (a) considérant la totalité des états
   résultant d'un _seul_ coup du joueur j (b) considérant la totalité des
   suites de parties possibles à partir du coup joué par j.

   Cette recherche s'implémente en une boucle (on boucle sur les positions
   trouvées en (a)) et à chaque étape de la boucle, on comptabilise les
   scores de suite de la partie (ce qui appelle récursivement la fonction
   compter()). Mais pour que la partie ait une suite, il faut s'assurer dans
   la boucle que (1): j n'a pas gagné (2): j n'a pas joué la dernière
   case du jeu et si on est dans le cas (1) ou (2), il faut mettre à jour
   les scores et passer à la position suivante de jeu de j. Ceci explique
   l'implémentation de la fonction compter(). */

#include <stdio.h>

/* Le côté du carré */
#define N 3

/* case du plateau non occupée */
#define VIDE 2

/* Toutes les parties évoluent dans une même structure Partie */
typedef
  struct {
  /* Le plateau */
  int t[N][N];
  /* Le joueur qui a le trait (toto=0 ou titi=1) */
  int j;
  /* gain[j] est le nombre de parties gagnées par j */
  int gains[2];

  /* Le nombre de parties nulles */
  int nulles;

  /* Le nombre de cases occupées. Quand ce nombre vaut N*N, le plateau ext
     complètement rempli. */
  int remplies;
} Partie;

/* Retourne 1 si il y a un alignement de 3 jetons du même joueur, retourne 0 
   sinon Effectue la vérification dans chacune des 3 lignes, chacune des 3
   colonnes et chacune des 2 diagonales */
int gagner(Partie * p)
{
  int (*t)[N] = p->t;

#define LIG(i) (t[i][0]!=VIDE && t[i][0]==t[i][1] && t[i][0]==t[i][2])
#define COL(j) (t[0][j]!=VIDE && t[0][j]==t[1][j] && t[0][j]==t[2][j])
  return LIG(0) || LIG(1) || LIG(2) || COL(0) || COL(1) || COL(2)
    || (t[0][0] != VIDE && t[0][0] == t[1][1] && t[0][0] == t[2][2])
    || (t[0][2] != VIDE && t[0][2] == t[1][1] && t[0][2] == t[2][0]);
}


/* Fonction récursive qui compte le nombre de parties en fonction du score
   (gain de toto, gain de titi, partie nulle). */
void compter(Partie * p)
{
  /* t pointe vers la première ligne du plateau de la partie courante */
  int (*t)[N] = p->t, j = p->j;

  int lin, col;

  /* On scanne le plateau ligne par colonne à la recherche d'une case vide */
  /* Pour chaque case vide on procède de la même façon. */
  for (lin = 0; lin < N; lin++)
    for (col = 0; col < N; col++)

      /* On a trouvé une case vide */
      if (t[lin][col] == VIDE)
        {
          /* le joueur qui a le trait s'y place */
          t[lin][col] = p->j;
          /* Mise à jour du nb de cases occupées */
          p->remplies++;
          /* On regarde si le nouveau plateau est gagnant pour j */
          if (gagner(p))
            /* Si oui, on met à jour son total de gain */
            (p->gains)[j]++;
          /* si le coup de j n'est pas gagnant et il reste des cases libres
             sur le plateau */
          else if (p->remplies < N * N)
            {                   /* La partie continue : */
              /* On change de joueur */
              p->j = 1 - p->j;
              /* on calcule tous les scores de toutes les parties possibles
                 à partir de la nouvelle position */
              compter(p);
              /* On se prépare à recommencer le décompte pour les autres
                 cases où leur joueur initial pouvait jouer (donc on revient 
                 au joueur initial) */
              p->j = 1 - p->j;
            }
          /* Si le coup n'est pas gagnant et qu'il ne reste aucune case libre 
           */
          else
            /* La partie est nulle */
            (p->nulles)++;
          /* on retire du plateau le jeton joué par j */
          p->remplies--;
          t[lin][col] = VIDE;
        }
}

int main(void)
{
  Partie p = { 0 };
  int i;

  int *z = &(p.t[0][0]);

  /* Le plateau au départ est vide */
  for (i = 0; i < N * N; i++)
    z[i] = VIDE;
  /* On lance le décompte des parties. Le joueur 0 commence */
  compter(&p);
  /* On affiche le nombre total de parties jouables */
  printf("%d\n", p.gains[0] + p.gains[1] + p.nulles);
  return 0;
}

/* Calcul du nombre de parties possibles du morpion */
/* Le principe est de faire un backtraking sur seulement 3 positions.
   On joue la partie en (a), celle en (b) et celle en (e).
    (a) | (b) | (c)
    (d) | (e) | (f)
    (g) | (h) | (i)
 Si on 'tourne' le plateau, jouer en (c) revient à jouer en (a),
 jouer en (i) revient à jouer en (a) et jouer en (g) revient à jouer en (a).
 Ce qui fait qu'au lieu de jouer à 4 positions, on joue à une seule
 et on multiplie le résultat par 4 (qui correspond à (a), (c), (i) et (g)).
 Même chose pour (b), (f), (h), (d).
 Pour (e) il n'y a qu'une seule possibilité.*/
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N       3
#define MAX_P   9

/* Structure contenant l'état de la partie :
  - tab : tableau du jeu
  - toto, titi, nul : Nombres de parties gagnées ou nulles
  - nb_pions : Nombre de pions présents sur le plateau */
typedef struct _partie {
  char tab[N][N];
  int toto, titi, nul;
  int nb_pions;
} partie;

/* Constantes pour définir les cases du plateau */
enum JOUEURS {
  RIEN, TOTO, TITI
};

/* Fonction qui vérifie si quelqu'un a gagné et retourne celui qui
  a gagné ou le cas échéant RIEN pour dire qu'une partie est nulle. */
int verifie(char (*tab)[N]) {
  int i;
  
  for (i = 0; i < N; i++) {
    /* Teste les lignes */
    if (tab[i][0] != RIEN &&
        tab[i][0] == tab[i][1] && tab[i][1] == tab[i][2])
      return tab[i][0];
    /* Teste les colonnes */
    if (tab[0][i] != RIEN &&
        tab[0][i] == tab[1][i] && tab[1][i] == tab[2][i])
      return tab[0][i];
  }
  /* Diagonale */
  if (tab[0][0] != RIEN &&
      tab[0][0] == tab[1][1] && tab[1][1] == tab[2][2])
    return tab[0][0];
  /* Diagonale */
  if (tab[2][0] != RIEN &&
      tab[2][0] == tab[1][1] && tab[1][1] == tab[0][2])
    return tab[2][0];
  return RIEN;
}

/* Joue un coup.
 Retourne 0 si le coup ne peut pas être joué, 1 sinon. */
int jouerCoup(partie * p, int tour, int lig, int col) {
  if (p->tab[lig][col] != RIEN)
    return 0;
  p->tab[lig][col] = tour;
  p->nb_pions++;
  return 1;
}

/* 'Supprime' un coup. */
void delCoup(partie * p, int lig, int col) {
  p->tab[lig][col] = RIEN;
  p->nb_pions--;
}

/* Evalue la partie pour savoir qui a gagné (ou pas).
  - ret : retour de la fonction evalue qui dit qui a gagné.
  - res : Retourne 1 si la partie est gagnée ou nulle, 0 sinon.
 */
int evalue(partie * p, int ret) {
  int res = 1;
  
  /* Si on a joué tous les pions et que personne n'a gagné */
  if (p->nb_pions == MAX_P && ret == RIEN)
    p->nul++;
  else if (ret == TOTO)
    p->toto++;
  else if (ret == TITI)
    p->titi++;
  else
    res = 0;
  return res;
}

/* Fonction récursive qui joue tous les coups possibles. */
void jouerParties(partie * p, int tour) {
  int lig, col;
  
  /* Pour qu'il y ai une ligne il faut au moins 3 pions d'un joueur.
     Il faut donc qu'au moins 2 pions de chaque joueur soit posé. */
  if (p->nb_pions > 4) {
    /* Si la partie est gagnée ou nulle on termine la fonction */
    int tmp = verifie(p->tab);
    if (evalue(p, tmp))
      return;
  }
  
  /* On parcours toutes les cases */
  for (lig = 0; lig < N; lig++) {
    for (col = 0; col < N; col++) {
      /* Si le coup n'est pas jouable, on passe */
      if (!jouerCoup(p, tour, lig, col))
        continue;
      /* Appel récursif que le prochain joueur joue */
      jouerParties(p, (tour == TOTO ? TITI : TOTO));
      /* On 'supprime' le coup joué précédement */
      delCoup(p, lig, col);
    }
  }
}

#define N_COUPS 3

/* Fonction qui joue les 3 coups définis plus haut */
void jouer3Coups(partie * p) {
  /* Lise des coups à jouer */
  int coups[N_COUPS][2] = { { 0, 0 }, { 1, 0 }, { 1, 1 } };
  /* Liste des facteurs multiplicateurs à appliquer aux résultats */
  int mult[N_COUPS] = { 4, 4, 1 };
  /* Variable pour la partie en cours */
  partie p3;
  int i;
  
  for (i = 0; i < N_COUPS; i++) {
    memset(&p3, 0, sizeof p3);
    /* On joue le coup */
    jouerCoup(&p3, TOTO, coups[i][0], coups[i][1]);
    /* Et on fait un backtraking sur le reste */
    jouerParties(&p3, TITI);
    /* On ajoute les valeurs trouvées aux résultats */
    p->toto += (p3.toto * mult[i]);
    p->titi += (p3.titi * mult[i]);
    p->nul += (p3.nul * mult[i]);
  }
}

int main(void) {
  int total;
  partie p;
  
  memset(&p, 0, sizeof p);
  jouer3Coups(&p);
  total = p.toto + p.titi + p.nul;
  
  printf("Toto  : %d\n", p.toto);
  printf("Titi  : %d\n", p.titi);
  printf("Null  : %d\n", p.nul);
  printf("Total : %d\n", total);
  return EXIT_SUCCESS;
}

$ time ./candide 
255168

real        0m0.058s
user        0m0.047s
sys        0m0.002s
pouet$ time ./gurney 
Toto    ->  131184
Titi    ->  77904
Nulles  ->  46080
Total   ->  255168

real        0m0.084s
user        0m0.078s
sys        0m0.002s
pouet$ time ./pouet 
Toto  : 131184
Titi  : 77904
Null  : 46080
Total : 255168

real        0m0.030s
user        0m0.027s
sys        0m0.002s