VISI201 Backtracking (PICHENOT Simon) - Historique des versions

Spichenot le 17 mai 2020 à 10:01

2020-05-17T10:01:45Z

← Version précédente		Version du 17 mai 2020 à 10:01
Ligne 9 :		Ligne 9 :
	[[Fichier:sudoku.png]]		[[Fichier:sudoku.png]]

			Durant ce projet j'ai réalisé 2 programme qui permettent de résoudre des sudoku avec du backtracking.
	Le Backtracking fonctionne bien pour les résolutions de casse tête comme le sudoku. Car on peut facilement tester les cases une par une avec a chaque fois les valeurs entre 1 et 9.

	==== Algorithme basique ====		==== Algorithme basique ====
Ligne 20 :		Ligne 20 :

	==== Algorithme avec réflexion ====		==== Algorithme avec réflexion ====

			Ce deuxième algorithme ressemble au premier, sauf que celui ci commence par enlever toutes les branches de l'arbre qui ne sont pas des solutions. Pour cela le programme regarde les valeurs possibles pour chaque case et donc élimine toutes les valeurs impossible. De ce fait l’algorithme parcours moins de branche de l'arbre ce qui diminue le nombre de backtracking. Par exemple pour une grille de niveau difficile le programme fait environ 5 backtracking. il peut ne même pas en faire sur des grilles assez simple.

	=== Algorithme python ===		=== Algorithme python ===

Spichenot : /* Algorithme basique */

2020-05-17T09:54:19Z

Algorithme basique

← Version précédente		Version du 17 mai 2020 à 09:54
Ligne 16 :		Ligne 16 :

	Cette méthode fonctionne mais l'algorithme fait environ 5000 backtracking pour des grilles de niveau facile. Cela vient du fait que le programme ne peut pas savoir que la branche qu'il explore est juste ou fausse tant qu'il n'est pas arrivé au bout.		Cette méthode fonctionne mais l'algorithme fait environ 5000 backtracking pour des grilles de niveau facile. Cela vient du fait que le programme ne peut pas savoir que la branche qu'il explore est juste ou fausse tant qu'il n'est pas arrivé au bout.

			Pour l'algorithme voir algorithme python, sudoku basique

	==== Algorithme avec réflexion ====		==== Algorithme avec réflexion ====

Spichenot : /* Algorithme python */

2020-05-17T09:52:41Z

Algorithme python

← Version précédente		Version du 17 mai 2020 à 09:52
Ligne 20 :		Ligne 20 :

	=== Algorithme python ===		=== Algorithme python ===

			Voici les algorithme que j'ai fait durant le projet.

	==== Sudoku basique ====		==== Sudoku basique ====

Spichenot le 17 mai 2020 à 09:51

2020-05-17T09:51:45Z

← Version précédente		Version du 17 mai 2020 à 09:51
Ligne 12 :		Ligne 12 :

	==== Algorithme basique ====		==== Algorithme basique ====
	[[Sudoku basique]]

	Ce premier algorithme teste toutes les branches de l'arbre de possibilité de la grille de sudoku. Pour ce faire l’algorithme commence par prendre une case vide.		Ce premier algorithme teste toutes les branches de l'arbre de possibilité de la grille de sudoku. Pour ce faire l’algorithme commence par prendre une case vide. Il lui fait prendre les valeur de 1 à 9. Si la valeur de cette case est juste il passe à la case suivante sinon il revient à la case précédente.

			Cette méthode fonctionne mais l'algorithme fait environ 5000 backtracking pour des grilles de niveau facile. Cela vient du fait que le programme ne peut pas savoir que la branche qu'il explore est juste ou fausse tant qu'il n'est pas arrivé au bout.

	==== Algorithme avec réflexion ====		==== Algorithme avec réflexion ====

Spichenot le 17 mai 2020 à 09:42

2020-05-17T09:42:30Z

← Version précédente		Version du 17 mai 2020 à 09:42
Ligne 12 :		Ligne 12 :

	==== Algorithme basique ====		==== Algorithme basique ====
			[[Sudoku basique]]


	Ce premier algorithme teste toutes les branches de l'arbre de possibilité de la grille de sudoku. Pour ce faire l’algorithme commence par prendre une case vide.		Ce premier algorithme teste toutes les branches de l'arbre de possibilité de la grille de sudoku. Pour ce faire l’algorithme commence par prendre une case vide.

Spichenot : /* Résolution de sudoku */

2020-05-17T09:41:47Z

Résolution de sudoku

← Version précédente		Version du 17 mai 2020 à 09:41
Ligne 9 :		Ligne 9 :
	[[Fichier:sudoku.png]]		[[Fichier:sudoku.png]]

	Le Backtracking fonctionne bien pour les résolutions de casse tête comme le sudoku.		Le Backtracking fonctionne bien pour les résolutions de casse tête comme le sudoku. Car on peut facilement tester les cases une par une avec a chaque fois les valeurs entre 1 et 9.

	==== Algorithme basique ====		==== Algorithme basique ====


	Ce premier algorithme teste toutes les branches de l'arbre de possibilité de la grille de sudoku. Pour ce faire l’algorithme commence par prendre une case vide.		Ce premier algorithme teste toutes les branches de l'arbre de possibilité de la grille de sudoku. Pour ce faire l’algorithme commence par prendre une case vide.

Spichenot : /* Résolution de sudoku */

2020-05-17T09:40:00Z

Résolution de sudoku

← Version précédente		Version du 17 mai 2020 à 09:40
Ligne 8 :		Ligne 8 :
	=== Résolution de sudoku ===		=== Résolution de sudoku ===
	[[Fichier:sudoku.png]]		[[Fichier:sudoku.png]]

	Le Backtracking fonctionne bien pour les résolutions de casse tête comme le sudoku.		Le Backtracking fonctionne bien pour les résolutions de casse tête comme le sudoku.

Spichenot : /* Résolution de sudoku */

2020-05-17T09:39:08Z

Résolution de sudoku

← Version précédente		Version du 17 mai 2020 à 09:39
Ligne 7 :		Ligne 7 :

	=== Résolution de sudoku ===		=== Résolution de sudoku ===
			[[Fichier:sudoku.png]]

	Le Backtracking fonctionne bien pour les résolutions de casse tête comme le sudoku.		Le Backtracking fonctionne bien pour les résolutions de casse tête comme le sudoku.

Spichenot le 16 mai 2020 à 09:25

2020-05-16T09:25:39Z

Voir les modifications

Spichenot le 16 mai 2020 à 09:23

2020-05-16T09:23:47Z

← Version précédente		Version du 16 mai 2020 à 09:23
Ligne 7 :		Ligne 7 :

	=== Résolution de sudoku ===		=== Résolution de sudoku ===

			Le Backtracking fonctionne bien pour les résolutions de casse tête comme le sudoku.

	==== Algorithme basique ====		==== Algorithme basique ====

			Ce premier algorithme teste toutes les branches de l'arbre de possibilité de la grille de sudoku. Pour ce faire l’algorithme commence par prendre une case vide.

	==== Algorithme avec réflexion ====		==== Algorithme avec réflexion ====

VISI201 Backtracking (PICHENOT Simon) - Historique des versions

Spichenot le 17 mai 2020 à 10:01

Spichenot : /* Algorithme basique */

Spichenot : /* Algorithme python */

Spichenot le 17 mai 2020 à 09:51

Spichenot le 17 mai 2020 à 09:42

Spichenot : /* Résolution de sudoku */

Spichenot : /* Résolution de sudoku */

Spichenot : /* Résolution de sudoku */

Spichenot le 16 mai 2020 à 09:25

Spichenot le 16 mai 2020 à 09:23

Spichenot : /* Algorithme basique */

Spichenot : /* Algorithme python */

Spichenot : /* Résolution de sudoku */

Spichenot : /* Résolution de sudoku */

Spichenot : /* Résolution de sudoku */