Résolution du Binero / Takuzu : les Joies du Backtracking

Coucou !

Les vacances approchent, et avec elles arrivent les livrets de jeux de vacances (youpi~).

Comme beaucoup de gens, mes parents achètent souvent des Sudoku à cette période de l'année... Mais aujourd'hui, ils sont revenus avec quelque chose de nouveau : des grilles de Binero (ou Binairo, ou Takuzu) !

Les règles du Binero / Takuzu

Le jeu se déroule sur une grille carrée avec un nombre pair de cases sur chaque ligne et chaque colonne.

Le but du jeu est de placer un 0 ou un 1 dans chaque case de telle sorte que chaque ligne et chaque colonne possède un nombre égal de 0 et de 1. Il est cependant nécessaire de respecter deux contraintes :

• Il ne peut pas y avoir plus de deux 0 ou deux 1 consécutifs
• Les lignes ou colonnes identiques sont interdites

Sur un petit exemple, la grille 4x4 suivante :

...se résout ainsi :

Les terrains classiques vont des tailles 4x4 à 14x14.

Sur des petites grilles le jeu est vraiment très simple. À un niveau plus avancé, la difficulté réside surtout dans le fait qu'il y ait parfois un choix arbitraire à effectuer sur une case pour arriver à la solution, ou à une contradiction qui permet d'en déduire que le choix effectué n'était pas le bon.

A mon humble avis, malgré son aspect épuré, le jeu possède un rapport de complexité / profondeur beaucoup moins intéressant que le Sudoku. Le Sudoku offre en effet une variété de techniques de résolution bien plus vaste que le Binaro, ce dernier m'a d'ailleurs lassé au bout de quelques grilles à peine.

En bref, j'ai trouvé plus intéressant de m'attaquer au problème avec un ordinateur qu'avec du papier et un crayon.

Résolution par Backtracking

Je décide de construire un algorithme en Python 3 capable de résoudre n'importe quelle grille de Binaro.

J'utiliserai une méthode de résolution par backtracking, ou "retour sur trace". Il s'agit d'une méthode d'essai-erreur où l'on fait des décisions arbitraires jusqu'à arriver à une impossibilité : on revient alors sur ces décisions passées pour sortir de l'impasse, et ce jusqu'à la résolution complète du puzzle.

Si vous n'avez jamais entendu parler de récursivité, les explications suivantes risquent de vous passer totalement au dessus de la tête...

Accrochez-vous !

Nous représenterons une grille de Binaro par un tableau à deux dimensions. Les "2" représentent les cases de valeur inconnue.

On s'intéresse par exemple à la grille 14x14 :

grille = [[2,2,2,2,2,1,1,2,2,2,1,2,2,0],
          [2,2,1,1,2,2,1,2,0,2,2,2,1,0],
          [2,2,2,1,2,2,2,2,2,0,2,2,1,2],
          [2,2,0,2,2,0,2,2,2,2,2,0,2,2],
          [2,2,2,2,2,2,2,2,2,2,2,2,2,2],
          [2,0,2,2,2,0,0,2,2,2,0,2,2,2],
          [2,2,2,2,2,0,0,2,2,2,2,2,2,0],
          [2,2,0,2,2,2,2,2,2,2,2,0,2,2],
          [2,2,0,0,2,2,2,2,0,2,2,2,2,2],
          [2,2,2,2,2,2,2,2,2,1,2,2,2,2],
          [2,2,2,2,2,2,2,2,2,2,2,2,1,2],
          [0,0,2,2,0,2,2,1,1,2,2,2,1,2],
          [0,2,2,1,2,2,0,2,1,2,2,0,2,2],
          [2,2,2,2,0,0,2,2,2,2,2,2,1,2]]

On va profiter des effets de bords de Python pour ne manipuler qu'un seul tableau tout le long des appels récursifs de la fonction principale.

def solve(grid,i = 0):
  dim = len(grid)
  if i == dim*dim:
    return True if checkIdenticalLines(grid) else False
  x = i % dim
  y = i//dim
  if grid[y][x] != 2:
    return solve(grid, i + 1)
  for j in range(2):
    row = grid[y]
    column = [row[x] for row in grid]
    if checkLine(row, x, j) and checkLine(column, y, j):
      grid[y][x] = j
      if solve(grid, i + 1):
        return True
  grid[y][x] = 2
  return False

Le paramètre i (en rouge) va correspondre au numéro de la case traitée, et les paramètres x et y à ses coordonnées (en vert et bleu) sur la grille :

par exemple dans le cas d'une grille 3x3, la case i = 1 est associée à x = 1 et y = 0

La fonction principale fait appel à deux fonctions annexes :

• checkIdenticalLines qui détermine si la grille finale possède des répétitions de lignes ou de colonnes.
• checkLine qui détermine si une ligne est juste ou non. Une ligne est correcte si :
• Son nombre de cases indéterminées est inférieur ou égal à la valeur absolue de la différence entre son nombre de 0 et son nombre de 1.
• On n'y trouve pas plus de deux 0 ou deux 1 consécutifs.

La fonction principale se décompose ainsi :

• On commence par l'appeler avec une valeur par défaut de i = 0.

• La variable dim prend la valeur de la dimension de la grille, par exemple si c'est une grille de 14x14, alors dim = 14.

• Si i = dim * dim, c'est qu'on a traité toutes les cases de la grille

• Dans ce cas si toutes les lignes et les colonnes sont différentes alors la grille est résolue, on renvoie True. Sinon la solution est fausse et on renvoie False. Cette propriété est déterminée grâce à checkIdenticalLines.

Dans tous les autres cas :

• On détermine les coordonnées x et y de la case i traitée.

• Si la case à laquelle on s'intéresse fait partie des données du problème (ie que sa valeur est différente de 2), alors on l'ignore et on s'intéresse à la case suivante en appelant la fonction récursivement avec une valeur de i incrémentée.

• Dans le cas contraire la case est indéterminée. On essaye alors de lui donner une valeur 0 puis 1. Si l'une des hypothèses n'entraîne pas de problème sur la ligne et la colonne de la case traitée (test effectué à l'aide de checkLine), alors on l'accepte et on s'intéresse à la case suivante par un appel récursif de la fonction avec une valeur de i incrémentée. Si celle-ci est correcte (ie que l'appel récursif de la fonction renvoie True) c'est que la solution a été trouvée en amont et on peut donc renvoyer True aussi.

• Si on arrive à un blocage, la case traitée est toujours indéterminée, et on renvoie False car nos hypothèses nous ont menées à une solution qui n'est pas la bonne.

Alors oui, la première fois qu'on lit ce genre d'algorithme, ça semble miraculeux que le machin fonctionne, et pourtant !

In [1]: solve(grille)
Out[1]: True

True est renvoyé, c'est donc que la solution a été trouvée !
Et grâce aux effets de bord, il suffit de rappeler la variable "grille" pour voir la solution !

In [2]: grille
Out[2]:
[[0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0],
 [0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0],
 [1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1],
 [1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1],
 [0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0],
 [1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1],
 [0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0],
 [1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1],
 [1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1],
 [0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0],
 [1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0],
 [0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1],
 [0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1],
 [1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0]]

Si vous n'avez pas tout suivi, prenez le temps de relire les explications et d'en chercher des complémentaires sur le backtracking... Cette méthode permet de résoudre de nombreux autres puzzles !

Je ne vais pas m'attarder sur les fonctions annexes évoquée plus haut, ce n'est pas le cœur de l'article. Sachez juste qu'elles ne possèdent pas d'effet de bord, elles.

Les voici :

def checkLine(line, k, value):
  zero, one, notFound = 0, 0, 0
  past = 2
  adj, m_adj = 1, 1
  line_c = line[::]
  line_c[k] = value
  for e in line_c:
    if e == 0:
      zero += 1
    elif e == 1:
      one += 1
    else:
      notFound += 1
    if past == e and past < 2:
      adj += 1
      if adj > m_adj:
        m_adj = adj
    else:
      adj = 1
    past = e
  return (abs(zero-one) <= notFound and m_adj < 3)

def checkIdenticalLines(g):
  return checkIdenticalColumns(grid) \
and checkIdenticalRows(grid)

def checkIdenticalRows(rows):
  i = 0
  l = len(rows)
  while i < l and rows[i] not in rows[:i]+rows[i+1:]:
    i += 1
  return i == l

def checkIdenticalColumns(grid):
  columns = \
[[row[x] for row in grid] for x in range(len(grid))]
  i = 0
  l = len(columns)
  while i < l and columns[i] not in columns[:i]+columns[i+1:]:
    i += 1
  return i == l

Notez bien que ces deux dernières fonctions sont sans doute optimisables, je ne garantie pas que le slicing soit adapté dans ce contexte.

Sur ce je vous dis à une prochaine fois !