-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathProgramme.s
565 lines (435 loc) · 25.8 KB
/
Programme.s
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
###################################################################
###################################################################
## ##
## PROJET SUDOMIPS ##
## ##
## Yassine Hamoudi ##
## ##
## ------------------------------------------ ##
## ##
## Fichier Programme.s ##
## ##
## ------------------------------------------ ##
## ##
## Consulter aussi les fichiers joints : ##
## - README : informations sur l'utilisation du programme ##
## - Rapport.pdf : rapport du projet ##
## - TEST : plusieurs grilles de test ##
## ##
## ##
###################################################################
###################################################################
.data
#####################################################################
# #
# // LA GRILLE // #
# la grille initiale peut etre remplie ci-dessous, ou depuis #
# le terminal lors de l'execution du programme #
# (des grilles tests figurent dans le fichier TEST joint) #
# #
#####################################################################
grille :
.byte 5, 3, 0, 0, 7, 0, 0, 0, 0
.byte 6, 0, 0, 1, 9, 5, 0, 0, 0
.byte 0, 9, 8, 0, 0, 0, 0, 6, 0
.byte 8, 0, 0, 0, 6, 0, 0, 0, 3
.byte 4, 0, 0, 8, 0, 3, 0, 0, 1
.byte 7, 0, 0, 0, 2, 0, 0, 0, 6
.byte 0, 6, 0, 0, 0, 0, 2, 8, 0
.byte 0, 0, 0, 4, 1, 9, 0, 0, 5
.byte 0, 0, 0, 0, 8, 0, 0, 7, 9
##################################
# #
# // CHAINES DE CARACTERES // #
# #
##################################
debut : .asciiz "-------------- \n| SudoMips | \n--------------\n"
demande_strategie : .asciiz "\n Veuillez entrer la strategie a appliquer (0 : strategie MIN, 1 : strategie MAX) : \n \n"
demande_saisie : .asciiz "\n Veuillez entrer le mode de saisie de la grille initiale (0 : la grille a ete remplie dans le code source, 1 : la grille doit etre rentree manuellement) : \n \n"
demande_position_x : .asciiz "\n Saisissez la ligne du nombre a ajouter (1<=..<=9), entrez 0 pour mettre fin a la saisie de la grille initiale : \n \n"
demande_position_y : .asciiz "\n Saisissez la colonne du nombre a ajouter (1<=..<=9) : \n \n"
demande_nombre : .asciiz "\n Saisissez le nombre a mettre dans cette case : \n \n"
espace : .asciiz " | "
line_normal : .asciiz "\n | | | |\n | "
line_separate : .asciiz "\n |-----------+-----------+-----------|\n | "
line_end : .asciiz "\n |-----------+-----------+-----------|\n"
point : .asciiz "."
string_debut : .asciiz " \n Voici la grille initiale : \n \n"
string_fail : .asciiz " \n Aucune solution n'existe. \n"
string_success : .asciiz " \n Voici une solution a la grille : \n \n"
#################
# #
# // MAIN // #
# #
#################
.text
main :
# Usage des registres de sauvegarde :
# $s0 : 0 si strategie minimum, 10 si strategie maximum
# $s1 : 10 si strategie minimum, 0 si strategie maximum
# $s2 : 1 si strategie minimum, -1 si strategie maximum
# $s6 : utilise lors du remplissage manuel de la grille par l'utilisateur, contient la position de la case en cours de remplissage
# $s7 : utilise pour verifier que la grille de depart ne contient pas deja de conflits. Contient les positions successives testees.
la $a0, debut
li $v0, 4
syscall # on affiche "SudoMips"
jal remplir_user # l'utilisateur donne ses options (strategie, mode de remplissage de la grille)
la $a0, string_debut
li $v0, 4
syscall # on affiche "Voici la grille initiale :"
jal affichage # on affiche la grille de depart
jal grille_valide # on verifie que la grille initiale ne contient pas deja des conflits
beq $v0, $0, return_fail # si elle n'est pas fausse, on poursuit
jal backtracking # application de l'algo de backtracking
beq $v0, $0, return_fail # si $v0=0, l'algo n'a trouve aucune solution, sinon il a reussi a remplir la grille
return_success : # l'algo a trouve une solution
la $a0, string_success
li $v0, 4
syscall # on affiche : "Voici une solution a la grille :"
jal affichage # on affiche la grille remplie
li $v0, 10
syscall
return_fail : # il n'y a pas de solution
la $a0, string_fail
li $v0, 4
syscall # on affiche "Aucune solution n'existe."
li $v0, 10
syscall
#################################################################
# #
# // REMPLIR_USER // #
# permettre a l'utilisateur de remplir la grille initiale #
# et de choisir une strategie #
# #
# Entree : #
# #
# Sortie : #
# #
#################################################################
remplir_user :
sub $sp, $sp, 4
sw $ra, 0($sp) # on sauve l'adresse de retour sur la pile
remplir_user_strategie :
la $a0, demande_strategie # demander quelle strategie appliquer
li $v0, 4
syscall
li $v0, 5
syscall # dans v0 : 0 si strat MIN, 1 si strat MAX
move $s0, $v0 # dans s0 : strategie choisie (0 ou 1)
mul $s0, $s0, 10 # dans s0 : 0 si MIN, 10 si MAX
bne $s0, $0, remplir_user_strategie_max # on remplie $s1 et $s0 selon la strategie choisie (cf conventions de remplissage au debut du main)
remplir_user_strategie_min :
li $s1, 10
li $s2, 1
j remplir_user_saisie # on passe au remplissage de la grille initiale
remplir_user_strategie_max :
li $s1, 0
li $s2, -1
remplir_user_saisie :
la $a0, demande_saisie # demander si l'utilisateur souhaite remplir manuellement la grille
li $v0, 4
syscall
li $v0, 5
syscall # dans v0 : 0 si grille remplie directement dans le fichier, 1 si remplissage manuel depuis terminal
move $a0, $v0 # dans a0, type de remplissage choisie (0 ou 1)
jal init # on appelle init, qui va mettre des 0 ou des 10 dans les cases vides (depend de la strategie et du mode de remplissage choisi)
beq $a0, $0, remplir_user_end # si l'user a choisi un remplissage directement dans le fichier, on a fini. Sinon, on poursuit avec le remplissage manuel
jal affichage # on affiche la grille totalement vide
remplir_user_case : # remplissage manuel de la grille
la $a0, demande_position_x # demander une position x
li $v0, 4
syscall
li $v0, 5
syscall # mettre position_x dans $v0
move $s6, $v0 # mettre position_x dans $s6
beq $s6, $0, remplir_user_end # si c'est 0, on quitte
sub $s6, 1 # decalage de 1 (on compte les lignes de 0 a 8)
mul $s6, $s6, 9 # mettre dans s6 premiere case de la ligne s6
sub $s6, 1 # decalage de 1 (on compte les colonnes de 0 a 8)
la $a0, demande_position_y # demander une position y
li $v0, 4
syscall
li $v0, 5
syscall # mettre position_y dans $v0
add $s6, $s6, $v0 # dans s6 : case choisie par l'user
la $a0, demande_nombre # demander un nb
li $v0, 4
syscall
li $v0, 5
syscall # mettre nb dans $v0
sb $v0, grille+0($s6) # enregistrer le nb dans la grille
jal affichage # afficher la grille
j remplir_user_case # passer a la case suivante
remplir_user_end :
lw $ra, 0($sp) # on recupere l'adresse de retour
addi $sp, $sp, 4 # on depile le -1
jr $ra
###################################################################################################
# #
# // INIT // #
# initialise la grille initiale : met des 0 ou des 10 #
# si strategie MIN : #
# si remplissage manuel de la grille : mettre des 0 dans toutes les cases #
# si remplissage directement dans le fichier : remplacer les 10 eventuels par des 0 #
# si strategie MAX : #
# si remplissage manuel de la grille : mettre des 10 dans toutes les cases #
# si remplissage directement dans le fichier : remplacer les 0 eventuels par des 10 #
# #
# Entree : #
# $a0 : 0 si auto (ie depuis un fichier), 1 si manuel #
# #
# Sortie : #
# #
# #
###################################################################################################
init :
li $t0, -1 # va contenir la position courante dans la grille
beq $a0, $0, init_remplir_auto
init_remplir_manuel : # si l'utilisateur veut remplir manuellement
addi $t0, $t0, 1 # on va a la case suivante
beq $t0, 81, init_end # si fin de grille, on sort
sb $s0, grille+0($t0) # sinon on met s0 (0 ou 10) dans la case
j init_remplir_manuel
init_remplir_auto : # si l'utilisateur veut remplir automatiquement, permet d'uniformiser les 0 et 10 suivant la strat choisie
addi $t0, $t0, 1 # on va a la case suivante
beq $t0, 81, init_end # on a fini
lb $t1, grille+0($t0)
bne $t1, $s1, init_remplir_auto # si t1 = s1, on doit inverser son contenu
sb $s0, grille+0($t0)
j init_remplir_auto
init_end :
jr $ra
#########################################################
# #
# // VERIFICATEUR // #
# verifie si un nb mis a une certaine position #
# ne contredit pas le reste de la grille #
# #
# Entree : #
# $a0 : nb a tester #
# $a1 : position de la case a tester (0<=..<=80) #
# #
# Sortie : #
# $v0 : 0 si non valide #
# 1 si valide #
#########################################################
verificateur :
li $t9, 9
div $a1, $t9
mflo $t0 # ligne contenant a1
mfhi $t2 # colonne contenant a1 = premiere case de la colonne contenant a1
mul $t1, $t0, 9 # premiere case de la ligne contenant a1
addi $t3, $t1, 9 # premiere case de la ligne en dessous de a1 (81 si on est en bout de grille)
addi $t5, $t2, 81 # premiere case située sous la colonne contenant a1 (81<=..<=89)
verificateur_ligne_valide :
beq $t1, $t3, verificateur_colonne_valide # si on a fini la ligne, on teste la colonne
beq $t1, $a1, verificateur_avancer_horizontalement # si on arrive sur la case a1, on l'evite
lb $t4, grille + 0($t1) # contenue de la case ou on est
beq $t4, $a0, verificateur_fail # a0 n'est pas compatible avec cette case
verificateur_avancer_horizontalement : # la case actuelle est compatible avec a0, on avance
addi $t1, $t1, 1
j verificateur_ligne_valide
verificateur_colonne_valide :
beq $t2, $t5, verificateur_bloc_valide # si on a fini la colonne, on teste le bloc
beq $t2, $a1, verificateur_avancer_verticalement # si on arrive sur la case a1, on l'evite
lb $t4, grille + 0($t2) # contenue de la case
beq $t4, $a0, verificateur_fail # a1 n'est pas compatible avec cette case
verificateur_avancer_verticalement : # la case actuelle est compatible avec a0, on avance
addi $t2, $t2, 9
j verificateur_colonne_valide
verificateur_bloc_valide :
sub $t5, $t5, 81
div $t6, $t0, 3
mul $t6, $t6, 27 # premiere case de la ligne contenant la case en haut a gauche du bloc de a1
div $t7, $t5, 3
mul $t7, $t7, 3 # colonne contenant la case en haut a gauche du bloc contenant a1 (0, 3 ou 6)
add $t6, $t6, $t7 # case en haut a gauche du bloc contenant a1
addi $t7, $t6, 3 # fin de ligne
addi $t8, $t6, 27 # fin de bloc
verificateur_bloc_valide_parcours :
beq $t6, $t8, verificateur_success # on a verifie tout le bloc
beq $t6, $t7, verificateur_bloc_ligne_suivante # on a verifie une ligne
beq $t6, $a1, verificateur_bloc_case_suivante # on passe a la case suivante
lb $t4, grille + 0($t6) # contenue de la case
beq $t4, $a0, verificateur_fail # a1 n'est pas compatible avec cette case, on echoue
j verificateur_bloc_case_suivante # a1 est compatible : on avance
verificateur_bloc_ligne_suivante : # on passe a la ligne suivante du bloc
addi $t6, $t6, 6 # debut de la ligne
addi $t7, $t7, 9 # fin de la ligne
j verificateur_bloc_valide_parcours
verificateur_bloc_case_suivante : # on passe a la case suivante
addi $t6, $t6, 1
j verificateur_bloc_valide_parcours
verificateur_success :
li $v0, 1
jr $ra
verificateur_fail :
li $v0, 0
jr $ra
#########################################################
# #
# // GRILLE_VALIDE // #
# test si la grille en entree est valide #
# #
# Entree : #
# #
# Sortie : #
# $v0 : 0 si non valide, 1 sinon #
# #
#########################################################
grille_valide :
li $s7, -1 # cases successives de la grille
li $v0, 1 # valeur de retour
sub $sp, $sp, 4
sw $ra, 0($sp) # on sauve l'adresse de retour sur la pile
grille_valide_parcourir :
addi $s7, $s7, 1 # on va a la case suivante
beq $s7, 81, grille_valide_exit # on a parcouru toute la grille, on sort
lb $a0, grille + 0($s7) # contenue de la case ou on est
beq $a0, $s0, grille_valide_parcourir # 0 ou 10 dans la case actuelle, on la saute
move $a1, $s7 # on met s7 dans a1 (en vu de l'appel de la fonction verificateur)
jal verificateur # on lance la verification
beq $v0, $0, grille_valide_exit # conflit dans la case actuelle, on quitte avec $v0=0
j grille_valide_parcourir # pas de conflit, on passe a la case suivante
grille_valide_exit :
lw $ra, 0($sp) # on recupere l'adresse de retour
addi $sp, $sp, 4
jr $ra
#############################################################################
# #
# // BEST // #
# si strategie MIN : trouve le plus petit nb (stricement superieur a $a0) #
# pouvant etre mis dans la case $a1 #
# si strategie MAX : trouve le plus grand nb (stricement inferieur a $a0) #
# pouvant etre mis dans la case $a1 #
# #
# Entree : #
# $a0 : plus petit, ou plus grand, nb non permis #
# $a1 : position de la case a remplir (0<=..<=80) #
# #
# Sortie : #
# $v0 : si aucune nb possible, contient $s0 #
# sinon, contient un nb 1<=..<=9 possible #
# #
#############################################################################
best :
sub $sp, $sp, 4
sw $ra, 0($sp) # on sauve l'adresse de retour sur la pile
move $v0, $s0 # on initialise $v0, au cas ou on jump directement a best_exit_fail
best_parcourir :
add $a0, $a0, $s2 # on teste si le chiffre suivant, ou precedant, $a0 est possible
beq $a0, $s1, best_exit_fail # si on a teste tous les chiffres sans succes, on sort
jal verificateur # on lance la fonction de verification
beq $v0, $0, best_parcourir # le chiffre ne convient pas, on passe au suivant
move $v0, $a0 # sinon a0 est valide, on le met dans v0
best_exit :
lw $ra, 0($sp) # on recupere l'adresse de retour
addi $sp, $sp, 4
jr $ra
best_exit_fail :
move $v0, $s0 # on place s0 dans v0 (0 si strategie MIN, 10 si strategie MAX)
lw $ra, 0($sp) # on recupere l'adresse de retour
addi $sp, $sp, 4
jr $ra
#########################################################
# #
# // BACKTRACKING // #
# essayer de remplir la grille avec une strategie #
# de bactracking #
# #
# Entree : #
# #
# Sortie : #
# $v0 : 0 si aucune solution, 1 sinon #
# #
#########################################################
backtracking :
li $a1, -1 # position courante dans la grille (0<=..<=80)
sub $sp, $sp, 8
sw $ra, 4($sp) # on sauve l'adresse de retour sur la pile
sw $a1, 0($sp) # permet de detecter le fond de pile = -1
backtracking_parcourir :
addi $a1, $a1, 1 # on passe a la case suivante
beq $a1, 81, backtracking_success # on a reussit a tout remplir, on renvoie success
lb $a0, grille + 0($a1) # contenue de la case numero $a1
bne $a0, $s0, backtracking_parcourir # on ne touche pas a la case si elle est imposee (ie contient 0 (strat MIN) ou 10 (strat MAX))
backtracking_remplissage : # dans a1 : position de la case actuelle, dans a0 : plus petit nb non permis pour a1
jal best # on cherche un chiffre dans la case $a1, en accord avec la strategie choisie (si MIN : le nb choisie doit etre strictement superieur a a0, si MAX : strictement inferieur)
sb $v0, grille + 0($a1) # on met le chiffre obtenu dans la grille
beq $v0, $s0, backtracking_go_back # si c'est s0, c'est qu'aucun chiffre ne convient, il faut revenir en arriere
sub $sp, $sp, 4 # sinon, on se rappelle que cette position peut etre modifiee
sw $a1, 0($sp) # on empile la position qu'on vient de remplir
j backtracking_parcourir # on passe a la case suivante
backtracking_go_back :
lw $a1, 0($sp) # on recupere la precedente case remplie
beq $a1, -1, backtracking_fail # on s'assure qu'on n'est pas en fond de pile
addi $sp, $sp, 4 # on depile
lb $a0, grille + 0($a1) # contenue de la case numero $a1
j backtracking_remplissage # on esssaye de poursuivre le remplissage
backtracking_fail :
li $v0, 0 # argument de retour
addi $sp, $sp, 4 # on enleve le -1 de la pile
lw $ra, 0($sp) # on recupere l'adresse de retour
jr $ra
backtracking_depile : # tout depiler
addi $sp, $sp, 4 # on depile
lw $t0, 0($sp) # on recupere le haut de pile
beq $t0, -1, backtracking_success # si c'est le -1, on sort
j backtracking_depile # sinon on poursuit
backtracking_success :
lw $t0, 0($sp) # on recupere le haut de pile
bne $t0, -1, backtracking_depile # si c'est le -1, on continue
addi $sp, $sp, 4 # on depile le -1
lw $ra, 0($sp) # on recupere l'adresse de retour
li $v0, 1 # argument de retour
jr $ra
#############################################
# #
# // AFFICHAGE // #
# afficher la grille de sudoku actuelle #
# #
# Entree : #
# #
# Sortie : #
#############################################
affichage :
li $t0, 0 # case courante dans la grille (0 <= .. <=80)
j print_newseparate # commencer par l'affichage de la barre en haut
print_parcourir :
lb $a0, grille + 0($t0) # contenue de la case courante
li $v0, 1 # affichage de la case courante
beq $a0, $0, print_parcourir_vide # si la case contient un 0, on affiche un point (a la place de 0)
beq $a0, 10, print_parcourir_vide # si la case contient un 10, on affiche un point (a la place de 10)
li $v0, 1 # si la case contient un nb 1<=..<=9, on l'affiche
syscall
j print_parcourir_suite
print_parcourir_vide : # si la case contient un 0 ou un 10
la $a0, point
li $v0, 4 # on affiche un point
syscall
print_parcourir_suite :
la $a0, espace # afficher un espace ( | ) entre les nb
li $v0, 4
syscall
addi $t0, $t0, 1 # mise a jour de l'indice de la case courante
beq $t0, 81, print_end # afficher la ligne finale quand il faut
rem $t1, $t0, 27 # afficher les barres fortes quand il faut
beq $t1, $0, print_newseparate
rem $t1, $t0, 9 # afficher les barres faibles quand il faut
beq $t1, $0, print_newline
j print_parcourir
print_newline :
la $a0, line_normal # affichage d'une barre separatrice faible
li $v0, 4
syscall
j print_parcourir
print_newseparate :
la $a0, line_separate # affichage d'une barre separatrice forte
li $v0, 4
syscall
j print_parcourir
print_end :
la $a0, line_end # affichage de la barre finale
li $v0, 4
syscall
jr $ra