Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
#1 06-06-2022 13:43:52
- passant
- Membre
- Inscription : 09-05-2020
- Messages : 8
Calcul combinatoire. (sudoku)
Bonjour,
Un problème sans intérêt pratique mais qui m'intrigue:
De combien de façons différentes peut on placer 18 pions sur une grille de Sudoku (9x9) en vérifiant:
Chaque ligne comprend exactement 2 pions
Chaque colonne comprend exactement 2 pions
Chaque bloc (sous grille 3x3) comprend exactement 2 pions
J'ai commencé par tenter le calcul ligne par ligne, soit 9x8 pour la 1ère mais dès la deuxième il y a deux cas possibles et je suis bloqué. Ce qui me suggère que ce n'est peut être pas la bonne méthode.
Peut être existe t-il une autre représentation du problème plus féconde ?
NB. A noter que si l'on se restreint à 9 pions le problème a été résolu: OEIS
PS. Pour les amateurs je précise que le problème concerne le nombre des "liens forts" dans une grille de Sudoku.
Dernière modification par passant (06-06-2022 17:55:12)
Hors ligne
#2 07-06-2022 15:42:00
- Zebulor
- Membre expert
- Inscription : 21-10-2018
- Messages : 2 220
Re : Calcul combinatoire. (sudoku)
Bonjour,
je me demande déjà s'il est possible de placer des pions comme tu l'indiques dans une grille (6x6)..Je pense que non par contre pour une grille (6x9) on le peut sauf erreur de ma part (pas 18 mais 12 points).
Je crois que c'est impossible de placer ces 18 points comme tu l'indiques dand cette grille 9x9
Dernière modification par Zebulor (07-06-2022 16:31:48)
Hors ligne
#3 08-06-2022 01:05:45
- Wan
- Membre
- Inscription : 12-02-2022
- Messages : 7
Re : Calcul combinatoire. (sudoku)
Bonsoir à tous les deux,
Sans avoir la réponse à la question de passant, et sans être expert du domaine,
Si nous considérons un ensemble de motifs {D,V,H}, avec :
D = 
V = 
H = 
Il est alors possible de placer, tout en respectant les consignes de passant, les 18 pions sur une grille de 9x9 en faisant attention à ce que chaque motif ne se retrouve qu'une seule fois par colonne et par ligne.
Par exemple : 
Qui donne le resultat : 
Il est évidemment possible de prendre pour le motif D, l'autre diagonale.
Il existe probablement d'autres ensembles de motifs similaires... Arriver à lister ses ensembles de motifs pourrait peut-être aider au dénombrement.
Amicalement,
W.
Dernière modification par Wan (08-06-2022 01:27:30)
Hors ligne
Pages : 1