Ce que tu décris, ça s'apelle grosso modo la propagation de contrainte.
Tu fais des déductions logiques en déduisant les valeurs impossibles dans chacune des cases, et quand il n'y a plus qu'une seule valeur possible, tu peux la prendre en compte dans tes déduction.
Et non, dans le cas du Sudoku, ça ne suffit pas pour résoudre la grille, en tout cas avec des méthodes de déductions "abordables" diront nous:
il y a des cas ou ta grille sera dans un état ou elle ne sera pas finie et ou tu ne pourra plus rien déduire avec les méthodes de déductions dont tu dispose.
Dans ces cas là, ce qu'on fait, c'est qu'on pose une hypothèse, genre on prend une case et on met un nombre encore possible arbitrairement (ou pas), et on vois ce qu'on peut en déduire. Si tu arrives dans un état impossible, genre t'as une case ou tu peux plus mettre de nombre, ton hypothèse est fausse, et tu peux retenter autre chose.
Si tu arrives de nouveau dans un état ou tu peux plus rien déduire, tu repose une hypothèse, etc.
PS: si on veut généraliser, en programmation par contrainte, pour tes cases, on utilise la notion de "variables", et pour tes boutons allumés/éteints, la notion de domaine d'une variable (l'ensemble des valeur que peux encore prendre une variable)
[^] # Re: Bof!
Posté par thoasm . En réponse au journal Résolution de sudokus avec Aptitude. Évalué à 2.
Tu fais des déductions logiques en déduisant les valeurs impossibles dans chacune des cases, et quand il n'y a plus qu'une seule valeur possible, tu peux la prendre en compte dans tes déduction.
Et non, dans le cas du Sudoku, ça ne suffit pas pour résoudre la grille, en tout cas avec des méthodes de déductions "abordables" diront nous:
il y a des cas ou ta grille sera dans un état ou elle ne sera pas finie et ou tu ne pourra plus rien déduire avec les méthodes de déductions dont tu dispose.
Dans ces cas là, ce qu'on fait, c'est qu'on pose une hypothèse, genre on prend une case et on met un nombre encore possible arbitrairement (ou pas), et on vois ce qu'on peut en déduire. Si tu arrives dans un état impossible, genre t'as une case ou tu peux plus mettre de nombre, ton hypothèse est fausse, et tu peux retenter autre chose.
Si tu arrives de nouveau dans un état ou tu peux plus rien déduire, tu repose une hypothèse, etc.
PS: si on veut généraliser, en programmation par contrainte, pour tes cases, on utilise la notion de "variables", et pour tes boutons allumés/éteints, la notion de domaine d'une variable (l'ensemble des valeur que peux encore prendre une variable)