Can Dancing Links peut-il être appliqué à ce CSP?

Question

L'implémentation de Dancing Links de l'algorithme X de Knuth peut-elle être utilisée pour résoudre this CSP? Dans ce jeu le premier et le dernier nombre sont toujours déjà dans le tableau et je crois qu'il n'y a qu'une seule solution à chaque problème bien formulé.

Answer 1

n °

Un solveur de contrainte pourrait certainement résoudre ce genre de problème, mais il semble peu probable que le meilleur moyen de le faire. D'un coup, il semble que ce serait difficile de dire au solveur "le chemin ne peut pas se traverser", ce qui est un indice utile.

Answer 2

Oui.

Supposons que nous voulons résoudre ce Hidato:

+---+ +---+ 
| | | 6 | 
+---+---+---+ 
| | | 
+---+---+ 
| 1 | | 
+---+---+ 

D'abord, nommons les cellules vides avec les lettres a, b, c, d:

+---+ +---+ 
| d | | 6 | 
+---+---+---+ 
| b | c | 
+---+---+ 
| 1 | a | 
+---+---+ 

Nous devons exprimer 3 types de contraintes pour chaque ligne de solution du

• Un nombre est utilisé (de sorte que le même nombre ne soit pas utilisé deux fois)
• Une cellule est utilisée (de sorte que la même cellule n'est pas utilisée deux fois)
• La cellule suivante est contrainte (de sorte que la cellule suivante ne peut être choisie que parmi les cellules adjacentes). Cette dernière contrainte ne nécessite pas de couverture exacte, elle ne doit donc être utilisée que comme colonnes secondaires dans la terminologie DLX.

La matrice de problème résultant est alors:

1 2 3 4 5 6 a b c d 2a 2b 2c 2d  3a 3b 3c 3d  4a 4b 4c 4d  5a 5b 5c 5d 
1        1 
    1   1   1    1  1 
    1   1   1    1 
    1    1   1    1 
    1    1   1  1  1 
    1  1       1    1  1 
    1   1       1    1 
    1   1       1    1 
    1    1       1  1  1 
     1  1           1    1  1 
     1  1           1    1 
     1   1           1    1 
     1   1           1  1  1 
     1 1               1 
     1  1               1 
     1 1  1               1 
     1   1               1 

Lorsque, par exemple, la deuxième ligne (sans compter la ligne de titre) peut être lu en tant que: cette ligne définit le numéro (première 1) dans la cellule a (seconde 1). Il est également contraint par la contrainte de lumière 2a. Et il contraint également 3 à ne pas être sur 3a et 3d, parce qu'ils ne sont pas adjacents à la cellule un.

Toutes les lignes Interprétés de cette façon, à l'exception:

• La première ligne qui indique que les contraintes sur le nombre .
• Les lignes (les 4 dernières), qui incorporent également la contrainte d'être adjacentes à .

La mise en œuvre est laissée en exercice pour le lecteur ...