Salut,

Je code en ce moment un programme qui permet de générer une grille de sudoku. Malgré plusieurs vérifications de mon code, ma grille comporte à la fin toujours des cases non assignées:

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import random


def evaluate_available(grid, x, y):
	available = [1, 2, 3, 4, 5, 6, 7, 8, 9]

	# Eliminates all row occurences:
	available = [cell for cell in available if cell not in grid[y]]


	# Eliminates all column occurences:
	column = []
	for row in grid:
		column.append(row[x])

	available = [cell for cell in available if cell not in column]


	# Eliminates all square occurences:
	square = []
	square_x = slice(x // 3 % 3 * 3, x // 3 % 3 * 3 + 3)
	square_y = slice(y // 3 % 3 * 3, y // 3 % 3 * 3 + 3)

	for row in grid[square_y]:
		square.extend(row[square_x])

	available = [cell for cell in available if cell not in square]
	

	if not available:
		return [0]

	return available


def generate():
	grid = [[0, 0, 0, 0, 0, 0, 0, 0, 0],
			[0, 0, 0, 0, 0, 0, 0, 0, 0],
			[0, 0, 0, 0, 0, 0, 0, 0, 0],
			[0, 0, 0, 0, 0, 0, 0, 0, 0],
			[0, 0, 0, 0, 0, 0, 0, 0, 0],
			[0, 0, 0, 0, 0, 0, 0, 0, 0],
			[0, 0, 0, 0, 0, 0, 0, 0, 0],
			[0, 0, 0, 0, 0, 0, 0, 0, 0],
			[0, 0, 0, 0, 0, 0, 0, 0, 0]]

	for y in range(9):
		for x in range(9):
			new_number = random.choice(evaluate_available(grid, x, y))
			#print('({}, {}) : {}'.format(x, y, evaluate_available(grid, x, y)))
			grid[y][x] = new_number
	return grid


def draw(grid):
	print('_' * 25)
	for i, row in enumerate(grid):
		if i in (3, 6):
			print("⊢–––––––+–––––––+––––––⊣")
		print("| {} {} {} | {} {} {} | {} {} {} |".format(*row))
	print('¯' * 25)

if __name__ == '__main__':
	draw(generate())

Voilà le résultat (mais pas celui que je souhaite):

_________________________
| 1 5 7 | 8 6 3 | 9 4 2 |
| 2 4 3 | 5 1 9 | 8 6 7 |
| 8 6 9 | 4 7 2 | 3 1 5 |
⊢–––––––+–––––––+––––––⊣
| 7 3 1 | 6 4 8 | 2 9 0 |
| 4 2 6 | 1 9 7 | 5 8 3 |
| 9 8 5 | 3 2 0 | 6 7 1 |
⊢–––––––+–––––––+––––––⊣
| 6 1 8 | 7 5 4 | 0 2 9 |
| 3 7 2 | 9 8 6 | 1 5 4 |
| 5 9 4 | 2 3 1 | 7 0 8 |
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

Je pense que "l'algorithme" est bon, mais toujours pas de grille sans zéro .

Merci,

AZ

-
Edité par Anonyme 5 septembre 2014 à 13:33:47

Je pense que c'est ton algorithme qui n'est pas bon. Prenons un exemple des 2 premières lignes:

#Ta première ligne du sudoku sera (de manière aléatoire):
6 1 2 3 4 5 9 8 7

#Ta seconde ligne sera aussi aléatoire, et pourra très bien te sortir encore une
#fois le 7 en dernier. Or puisque tu vérifie qu'il ne doit pas y avoir deux fois
#le chiffre 7 dans une même colonne, tu renvoie le chiffre 0.

#En fait ça aurait été aussi vrai si ton 7 serait apparue dans les 3 derniers,
#car il ne doit pas y en avoir deux dans le même carré


#C'est exactement ce qui se passe. J'ai regardé la façon de faire en plaçant des
#print() à chaque available, et j'ai rajouté (et c'est là où c'est visible) un
#draw(grid) dans ta fonction evaluate_available

PS: Tu m'a fait découvrir l'objet slice . J'ai mis un peu de temps à comprendre à quoi il servait 

PS2: Je n'ai plus le pouce négatif. Est-ce que tu l'as encore toi?

PS3: Je suis pas sûr que t'es besoin du modulo dans ton slice (en tout cas en python 3)

-
Edité par Olygrim 4 septembre 2014 à 18:55:49

Ouais mais non parce que ton exemple n'est pas valable (enfin il me semble) parce que mon programme ne peut ressortir un même nombre sur une même colonne. Sinon, pour le pouce vers le bas là je sais pas je te répond depuis mobile donc là présentation est un peu foireuse. Et j'ai besoin du modulo, essaie sans tu vas voir pourquoi.

"ton exemple n'est pas valable (enfin il me semble) parce que mon programme ne peut ressortir un même nombre sur une même colonne"

Si, si c'est exactement ce qui se passe. En fait j'ai testé ton programme et j'ai affiché ta grille de sudoku étape par étape avec le draw(grid). Et l'exemple que je t'ai donné est un exemple réel.

Comme tu le souligne, ton programme ne peux pas ressortir un même nombre sur la même colonne. Mais ça ne veux pas dire que ton nombre sera sélectionné pour être placé avant. Reprenons l'exemple avec le chiffre 7 que j'ai obtenu en dernière position (et donc dans le dernier carré): Rien n'oblige dans ton programme à ce que ton chiffre 7 soit placé dans les carrés précédent. Et donc s'il n'est pas sélectionné avant, il ne pourra pas s'afficher. D'où le 0.

Un autre exemple:

#Première ligne:
123   456   789

#Rien n'empêche ton programme de faire:
123   456   789
4

123   456   789
45

123   456   789
456

123   456   789
456   1

123   456   789
456   12

123   456   789
456   123

123   456   789
456   123   000

Pourquoi ne pas utiliser sample du module random ?

>>> random.sample(range(1, 10), 9)
[1, 8, 2, 5, 3, 7, 9, 4, 6]

Sympa!! Je ne connaissais pas cette méthode. J'étais parti sur une boucle avec randchoice() mais ta méthode est parfaite (pour choisir la première ligne).

-
Edité par Olygrim 4 septembre 2014 à 18:53:35

Oh, je vois. Mais alors c'est quoi le bon algorithme ? Ma méthode me paraissait évidente et infaillible mais... en fait non . J'ai beau faire marcher ma petite tête je ne trouve l'algo... Si l'un de vous le trouve, ça serait sympa de m'expliquer (sans faire le code). Et merci pour l'explication Olygrim .

Je ne sais pas. Comme ça, je dirai que ta première ligne tu l'as fait avec la méthode proposée par OldP. Ensuite pour les suivantes: tu les divises en 3 parties, qui correspond à chaque carré. Tu force la première partie à choisir entre 0 et 3 nombres compris dans la 3ème partie. Pour la 2ème partie, tu lui force à choisir 3-n nombres dans la 3ème partie. Un exemple:

#La première ligne
#PARTIE 1     PARTIE 2     PARTIE 3
   123          456          789

#Deuxième ligne. La PARTIE 1 va prendre 2 éléments de la PARTIE 3, et la 
#PARTIE 2 va prendre 3-2=1 élément:
#PARTIE 1     PARTIE 2     PARTIE 3
   123          456          789
   784          912          356

#Et pour la dernière ligne, tu dispose aléatoirement les élément qui manque dans
#le carré
PARTIE 1: manque 569
PARTIE 2: manque 378
partie 3: manque 124

Un truc comme ça. A voir s'il faut rajouter des conditions de vérifications (notamment pour les carrés suivants)

-
Edité par Olygrim 4 septembre 2014 à 14:55:42

Sinon sans utiliser random, on peut faire du backtracking

Bonjour,

Je pense que le pb dans l'algorithme initial vient du fait que tu supposes qu'il y a toujours une solution, ce qui est faux. Quand tu as placé un certain nombre de chiffres, tu peux très bien tomber sur une configuration bloquée qui n'a aucune solution : dans ce cas, la fonction evaluate_available retournera zéro.

C'est un exemple que donne Olygrim, et j'ai peur que ça soit assez courant ...

Après la question, c'est qu'est-ce qu'on fait quand on est bloqué ! le plus trivial serait de repartir avec une grille à zéro jusqu'à ce que le hasard fasse bien les choses et tire une grille qui a une solution, mais c'est pas trop classe et la proba est peut être très faible ! J'y ai pas trop réfléchi et je n'ai pas de solution.

Remarque pour en rajouter une couche : une grille de sudoku valable (dite 'bien formée') doit avoir une et une seule solution, ce qui parait assez coton à détecter.

Exemple simple de mauvaise grille :

* * * * * * * * *

* * 2 * * * * 3 *

* * * * * * * * *

* * 3 * * * * 2 *

* * * * * * * * *

...

même en suposant que les autres nombres remplissent les conditions classiques du sudoku, c'est mauvais parce que ça marche avec le couple 2-3 sur la ligne 2 + couple 3-2 sur la ligne 4 mais aussi avec 3-2 sur ligne 2 et 2-3 sur ligne 4 donc deux solutions distinctes.

Je vais continuer à y réfléchir mais ça semble un peu cramé (au moins pour mes compétences !)  parce que si j'ai bien compris ce que dit wikipedia que je viens d'aller voir, il existe plusieurs solutions informatiques pour résoudre une grille donnée (pas forcement très simples) , mais on n'en connaît pas pour générer complètement une grille

oldProgrammer a écrit:

Pourquoi ne pas utiliser sample du module random ?

Parce que shuffle est plus adapté ?

Comment ça c'est plus adapté ? Ils font la même chose à part que l'un (sample) renvoi une liste, alors que l'autre (shuffle) modifie une liste.

En quoi est-ce plus adapté ?

Donc si c'est une question sérieuse, non, ce n'est pas plus adapté, sinon évite ce genre de question hautaine.

Faut pas s'énerver pour si peu.

En quoi est-ce plus adapté ?

Parce que sample fait un échantillon de taille quelconque, alors que shuffle fait un mélange. D'un point de vue sens, il est beaucoup plus logique lorsque tu veux mélanger une liste comme ici d'utiliser shuffle plutôt que de faire un échantillon de la même taille que la liste. Fondamentalement, les deux font la même chose. Mais lorsque tu relis un code, et que tu vois un sample, il faut ensuite le temps de capter que la longueur de la population et de l'échantillon sont les même pour comprendre que tu fais en fait un mélange. Avec shuffle, c'est immédiat.

mais on n'en connaît pas pour générer complètement une grille

Générer une grille, c'est pareil que d'en résoudre une vide. C'est comme ça que j'avais fais dans un programme en C++. Si la résolution est bien codée (typiquement avec un backtracking un peu malin pour gagner en temps), tu génères autant de grilles que tu veux.

-
Edité par Anonyme 5 septembre 2014 à 11:29:36

il est beaucoup plus logique lorsque tu veux mélanger une liste comme ici d'utiliser shuffle plutôt que de faire un échantillon de la même taille que la liste.

On ne veut pas mélanger mais générer, c'est tout un autre sens

Je ne veux justement pas qu'on comprenne qu'on fait un mélange, ce n'est pas le cas ici, je génère une liste de nombre aléatoire compris entre 1 et 9.

@@dri1 :

"Générer une grille, c'est pareil que d'en résoudre une vide. C'est comme ça que j'avais fais dans un programme en C++. Si la résolution est bien codée (typiquement avec un backtracking un peu malin pour gagner en temps), tu génères autant de grilles que tu veux"

Exact. J'ai fait confiance un peu vite à l'article de wikipedia.fr !

Je suis parti moi-aussi sur cette piste du backtracking. J'ai codé la résolution d'une grille, il me reste maintenant à adapter mon code pour détecter si une grille donnée a une solution unique (et pas plusieurs ou aucune) et à mettre un peu d'aléatoire dans tout ça parce qu'évidemment avec un programme déterministe, partir d'une grille vide me done toujours la même grille résultat ...

-
Edité par Rozo2 6 septembre 2014 à 9:00:39