Je n'ai pas pu continuer j'avais un message me refusant l'acces
sinon j'ecrirait un tuto
en attendant je continue reprendre a la suite...
donc la premiere chose a faire c'est s'occuper de la chaine 123456789 selon:on attribue une correspondance qui pour toute valeur comprise entre 1 et 9!=362880 donne un arrangement de la chaine
selon cette methode:
exemple avec 3!
rang 1: 123
rang 2: 132
rang 3: 213
rang 4: 231
rang 5: 312
rang 6: 321
on peut faire de meme pour 9!
la suite plus tard ça recommence...

Citation : Arthurus

Peut être bien que ça existe au final.

Je crois que oui, par des méthodes de programmation par contraintes. Ce genre de méthode permet de résoudre très rapidement le problème des N-reines sans backtracking, j'avais été étonné de voir ça un jour. Une référence que j'ai trouvé sur le net par quelqu'un qui semble un chercheur dans le domaine : sudoku.pdf

la suite...
rang 1 : 123456789
rang 2 : 123456798
...
rang 210 : 123587964
...
rang 9!=362880: 987654321
Methode pour la correspondance:
Donner un arrangement a partir du rang
exemple pour rang=210
On pose m=210 et n=9
la suite plus tard pour eviter les problemes
et a condition qu'on m'en laisse la possibilite
il y a aussi d'autres moyens...

Citation : candide

Je crois que oui, par des méthodes de programmation par contraintes. Ce genre de méthode permet de résoudre très rapidement le problème des N-reines sans backtracking, j'avais été étonné de voir ça un jour. Une référence que j'ai trouvé sur le net par quelqu'un qui semble un chercheur dans le domaine : sudoku.pdf

Intéressant le lien.
Cependant leur méthode n'est pas général, elle ne marche pas sur toutes les grilles :

Citation

The programs seem to be working quite well in finding solutions without
search, except for the “tough” and “diabolical” puzzles from [29] and those
from [44]. These puzzles require either more powerful reasoning, or some form
of search

J'ai quelque chose à proposer (même si cela peut-être faux) : essaie de créer un tableau pour chaque "endroit" qui ne doit pas contenir deux fois les mêmes valeurs : une fois que l'utilisateur à validé, tu compare chaque valeurs des différents tableaux et tu fais en fonction de cela.

Enfin, c'est ce que je pense.

Mais comme ton algorithme n'a pas l'aire de faire des trucs comme ça, je pense que c'est inutile

Citation : candide

Je crois que oui

Bon j'ai fait mes petites recherches de mon coté, et voici ce que j'ai pu en découler :
Si on trouve un algorithme qui résout le sudoku sans backtrack, cela voudra dire que la classe P est égale à NP.
Le problème est que jusqu'à maintenant, on ne sait pas encore si P=NP ou pas.
On a juste l'intuition que P est différent de NP, mais on en sait rien.

Donc on peut dire que : On ne sait pas s'il peut exister un algo qui résout sudoku sans backtrack.

@Marc Mongenet : idem en fait pour la coloration de graphe.

Bonjour!
Je vais arreter de repondre car je trouve plus pratique d'ecrire un tuto dessus
la seule chose que j'ajouterai est que comme j'espere que vous pourrez le verifier .Oui effectivement il est tout a fait possible de creer des sudoku a l'aide d'un algorithme aleatoire
dans ce tuto notamment j'en apporterai la preuve.
En attendant cette prise de position sans aucun element n'enge que moi
merci et à plus tard...

Ben alors la, je suis très impatient de voir ton tuto Ulbritch48.
Bon courage pour la rédaction.

Salut!
J'en suis encore tres loin...
Avant toute chose:
Est-il au moins démontrable
qu'un tel algorithme puisse être élaboré ?

Effectivement il serait vraiment dommage d'entamer l'étude pratique
pour la construction de grilles de Sudoku, puis s'apercevoir plus tard:
-soit que l'algorithme ne répond pas à toutes les exigences nécéssaires
-soit pire encore qu'il existe une démonstration
de l'impossibilité de l'existence de tels algorithmes
Ce serait un peu comme si le tutoriel se proposait de démontrer la quadrature du cercle

C'est à la réponse à cette question que la première partie est principalement consacrée.

Vous,vous demandez si vous avez le niveau nécéssaire pour
comprendre et soûrtout acquérir le sujet ?
Ne vous inquiétez pas ! Si vous savez effectuer les quatres operations de base,
vous n'aurez besoin alors uniquement juste d'un peu de bon sens.


<math>\(\Gamma (Z) =\int_0^\infty e^{-t} t^{z-1}\mathrm{d}t\)</math><math>\(\TeX\)</math>

Je supose que oui, je voit mal les livres de sudoku rédiger à la main .... Imaginez vous des milliers de grilles

Citation : Marc Mongenet

Citation : candide

faut dire que j'ai jamais vu en le sudoku qu'un problème de brute force ...

Il me semble avoir lu que le sudoku peut être ramené à un problème de coloration de graphe (9 couleurs, une arête entre chaque sommet de chaque ligne, colonne, mini-carré).

[je n'avais pas vu ta réponse c'est pour ça que je réponds maintenant]

Résolution d'un sudoku N*N*N*N = coloration d'un graphe est évident. Question (à ceux qui connaissent les rudiment de théorie des graphes) : trouver son nombre chromatique.

Citation : Marc Mongenet

En tout cas j'ai fait un solveur ''brute force'', et sur une grille difficile (trouvée sur Internet), il peut tourner un jour sans trouver de solution. Un algorithme ''brute force'' ne m'apparaît pas comme une solution pratique au sudoku.

Je suis très étonné, je n'ai jamais trouvé de grille y compris dans les diaboliques qui ait résisté plus de 5 secondes sur mon PC de 2001, y compris parmi les grilles qui contiennent le plus petit nombre possible de cases remplies. Mon solveur en plus n'est pas du tout optimisé, le backtracking n'est même pas gourmand. Donc je serais curieux de pouvoir essayer ta grille ou une autre que ton solveur met longtemps à résoudre.

Citation : Marc Mongenet

Un algorithme ''brute force'' ne m'apparaît pas comme une solution pratique au sudoku.

C'est pas impossible parce que pour faire une exploration complète, si on a vraiment pas de chance, on est obligé d'explorer l'arbre très en profondeur ce qui peut être très couteux et même inaccessible.


Si Fvirtmann suit ce fil, il serait intéressant qu'il nous dise quelle méthode emploie son solveur, je l'avais essayé il était super-rapide.

Peut être qu'il commence par utiliser d'autres méthodes, et la force butes en dernier recours exemple : dans chaque cases tu met tous les chiffres qui sont possibles, et à chaque fois qu'une case a un seul nombre possible, tu met ce nombre définitivement dans la cases et tu actualise les possiblité dans la ligne et la colonne et le cadre où se trouve cette case.

Citation : candide

Si Fvirtmann suit ce fil, il serait intéressant qu'il nous dise quelle méthode emploie son solveur, je l'avais essayé il était super-rapide.

On va l'appeler

Citation : Arthurus

Citation : candide

Si Fvirtmann suit ce fil, il serait intéressant qu'il nous dise quelle méthode emploie son solveur, je l'avais essayé il était super-rapide.

On va l'appeler

Me voila
Alors je n'ai pas tout lu, j'ai juste lu que les méthodes brute force dont vous parlez peuvent tourner longtemps.
Pour ma part, j'ai 2 techniques de solution cognitive, puis une brute force si ça échoue :

c'est aussi une méthode brute force, mais avec quelques astuces.

En effet, une méthode bien bourrine consisterait, d'entrée, a considérer 81 cas (un départ sur chaque case) multiplié par 9 chiffres : en gros, 81*9 cas de départ.
Mais ça, c'est long, très très long.

L'astuce est de se dire : de toute façon, il faudra remplir toutes les cases. Donc je commence par la première, et j'essaie chacun des chiffres. J'ai donc que 9 possibilités de départ, et non 81*9. Je commence toujours par la première case.
Ensuite, je parcours les cases dans l'ordre, et avec les contraintes des chiffres déjà posées, j'élague à toute vitesse !

ça me rappel que pour l'école ou avait un rush de 2 jours pour faire un algo de résolution de sudoku le plus rapide possible...

Avec mon collègue on a proceder par elimination avec un tableau a 3 dimension et ensuite on faisait un fork() a chaque fois que plusieur possibilité apparaissait. ça marchai nickel.. Super rapide et tout... Sauf que notre DPR a fait une grille bien salé prevu pour ce genre d'algo... Du coup notre prog est parti en fork bomb et a planté de le serveur MDR !

Je te déconseille cette méthode de bourin

Il faut faire attention avec le multithread et le multiprocess : si tu en fais trop (fork bomb), la machine passe plus de temps à faire du scheduling que de gérer le programme lui même !

Si j'étais toi, je forkerais que sur le premier level de récursion
(oui, oui, c'est le verbe forker )

Citation : candide

Je suis très étonné, je n'ai jamais trouvé de grille y compris dans les diaboliques qui ait résisté plus de 5 secondes sur mon PC de 2001, y compris parmi les grilles qui contiennent le plus petit nombre possible de cases remplies. Mon solveur en plus n'est pas du tout optimisé, le backtracking n'est même pas gourmand. Donc je serais curieux de pouvoir essayer ta grille ou une autre que ton solveur met longtemps à résoudre.

Il me semble que j'avais testé des grilles présentées dans http://en.wikipedia.org/wiki/Algorithmics_of_sudoku
Pour l'instant, mon solveur est vraiment simple, seule la règle de base est appliquée (pas 2 fois le même chiffre), et ensuite essais et backtracking. Mais je n'ai pas mon code sous la main, j'en écrirai plus à l'occasion.

Oui on était conscient de ça... Mais c'était un RUSH (2 jours pendant un weekend) donc on a privilégié la vitesse a la logique...

Bref c'était quand même marrant, quand je suis arrivé a l'école le jour des soutenance tout le monde a applaudi... Notre prog avait planté le serveur de rendu de Rennes et de Nantes... Du coup pas de soutenance ce jour là xD

Saboteur

Hihihi Sur le coup j'était un peu dégouté, mais finalement c'est un bon souvenir

Citation : Marc Mongenet

Il me semble que j'avais testé des grilles présentées dans http://en.wikipedia.org/wiki/Algorithmics_of_sudoku

Je viens d'en essayer dans la liste des exceptionnellement difficiles et mon solveur les traite en quelques millisecondes ou centièmes de seconde (donc il faut comprendre exceptionnelement difficile pour un raisonnement humain). Le seul qui résiste vraiment est celui qualifié de "Near worst case" : il tient onze secondes mais il a été construit pour justement être difficile à être résolu par backctraking.

Il faut que je retrouve la grille qui a fait planté mon algo... ça c'est du costaud... Parceque les grilles soit disant difficile il les passait en même pas une seconde aussi...

Citation : candide

Citation : Marc Mongenet

Il me semble que j'avais testé des grilles présentées dans http://en.wikipedia.org/wiki/Algorithmics_of_sudoku

Je viens d'en essayer dans la liste des exceptionnellement difficiles et mon solveur les traite en quelques millisecondes ou centièmes de seconde (donc il faut comprendre exceptionnelement difficile pour un raisonnement humain). Le seul qui résiste vraiment est celui qualifié de "Near worst case" : il tient onze secondes mais il a été construit pour justement être difficile à être résolu par backctraking.

Je viens d'essayer cette grille avec mon algo en désactivant mes algos cognitifs : donc en allant direct sur le brute force, je calcule le résultat entre 2 et 3 secondes.
Mon algo de brute force utilise l'astuce dont j'ai parlé plus haut, et j'ai également remplacé la recursivité par un algo itératif en utilisant une pile explicite.

EDIT : j'ai mis a jour mon site : la nouvelle version de mon Sudoku part directement en brute force si on appuie sur "f"

C'est pas plus mal.., Parceque le recursif ça bouffe la stack surtout s'il y a beaucoup de niveau de récursivité...

Sans rentrer dans le détail, voici mon algo. Oui, c'est du C++.

Sud BruteForce(const Sud& sud)
{
	int k;
	std::stack<Sud> S;
	S.push(sud);
	int x,y;
	while(!S.empty())
	{
		Sud s = S.top();
		S.pop();
		s.FindCaseLibre(x,y);
		if (x==-1)
		{
			return s; // trouvé.
		}
		for(k=1;k<=9;k++)
		{
			if (!s.Impossible(x,y,k))
			{
				Sud s2=s;
				s2.SetChiffre(x,y,k);
				S.push(s2);
			}
		}
	}
	return Sud();
}

Citation : Dr.

C'est pas plus mal.., Parceque le recursif ça bouffe la stack surtout s'il y a beaucoup de niveau de récursivité...

Sur un Sudoku, a priori je dirais que c'est limité à 9 * 9 niveaux de récursions, non?

A part ça, mon solveur brute force doit être vraiment très très bête, car il lui faut généralement plusieurs minutes sur des grilles quelconque, et sur un PC rapide.
Je le rendrai plus rapide, mais d'abord je dois finir les micro-optimisations de mon rectangle vide maximum pour aller plus vite que ce qui a été posté jusqu'à présent dans le forum.

Citation : Marc Mongenet

Citation : Dr.

C'est pas plus mal.., Parceque le recursif ça bouffe la stack surtout s'il y a beaucoup de niveau de récursivité...

Sur un Sudoku, a priori je dirais que c'est limité à 9 * 9 niveaux de récursions, non?

Oui, il n'y a donc a priori pas de danger de faire sauter la pile. Mais j'ai voulu mettre une pile explicite. Je ne sais pas si c'est plus rapide, mais ça marche bien.

EDIT : Marc, si tu as une solution plus rapide pour le rectangle, je suis preneur ! Moi je n'arrive plus à gagner en vitesse. Mais je suis arrivé sous les 100 ms pour la grille 1000x1000 de Candide

Citation : Dr.

ça me rappel que pour l'école ou avait un rush de 2 jours pour faire un algo de résolution de sudoku le plus rapide possible...

Je l'ai justement fait cette annee :).
Moi si mes souvenirs sont bons, je crois que je passais toutes les maps en quasi instantanee, il faudrait que je regarde mais si ca vous interesse, je peux soit montrer le code, soit fournir l'executable

Ca fait un bou de temps que je n'ai plus répondu (wacances), je vois que le topic a du succès.
Merci à tous (j'ai déjà commencé à lire les réponses),
j'attends avec impatience le tuto de Ulbritch48

Citation : Dr.

Oui on était conscient de ça... Mais c'était un RUSH (2 jours pendant un weekend) donc on a privilégié la vitesse a la logique...

Bref c'était quand même marrant, quand je suis arrivé a l'école le jour des soutenance tout le monde a applaudi... Notre prog avait planté le serveur de rendu de Rennes et de Nantes... Du coup pas de soutenance ce jour là xD

Je suis un témoin de cet applaudissement
Sinon je propose le backtracking comme algo assez facile à mettre en place et plutot efficace