La légende de Sissa, l'inventeur du jeu d'échecs, est une histoire légendaire qui remonte à l'Inde ancienne.

Selon le mythe, il y avait un roi indien du nom de Belkib (parfois appelé Buzurjmihr ou Bozorgmehr). Ce roi était confronté à une situation difficile et cherchait un moyen d'enseigner à son fils la sagesse, la stratégie et la prudence. C'est alors qu'un homme du nom de Sissa, réputé pour sa sagesse, fut présenté au roi.

Sissa proposa un jeu qu'il avait inventé. Il expliqua les règles et la structure du jeu au roi, soulignant comment chaque pièce avait des mouvements spécifiques et comment la victoire dépendait de la stratégie et de la planification. Le roi fut impressionné par le jeu et demanda à Sissa ce qu'il désirait en récompense. Sissa répondit qu'il voulait du grain pour nourrir sa famille. Cependant, il avait une demande particulière quant à la quantité de grain : il demanda au roi de placer un grain de blé sur la première case du plateau, deux grains sur la deuxième case, quatre grains sur la troisième case, et ainsi de suite, en doublant la quantité de grains à chaque case jusqu'à la soixante-quatrième case du plateau.

Le roi accepta rapidement cette demande, pensant que cela ne représenterait pas une grande quantité de grain. Cependant, il sous-estima rapidement la croissance d'une multiplication par deux récurrente. Le total de grains de blé nécessaire pour recouvrir l'ensemble des cases est astronomique, dépassant de loin la capacité de production mondiale actuelle.

Si on note $(u_n)$ la suite représentant le nombre de grains de chacune des cases de l'échiquier avec $u_n$ le nombre de grains sur la case numéro $n$ et $u_0=1$, on a :

$u_1 = 2$ ; $u_2=4$ ; $u_3=8$.

C'est-à-dire que $(u_n)$ est une suite géométrique de raison $2$ et donc on a une formule pour calculer la somme $S = u_0+u_1+\cdots+u_{63}$ :

$$S=u_0\times\dfrac{1-2^{64}}{1-2} = 2^{64}-1\approx1,844\times10^{19}.$$

En estimant que la masse moyenne d'un grain de riz est de $0,28$ grammes, la masse totale sur cet échiquier serait de $5,165\times10^{12}$ tonnes, alors que la production annuelle mondiale actuelle est de $527$ milions de tonnes.

Il est assez complexe de déterminer le nombre de parties possibles pour le jeu d'échecs. Il faut en effet compter tous les coups possibles mais qui ont du sens : deux pièces n'occupent pas la même case, déplacement interdit du roi car il se mettrait en échec etc.

De nombreux mathématiciens ont essayé de dénombrer l'ensemble des parties possibles, et c'est Claude Shannon -1916 - 2001), le père de la théorie de l'information, qui a laissé son nom pour ce problème.

Shannon a estimé qu'une partie est généralement constituée de 40 coups, un coup représentant un déplacement des blancs puis un déplacement des noirs, soit deux demi-coups. Il affirme ensuite qu'à chaque demi-coup, un joueur à en moyenne une trentaine de mouvements possibles. Il y aurait donc un nombre moyen de coup possibles de :

$$(30\times30)^{40}\approx1,478\times10^{118}.$$

Ce nombre, vu l'ensemble des approximations faites, a été arrondi à $10^{120}$.

Cependant ce nombre ne tient pas compte des positions légales ou non des pièces. Le nombre de parties légales est à l'heure actuelle estimé à $4,8\times10^{44}$ et il est beaucoup plus complexe à déterminer.

Le problème du cavalier d'Euler est le suivant :

On positionne un cavalier sur une case quelconque d'un échiquier. Existe-t-il un trajet lui permettant de parcourir toutes les cases et de revenir à sa position initiale sans jamais passer deux fois par une même case ?

Ce problème est ancien, remontant sans doute au premier millénaire et des solutions existent au moins depuis le XVIIe siècle. C'est à partir du XVIIIe que des mathématiciens s’attellent à une étude plus approfondie. Leonhard Euler (1707 - 1783) rédige un mémoire sur le sujet dans lequel il propose, comme à son habitude, plus qu'une simple solution mais une analyse structurelle suivant les points ci-dessous :

- obtention d'un trajet complet à partir d'un trajet partiel ;

- transformation d'un trajet ouvert en trajet fermé ;

- obtention d'un trajet symétrique à un trajet donné ;

- obtention de trajets sur des échiquiers de taille et de forme variable (carrée, rectangulaire, en croix ou rhombiques).

Dans le tableau ci-dessous, les numéros représentent les positions successives du cavalier. On peut remarquer que cette solution est quasiment un carré magique, c'est-à-dire que si on additionne les nombres composant une ligne quelconque, on obtiendra la même somme que pour une colonne, $260$ dans le cas présent. Dans un carré magique la somme des diagonales est également identique, ce qui n'est pas vérifié ici.

La résolution de ce problème fait partie, en théorie des graphes, d'une situation de graphe hamiltonien. De manière générale, la recherche d'un circuit hamiltonien est un problème NP-complet (c'est-à-dire a priori très long à calculer) mais dans le cas du cavalier d'Euler le temps de calcul est linéaire. Il a été de plus démontré que sur échiquier de $64$ cases il existe $26\, 534\, 728 \,821 \,064$ solutions de parcours fermés.

Le problème des huit dames est un problème de placement sur un échiquier, dans lequel l'objectif est de placer huit dames sur un plateau d'échecs de $64$ cases de manière à ce qu'aucune dame ne puisse attaquer une autre dame. En d'autres termes, aucune dame ne doit partager la même ligne, colonne ou diagonale avec une autre dame.

L'algorithme Python ci-dessous permet de donner la liste de l'ensemble des positionnements solutions du problème. nbSol = 0 def est_valide(chessboard, row, col): """ Vérifie si placer une dame à la position (row, col) sur l'échiquier est valide. """ # Vérifie la colonne for i in range(row): if chessboard[i] == col or \ chessboard[i] - i == col - row or \ chessboard[i] + i == col + row: return False return True def placer_dame(chessboard, row): """ Place une dame sur l'échiquier, une ligne à la fois, en utilisant la récursivité et le backtracking. """ size = len(chessboard) if row == size: # Toutes les dames sont placées avec succès afficher_solution(chessboard) return for col in range(size): if est_valide(chessboard, row, col): # Place la dame et continue avec la ligne suivante chessboard[row] = col placer_dame(chessboard, row + 1) # Backtrack : retirer la dame pour essayer une autre colonne chessboard[row] = -1 def afficher_solution(chessboard): """ Affiche une solution du problème des huit dames. """ global nbSol nbSol = nbSol + 1 print("----------------------------------") print("Solution n° "+str(nbSol)+"\n") for row in range(len(chessboard)): line = "" for col in range(len(chessboard)): if chessboard[row] == col: line += "D " else: line += ". " print(line) print("\n") def resolution_huit_dames(): """ Initialise et lance le processus de résolution du problème des huit dames. """ size = 8 # taille de l'échiquier chessboard = [-1] * size # initialise un tableau pour l'échiquier placer_dame(chessboard, 0) # Lancer la résolution du problème des huit dames resolution_huit_dames()