Path: ...!weretis.net!feeder6.news.weretis.net!feeder8.news.weretis.net!news.mixmin.net!aioe.org!wWi+bf82x/J4IG13ZEtRgw.user.46.165.242.75.POSTED!not-for-mail
From: Samuel DEVULDER <samuel_dot_devulder@laposte_dot_net.invalid>
Newsgroups: fr.sci.maths
Subject: =?UTF-8?Q?Amorce_de_Sudoku_=5b=c3=a9tait_Re=3a_Sugurus=5d?=
Date: Sun, 29 Aug 2021 16:20:35 +0200
Organization: Aioe.org NNTP Server
Message-ID: <sgg53j$c2t$1@gioia.aioe.org>
References: <61291b21$0$21601$426a74cc@news.free.fr>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Info: gioia.aioe.org; logging-data="12381"; posting-host="wWi+bf82x/J4IG13ZEtRgw.user.gioia.aioe.org"; mail-complaints-to="abuse@aioe.org";
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
 Thunderbird/91.0.3
X-Antivirus: Avast (VPS 210829-4, 29/8/2021), Outbound message
X-Antivirus-Status: Clean
X-Notice: Filtered by postfilter v. 0.9.2
Content-Language: fr
Bytes: 4053
Lines: 65

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)