Your task is to write a program that finds a solution in the fewest moves possible single moves to a random Fifteen Puzzle Game.

For this task you will be using the following puzzle:


15 14  1  6
 9 11  4 12
 0 10  7  3
13  8  5  2


 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15  0

The output must show the moves' directions, like so: left, left, left, down, right... and so on.

There are two solutions, of fifty-two moves:

rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd

rrruldluuldrurdddluulurrrdlddruldluurddlulurruldrrdd

see: Pretty Print of Optimal Solution

Finding either one, or both is an acceptable result.


Extra credit.
Solve the following problem:

  0 12  9 13
 15 11 10 14
  3  7  2  5
  4  8  6  1



Related Task

 15 puzzle game
 A* search algorithm


 
/* ARM assembly AARCH64 Raspberry PI 3B */
/*  program puzzle15solvex64.s   */
/* this program is a adaptation algorithme C++ and go rosetta code */
/* thanck for the creators */ 
/* 1 byte by box on game board */
 
/* create a file with nano  */
/*  15,  2,   3,   4
    5,   6,   7,   1
    9,   10,  8,   11
   13,  14,  12, 0     */
 
/*   Run this programm : puzzle15solver64 <file name> */
/*   wait several minutes for résult */
 
/*******************************************/
/* Constantes file                         */
/*******************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeConstantesARM64.inc"
 
.equ TRUE, 1
.equ FALSE, 0
 
.equ SIZE,           4
.equ NBBOX,          SIZE * SIZE
.equ TAILLEBUFFER,   100
.equ NBMAXIELEMENTS, 100
 
.equ CONST_I,    1
.equ CONST_G,    8
.equ CONST_E,    2
.equ CONST_L,    4
 
/*********************************/
/* Initialized data              */
/*********************************/
.data
szMessTitre:           .asciz "File name : "
sMessResult:           .ascii " "
sMessValeur:           .fill 22, 1, ' '             // size => 21
szCarriageReturn:      .asciz "\n"
szMessCounterSolution: .asciz "Solution in @ moves : \n"
 
szMessErreur:          .asciz "Error detected.\n"
szMessImpossible:      .asciz "!!! Impossible solution !!!\n"
szMessErrBuffer:       .asciz "buffer size too less !!"
szMessSpaces:          .asciz "    "
 
qTabNr:  .quad 3, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3
qTabNc:  .quad 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss
.align 8
sZoneConv:      .skip 24
qAdrHeap:       .skip 8
tbBox:          .skip SIZE * SIZE           // game boxes
qAdrFicName:    .skip 8
qTabN0:         .skip 8 * NBMAXIELEMENTS    // empty box
qTabN3:         .skip 8 * NBMAXIELEMENTS    // moves
qTabN4:         .skip 8 * NBMAXIELEMENTS    // ????
qTabN2:         .skip 8 * NBMAXIELEMENTS    // table game address
sBuffer:        .skip TAILLEBUFFER
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:                            // INFO: main
    mov x0,sp                    // stack address for load parameter
    bl traitFic                  // read file and store value in array
    cmp x0,#-1
    beq 100f                     // error ?
 
    ldr x0,qAdrtbBox
    bl displayGame               // display array game
 
    ldr x0,qAdrtbBox              // control if solution exists
    bl controlSolution
    cmp x0,#TRUE
    beq 1f
    ldr x0,qAdrszMessImpossible  // no solution !!!
    bl affichageMess
    b 100f
 
1:
 
    ldr x0,qAdrtbBox
    ldr x9,qAdrqTabN2
    str x0,[x9]                  // N2 address global
    mov x10,#0                   // variable _n global
    mov x12,#0                   // variable n global 
    bl searchSolution
    cmp x0,#TRUE
    bne 100f                     // no solution ?
    ldr x3,qAdrqTabN2
    ldr x0,[x3,x12,lsl #3]       // visual solution control
    bl displayGame
    mov x0,x12                   // move counter
    ldr x1,qAdrsZoneConv
    bl conversion10              // conversion counter
    ldr x0,qAdrszMessCounterSolution
    bl strInsertAtCharInc
    ldr x1,qAdrsZoneConv
    bl affichageMess
    ldr x5,qAdrqTabN3
    ldr x3,qAdrsBuffer
    mov x2,#1
    mov x4,#0
2:                                // loop solution display 
    ldr x1,[x5,x2,lsl 3]
    cmp x2,#TAILLEBUFFER
    bge 99f
    strb w1,[x3,x4]
    add x4,x4,#1
    add x2,x2,#1
    cmp x2,x12
    ble 2b
    mov x1,#0
    strb w1,[x3,x4]                 // zéro final
    mov x0,x3
    bl affichageMess
    ldr x0,qAdrszCarriageReturn
    bl affichageMess
 
    b 100f
 
99:
    ldr x0,qAdrszMessErrBuffer
    bl affichageMess
100:                                 // standard end of the program 
    mov x0, #0                       // return code
    mov x8, #EXIT                    // request to exit program
    svc #0                           // perform the system call
 
qAdrtbBox:                  .quad tbBox
qAdrqTabN0:                .quad qTabN0
qAdrqTabN2:                .quad qTabN2
qAdrqTabN3:                .quad qTabN3
qAdrqTabN4:                .quad qTabN4
qAdrszMessCounterSolution: .quad szMessCounterSolution
qAdrszMessImpossible:      .quad szMessImpossible
qAdrszMessErrBuffer:       .quad szMessErrBuffer
qAdrsZoneConv:             .quad sZoneConv
/******************************************************************/
/*      search    Solution                                        */ 
/******************************************************************/
searchSolution:                  // INFO: searchSolution
    stp x1,lr,[sp,-16]!          // save  registres
    stp x2,x3,[sp,-16]!          // save  registres
    stp x4,x5,[sp,-16]!          // save  registres
    stp x6,x7,[sp,-16]!          // save  registres
    stp x8,x9,[sp,-16]!          // save  registres
                                 // address allocation place on the heap
    mov x0,#0                    // allocation place heap
    mov x8,BRK                   // call system 'brk'
    svc #0
    cmp x0,#-1                   // allocation error
    beq 99f
    ldr x1,qAdrqAdrHeap
    str x0,[x1]                  // store heap address
    bl functionFN
    ldr x3,qAdrqTabN2
    ldr x0,[x3,x12,lsl #3]       // last current game
    bl gameOK                    // it is Ok ?
    cmp x0,#TRUE
    beq 100f                     // yes --> end
 
    ldr x1,qAdrqAdrHeap          // free up resources
    ldr x0,[x1]                  // restaur start address heap
    mov x8,BRK                   // call system 'brk'
    svc #0
    cmp x0,#-1                   // allocation error
    beq 99f
    add x10,x10,#1               // _n
    mov x12,#0                   // n
    bl searchSolution            // next recursif call
    b 100f
99:
    ldr x0,qAdrszMessErreur
    bl affichageMess
100:
    ldp x8,x9,[sp],16            // restaur des  2 registres
    ldp x6,x7,[sp],16            // restaur des  2 registres
    ldp x4,x5,[sp],16            // restaur des  2 registres
    ldp x2,x3,[sp],16            // restaur des  2 registres
    ldp x1,lr,[sp],16            // restaur des  2 registres
    ret
qAdrszMessErreur:           .quad szMessErreur
qAdrqAdrHeap:               .quad qAdrHeap
/******************************************************************/
/*     Fonction FN                                                */ 
/******************************************************************/
functionFN:                      // INFO: functionFN
    stp x1,lr,[sp,-16]!          // save  registres
    ldr x4,qAdrqTabN3
    ldr x3,[x4,x12,lsl #3]
    ldr x5,qAdrqTabN0            // load position empty box
    ldr x6,[x5,x12,lsl #3]
    cmp x6,#15                   // last box
    bne 2f
    cmp x3,#'R'
    bne 11f
    mov x0,#CONST_G
    bl functionFZ
    b 100f
11:
    cmp x3,#'D'
    bne 12f
    mov x0,#CONST_L
    bl functionFZ
    b 100f
12:
    mov x0,#CONST_G + CONST_L
    bl functionFZ
    b 100f
 
2:
    cmp x6,#12
    bne 3f
    cmp x3,#'L'
    bne 21f
    mov x0,#CONST_G
    bl functionFZ
    b 100f
21:
    cmp x3,#'D'
    bne 22f
    mov x0,#CONST_E
    bl functionFZ
    b 100f
22:
    mov x0,#CONST_E + CONST_G
    bl functionFZ
    b 100f
3:
    cmp x6,#13
    beq 30f
    cmp x6,#14
    bne 4f
30:
    cmp x3,#'L'
    bne 31f
    mov x0,#CONST_G + CONST_L
    bl functionFZ
    b 100f
31:
    cmp x3,#'R'
    bne 32f
    mov x0,#CONST_G + CONST_E
    bl functionFZ
    b 100f
32:
    cmp x3,#'D'
    bne 33f
    mov x0,#CONST_E + CONST_L
    bl functionFZ
    b 100f
33:
    mov x0,#CONST_L + CONST_E + CONST_G
    bl functionFZ
    b 100f
4:
    cmp x6,#3
    bne 5f
    cmp x3,#'R'
    bne 41f
    mov x0,#CONST_I
    bl functionFZ
    b 100f
41:
    cmp x3,#'U'
    bne 42f
    mov x0,#CONST_L
    bl functionFZ
    b 100f
42:
    mov x0,#CONST_I + CONST_L
    bl functionFZ
    b 100f
5:
    cmp x6,#0
    bne 6f
    cmp x3,#'L'
    bne 51f
    mov x0,#CONST_I
    bl functionFZ
    b 100f
51:
    cmp x3,#'U'
    bne 52f
    mov x0,#CONST_E
    bl functionFZ
    b 100f
52:
    mov x0,#CONST_I + CONST_E
    bl functionFZ
    b 100f
6:
    cmp x6,#1
    beq 60f
    cmp x6,#2
    bne 7f
60:
    cmp x3,#'L'
    bne 61f
    mov x0,#CONST_I + CONST_L
    bl functionFZ
    b 100f
61:
    cmp x3,#'R'
    bne 62f
    mov x0,#CONST_E + CONST_I
    bl functionFZ
    b 100f
62:
    cmp x3,#'U'
    bne 63f
    mov x0,#CONST_E + CONST_L
    bl functionFZ
    b 100f
63:
    mov x0,#CONST_I + CONST_E + CONST_L
    bl functionFZ
    b 100f
7:
    cmp x6,#7
    beq 70f
    cmp x6,#11
    bne 8f
70:
    cmp x3,#'R'
    bne 71f
    mov x0,#CONST_I + CONST_G
    bl functionFZ
    b 100f
71:
    cmp x3,#'U'
    bne 72f
    mov x0,#CONST_G + CONST_L
    bl functionFZ
    b 100f
72:
    cmp x3,#'D'
    bne 73f
    mov x0,#CONST_I + CONST_L
    bl functionFZ
    b 100f
73:
    mov x0,#CONST_I + CONST_G + CONST_L
    bl functionFZ
    b 100f
8:
    cmp x6,#4
    beq 80f
    cmp x6,#8
    bne 9f
80:
    cmp x3,#'D'
    bne 81f
    mov x0,#CONST_I + CONST_E
    bl functionFZ
    b 100f
81:
    cmp x3,#'U'
    bne 82f
    mov x0,#CONST_G + CONST_E
    bl functionFZ
    b 100f
82:
    cmp x3,#'L'
    bne 83f
    mov x0,#CONST_I + CONST_G
    bl functionFZ
    b 100f
83:
    mov x0,#CONST_G + CONST_E + CONST_I
    bl functionFZ
    b 100f
9:
    cmp x3,#'D'
    bne 91f
    mov x0,#CONST_I + CONST_E + CONST_L
    bl functionFZ
    b 100f
91:
    cmp x3,#'L'
    bne 92f
    mov x0,#CONST_I + CONST_G + CONST_L
    bl functionFZ
    b 100f
92:
    cmp x3,#'R'
    bne 93f
    mov x0,#CONST_I + CONST_G + CONST_E
    bl functionFZ
    b 100f
93:
    cmp x3,#'U'
    bne 94f
    mov x0,#CONST_G + CONST_E +  CONST_L
    bl functionFZ
    b 100f
94:
    mov x0,#CONST_G + CONST_L + CONST_I + CONST_E
    bl functionFZ
    b 100f
 
99:                             // error
    ldr x0,qAdrszMessErreur
    bl affichageMess
100:
    ldp x1,lr,[sp],16           // restaur des  2 registres
    ret
 
/******************************************************************/
/*     function FZ                           */ 
/*                                                 */
/***************************************************************/
/* x0 contains variable w           */
functionFZ:                    // INFO: functionFZ
    stp x1,lr,[sp,-16]!        // save  registres
    stp x2,x3,[sp,-16]!        // save  registres
    mov x2,x0 
    and x1,x2,#CONST_I
    cmp x1,#0
    ble 1f
    bl functionFI
    bl functionFY
    cmp x0,#TRUE
    beq 100f
    sub x12,x12,#1              // variable n
1:
    ands x1,x2,#CONST_G
    ble 2f
    bl functionFG
    bl functionFY
    cmp x0,#TRUE
    beq 100f
    sub x12,x12,#1              // variable n
2:
    ands x1,x2,#CONST_E
    ble 3f
    bl functionFE
    bl functionFY
    cmp x0,#TRUE
    beq 100f
    sub x12,x12,#1              // variable n
3:
    ands x1,x2,#CONST_L
    ble 4f
    bl functionFL
    bl functionFY
    cmp x0,#TRUE
    beq 100f
    sub x12,x12,#1              // variable n
4:
    mov x0,#FALSE
100:
    ldp x2,x3,[sp],16           // restaur des  2 registres
    ldp x1,lr,[sp],16           // restaur des  2 registres
    ret
/******************************************************************/
/*               function FY                                 */ 
/******************************************************************/
functionFY:                    // INFO: functionFY
    stp x1,lr,[sp,-16]!        // save  registres
    ldr x1,qAdrqTabN2
    ldr x0,[x1,x12,lsl #3]
    bl gameOK                  // game OK ?
    cmp x0,#TRUE
    beq 100f
    ldr x1,qAdrqTabN4
    ldr x0,[x1,x12,lsl #3]
    cmp x0,x10
    bgt 1f
    bl functionFN
    b 100f
1:
    mov x0,#FALSE
100:
    ldp x1,lr,[sp],16           // restaur des  2 registres
    ret
/******************************************************************/
/*     the empty box is down                                     */ 
/******************************************************************/
functionFI:                       // INFO: functionFI
    stp x1,lr,[sp,-16]!          // save  registres
    stp x2,x3,[sp,-16]!          // save  registres
    stp x4,x5,[sp,-16]!          // save  registres
    stp x6,x7,[sp,-16]!          // save  registres
    stp x8,x9,[sp,-16]!          // save  registres
    ldr x0,qAdrqTabN0
    ldr x1,[x0,x12,lsl #3]        // empty box
    add x2,x1,#4
    ldr x3,[x9,x12,lsl #3]        // load game current
    ldrb w4,[x3,x2]               // load box down empty box
    add x5,x12,#1                 // n+1
    add x8,x1,#4                  // new position empty case
    str x8,[x0,x5,lsl #3]         // store new position empty case
    ldr x6,qAdrqTabN3
 
    mov x7,#'D'                   // down
    str x7,[x6,x5,lsl #3]         // store move
    ldr x6,qAdrqTabN4
    ldr x7,[x6,x12,lsl #3]
    str x7,[x6,x5,lsl #3]         // N4 (n+1) = n4(n)
    mov x0,x3
    bl createGame                 // create copy game
    ldrb w3,[x0,x1]               // and inversion box
    ldrb w8,[x0,x2]
    strb w8,[x0,x1]
    strb w3,[x0,x2]
    str x0,[x9,x5,lsl #3]         // store new game in table
    lsr x1,x1,#2                  // line position empty case = N°/ 4
    ldr x0,qAdrqTabNr
    ldr x2,[x0,x4,lsl #3]         // load N° line box moved
    cmp x2,x1                     // compare ????
    ble 1f
    add x7,x7,#1                  // and increment ????
    str x7,[x6,x5,lsl #3]
1:
    add x12,x12,#1                // increment N
    ldp x8,x9,[sp],16           // restaur des  2 registres
    ldp x6,x7,[sp],16           // restaur des  2 registres
    ldp x4,x5,[sp],16           // restaur des  2 registres
    ldp x2,x3,[sp],16           // restaur des  2 registres
    ldp x1,lr,[sp],16           // restaur des  2 registres
    ret
qAdrqTabNr:        .quad qTabNr
qAdrqTabNc:        .quad qTabNc
/******************************************************************/
/*     empty case UP   see explain in english in function FI      */ 
/******************************************************************/
functionFG:                      // INFO: functionFG
    stp x1,lr,[sp,-16]!          // save  registres
    stp x2,x3,[sp,-16]!          // save  registres
    stp x4,x5,[sp,-16]!          // save  registres
    stp x6,x7,[sp,-16]!          // save  registres
    stp x8,x9,[sp,-16]!          // save  registres
    ldr x0,qAdrqTabN0
    ldr x1,[x0,x12,lsl #3]       // case vide
    sub x2,x1,#4                 // position case au dessus
    ldr x3,[x9,x12,lsl #3]       // extrait jeu courant
    ldrb w4,[x3,x2]              // extrait le contenu case au dessus
    add x5,x12,#1                // N+1 = N
    sub x8,x1,#4                 // nouvelle position case vide
    str x8,[x0,x5,lsl #3]        // et on la stocke
    ldr x6,qAdrqTabN3
    mov x7,#'U'                  // puis on stocke le code mouvement
    str x7,[x6,x5,lsl #3]
    ldr x6,qAdrqTabN4
    ldr x7,[x6,x12,lsl #3]
    str x7,[x6,x5,lsl #3]        // N4 (N+1) = N4 (N)
    mov x0,x3                    // jeu courant
    bl createGame                // création nouveau jeu
    ldrb w3,[x0,x1]              // et echange les 2 cases
    ldrb w8,[x0,x2]
    strb w8,[x0,x1]
    strb w3,[x0,x2]
    str x0,[x9,x5,lsl #3]        // stocke la nouvelle situation 
    lsr x1,x1,#2                 // ligne case vide = position /4
    ldr x0,qAdrqTabNr
    ldr x2,[x0,x4,lsl #3]        // extrait table à la position case
    cmp x2,x1                    // et comparaison ???
    bge 1f
    add x7,x7,#1                 // puis increment N4 de 1  ???
    str x7,[x6,x5,lsl #3]
1:
    add x12,x12,#1               // increment de N
    ldp x8,x9,[sp],16           // restaur des  2 registres
    ldp x6,x7,[sp],16           // restaur des  2 registres
    ldp x4,x5,[sp],16           // restaur des  2 registres
    ldp x2,x3,[sp],16           // restaur des  2 registres
    ldp x1,lr,[sp],16           // restaur des  2 registres
    ret
/******************************************************************/
/*    empty case go right see explain finction FI ou FG en français */ 
/******************************************************************/
functionFE:                       // INFO: functionFE
    stp x1,lr,[sp,-16]!          // save  registres
    stp x2,x3,[sp,-16]!          // save  registres
    stp x4,x5,[sp,-16]!          // save  registres
    stp x6,x7,[sp,-16]!          // save  registres
    stp x8,x9,[sp,-16]!          // save  registres
    ldr x0,qAdrqTabN0
    ldr x1,[x0,x12,lsl #3]
    add x2,x1,#1
    ldr x3,[x9,x12,lsl #3]
    ldrb w4,[x3,x2]               // extrait le contenu case 
    add x5,x12,#1
    add x8,x1,#1
    str x8,[x0,x5,lsl #3]         // nouvelle case vide
    ldr x6,qAdrqTabN3
    mov x7,#'R'
    str x7,[x6,x5,lsl #3]         // mouvement
    ldr x6,qAdrqTabN4
    ldr x7,[x6,x12,lsl #3]
    str x7,[x6,x5,lsl #3]         // N4 ??
    mov x0,x3
    bl createGame
    ldrb w3,[x0,x1]               // exchange two boxes
    ldrb w8,[x0,x2]
    strb w8,[x0,x1]
    strb w3,[x0,x2]
    str x0,[x9,x5,lsl #3]         // stocke la nouvelle situation 
    lsr x3,x1,#2
    sub x1,x1,x3,lsl #2
    ldr x0,qAdrqTabNc
    ldr x2,[x0,x4,lsl #3]         // extrait table à la position case
    cmp x2,x1
    ble 1f
    add x7,x7,#1
    str x7,[x6,x5,lsl #3]
1:
    add x12,x12,#1
    ldp x8,x9,[sp],16           // restaur des  2 registres
    ldp x6,x7,[sp],16           // restaur des  2 registres
    ldp x4,x5,[sp],16           // restaur des  2 registres
    ldp x2,x3,[sp],16           // restaur des  2 registres
    ldp x1,lr,[sp],16           // restaur des  2 registres
    ret
/******************************************************************/
/*     empty box go left see explain function FI ou FG en français */ 
/******************************************************************/
functionFL:                       // INFO: functionFL
    stp x1,lr,[sp,-16]!          // save  registres
    stp x2,x3,[sp,-16]!          // save  registres
    stp x4,x5,[sp,-16]!          // save  registres
    stp x6,x7,[sp,-16]!          // save  registres
    stp x8,x9,[sp,-16]!          // save  registres
    ldr x0,qAdrqTabN0
    ldr x1,[x0,x12,lsl #3]        // case vide
    sub x2,x1,#1
    ldr x3,[x9,x12,lsl #3]       // extrait jeu courant
    ldrb w4,[x3,x2]              // extrait le contenu case 
    add x5,x12,#1
    sub x8,x1,#1
    str x8,[x0,x5,lsl #3]         // nouvelle case vide
    ldr x6,qAdrqTabN3
    mov x7,#'L'
    str x7,[x6,x5,lsl #3]         // mouvement
    ldr x6,qAdrqTabN4
    ldr x7,[x6,x12,lsl #3]
    str x7,[x6,x5,lsl #3]         // N4 ??
    mov x0,x3
    bl createGame
    ldrb w3,[x0,x1]               // exchange two boxes
    ldrb w8,[x0,x2]
    strb w8,[x0,x1]
    strb w3,[x0,x2]
    str x0,[x9,x5,lsl #3]         // stocke la nouvelle situation 
    lsr x3,x1,#2
    sub x1,x1,x3,lsl #2           // compute remainder
    ldr x0,qAdrqTabNc
    ldr x2,[x0,x4,lsl #3]         // extrait table colonne à la position case
    cmp x2,x1
    bge 1f
    add x7,x7,#1
    str x7,[x6,x5,lsl #3]
1:
    add x12,x12,#1
    ldp x8,x9,[sp],16           // restaur des  2 registres
    ldp x6,x7,[sp],16           // restaur des  2 registres
    ldp x4,x5,[sp],16           // restaur des  2 registres
    ldp x2,x3,[sp],16           // restaur des  2 registres
    ldp x1,lr,[sp],16           // restaur des  2 registres
    ret
/******************************************************************/
/*     create new Game                                            */ 
/******************************************************************/
/* x0 contains box address            */
/* x0 return address new game  */
createGame:                          // INFO: createGame
    stp x1,lr,[sp,-16]!          // save  registres
    stp x2,x3,[sp,-16]!          // save  registres
    stp x4,x5,[sp,-16]!          // save  registres
    stp x6,x7,[sp,-16]!          // save  registres
    stp x8,x9,[sp,-16]!          // save  registres
    mov x4,x0                    // save value
    mov x0,#0                    // allocation place heap
    mov x8,BRK                   // call system 'brk'
    svc #0
    cmp x0,#-1                   // allocation error
    beq 99f
    mov x5,x0                    // save address heap for output string
    add x0,x0,#SIZE * SIZE       // reservation place one element
    mov x8,BRK                   // call system 'brk'
    svc #0
    cmp x0,#-1                   // allocation error
    beq 99f
    mov x2,#0
1:                               // loop copy boxes
    ldrb w3,[x4,x2]
    strb w3,[x5,x2]
    add x2,x2,#1
    cmp x2,#NBBOX
    blt 1b
    add x11,x11,#1
    mov x0,x5
    b 100f
99:                              // error
    ldr x0,qAdrszMessErreur
    bl affichageMess
100:
    ldp x8,x9,[sp],16           // restaur des  2 registres
    ldp x6,x7,[sp],16           // restaur des  2 registres
    ldp x4,x5,[sp],16           // restaur des  2 registres
    ldp x2,x3,[sp],16           // restaur des  2 registres
    ldp x1,lr,[sp],16           // restaur des  2 registres
    ret
/******************************************************************/
/*     read file                                                   */ 
/******************************************************************/
/* x0 contains address stack begin           */
traitFic:                             // INFO: traitFic
    stp x1,lr,[sp,-16]!          // save  registres
    stp x2,x3,[sp,-16]!          // save  registres
    stp x4,x5,[sp,-16]!          // save  registres
    stp x6,x7,[sp,-16]!          // save  registres
    stp x8,fp,[sp,-16]!          // save  registres
    mov fp,x0                         //  fp <- start address
    ldr x4,[fp]                       // number of Command line arguments
    cmp x4,#1
    ble 99f
    add x5,fp,#16                      // second parameter address 
    ldr x5,[x5]
    ldr x0,qAdrqAdrFicName
    str x5,[x0]
    ldr x0,qAdrszMessTitre
    bl affichageMess                  // display string
    mov x0,x5
    bl affichageMess 
    ldr x0,qAdrszCarriageReturn
    bl affichageMess                  // display carriage return
 
    mov x0,AT_FDCWD
    mov x1,x5                         // file name
    mov x2,#O_RDWR                    // flags    
    mov x3,#0                         // mode 
    mov x8, #OPEN                     // call system OPEN 
    svc 0 
    cmp x0,#0                         // error ?
    ble 99f
    mov x7,x0                         // File Descriptor
    ldr x1,qAdrsBuffer                // buffer address
    mov x2,#TAILLEBUFFER              // buffer size
    mov x8,#READ                      // read file
    svc #0
    cmp x0,#0                         // error ?
    blt 99f
    // extraction datas
    ldr x1,qAdrsBuffer                // buffer address
    add x1,x1,x0
    mov x0,#0                         // store zéro final
    strb w0,[x1] 
    ldr x0,qAdrtbBox                   // game box address
    ldr x1,qAdrsBuffer                // buffer address
    bl extracDatas
                                      // close file
    mov x0,x7
    mov x8, #CLOSE 
    svc 0 
    mov x0,#0
    b 100f
99:                                   // error
    ldr x0,qAdrszMessErreur           // error message
    bl   affichageMess
    mov x0,#-1
100:
    ldp x8,fp,[sp],16           // restaur des  2 registres
    ldp x6,x7,[sp],16           // restaur des  2 registres
    ldp x4,x5,[sp],16           // restaur des  2 registres
    ldp x2,x3,[sp],16           // restaur des  2 registres
    ldp x1,lr,[sp],16           // restaur des  2 registres
    ret
qAdrqAdrFicName:              .quad qAdrFicName
qAdrszMessTitre:              .quad szMessTitre
qAdrsBuffer:                  .quad sBuffer
/******************************************************************/
/*     extrac digit file buffer                                   */ 
/******************************************************************/
/* x0 contains boxs address           */
/* x1 contains buffer address         */
extracDatas:                     // INFO: extracDatas
    stp x1,lr,[sp,-16]!          // save  registres
    stp x2,x3,[sp,-16]!          // save  registres
    stp x4,x5,[sp,-16]!          // save  registres
    stp x6,x7,[sp,-16]!          // save  registres
    stp x8,x9,[sp,-16]!          // save  registres
    mov x7,x0
    mov x6,x1
    mov x2,#0                    // string buffer indice
    mov x4,x1                    // start digit ascii
    mov x5,#0                    // box index
1:
    ldrb w3,[x6,x2]
    cmp x3,#0                    // datas end ?
    beq 4f
    cmp x3,#0xA                  // line end ?
    beq 2f
    cmp x3,#','                  // box end ?
    beq 3f
    add x2,x2,#1
    b 1b
2:
    mov x3,#0
    strb w3,[x6,x2]              // zero final
    add x3,x2,#1                 // next character
    ldrb w3,[x6,x3] 
    cmp x3,#0xD                  // line return 
    bne 21f
    add x2,x2,#2                 // yes
    b 4f
21:
    add x2,x2,#1
    b 4f
3:
    mov x3,#0                    // zero final
    strb w3,[x6,x2]
    add x2,x2,#1
4:  
    mov x0,x4                    // conversion character ascii in integer
    bl conversionAtoD
    strb w0,[x7,x5]              // and store value on 1 byte box
    cmp x0,#0                    // empty box ?
    bne 5f
    ldr x0,qAdrqTabN0
    str x5,[x0]                  // empty box in item zéro
5:
    add x5,x5,#1                 // increment counter boxes
    cmp x5,#NBBOX                // number box = maxi ?
    bge 100f 
    add x4,x6,x2                 // new start address digit ascii
    b 1b
100:
    ldp x8,x9,[sp],16           // restaur des  2 registres
    ldp x6,x7,[sp],16           // restaur des  2 registres
    ldp x4,x5,[sp],16           // restaur des  2 registres
    ldp x2,x3,[sp],16           // restaur des  2 registres
    ldp x1,lr,[sp],16           // restaur des  2 registres
    ret
/******************************************************************/
/*     control of the game solution                                      */ 
/******************************************************************/
/* x0 contains boxs address           */
/* x0 returns 0 if not possible       */
/* x0 returns 1 if possible           */
controlSolution:                 // INFO: controlSolution
    stp x1,lr,[sp,-16]!          // save  registres
    stp x2,x3,[sp,-16]!          // save  registres
    stp x4,x5,[sp,-16]!          // save  registres
    stp x6,x7,[sp,-16]!          // save  registres
    stp x8,x9,[sp,-16]!          // save  registres
    mov x5,x0
    ldr x8,qAdrqTabN0
    ldr x8,[x8]                  // empty box
    //mov x7,#0
    cmp x8,#1
    cset x7,eq
    beq 1f
    cmp x8,#3
    cset x7,eq
    beq 1f
    cmp x8,#4
    cset x7,eq
    beq 1f
    cmp x8,#6
    cset x7,eq
    beq 1f
    cmp x8,#9
    cset x7,eq
    beq 1f
    cmp x8,#11
    cset x7,eq
    beq 1f
    cmp x8,#12
    cset x7,eq
    beq 1f
    cmp x8,#14
    cset x7,eq
1:
    mov x9,NBBOX - 1
    sub x6,x9,x8
    add x7,x7,x6
                                 // count permutations
    mov x1,#-1
    mov x6,#0
2:
    add x1,x1,#1
    cmp x1,#NBBOX
    bge 80f
    cmp x1,x8
    beq 2b
    ldrb w3,[x5,x1]
    mov x2,x1
3:
    add x2,x2,#1
    cmp x2,#NBBOX
    bge 2b
    cmp x2,x8
    beq 3b
    ldrb w4,[x5,x2]
    cmp x4,x3
    cinc x6,x6,lt
    b 3b
80:
    add x6,x6,x7
    tst x6,#1
    cset x0,eq
100:
    ldp x8,x9,[sp],16           // restaur des  2 registres
    ldp x6,x7,[sp],16           // restaur des  2 registres
    ldp x4,x5,[sp],16           // restaur des  2 registres
    ldp x2,x3,[sp],16           // restaur des  2 registres
    ldp x1,lr,[sp],16           // restaur des  2 registres
    ret    
/******************************************************************/
/*     game Ok ?                                      */ 
/******************************************************************/
/* x0 contains boxs address           */
gameOK:                          // INFO: gameOK
    stp x1,lr,[sp,-16]!          // save  registres
    stp x2,x3,[sp,-16]!          // save  registres
    stp x4,x5,[sp,-16]!          // save  registres
    mov x2,#0
    ldrb w3,[x0,x2]
    cmp x3,#0
    bne 0f
    mov x3,#0xF
0:
    add x2,x2,#1
1:
    ldrb w4,[x0,x2]
    cmp x4,#0
    bne 11f
    mov x3,#0xF
11:
    cmp x4,x3
    ble 99f
    mov x3,x4
    add x2,x2,#1
    cmp x2,#NBBOX -2
    ble 1b
    mov x0,#TRUE                  // game Ok
    b 100f
99:
   mov  x0,#FALSE              // game not Ok
100:
    ldp x4,x5,[sp],16           // restaur des  2 registres
    ldp x2,x3,[sp],16           // restaur des  2 registres
    ldp x1,lr,[sp],16           // restaur des  2 registres
    ret
/******************************************************************/
/*     display game                                       */ 
/******************************************************************/
/* x0 contains boxs address           */
displayGame:                            // INFO: displayGame
    stp x1,lr,[sp,-16]!          // save  registres
    stp x2,x3,[sp,-16]!          // save  registres
    stp x4,x5,[sp,-16]!          // save  registres
    mov x4,x0
    ldr x0,qAdrszMessTitre
    bl affichageMess            // display titre
    ldr x0,qAdrqAdrFicName
    ldr x0,[x0]
    bl affichageMess            // display string
    ldr x0,qAdrszCarriageReturn
    bl affichageMess            // display line return
    mov x2,#0
    ldr x1,qAdrsMessValeur
1:
    ldrb w0,[x4,x2]
    cmp x0,#0
    beq 3f
    bl conversion10             // call conversion decimal
    cmp x0,1
    bne 2f
    mov x0,#0x002020
    str w0,[x1,#1]              // zéro final
    b 4f
2:
    mov x0,#0x20
    str w0,[x1,#2]              // zéro final
    b 4f
3:
    ldr x0,iSpaces              // store spaces to empty case
    str w0,[x1]
4:
    ldr x0,qAdrsMessResult
    bl affichageMess            // display message
    add x0,x2,#1
    tst x0,#0b11
    bne 5f
    ldr x0,qAdrszCarriageReturn
    bl affichageMess            // display message
5:
    add x2,x2,#1
    cmp x2,#NBBOX - 1
    ble 1b
    ldr x0,qAdrszCarriageReturn
    bl affichageMess            // display line return
 
100:
    ldp x4,x5,[sp],16           // restaur des  2 registres
    ldp x2,x3,[sp],16           // restaur des  2 registres
    ldp x1,lr,[sp],16           // restaur des  2 registres
    ret
iSpaces:                       .quad 0x00202020       // spaces
qAdrszCarriageReturn:          .quad szCarriageReturn
qAdrsMessValeur:               .quad sMessValeur
qAdrsMessResult:               .quad sMessResult
/********************************************************/
/*        File Include fonctions                        */
/********************************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
 