Jeux de reflexion et de logique :

Sudoku :

http://vincent.planete.org/sudoku/faq.php
http://fr.wikipedia.org/wiki/Math%C3%A9matiques_du_Sudoku
http://www.math.univ-toulouse.fr/~jbhu/Sudoku.pdf
http://www.sudoku-land.com/pres-sudoku/math-sudoku.php
http://sudoku.nerdzblog.com/Des-milliards-de-grilles-de-Sudoku-avec-un-seul-grille-104.php
http://www.developpez.net/forums/d54373/autres-langages/algorithmes/automatiser-reponse-sudoku/
http://ronan.kerviche.free.fr/TIPE_2008_2009/Dossier_Sudoku.pdf
Nombre de grilles complètes possibles
Il est évident que le nombre de grilles complètes est inférieur au nombre de façons de placer neuf chiffres 1, neuf chiffres 2, ..., neuf chiffres 9 dans une grille de 81 cases. Le nombre de grilles est donc très inférieur à
$\frac{81!}{9!^9}$
En effet, dans ce décompte, on ne tient compte d'aucune des contraintes d'unicité.

Le nombre de grilles complètes possibles est également inférieur au nombres de carrés latins de côté 9.

Enfin, le nombre de grilles complètes possibles est inférieur à 9!⁹ qui correspondrait au nombre de façons de construire les régions sans tenir compte des contraintes sur les lignes et les colonnes.

En 2005, Bertram Felgenhauer et Frazer Jarvis ont prouvé que ce nombre de grilles était de :

$6 670 903 752 021 072 936 960 \approx 6,67.10^{21}$

Ce nombre est égal à :

$9! \cdot 72^2 \cdot 2^7 \cdot 27 704 267 971$

Le dernier facteur est un nombre premier. Ce résultat a été prouvé grâce à une recherche exhaustive. Frazer Jarvis a ensuite considérablement simplifié la preuve grâce à une analyse détaillée. La démonstration a été validée de manière indépendante par Ed Russell. Jarvis et Russell ont par la suite montré qu'en tenant compte des symétries, il y avait 5 472 730 538 solutions.

En revanche, à cette date, aucun résultat n'existe sur le nombre de grilles complètes dans un super sudoku (grille 16 × 16). Si maintenant, on s'intéresse aux nombres de problèmes proposables, ce nombre est nettement plus important car il existe plusieurs façons de révéler les chiffres d'une même grille.

Le problème de savoir combien de cases remplies sont nécessaires au préalable pour rendre la résolution unique est, à ce jour, sans réponse. Le meilleur résultat, obtenu par des Japonais, est de 17 cases sans contrainte de symétrie. Rien ne dit que ce ne soit pas possible avec moins de nombres. Gordon Royle indique que deux résolutions sont considérées comme différentes si elles ne peuvent pas être transformées l'une vers l'autre (ou l'inverse) grâce à une combinaison des opérations suivantes :
- permutations des 9 nombres
- échange des lignes avec les colonnes (transposition)
- permutation des lignes dans un seul bloc
- permutation des colonnes dans un seul bloc
- permutation des blocs sur une ligne de blocs
- permutation des blocs sur une colonne de blocs

On remarque l'analogie avec les opérations matricielles en algèbre linéaire.

Mathématiques

Le problème de placer des chiffres sur une grille de n²×n² comprenant n×n régions est NP-complet . Cela signifie qu'il n'existe pas d'algorithme efficace (polynomial) pour résoudre tous les Sudoku. Sur les grilles de taille finie, la résolution peut se faire via un automate fini qui connaît l'ensemble de l'arbre du jeu.

La résolution d'un Sudoku peut être formalisée par le problème de la coloration de graphe. Le but, dans la version classique du jeu, est d'appliquer 9 couleurs sur un graphe donné, à partir d'un coloriage partiel (la configuration initiale de la grille). Ce graphe possède 81 sommets, un par cellule. Chacune peut être étiquetée avec un couple ordonné (x,y), où x et y sont des entiers compris entre 1 et 9. Deux sommets distincts étiquetés par (x,y) et (x',y') sont reliés par une arête si et seulement si :

x=x' ou,
y=y' ou,
[x/3] = [x'/3] et [y/3] = [y'/3]

Le puzzle se complète en affectant un entier entre 1 et 9 pour chaque sommet, de façon que tous les sommets liés par une arête ne partagent pas le même entier.

Une grille solution est aussi un carré latin. Il y a notablement moins de grilles solutions que de carrés latins, car le Sudoku impose des contraintes supplémentaires. Néanmoins, le nombre de grilles solution valides de taille 9×9, calculé par Bertram Felgenhauer en 2005, serait de 6 670 903 752 021 072 936 960. Ce nombre est égal à 9! × 72² × 2⁷ × 27 704 267 971, ce dernier nombre étant un premier. Ce résultat est obtenu en partie par la logique et en partie par calculs en:brute force. Frazer Jarvis a notablement simplifié la méthode de calcul et Ed Russell a confirmé le résultat. Russell et Jarvis ont aussi démontré que lorsqu'il y a symétrie, il reste 5 472 730 538 solutions.

Le nombre maximum de dévoilés sans qu'une solution unique n'apparaisse immédiatement, peu importe la variante, est la taille de la grille moins 4 : si deux paires de candidats ne sont pas inscrits et que les cellules vides occupent les coins d'un rectangle, et que exactement deux cellules sont dans une région, alors il existe deux façons d'inscrire les candidats. L'opposé de ce problème, à savoir le nombre minimum de dévoilés pour garantir une solution unique, est un problème non résolu, bien que des enthousiastes japonais aient découvert une grille 9×9 sans symétrie qui contient seulement 17 dévoilés, alors que 18 est le nombre minimum de dévoilés pour les grilles 9×9 symétriques.

SUDOKU ET FRANCAIS

Forget Sudoku and smile for the camera

by Marianne Freiberger

Submitted by plusadmin on March 27, 2006

This is a version of Sudoku designed by Elser's algorithm. Your task is to fill the letters from A to Y into the 25 by 25 grid so that every letter appears exactly once in each row, column and 5 by 5 sub-grid. The solution will spell out the name of one of the founders of Cornell University.

It's often claimed that solutions to difficult problems can come to you when you're thinking of something entirely different. Physicist Veit Elser from Cornell University is a case in point: he accidentally found a recipe for solving Sudoku puzzles while trying to take pictures of really small things. The algorithm he and his colleagues developed for a microscopy technique called x-ray diffraction microscopy can solve any Sudoku puzzle you care to throw at it.

This in itself isn't a new thing. Algorithms for solving Sudoku have been around for a long time. But in realising that the difference-map algorithm he and his colleagues developed to analyse waveforms — in this case light waves — can double up in this way, Elser shed new light on how amazingly versatile the algorithm could be. "As a personal benefit," Elser says, "I can now explain to the person on the street what I do!"

The reason the difference-map algorithm works for both Sudoku and for creating images of tiny things (such as single cells) is that both reduce to solving problems whose solutions must satisfy two independent rules, or constraints. In Sudoku, these constraints are easy to pin-point. One way of phrasing them is: fill the numbers between 1 and 9 into a 9 by 9 grid so that

each number appears exactly once in each row and column, and
each number appears exactly once in each 3 by 3 sub-grid.

In fact, there are many other problems that fit a similar pattern. In producing a time table for university lectures, for example, you are constrained by the availability of lecturers and lecture theatres. If there are exactly two constraints that are independent of each other, then there's a good chance that the difference-map algorithm will do the trick. "There are a lot of problems that you can represent in terms of this language," says Elser. "We're providing the technique. Whatever people use it for, it's great for us." But how does creating an image of something such as a single cell lead to a "two constraint puzzle"?
Really small objects can't be captured by an ordinary microscope because they are smaller than the wavelength of ordinary visible light. In x-ray diffraction microscopy the object to be imaged is therefore bombarded with x-rays, which have a much finer wavelength. The way the light is scattered, or diffracted, by the object then contains the information needed to recreate a magnified image. If you were using an ordinary microscope the job of re-assembling this information to give an image would be achieved by a lens. This is impossible if the object is too small. All you can do is measure the scattered rays directly, and then re-combine them using a mathematical process called Fourier synthesis.
Fourier synthesis relies on the fact that any waveform can be expressed as the sum of individual sine and cosine functions. These constituent functions each have their own frequency, amplitude and phase (see figure 1). If you know what these are, you can re-construct the original waveform simply by adding up its constituent parts. In our example of x-ray diffraction, the constituent waves come from the scattered rays, which you measure, and adding them up gives a waveform which you use to create the image.

Figure 1: a sine wave of the form a sin(bx+c) has amplitude a, frequency b and phase c. The blue graph represents the wave sin(x+π/2), the green graph represents the wave sin(3x)/3, and the red wave represents their sum.

The problem is that when you are measuring the scattered rays, you lose vital information about their phase. If you simply resort to guess work, and randomly compute the phases in some way, then you are likely to end up with a meaningless image, or noise as mathematicians call it. Just like randomly filling numbers into a 9 by 9 grid is unlikely to give you the solution to a Sudoku puzzle. What you need are extra clues: rules that the phases have to obey. "People used to say that's an impossible problem," Elser says. "Then people got to thinking about the fact that there are going to be constraints coming from some rather mundane facts — that in principle will make the problem of deducing the phase like the solution of a solvable puzzle."
And the constraints here turn out to be very mundane indeed: one of them simply comes from the fact that the object in question has a well-defined boundary. In any image of the object, nothing should appear outside of that boundary, in other words, the pixel values there should be zero. "If I set up waves with known amplitudes and synthesize them, I'll find that for essentially all random combinations of phases, the thing I get is an object not confined," Elser says. "It takes a very clever combination of the phases of all those waves to add up to something in only one region; and cancel out everywhere else." The other constraint seems even more obvious: the waves you feed into your Fourier synthesis mechanism should have the amplitudes you have measured in your scattered waves.
With these two constraints in place, the imaging problem becomes a puzzle that Elser's algorithm can solve, just as it can solve any Sudoku puzzle. It will chomp through the calculations and spit out exactly those phases that give the correct image. Elser and colleagues have already used the algorithm to produce images of a single yeast cell, which have been published in a paper in the Proceedings of the national academy of sciences.

And where does all this leave Sudoku maniacs? The existence of a clever new algorithm probably won't cure them of their disease... unless they are true mathematicians: they often lose interest in a problem as soon as they know that a solution exists, even if no-one knows what that solution is!

---> http://plus.maths.org/content/forget-sudoku-and-smile-camera

Boggle :