Sugurus

[robby]

je ne sais pas si vous connaissez les Sugurus, plus intéressants que les
Sudokus: https://krazydad.com/suguru/

Une grille comporte diverses formes ("boites")  imbriquées, de 1 à 5 cases.
Dans chaque case on doit attribuer un nombre de 1 à 5 de telle sorte que
- chaque boîte soit complete
- chaque chiffre soit unique dans son 8-voisinage.

Il y a une façon algorithmique classique de résoudre ça en parcourant
l'arbre des hypothèses.
Les humains procèdent différemment, sinon ce serait laborieux de tracer
puis effacer les hypothèses (souvent invalidées profond dans l'arbre).
( perso après avoir épuisé les évidences, je trace les contraintes et
tente de faire des chaines de corrélations jusqu'à ce qu'elles
s'effondrent).
Je me demande de quelles façon on pourrait poser mathématiquement un
"système" à résoudre, et sa matrice associée ?

evidemment il ne s'agit pas d'un système linaire: on est en nombre
entiers, il ne s'agit pas de faire des sommes, etc.
Si on remplace les 5 chiffres par 5 nombres premiers > 1 alors la
contrainte de remplissage d'une 5-boite peut s'ecrire
produit_i=1..5{cases_i} = 2*3*5*7*11, mais rien de tel pour le
8-voisinage, à par dire que la valeur centrale ne divise celle d'aucun
voisin ( et après ).

Des idées ?
Ou bien il n'y a pas de façon mathématique de poser ce problème qui
puisse se résoudre systématiquement de façon non gloutonne ?

--
Fabrice

[Stéphane CARPENTIER]

Le 27-08-2021, robby <m...@pla.net.invalid> a écrit :
> je ne sais pas si vous connaissez les Sugurus, plus intéressants que les
> Sudokus: https://krazydad.com/suguru/

Je ne connaissais pas.

> evidemment il ne s'agit pas d'un système linaire: on est en nombre
> entiers, il ne s'agit pas de faire des sommes, etc.

J'ai l'impression que même si tu vois que tes chiffres ne sont pas à
additionner, le fait que ce soient des chiffres te perturbe.

> Si on remplace les 5 chiffres par 5 nombres premiers > 1

Pourquoi ne pas remplacer les entiers par autre chose que d'autres
chiffres ? Genre des couleurs ? Tu vois où je veux en venir ?

> alors la
> contrainte de remplissage d'une 5-boite peut s'ecrire
> produit_i=1..5{cases_i} = 2*3*5*7*11, mais rien de tel pour le
> 8-voisinage, à par dire que la valeur centrale ne divise celle d'aucun
> voisin ( et après ).

Comment tu définis le voisin si la forme de la boite change avec chaque
problème ? L'intérieur d'une boite, OK, c'est facile, mais le voisin ?
Et si la case est sur le côté, il y a moins de voisins. Qui peuvent être
dans la même boite. Ou pas. Pareil pour l'angle.

> Des idées ?

Pour moi, ça a beau être des chiffres, c'est de la topologie. Je ne suis
pas un expert, ça fait très très longtemps que j'en ai fait.

> Ou bien il n'y a pas de façon mathématique de poser ce problème qui
> puisse se résoudre systématiquement de façon non gloutonne ?

Vu que certains considèrent que les stats ne sont pas des mathématiques,
c'est possible que tu considères que la topologie n'est pas des maths.

--
Si vous avez du temps à perdre :
https://scarpet42.gitlab.io

[Olivier Miakinen]

Le 28/08/2021 à 18:50, Stéphane CARPENTIER répondait à robby :

>
>> je ne sais pas si vous connaissez les Sugurus, plus intéressants que les
>> Sudokus: https://krazydad.com/suguru/
>
> Je ne connaissais pas.

Moi oui, je me suis déjà amusé à en résoudre quelques uns.

>> evidemment il ne s'agit pas d'un système linaire: on est en nombre
>> entiers, il ne s'agit pas de faire des sommes, etc.
>
> J'ai l'impression que même si tu vois que tes chiffres ne sont pas à
> additionner, le fait que ce soient des chiffres te perturbe.
>
>> Si on remplace les 5 chiffres par 5 nombres premiers > 1
>
> Pourquoi ne pas remplacer les entiers par autre chose que d'autres
> chiffres ? Genre des couleurs ? Tu vois où je veux en venir ?

On n'a effectivement pas besoin de définir une addition sur ces nombres,
mais il faut une relation d'ordre, et même une relation d'ordre total.
En effet, pour une région de N cases on doit utiliser tous les nombres
de 1 à N et aucun autre. Ça veut dire que même s'il y a des nombres 5
dans la grille, ce nombre ne sera pas présent dans les régions de moins
de 5 cases.


--
Olivier Miakinen

[Stéphane CARPENTIER]

Ce que je dis, c'est que la répartition des nombres bien définie dans le
sudoku pour tous les problèmes n'existe plus ici. Puisque ça dépend
aussi de la forme des boites et que cette forme change avec chaque
problème.

Par exemple, j'ai essayé un peu pour voir. Je ne sais pas si je me suis
planté ou pas sur ce que j'ai fait, mais ça ne change rien.
<https://ibb.co/mhMprBg>

Ici, si tu enlèves tous les chiffres de ta grille, tu vois que le
chiffre dans la case rouge est forcément 5. Et ça, c'est parce que cette
case est adjacente avec toutes les cases de la boite bleue. Si tu
changes la forme de la boite bleue, ce n'est plus forcément valable.
Donc, pour le choix des valeurs dans la boite, il faut une liste
ordonnée, mais ça s'arrête là plus où moins là.

[Olivier Miakinen]

Le 28/08/2021 à 20:53, Stéphane CARPENTIER a écrit :
>>
>> On n'a effectivement pas besoin de définir une addition sur ces nombres,
>> mais il faut une relation d'ordre, et même une relation d'ordre total.
>> En effet, pour une région de N cases on doit utiliser tous les nombres
>> de 1 à N et aucun autre. Ça veut dire que même s'il y a des nombres 5
>> dans la grille, ce nombre ne sera pas présent dans les régions de moins
>> de 5 cases.
>
> Ce que je dis, c'est que la répartition des nombres bien définie dans le
> sudoku pour tous les problèmes n'existe plus ici. Puisque ça dépend
> aussi de la forme des boites et que cette forme change avec chaque
> problème.

Note que c'est aussi le cas de certaines variantes du sudoku :
<https://fr.wikipedia.org/wiki/Math%C3%A9matiques_du_sudoku#Sudoku_avec_des_r%C3%A9gions_irr%C3%A9guli%C3%A8res>
(la forme des régions change, mais pas leur taille).

>
> Par exemple, j'ai essayé un peu pour voir. Je ne sais pas si je me suis
> planté ou pas sur ce que j'ai fait, mais ça ne change rien.
> <https://ibb.co/mhMprBg>
>
> Ici, si tu enlèves tous les chiffres de ta grille, tu vois que le
> chiffre dans la case rouge est forcément 5. Et ça, c'est parce que cette
> case est adjacente avec toutes les cases de la boite bleue.

Oui, je suis d'accord. Si une région de taille N a une case
adjacente avec toutes les cases d'une région de taille N-1,
alors cette case doit contenir le nombre N. On peut étendre
cette règle à plus d'une case de différence ou plus d'une case
adjacente (même si la géométrie rend difficile de rencontrer
cette situation pour des régions à plus de quelques cases) ;
par exemple, si deux cases d'une région de taille 4 sont
adjacentes toutes les deux aux deux cases d'une région de
taille 2, alors on sait collectivement quelles cases portent
les nombres 1 et 2, et quelles cases les nombres 3 et 4.

Ce genre de considération devrait permettre potentiellement
l'existence de sugurus sans aucun indice. (ou pas ?)

> Si tu
> changes la forme de la boite bleue, ce n'est plus forcément valable.
> Donc, pour le choix des valeurs dans la boite, il faut une liste
> ordonnée, mais ça s'arrête là plus où moins là.

Oui, nous sommes d'accord.


--
Olivier Miakinen

[robby]

Le 28/08/2021 à 18:50, Stéphane CARPENTIER a écrit :
> Pourquoi ne pas remplacer les entiers par autre chose que d'autres
> chiffres ? Genre des couleurs ? Tu vois où je veux en venir ?

non: quand tu veux poser mathématiquement un problème, tu fais plutôt
l'inverse: tu transformes tout en chiffres, par exemple les couleurs ;-)

> Comment tu définis le voisin si la forme de la boite change avec chaque
> problème ? L'intérieur d'une boite, OK, c'est facile, mais le voisin ?
> Et si la case est sur le côté, il y a moins de voisins. Qui peuvent être
> dans la même boite. Ou pas. Pareil pour l'angle.

évidemment !

Je ne sais pas si tu est familier de la méthode des éléments finis, et
de comment on construit la matrice qui va permettre de résoudre la simu
( du moins d'effectuer un pas ):
Pour N noeuds, tu fait une matrice NxN, encodant toutes les contraintes
( + un vecteur N pour les constantes ).
Les valeurs de la matrice vont coder les liens de voisinage, et les
conditions au bord.
Pour un environnement donné ( par ex avec des parois ), ta matrice sera
donc différente.
Tout cet aspect là est quasi identique ( au "détail" près que la matrice
ne sera pas celle d'un système linéaire ).

> Vu que certains considèrent que les stats ne sont pas des mathématiques,
> c'est possible que tu considères que la topologie n'est pas des maths.

topologie et stats sont évidemment des maths.

par ailleurs ici je me fiche de notion grandiloquante de ce qui est
digne d'être appelé "Vrai Problème Digne des Mathématiques", mais de ce
qui est formalisable et solvable par maths applis ;-)

--
Fabrice

[robby]

Le 28/08/2021 à 19:30, Olivier Miakinen a écrit :
> On n'a effectivement pas besoin de définir une addition sur ces nombres,
> mais il faut une relation d'ordre, et même une relation d'ordre total.
> En effet, pour une région de N cases on doit utiliser tous les nombres
> de 1 à N et aucun autre. Ça veut dire que même s'il y a des nombres 5
> dans la grille, ce nombre ne sera pas présent dans les régions de moins
> de 5 cases.

je parlais de nombres premiers parceque j'ai déjà vu un logiciel de
calcul formel procéder ainsi pour le stockage des flags ( 1 bit = 1
nombre premier ).

si tu as une boite de taille N, alors ta contrainte "tous les nombres
n_i de 1 à N sont présents" peut par exemple s'écrire sous la forme:
v1*v2*v3*v4*v5 = 2*3*5*7*11 ( i.e. produit des N premiers nombres
premiers ),   où la valeur n_i pour une  case est encodée comme v_i =
n_i ème nombre premier

du coup tu peux traduire certaines contraintes par "a divise b", etc.

mais ça ne me mềne pas beaucoup plus loin.

--
Fabrice

[robby]

Le 29/08/2021 à 00:18, Olivier Miakinen a écrit :
> Ce genre de considération devrait permettre potentiellement
> l'existence de sugurus sans aucun indice. (ou pas ?)

j'ai déjà fait des "difficulté 100" avec ~3 indices.

détail: dans https://krazydad.com/suguru/   choisir la taille, puis le
volume ( = instances différentes ). Ensuite, book = difficulté. Sauf que
100 pour small doit etre en gros l'équivalent de 60 pour médium ).


cela dit la notion de nombre d'indices est floue: tu peux n'avoir aucun
indice, mais des boites de taille 1 ( qui ne peuvent donc contenir que
"1" ),
possiblement jouxtant une boite de taille 2 ( au contenu "2", "1" ainsi
déterminé ), etc.


en fait la difficulté ici provient plutot des méthodes de construction
de ces grilles, consistant a produire aléatoirement des grilles valides,
puis à les simplifier tant qu'elles restent solubles de façon unique.
Donc pas trop de controles.

Pire: le vrai défi mathématique des sugurus ( et sudokus ) est de
produire une note de difficulté. souvent ils utilisent la profondeur
d'arbre nécessaire (ou heuristiques voisines), alors que les méthodes de
résolutions humaines sont très différentes, et ne coincent donc pas aux
meme endroits.


--
Fabrice

[robby]

Le 27/08/2021 à 19:04, robby a écrit :
> Ou bien il n'y a pas de façon mathématique de poser ce problème qui
> puisse se résoudre systématiquement de façon non gloutonne ?

voici le genre de méthode manuelle que j'utilise ( mon principe est de
ne jamais écrire d'hypothèses à dérouler puis effacer : je n'écris qu'à
coup sûr ).

#1 trivial
- épuiser les évidences ( cases résolues )

#2 possibles
- dans chaque boite, noter en petit les chiffres qui ne peuvent
apparaitre qu'à 2 endroits max
- dans chaque case, noter en entouré quand qu'il n'y a que 2 chiffres
possibles pour cette case
→ ceci permet parfois déjà de résoudre des voisins

#3 corrélations
- un cas de figure très puissant est quand dans la même boite il y a une
paire  ab et ba, qui est donc forcément (ab) et (ba) (i.e., seuls
possibles),
  et qui contraint certains voisins immédiats exactement comme si on
savait où étaient a et b
- un autre: quand 2 voisins a travers une frontière de bloc ont
forcément l'un d'eux a la valeur a (que je marque alors sur le bord),
  et mieux encore, (ab) , qui contraint les voisins

#3b corrélations ++
- chainage des corrélations entre cases de différentes boites, fussent
elles vides
- et a plus forte raisons si elles contaignent un (ab), que je propage. 
dans une chaîne (ou arbre) de corrélations, bien noter (ba) différemment
de (ab), ce qui ajoute des contraintes chaque fois que les 2 voisines,
fusse par proximité de 2 branches de l'arbre.

ce qui donne ce genre de graphe:  https://i.imgur.com/cqAk6NO.png

Dernier truc: comme la solution est toujours possible et unique, si dans
un recoin une dernière poche d'inconnues risque de se faire refermer,
alors le "bouchon" ne doit pas rendre la poche indéterminée.


Je ne me suis pas encore amusé à programmer ces heuristiques pour voir
si elles suffisent a résoudre tout, et surtout, a comprendre pourquoi
certaines notes de difficulté sont parfois très sous-estimées, et
parfois très sur-estimées.

Mais dans ce fil ma question était un peu différente: l'idée d'arriver à
"poser un système à résoudre mathématiquement", pourrait eventuellement
faire tout ce qui est au dessus en parallèle, voire d'autres choses et
plus profondément, alors que nous on ne sait faire que de proche en
proche, de manière constructive et itérative.

--
Fabrice

[Stéphane CARPENTIER]

Le 28-08-2021, Olivier Miakinen <om+...@miakinen.net> a écrit :

> Le 28/08/2021 à 20:53, Stéphane CARPENTIER a écrit :
>>
>> Ce que je dis, c'est que la répartition des nombres bien définie dans le
>> sudoku pour tous les problèmes n'existe plus ici. Puisque ça dépend
>> aussi de la forme des boites et que cette forme change avec chaque
>> problème.
>
> Note que c'est aussi le cas de certaines variantes du sudoku :
><https://fr.wikipedia.org/wiki/Math%C3%A9matiques_du_sudoku#Sudoku_avec_des_r%C3%A9gions_irr%C3%A9guli%C3%A8res>
> (la forme des régions change, mais pas leur taille).

Je ne connaissais pas. Mais là, du coup, ça va aussi la façon de le
résoudre mathématiquement.

[Stéphane CARPENTIER]

Le 29-08-2021, robby <m...@pla.net.invalid> a écrit :
> Le 28/08/2021 à 18:50, Stéphane CARPENTIER a écrit :
>> Pourquoi ne pas remplacer les entiers par autre chose que d'autres
>> chiffres ? Genre des couleurs ? Tu vois où je veux en venir ?
>
> non: quand tu veux poser mathématiquement un problème, tu fais plutôt
> l'inverse: tu transformes tout en chiffres, par exemple les couleurs ;-)

Ce que je veux dire, c'est que contrairement à un truc où la réponse est
la somme des valeurs d'une ligne, ça me fais plus penser à une carte où
tu ne dois pas avoir deux régions contingentes avec la même couleur et
tu dois savoir combien de couleurs minimum tu peux utiliser.

> Je ne sais pas si tu est familier de la méthode des éléments finis,

Non. Mes cours de maths sont... loins.

> et
> de comment on construit la matrice qui va permettre de résoudre la simu
> ( du moins d'effectuer un pas ):
> Pour N noeuds, tu fait une matrice NxN, encodant toutes les contraintes
> ( + un vecteur N pour les constantes ).
> Les valeurs de la matrice vont coder les liens de voisinage, et les
> conditions au bord.

Ça me rappelle vaguement de vieux souvenirs. Honnêtement, je n'en ai pas
fait beaucoup et j'en ai fait il y a trèèèèès longtemps. Dans mes
souvenirs, on abordait les problèmes de coloriages de carte de façon
différente des calculs de carrés magiques et c'était juste une piste.

[Samuel DEVULDER]

Le 27/08/2021 à 19:04, robby a écrit :

> je ne sais pas si vous connaissez les Sugurus, plus intéressants que les
> Sudokus: https://krazydad.com/suguru/

A propos des Sudokus, je me suis posé une question que je n'arrive pas à
résoudre et ca me frustre.

Dans le cadre d'un amusement retro-informatique je me suis mis en tête
de faire un générateur de sudoku "aléatoire". Ce genre d'algo commence
par un sudoku résolu puis vide une case au pif, vérifie que la solution
est toujours unique (on a un algo pour ca). Si oui on vide une autre
case au pif etc. Si non, on y remets la valeur antérieure et on retire
une nouvelle case à éliminer. Quand on ne peut plus retirer de cases on
a un Sudoku vrai (c'est à dire à solution unique) avec un certain nombre
de cases vides.

C'est simple, à condition d'avoir un sudoku résolu au départ.

Pour faire cela on commence par placer quelques chiffres au hasard dans
un sudoku vide et on lance une résolution. On se dit que oui naïvement
ca va produire un Sudoku tout résolu sans les particularité des
constructions de sudoku "automatisées" qui sont elles aussi prévu pour
être soluble (https://tinyurl.com/5amuzh4k).

Oui sauf qu'à un moment on tombe sur ce genre de configurations:
..1 ... .1.
C'est à dire une ligne avec deux fois le même chiffre, donc insoluble.

Ok, il faut donc que les chiffres qu'on place en amorce soient tous
différents. Là on se dit qu'en plaçant les chiffres 1 à 9 au hasard dans
un sudoku vide, il sera forcément soluble, oui ?

Non! Car on peut tomber sur cette configuration:
123 456 78.
... ... ..9
... ... ...
dans laquelle la case en haut à droite ne peut plus rien contenir.

Ah oui, dans ce cas là oui, forcément. Bon ben c'est parce que 9
chiffres distinct contraint trop le problème. Essayons alors avec 8 ou 7
chiffres distincts alors. Ca devrait marcher, là.. non ?


Et bien non ca ne marche pas toujours car on a cette configuration qui
est possible avec 7 chiffres distincts:
093 000(000)
000 000 250
000 000 761
Dans laquelle on doit remplir les 3 cases entres parenthèse avec
seulement les chiffres 4 et 8, ce qui est aussi impossible.

Donc une amorce avec 9, 8 ou 7 chiffres distinct n'est pas toujours
possible. Qu'en est il avec 6 ? Et bien je sais pas, d'où ma question
posée à vos éminents cerveaux:

Quel est le plus petit nombre Z de chiffres différents que l'on peut
mettre dans une grille de Sudoku vide et qui soit impossible à résoudre.

Nota: ici contrairement aux sudoku où l'on exige l'unicité, ici je
cherche juste s'il existe pas de grille pleine respectant les
contraintes du Sudoku qui s'appuie sur ces chiffres d'amorce.

Je ne sais pour l'instant que Z>=7, mais peut-on le baisser ? Si oui un
contre-exemple serait sympa. Si non comment le prouver ?

sam (je sens que ca n'est pas simple)

[Samuel DEVULDER]

Le 29/08/2021 à 00:18, Olivier Miakinen a écrit :

> Ce genre de considération devrait permettre potentiellement
> l'existence de sugurus sans aucun indice. (ou pas ?)

Ils en existe!

Le Suguru à 1 case en est (trivialement 1) un
_
|_|


En 2x2 ne ne pense pas qu'il y en ait car le voisinage de "1" interdit
les autres cases de porter ce 1)

Après en 3x3 je crois que

C A A
C B B
C B B

en est "presque" un (A, B, C = régions) car

1 2 1
3 4 3
2 1 2
et
2 1 2
3 4 3
1 2 1

sont les deux seules solutions. Elles se déduisent l'une de l'autre en
échangeant 1 et 2 dans toute la grille.

Je me demande du coup s'il en existe en 3x3 sans indices, car j'ai le
sentiment que l'échange de 2 valeurs sur toute la grille permet toujours
de trouver deux solutions distinctes comme ici.

C'est une intuition "forte", mais je ne sais pas justifier que cela
marche spécifiquement en 3x3 ou même toute taille. Je manque d'outil
pour raisonner proprement sur les régions.

Cela dit le sujet a été abordé sur stack-exchange, et il y est montré
qu'un suguru sans indice ce 8x8 existe, donc mon intuition qu'il n'en
existait pas autre que le trivial 1x1 était mauvaise:
+---+---+---+---+---+---+---+---+
| | | |
|---+---+---+---+---+ +---+---|
| | | | |
|---+---+ +---+ +---+---+ |
| | | | | | |
| + +---+ + + +---+ |
| | | | | |
|---+ + +---+---+ + +---|
| | | | | | |
| +---+---+ +---+---+---+ |
| | | | |
| +---+ +---+ +---+---+ |
| | | | | | |
|---+---+---+---+ +---+ +---|
| | | |
+---+---+---+---+---+---+---+---+

sam.

[Samuel DEVULDER]

Le 27/08/2021 à 19:04, robby a écrit :

> Ou bien il n'y a pas de façon mathématique de poser ce problème qui
> puisse se résoudre systématiquement de façon non gloutonne ?

Oui avec un programme quadratique en nombre entier ou un solveur SMT
(Satisfiability Modulo Theories)

https://www.researchgate.net/publication/346020801_Solving_Suguru_using_an_SMT_Integer_solver

En gros on encore chaque case par une variable d'un programme linéaire.
Une variable une case vide dans une région de N places s'encode avec 1
<= V <= N, une case avec un indice devient V = indice. Ensuite on ajoute
à ce programme linéaire les contraintes d'adjacence qui sont de la forme
V1!=V2, ce qui s'encode avec la contrainte quadratique suivante:
(V1-V2)² >= 1.

Cependant il me semble que l'encodage en programme linéaire/quadratique
ou contraintes SMT n'est pas spécialement adapté aux propriétés de ces
systèmes, et ne me semble pas plus puissant qu'une résolution par force
brute.

sam.

[robby]

Le 30/08/2021 à 14:22, Samuel DEVULDER a écrit :
> Oui avec un programme quadratique en nombre entier ou un solveur SMT
> (Satisfiability Modulo Theories)
> https://www.researchgate.net/publication/346020801_Solving_Suguru_using_an_SMT_Integer_solver
>
>
> En gros on encore chaque case par une variable d'un programme
> linéaire. Une variable une case vide dans une région de N places
> s'encode avec 1 <= V <= N, une case avec un indice devient V = indice.
> Ensuite on ajoute à ce programme linéaire les contraintes d'adjacence
> qui sont de la forme V1!=V2, ce qui s'encode avec la contrainte
> quadratique suivante: (V1-V2)² >= 1.

cool !

merci

--
Fabrice

[robby]

Le 30/08/2021 à 12:34, Samuel DEVULDER a écrit :
> En 2x2 ne ne pense pas qu'il y en ait car le voisinage de "1" interdit
> les autres cases de porter ce 1)

du coup le seul 2x2 possible est constitué d'une seule boite 2x2,
necessitant 3 indices explicites.

en 2x3 sauf erreur seuls sont solubles ( + symétries )

AAA
AAB   necessitant 3 indices explicites.

AAB
AAB  necessitant 3 indices explicites

> Après en 3x3 je crois que (...) en est "presque" un

autre façon de voir:

pour propager des indices implicites, il faut commencer par un pattern

ABB  → 1 | 2 1   ( ou ev allongés en  ABBCDD, ou ABBCDD , etc )

dès qu'on rajoute une ligne il faut des blocs >=4 , genre

 ABB     _1|2_1_
 CCD    _|3_4|3|_
CCDDE  |1_2|1_2|1|

--
Fabrice

[robby]

Le 30/08/2021 à 14:22, Samuel DEVULDER a écrit :

> En gros on encore chaque case par une variable d'un programme
> linéaire. Une variable une case vide dans une région de N places
> s'encode avec 1 <= V <= N, une case avec un indice devient V = indice.
> Ensuite on ajoute à ce programme linéaire les contraintes d'adjacence
> qui sont de la forme V1!=V2, ce qui s'encode avec la contrainte
> quadratique suivante: (V1-V2)² >= 1.

ça suffit a imposer des entiers, ça, meme si résolu dans R ?

> Cependant il me semble que l'encodage en programme
> linéaire/quadratique ou contraintes SMT n'est pas spécialement adapté
> aux propriétés de ces systèmes, et ne me semble pas plus puissant
> qu'une résolution par force brute.

tout dépend ce qu'on appelle puissant, et des contraintes qu'on se donne.

par exemple la résolution par exploration systématique des arbres
suppose pas mal de mémoire, dont une pile, et peut demander beaucoup de
pas avant de trouver la solution ( vu qu'on back track pour explorer
potentiellement tout l'arbre des possibles si pas de bol ).
La méthode que tu cite ici est peut-etre plus directe.

--
Fabrice

[Samuel DEVULDER]

Le 30/08/2021 à 15:19, robby a écrit :
> ça suffit a imposer des entiers, ça, meme si résolu dans R ?

Humm possible, mais il faut imposer à la somme des variables d'être
minimale. Quoique je me demande si les contraintes de régions (chiffres
tous différents compris entre 1 et taille-région) + les contraintes de
distances >=1 entre nombres adjacents me semble automatiquement tout
"caler" sur des entiers.

On doit pouvoir jouer avec solveurs QCP
(https://en.wikipedia.org/wiki/Quadratically_constrained_quadratic_program),
mais beaucoup sont payants :( Mais probablement que les "academics" y
ont droit sans frais.

https://community.ibm.com/community/user/datascience/blogs/xavier-nodet1/2020/07/09/cplex-free-for-students

sam.

[Olivier Miakinen]

Le 30/08/2021 12:34, Samuel DEVULDER a écrit :
>
> +---+---+---+---+---+---+---+---+
> | | | |
> |---+---+---+---+---+ +---+---|
> | | | | |
> |---+---+ +---+ +---+---+ |
> | | | | | | |
> | + +---+ + + +---+ |
> | | | | | |
> |---+ + +---+---+ + +---|
> | | | | | | |
> | +---+---+ +---+---+---+ |
> | | | | |
> | +---+ +---+ +---+---+ |
> | | | | | | |
> |---+---+---+---+ +---+ +---|
> | | | |
> +---+---+---+---+---+---+---+---+

Merci pour cette grille délicieusement difficile.


--
Olivier Miakinen

[robby]

Le 30/08/2021 à 17:53, Olivier Miakinen a écrit :
>> Merci pour cette grille délicieusement difficile.

bah le plus dur c'était de remplir la grille a l'intérieur du mail ;-)

> Le 30/08/2021 12:34, Samuel DEVULDER a écrit :
>> +---+---+---+---+---+---+---+---+

>> | 1 3 2 | 4 1 3 | 1 2 |
>> |---+---+---+---+---+ +---+---|
>> | 2 4 1 3 | 5 | 2 5 | 3 |
>> |---+---+ +---+ +---+---+ |
>> | 1 | 3 | 5 | 2 1 | 3 4 | 1 |

>> | + +---+ + + +---+ |

>> | 2 | 4 1 | 3 4 | 5 | 2 5 |

>> |---+ + +---+---+ + +---|

>> | 1 | 5 2 | 5 | 2 1 | 4 | 3 |
>> | +---+---+ +---+---+---+ |
>> | 2 | 4 3 1 | 3 | 5 2 1 |
>> | +---+ +---+ +---+---+ |
>> | 3 | 1 | 2 | 4 2 | 4 3 | 4 |
>> |---+---+---+---+ +---+ +---|
>> | 2 4 3 1 | 5 1 | 2 1 |

>> +---+---+---+---+---+---+---+---+
> Merci pour cette grille délicieusement difficile.

blague à part, c'était pas mal !

tu l'as construite comment ?

--
Fabrice

[Samuel DEVULDER]

Le 30/08/2021 à 18:33, robby a écrit :
>
> tu l'as construite comment ?

Copy/paste ..

sam :-P

[robby]

:-D

tu as une source avec d'autres du même genre ?

--
Fabrice

[robby]

Le 30/08/2021 à 12:34, Samuel DEVULDER a écrit :
> Cela dit le sujet a été abordé sur stack-exchange, et il y est montré
> qu'un suguru sans indice ce 8x8 existe

ah oui, ici. yen avait d'autres ?
Tu filerais le lien ?

--
Fabrice

[Samuel DEVULDER]

Le 31/08/2021 à 07:41, robby a écrit :

> tu as une source avec d'autres du même genre ?

Ben non je suis tombé dessus par hasard sur stack-exchange via google en
fait.

sam.

[Samuel DEVULDER]

Le 31/08/2021 à 08:29, robby a écrit :

> Le 30/08/2021 à 12:34, Samuel DEVULDER a écrit :
>> Cela dit le sujet a été abordé sur stack-exchange, et il y est montré
>> qu'un suguru sans indice ce 8x8 existe
>
> ah oui, ici. yen avait d'autres ?

non

> Tu filerais le lien ?

voilà:
https://math.stackexchange.com/questions/3927769/suguru-puzzles-with-no-given-clues

sam.

[Samuel DEVULDER]

Le 31/08/2021 à 08:47, Samuel DEVULDER a écrit :

>> ah oui, ici. yen avait d'autres ?
>
> non

enfin d'autre "sans indices", sinon il y a ceci:
https://puzzling.stackexchange.com/questions/106689/a-7x7-suguru-ss9/106690#106690

sam.

[Samuel DEVULDER]

Le 28/08/2021 à 19:30, Olivier Miakinen a écrit :

> On n'a effectivement pas besoin de définir une addition sur ces nombres,
> mais il faut une relation d'ordre, et même une relation d'ordre total.

En codant un solveur en Prolog je me rend compte qu'il n'est pas besoin
d'ordre. Les seules contraintes sont donc:
- tous les éléments du voisinage d'une case sont différents (on peut
réduire cela à seulement 4 cases).
- tous les éléments d'une même région sont deux à deux différents.

Il est juste besoin de savoir différencier le contenu de deux cases en
fait.

sam.

[Jacques Mathon]

Le jeu me paraissait plus contraint... par le fait que les régions les
plus petites (en nombre de cases) ne pouvaient contenir que les plus
"petits" contenus.

Autrement dit, dans une case seule on ne peut mettre que "1" et pas les
autres "chiffres".

Mais peut-être ai-je mal compris. C'est de cette manière que je viens
juste de commencer à résoudre le problème 8x8 sans indices (en mettant
un "1" dans la seule région d'une seule case).

Amicalement
--
Jacques

[Olivier Miakinen]

Bonjour,

Le 31/08/2021 09:23, Samuel DEVULDER me répondait :

>
>> On n'a effectivement pas besoin de définir une addition sur ces nombres,
>> mais il faut une relation d'ordre, et même une relation d'ordre total.
>
> En codant un solveur en Prolog je me rend compte qu'il n'est pas besoin
> d'ordre.

On en a besoin lorsque toutes les régions n'ont pas la même taille afin
de savoir quels sont les nombres utilisables dans les régions de taille
inférieure.

Par exemple, dans la grille 8×8 que tu as donnée, sans cette contrainte
d'autres solutions seraient possibles en mettant un 5 à la place du 1
ou du 2 de la région en bas à droite, ou bien en échangeant tous les 1
et tous les 2 avec donc un 2 dans la région d'une seule case.

--
Olivier Miakinen

[Olivier Miakinen]

Le 31/08/2021 09:31, Jacques Mathon répondait à Samuel Devulder :

>
> Le jeu me paraissait plus contraint... par le fait que les régions les
> plus petites (en nombre de cases) ne pouvaient contenir que les plus
> "petits" contenus.
>
> Autrement dit, dans une case seule on ne peut mettre que "1" et pas les
> autres "chiffres".

Exactement.

> Mais peut-être ai-je mal compris. C'est de cette manière que je viens
> juste de commencer à résoudre le problème 8x8 sans indices (en mettant
> un "1" dans la seule région d'une seule case).

... et c'est la seule manière d'assurer l'unicité.


--
Olivier Miakinen

[Samuel DEVULDER]

Le 31/08/2021 à 09:31, Jacques Mathon a écrit :
> Le jeu me paraissait plus contraint... par le fait que les régions les
> plus petites (en nombre de cases) ne pouvaient contenir que les plus
> "petits" contenus.
>
> Autrement dit, dans une case seule on ne peut mettre que "1" et pas les
> autres "chiffres".

Tu as raison, mais cela revient à dire que cette valeur est distincte de
2, 3, 4 et 5.

D'une façon ou d'une autre on arrive toujours à exprimer les contraintes
sous forme de "equal/not equal".

Par exemple une region (donc 3 variables X, Y, Z) avec 3 valeur
s'exprime par la résolution de ce système logique:

(
(X=1 and Y!=1 and Z!=1) or
(X=2 and Y!=2 and Z!=2) or
(X=3 and Y!=3 and Z!=3)
)
and
(
(Y=1 and Z!=1) or
(Y=2 and Z!=2) or
(Y=3 and Z!=3) or
)
and
(
Z=1 or
Z=2 or
Z=3
)

Bref, cela s'encode très bien sous la forme de prédicats Prolog, par
exemple là:
https://pastebin.com/sKq1DRMk

Le code Prolog est généré par ce script Lua que j'ai écrit rapidement(il
est archi perfectible et ne m'aide qu'à expérimenter):
https://pastebin.com/uATrbBUD

sam.

[Samuel DEVULDER]

Le 31/08/2021 à 10:09, Olivier Miakinen a écrit :
> Par exemple, dans la grille 8×8 que tu as donnée, sans cette contrainte
> d'autres solutions seraient possibles en mettant un 5 à la place du 1
> ou du 2 de la région en bas à droite, ou bien en échangeant tous les 1
> et tous les 2 avec donc un 2 dans la région d'une seule case.

Pour moi les solutions à un renommage près sont les mêmes c'est ce que
je disais plus haut en parlant d'échanger les 2 et les 3 sur l'ensemble
de la grille. Je travaille avec une classe d'équivalence des solutions :)

Mais oui tu as raison, il faut, pour l'unicité de la solution pouvoir
ordonner les valeurs possibles en effet.

sam..

[robby]

Le 31/08/2021 à 10:41, Samuel DEVULDER a écrit :
> Pour moi les solutions à un renommage près sont les mêmes c'est ce que
> je disais plus haut en parlant d'échanger les 2 et les 3 sur
> l'ensemble de la grille. Je travaille avec une classe d'équivalence
> des solutions :)
>
> Mais oui tu as raison, il faut, pour l'unicité de la solution pouvoir
> ordonner les valeurs possibles en effet.

oui, car si tu as 2 " 1-block " dont le contenu pourrait etre différent,
ça ne donne plus la meme classe d'equivalence

>
> sam..


--
Fabrice

[Olivier Miakinen]

Le 31/08/2021 10:41, Samuel DEVULDER m'a répondu :

>
>> Par exemple, dans la grille 8×8 que tu as donnée, sans cette contrainte
>> d'autres solutions seraient possibles en mettant un 5 à la place du 1
>> ou du 2 de la région en bas à droite, ou bien en échangeant tous les 1
>> et tous les 2 avec donc un 2 dans la région d'une seule case.
>
> Pour moi les solutions à un renommage près sont les mêmes c'est ce que
> je disais plus haut en parlant d'échanger les 2 et les 3 sur l'ensemble
> de la grille. Je travaille avec une classe d'équivalence des solutions :)

Ce sont les mêmes dans mon second exemple (remplacer tous les 1 par des 2
et tous les deux par des 1), mais pas dans mon premier exemple (remplacer
le 1 en bas à droite par un 5 en laissant le reste inchangé).


--
Olivier Miakinen

[Olivier Miakinen]

[Supersedes <sgkqb4$i68$1...@cabale.usenet-fr.net>]

Le 31/08/2021 10:41, Samuel DEVULDER m'a répondu :
>

>> Par exemple, dans la grille 8×8 que tu as donnée, sans cette contrainte
>> d'autres solutions seraient possibles en mettant un 5 à la place du 1
>> ou du 2 de la région en bas à droite, ou bien en échangeant tous les 1
>> et tous les 2 avec donc un 2 dans la région d'une seule case.
>
> Pour moi les solutions à un renommage près sont les mêmes c'est ce que
> je disais plus haut en parlant d'échanger les 2 et les 3 sur l'ensemble
> de la grille. Je travaille avec une classe d'équivalence des solutions :)

Ce sont les mêmes dans mon second exemple (remplacer tous les 1 par des 2

et tous les 2 par des 1), mais pas dans mon premier exemple (remplacer

[Olivier Miakinen]

Le 29/08/2021 08:49, robby écrivait :
>
> je parlais de nombres premiers parceque j'ai déjà vu un logiciel de
> calcul formel procéder ainsi pour le stockage des flags ( 1 bit = 1
> nombre premier ).
>
> si tu as une boite de taille N, alors ta contrainte "tous les nombres
> n_i de 1 à N sont présents" peut par exemple s'écrire sous la forme:
> v1*v2*v3*v4*v5 = 2*3*5*7*11 ( i.e. produit des N premiers nombres
> premiers ),   où la valeur n_i pour une  case est encodée comme v_i =
> n_i ème nombre premier

En résumé, on pourrait simplement écrire que chaque case contient un nombre
premier, et que le produit des valeurs de toutes les cases d'une région est
une primorielle. Ça fera plaisir à remy. ;-)

> du coup tu peux traduire certaines contraintes par "a divise b", etc.

Oui, ou par « le produit de tous les nombres de cases adjacentes est un
nombre sans carré ».

> mais ça ne me mềne pas beaucoup plus loin.

En effet.

--
Olivier Miakinen

[Samuel DEVULDER]

Le 29/08/2021 à 08:49, robby a écrit :
> si tu as une boite de taille N, alors ta contrainte "tous les nombres
> n_i de 1 à N sont présents" peut par exemple s'écrire sous la forme:
> v1*v2*v3*v4*v5 = 2*3*5*7*11 ( i.e. produit des N premiers nombres
> premiers ),   où la valeur n_i pour une  case est encodée comme v_i =
> n_i ème nombre premier

Oui et pareil pour les contraintes de proximités. Si j'appelle les
variables Vij (1<=i,j<=N), on a aussi

Vij ~| V(i-1)(j+1) * V(i+0)j * V(i+1)j * Vi(j+1) 1<=i,j<N

(~| = "ne divise pas" a ~| b <=> b != 0 (mod a) ).

Cette relation "~|" permet d'encoder efficacement pas mal de contraintes
et ainsi ramener n'importe quel Suguru de n cases à r régions avec i
indices à une résolution de (n+r+i-1) équations en nombre entiers.

Exemple:

C1 A A a b c
C B3 B -> d e f
C B B g h i

qui est de 9 cases avec 3 régions et 2 indices (les entier en colonne
impaires sont les indices, les lettres en colonne paires sont les
régions) s'encode avec les 9+3+2-1=13 contraintes suivantes:

trouver a,b,c,d,e,f,h,i,j entiers naturels tels que

## indices:
a | 2 ( a divise deux, e divise 3 )
e | 3 ( --> a = 2, e = 3 )
## régions:
bc | 6 ( (b,c)=(2,3) ou (3,2) )
adg | 30 ( --> dg | 15 )
efgh | 210 ( --> fgh | 70 )
## proximité
a ~| bed ( a ne divise pas b*e*d )
b ~| cfed ( ce qui encore a != b, )
c ~| ef ( et a != e, et a != d )
d ~| ehg
e ~| fihg
f ~| ih
g ~| h
h ~| i

J'ai pas tenté de voir si les solveurs numérique savent manger ce genre
d'équations, par contre cela permet peut-être d'appliquer des théorèmes
d'arithmétique entière.

sam.

[Jacques Mathon]

Oui et pour aider à la résolution, j'ai fait l'hypothèse de la justesse
de l'énoncé (suguru "valide" càd à solution unique) ce qui la rend plus
"facile".

Du coup, je n'ai pas eu à faire d'autres hypothèses pour résoudre. :-)

Amicalement
--
Jacques

[Samuel DEVULDER]

Le 31/08/2021 à 10:33, Samuel DEVULDER a écrit :
>
> Bref, cela s'encode très bien sous la forme de prédicats Prolog, par
> exemple là:
> https://pastebin.com/sKq1DRMk
>
> Le code Prolog est généré par ce script Lua que j'ai écrit rapidement(il
> est archi perfectible et ne m'aide qu'à expérimenter):
> https://pastebin.com/uATrbBUD

Erratum, j'ai pasté une mauvaise version, voici la bonne version du
générateur:

https://pastebin.com/uX9vz7Lu

qui donne ce genre de fichier Prolog:

----8<--------------------------------------------------------------
eq(X,X).
ne(X,X):-!,fail.
ne(_,_).
ex(_,[]).
ex(X,[X|_]):-!,false.
ex(X,[_|L]):-ex(X,L).
in(X,[X|L],L).
in(X,[Y|L],[Y|M]):-in(X,L,M).
match([],[]).
match([X|L],Q):-in(X,Q,M),match(L,M).
suguru([
[V1_1,V1_2,V1_3],
[V2_1,V2_2,V2_3],
[V3_1,V3_2,V3_3]]) :-
eq(V1_1, 1),
match([V1_2,V1_3], [1,2]),
match([V2_1,V3_1], [2,3]),
match([V2_2,V2_3,V3_2,V3_3], [1,2,3,4]),
ex(V1_2, [V2_2,V2_3]),
ex(V1_3, [V2_3]),
ex(V1_1, [V1_2,V2_2]),
ex(V2_1, [V2_2,V1_2,V3_2]),
ex(V3_1, [V3_2,V2_2]),
ex(V2_2, [V1_3]),
true.
describe:-write('solving...\n'),
write('+---+---+---+\n'),
write('| 1 | |\n'),
write('+ +---+---+\n'),
write('| | |\n'),
write('+ + + +\n'),
write('| | |\n'),
write('+---+---+---+\n'),
true.
w([]).
w([X|L]):-write(X),write('\n'),w(L).
r:-reconsult(suguru).
h:-halt.
x:-describe,time(suguru(L)),w(L).
----8<--------------------------------------------------------------

Qui se résout très facilement:

----8<--------------------------------------------------------------
$ lua suguru.lua > suguru.pl && swipl -s suguru.pl -t "x,fail;h"
Welcome to SWI-Prolog (Multi-threaded, 32 bits, Version 7.2.3)
Copyright (c) 1990-2015 University of Amsterdam, VU Amsterdam
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.

For help, use ?- help(Topic). or ?- apropos(Word).

solving...
+---+---+---+
| 1 | |
+ +---+---+
| | |
+ + + +
| | |
+---+---+---+
% 1,162 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
[1,2,1]
[3,4,3]
[2,1,2]
% 32 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
----8<--------------------------------------------------------------

sam.

[robby]

Le 31/08/2021 à 11:37, Samuel DEVULDER a écrit :
> J'ai pas tenté de voir si les solveurs numérique savent manger ce
> genre d'équations

oui, c'etait un peu la question: existe t'il des solveurs pour ce genre
de trucs ?


--
Fabrice