Feuille de travaux pratiques numéro 3 cours d'algorithmique de licence

Backtracking sur l'échiquier

Objectifs : réaliser un classique de la programmation.

Temps : 1 séance de 3 heures.

Un algorithme de backtracking parcourt récursivement un arbre abstrait à la recherche des solutions d'un problème. Une méthodologie qui consiste à faire travailler la pile de votre ordinateur à la place de vos neuronnes... Il ne faut pas s'attendre à des miracles, les temps de calculs sont le plus souvent exponentiels et plus encore. Une approche brutale qui permet d'obtenir des succès là ou les génies échouent ! C'est le cas des célèbres puzzles échiquéens inventés par Leonhard Euler (1707-1783) et Carl Friederich Gauss (1777-1855). Pour cette séance, nous vous demandons de traiter un des trois classiques : cavalier d'Euler, 8 Dames de Gauss et le jeu du compte est bon. Dans tous les cas, il s'agit d'écrire un programme récursif en donnant des précisions sur l'aspect complexité et temps de calculs.

[ 1 ] Le cavalier d'Euler

Il s'agit de trouver les parcours de cavalier sur un échiquier qui passent une et une seule fois par toutes les cases de l'échiquier avant de revenir sur la case de départ. Le problème se généralise de façon évidente. Ecrire un algorithme de backtracking pour résoudre Euler(n). Dans son fameux bréviaire des échecs 1933, le maitre Xavier Tartakover donne une des nombreuses solutions :

14	29	34	55	12	27	24	49
35	56	13	28	33	50	11	26
30	15	54	51	58	25	48	23
41	36	57	32	61	52	63	10
16	31	40	53	64	59	22	47
37	42	1	60	19	62	9	6
2	17	44	39	4	7	46	21
43	38	3	18	45	20	5	8

http://eleves.mines.u-nancy.fr/~taddei/page_echecs/curiosites/sol_cavEuler.htm

[ 2 ] Les 8 Dames de Gauss.

Comment placer 8 dames sur un échiquier sans qu'aucune ne soit en prise vis à vis d'une autre. En 1848, Gauss avait trouvé 72 solutions. Vous n'êtes pas Gauss mais vous avez un ordinateur ! Trouver toutes les solutions à une symétrie prés, le prince des mathématiques avait-il raison ? Là encore, le problème se généralise en un puzzle Gauss(n) à résoudre.

http://w3.edu.polytechnique.fr/profs/informatique/Bruno.Salvy/TD3/TD3.html

[ 3 ] Le compte est bon.

Les allergiques aux 64 cases traiteront du compte est bon, la phase arithmétique du célèbre jeu télévisé des chiffres et des lettres. Rappelons qu'il s'agit d'approcher au plus prés un nombre de trois chiffres tiré au hasard entre 100 et 999 à l'aide des quatre opérations usuelles et de 6 autres nombres tirés au hasard dans un ensemble de plaques : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 25, 50, 75 et 100. Tous les calculs doivent être effectués sur des nombres entiers. Ecrire une procédure LeBonCompte(v, t, n) pour trouver le bon compte v avec les nombres t[1], t[2],?,t[n].

14	29	34	55	12	27	24	49
35	56	13	28	33	50	11	26
30	15	54	51	58	25	48	23
41	36	57	32	61	52	63	10
16	31	40	53	64	59	22	47
37	42	1	60	19	62	9	6
2	17	44	39	4	7	46	21
43	38	3	18	45	20	5	8

14	29	34	55	12	27	24	49
35	56	13	28	33	50	11	26
30	15	54	51	58	25	48	23
41	36	57	32	61	52	63	10
16	31	40	53	64	59	22	47
37	42	1	60	19	62	9	6
2	17	44	39	4	7	46	21
43	38	3	18	45	20	5	8

14	29	34	55	12	27	24	49
35	56	13	28	33	50	11	26
30	15	54	51	58	25	48	23
41	36	57	32	61	52	63	10
16	31	40	53	64	59	22	47
37	42	1	60	19	62	9	6
2	17	44	39	4	7	46	21
43	38	3	18	45	20	5	8