Tout sauf carré de carrés magiques à Sudoku
Qu'est-ce qu'un carré magique?
Nymphe de la rivière Lo. un dessin d'encre sur une handscroll, dynastie Ming, 16ème siècle. Freer Gallery of Art
Le carré magique Lo Shu
propriétés mathématiques
Lorsque les mathématiciens parlent de carrés magiques, ils parlent souvent de l'ordre de la place. Ceci est juste le nombre de lignes ou colonnes que le carré magique a. Par exemple, un 3 par 3 carré magique a trois lignes et trois colonnes, de sorte que son ordre est 3.
Dans un carré magique typique, vous commencez avec 1 puis passez par l'ensemble des numéros un par un. Par exemple, un carré magique d'ordre 3 contient tous les nombres de 1 à 9, et un carré d'ordre 4 contient les numéros 1 à 16. Sans surprise, les carrés magiques faites de cette manière sont appelés carrés magiques normaux.
Dans le Lo Shu carré magique, qui est un carré magique normale, toutes les lignes, toutes les colonnes et les deux diagonales ajoutent au même numéro, 15. Nous appelons ce nombre la constante magique. et il y a une formule simple, vous pouvez utiliser pour travailler la constante magique pour tout carré magique normale. Pour un carré magique d'ordre n. la constante est magique
Il se trouve que les carrés magiques normaux existent pour toutes les commandes, sauf ordre 2. Il n'y a qu'un carré magique d'ordre 1 et il est pas particulièrement intéressante: un carré unique avec le numéro 1 à l'intérieur! Vous pouvez travailler pour vous-même pourquoi la place de l'ordre 2 n'existe pas. Mathématiciens considèrent normalement deux carrés magiques comme étant le même si vous pouvez obtenir un de l'autre par rotation ou réflexion. Compté de cette façon, il n'y a qu'un seul carré magique d'ordre 3, qui est le carré magique Lo Shu ci-dessus. Il y a 880 places magiques distinctes d'ordre 4 et 275305224 de l'ordre 5. Personne ne sait combien de carrés magiques distincts existent 6 de l'ordre, mais il est estimé à plus d'un million de millions de millions!
De La Loubère et la méthode siamois
Vous pouvez maintenant se demander s'il existe un moyen facile de faire un carré magique sans avoir recours à des conjectures. Heureusement, il y a. De La Loubère était l'ambassadeur français au Siam (aujourd'hui la Thaïlande) à la fin du XVIIe siècle. A son retour en France, il a apporté avec lui une méthode pour construire des carrés magiques avec un nombre impair de lignes et de colonnes, autrement connu sous forme de carrés d'ordre impair.
Lorsque toutes les cellules sont remplies, les deux diagonales principales et chaque ligne et colonne doivent totaliser le même nombre, comme par magie!
Bien que cela, la méthode dite siamoise. est probablement la méthode la plus connue pour faire des carrés magiques, d'autres méthodes existent. Le maître d'école allemand Johann Faulhaber a publié une méthode similaire à la méthode siamoise avant qu'il ne soit découvert par De Le Loubère. Une autre façon est la méthode Pastille par John Horton Conway. un mathématicien britannique prolifique. Prouver que ces travaux de méthodes peut être fait en utilisant l'algèbre, mais il est pas facile!
Les carrés magiques de même ordre
Bien que la méthode siamois peut être utilisé pour générer un carré magique pour tout nombre impair, il n'y a pas de méthode simple qui fonctionne pour tous les carrés magiques de même ordre. Heureusement, il y a une belle méthode que nous pouvons utiliser si l'ordre de la place est un nombre pair divisible par 4. (Pour ceux qui sont intéressés, la méthode LUX a été inventé par JH Conway pour faire face à des nombres pairs qui ne sont pas divisibles par 4).
Au lieu de dire « nombres divisibles par 4 », les mathématiciens disent généralement « nombres de la forme 4k ». Par exemple, 12 est de la forme 4k. parce que vous pouvez remplacer k avec 3. En utilisant la même idée, les chiffres qui donnent un reste de 2 lorsque vous les diviser par 4 peuvent être appelés nombres de la forme 4k + 2.
Si vous feuilletez ce carré magique sur, il est identique à celui qui est dessiné par le célèbre artiste allemand, Albrecht Dürer. Vous pouvez le voir dans le coin de sa gravure Mélancolie.
1514 Gravure Mélancolie de Dürer.
Le carré magique apparaissant dans Mélancolie montré en gros plan.
Voici un exemple de 8 par 8 carré magique construit en utilisant la même méthode. Le carré a été divisé en quatre carrés de 4 par 4, et les diagonales ont été colorées. Les chiffres de couleur qui ajoutent jusqu'à 65 ans ont été passés: 1 a été échangé avec 64, 4 a été échangé avec 61, et ainsi de suite.
Conte de Chevalier
Comme tout joueur d'échecs saura, un ordre 8 carré magique a le même nombre de cellules en tant que jeu d'échecs. Cette similitude signifie que nous pouvons créer un type spécial de carré magique basée sur les mouvements d'un ChessPiece.
Le chevalier est une pièce intéressante, car à la différence des autres pièces, il ne se déplace pas verticalement, horizontalement ou en diagonale le long d'une ligne droite. Au lieu de cela, le cavalier se déplace dans une forme de L, comme indiqué sur le schéma. Mais est-il possible pour un chevalier qui se déplace dans cette façon de visiter toutes les places sur l'échiquier exactement une fois?
L'un des premiers mathématiciens à enquêter sur la tournée du chevalier, le problème est devenu connu, était le grand mathématicien suisse Leonhard Euler. Son travail a inspiré les autres à relever le défi.
En utilisant le concept de la tournée du chevalier William Beverley a réussi à produire un carré magique, comme indiqué ci-dessous. Les cellules sont numérotées en séquence, comme le chevalier les visite. Bien que les lignes et les colonnes tous les ajouter jusqu'à 260, les grandes diagonales ne sont pas, à proprement parler, donc il est un carré semi-magique. En fait, un carré magique basée sur la tournée d'un chevalier est souvent appelé un tour de magie, de sorte que Beverley produit en 1848 est une visite semi-magique!
À première vue, il semble que le carré magique suivant par Feisthamel correspond à la facture. Les lignes, colonnes et diagonales tout somme 260. Malheureusement, il est seulement la tournée d'un chevalier partiel, car il y a un saut 32-33.
Latin Squares
carrés latins sont les véritables ancêtres de Sudoku. Vous trouverez des exemples de carrés latins dans la littérature arabe plus de 700 ans. Ils ont été découverts par Euler quelques siècles plus tard, qui les considérait comme un nouveau type de carré magique, et il est grâce à lui que nous les appelons carrés latins.
carrés latins sont des grilles remplies de chiffres, de lettres ou de symboles, de telle sorte qu'aucun numéro apparaît deux fois dans la même ligne ou colonne. La différence entre le nombre de symboles utilisés un carré magique et un carré latin. Par exemple, il y a 16 numéros différents dans un 4 par 4 carré magique, mais vous avez seulement besoin de 4 numéros différents ou des lettres pour faire un 4 par 4 carré latin.
Voici un exemple d'un carré latin, avec les numéros 1 à 4 dans chaque ligne et colonne. Si vous regardez la première ligne et la première colonne, vous remarquerez que les numéros se produisent dans l'ordre: 1, 2, 3, 4. Lorsque cela se produit, nous disons que le carré latin est sous forme standard ou normalisée. Tout carré latin peut être transformé en forme standard en échangeant des paires de lignes et paires de colonnes.
Il n'y a qu'un seul carré latin normalisé d'ordre 3, et il n'y a que 4 des organes distincts de l'ordre 4, mais une 377.597.570.964.258.816 stupéfiante de l'ordre 9. En 1979, JR Nechvatal a élaboré une formule complexe donnant le nombre de carrés latins normalisés distincts de tout ordre . A ce jour, personne n'a pu tirer de cela, ou toute autre formule, à quelle vitesse ce nombre croît que l'ordre de la place devient grand.
Si nous combinons les deux carrés latins ci-dessous, nous obtenons une nouvelle place avec des paires de lettres et de chiffres. Aucune paire est répété, mais la grille contient toutes les combinaisons unique. Nous appelons cette nouvelle place une place Euler ou un carré gréco-latin. et les deux carrés qui formaient le carré d'Euler sont appelés mutuellement orthogonaux.
Trente-six officiers Problème
Euler a fait un travail considérable sur les carrés latins, et même venu avec quelques méthodes pour les construire. Euler facile à trouver des méthodes pour construire des carrés impairs d'ordre gréco-latins et les places pour lesquels l'ordre est un multiple de 4, mais il ne pouvait pas produire un carré gréco-latine de l'ordre 6.
Il a même posé un fameux problème qui ne pouvait être résolu en faisant un carré gréco-latine de l'ordre 6. Le problème des 36 officiers va comme ceci: est-il possible d'organiser six régiments, chacun composé de six officiers de différents grades, en de telle sorte qu'aucune ligne ou une colonne contient deux agents ou plus du même régiment ou avec le même rang?
Euler n'a jamais résolu ce problème. En fait, il croyait qu'il était impossible de faire un carré gréco-latine, si l'ordre est de la forme 4k + 2.
Un peu plus de cent ans auparavant, la prédiction d'Euler a été partiellement donné raison. Un mathématicien français appelé Gaston Tarry vérifié toutes les combinaisons possibles pour un 6 par 6 Euler carré et a montré que n'existait pas.
Enfin, en 1960, Bose, Shrikhande et Parker ont réussi à prouver que les places d'Euler existent pour toutes les commandes, sauf 2 et 6. Mais compte tenu du fait qu'ils avaient des ordinateurs à leur disposition, une pensée pour Tarry qui devait tout faire à la main!
Si vous prenez un train à Londres, vous verrez beaucoup de navetteurs avec un stylo à la main, un journal sur leurs genoux et une chose sur leur esprit - Sudoku.
Sudoku ou Su Doku sont un type spécial de carrés latins. Ils sont généralement 9 de 9 grilles, divisé en 9 petits 3 par 3 cases. Le but du jeu consiste à remplir chaque cellule avec l'un des nombres de 1 à 9, de sorte que chaque numéro apparaît exactement une fois dans chaque rangée, colonne et 3 par 3 boîte. Pour vous aider à compléter le casse-tête, quelques chiffres sont déjà donnés à titre d'indices.
Il est difficile de dire combien de grilles de Sudoku distincts a terminé il y a, mais les mathématiciens Bertram Felgenhauer et Frazer Jarvis a utilisé une recherche informatique exhaustive de trouver le nombre 6.670.903.752.021.072.936.960, qui a été confirmé plus tard par Ed Russell.
La résolution Sudoku nécessite une réflexion logique et une approche systématique. Normalement, suffisamment nombreux chiffres sont donnés à titre d'indices dans la grille initiale - celle que vous démarrez le puzzle avec - pour assurer qu'il n'y a qu'une seule solution. Les autres numéros sont remplis d'abord, plus le casse-tête devient bien sûr. Donc, de vrais accros Sudoku préfèrent probablement un petit nombre d'indices initiaux. Mais quel est le nombre minimal d'indices qui doivent être donnés pour garantir qu'il ya exactement un - et plus - solution? Ceci est une bonne question, et qui mathématiciens jusqu'à présent ont été incapables de répondre, bien qu'il y ait de bonnes raisons de croire que le nombre est de 17.
Et si nous nous tournons cette question autour? Compte tenu d'une grille complétée individuel, le nombre de grilles initial minimum sont là qui ont cette grille comme une solution? nous entendons ici les grilles de départ à partir de laquelle plus numéro peut être enlevé sans faire plusieurs solutions possibles. Encore une fois, les mathématiciens ne savent pas la réponse à cette question.
Mais nous allons jeter un regard sur la façon de s'y prendre pour résoudre un casse-tête Sudoku. Voici ce que je crée pour illustrer l'une des techniques de base, connu sous le nom de balayage.
En regardant les trois boîtes intermédiaires, nous avons un 3 dans la boîte à la main gauche et une dans la zone du milieu, mais nous avons encore besoin de mettre un 3 dans la boîte à la main droite. Alors, où faut-il aller? Eh bien, il ne peut pas aller dans la rangée du haut, car il y a déjà un 3 dans cette ligne. Pour la même raison, il ne peut pas aller dans la rangée du bas, ce qui laisse la ligne médiane. Il n'y a qu'une seule cellule libre dans la rangée du milieu, de sorte que le 3 doit aller en elle.
Les trois boîtes intermédiaires
Maintenant, si nous regardons les trois boîtes en bas, une des lignes a déjà 6 numéros. Je l'ai appelé les cellules vides A, B et C (dans l'ordre de gauche à droite), et les chiffres qui manquent sont 3, 7 et 8. Si vous regardez cellule C, le seul numéro qui peut aller est 7. en effet, la colonne C se trouve dans contient déjà 3 et 8.
Trouver A et B est maintenant assez simple. Il y a déjà 3 dans la même colonne que B, alors B doit être 8. Cela signifie que A doit être le reste 3. Résolution du puzzle est un peu plus compliqué, mais en vaut la peine.
Les deux rangées inférieures
L'engouement Sudoku a balayé à travers le monde, et il ne montre aucun signe de ralentissement. Plusieurs variantes ont développé à partir du thème de base, tels que 16 par 16 versions et combinaisons multi-réseau (vous pouvez essayer une différence duplex sudoku dans le puzzle Plus). Mais comme avec les carrés magiques et carrés latins, la popularité du Sudoku dépendra si elles peuvent continuer à offrir de nouveaux défis.
A propos de l'auteur
Hardeep Aiden est diplômé du Département de mathématiques à l'Imperial College, Londres. En dehors des mathématiques, il est intéressé par les langues et linguistique, et est en train d'apprendre le japonais, français et anglais langue des signes.