 


Task

Implement the Fifteen Puzzle Game.



The   15-puzzle   is also known as:

   Fifteen Puzzle
   Gem Puzzle
   Boss Puzzle
   Game of Fifteen
   Mystic Square
   14-15 Puzzle
   and some others.


Related Tasks

   15 Puzzle Solver
   16 Puzzle Game


 
 
/* ARM assembly Raspberry PI  */
/*  program puzzle15.s   */
 
/************************************/
/* Constantes                       */
/************************************/
.equ STDIN,  0     @ Linux input console
.equ STDOUT, 1     @ Linux output console
.equ EXIT,   1     @ Linux syscall
.equ READ,   3     @ Linux syscall
.equ WRITE,  4     @ Linux syscall
 
.equ IOCTL,     0x36  @ Linux syscall
.equ SIGACTION, 0x43  @ Linux syscall
.equ SYSPOLL,   0xA8  @ Linux syscall
 
.equ TCGETS,    0x5401
.equ TCSETS,    0x5402
.equ ICANON,    2
.equ ECHO,     10
.equ POLLIN,    1
 
.equ SIGINT,   2    @ Issued if the user sends an interrupt signal (Ctrl + C)
.equ SIGQUIT,  3    @ Issued if the user sends a quit signal (Ctrl + D)
.equ SIGTERM, 15    @ Software termination signal (sent by kill by default)
.equ SIGTTOU, 22    @ 
 
.equ NBBOX,  16
.equ TAILLEBUFFER,   10
 
/*******************************************/
/* Structures                               */
/********************************************/
/* structure termios see doc linux*/
    .struct  0
term_c_iflag:                    @ input modes
    .struct  term_c_iflag + 4 
term_c_oflag:                    @ output modes
    .struct  term_c_oflag + 4 
term_c_cflag:                    @ control modes
    .struct  term_c_cflag + 4 
term_c_lflag:                    @ local modes
    .struct  term_c_lflag + 4 
term_c_cc:                       @ special characters
    .struct  term_c_cc + 20      @ see length if necessary 
term_fin:
 
/* structure sigaction see doc linux */
    .struct  0
sa_handler:
    .struct  sa_handler + 4 
sa_mask:
    .struct  sa_mask + 4 
sa_flags:
    .struct  sa_flags + 4 
sa_sigaction:
    .struct  sa_sigaction + 4 
sa_fin:
 
/* structure poll see doc linux */
    .struct  0
poll_fd:                            @   File Descriptor
    .struct  poll_fd + 4 
poll_events:                        @  events mask
    .struct  poll_events + 4 
poll_revents:                       @ events returned
    .struct  poll_revents + 4 
poll_fin:
/*********************************/
/* Initialized data              */
/*********************************/
.data
sMessResult:           .ascii " "
sMessValeur:           .fill 11, 1, ' '             @ size => 11
szCarriageReturn:      .asciz "\n"
szMessGameWin:         .ascii "You win in "
sMessCounter:           .fill 11, 1, ' '            @ size => 11
                       .asciz " move number !!!!\n"
szMessMoveError:       .asciz "Huh... Impossible move !!!!\n"
szMessErreur:          .asciz "Error detected.\n"
szMessSpaces:          .asciz "    "
iGraine:               .int 123456
/*************************************************/
szMessErr: .ascii	"Error code hexa : "
sHexa: .space 9,' '
         .ascii "  decimal :  "
sDeci: .space 15,' '
         .asciz "\n"
szClear:     .byte 0x1B 
		     .byte 'c'                         @ console clear
		     .byte 0
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss
.align 4
iCodeError:     .skip 4
ibox:          .skip 4 * NBBOX                 @ game boxes
iEnd:           .skip 4                        @ 0 loop  1 = end loop
iTouche:        .skip 4                        @ value key pressed
stOldtio:       .skip term_fin                 @ old terminal state
stCurtio:       .skip term_fin                 @ current terminal state
stSigAction:    .skip sa_fin                   @ area signal structure
stSigAction1:   .skip sa_fin
stPoll1:        .skip poll_fin                 @ area poll structure
stPoll2:        .skip poll_fin
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:                                @ entry of program 
    mov r0,#0
    ldr r2,iAdribox
    mov r9,#0                        @ move counter 
1:                                   @ loop init boxs
    add r1,r0,#1                     @ box value
    str r1,[r2,r0, lsl #2]           @ store value
    add r0,#1                        @ increment counter
    cmp r0,#NBBOX - 2                @ end ?
    ble 1b
    mov r10,#15                      @ empty box location 
    ldr r0,iAdribox
    bl shuffleGame
2:                                   @ loop moves
    ldr r0,iAdribox
    bl displayGame
    //ldr r0,iAdribox
    //bl gameOK                      @ end game ?
    //cmp r0,#1
    //beq 50f
    bl readKey                       @ read key 
    cmp r0,#-1
    beq 100f                         @ error or control-c
    mov r1,r0                        @ key
    ldr r0,iAdribox
    bl keyMove
    ldr r0,iAdribox
    bl gameOK                        @ end game ?
    cmp r0,#1
    bne 2b                           @ no -> loop
50:                                  @ win
    mov r0,r9                        @ move counter
    ldr r1,iAdrsMessCounter
    bl conversion10
    ldr r0,iAdrszMessGameWin
    bl affichageMess
 
100:                                 @ standard end of the program 
    mov r0, #0                       @ return code
    mov r7, #EXIT                    @ request to exit program
    svc #0                           @ perform the system call
 
iAdrsMessValeur:          .int sMessValeur
iAdrszCarriageReturn:     .int szCarriageReturn
iAdrsMessResult:          .int sMessResult
iAdribox:                 .int ibox
iAdrszMessGameWin:        .int szMessGameWin
iAdrsMessCounter:         .int sMessCounter
/******************************************************************/
/*     key move                                                   */ 
/******************************************************************/
/* r0 contains boxs address           */
/* r1 contains key value               */
/* r9 move counter                     */
/* r10 contains location empty box    */
keyMove:
    push {r1-r8,lr}                  @ save  registers
    mov r8,r0
    cmp r1,#0x42                     @ down arrow 
    bne 1f
    cmp r10,#4                       @ if r10 < 4   error
    blt 80f
    sub r2,r10,#4                    @ compute location
    b 90f
1:
    cmp r1,#0x41                     @ high arrow
    bne 2f
    cmp r10,#11                      @ if r10 > 11   error
    bgt 80f
    add r2,r10,#4                    @ compute location
    b 90f
2:
    cmp r1,#0x43                     @ right arrow
    bne 3f
    tst r10,#0b11                    @ if r10 = 0,4,8,12   error
    beq 80f
    sub r2,r10,#1                    @ compute location
    b 90f
3:
    cmp r1,#0x44                     @ left arrow
    bne 100f
    and r3,r10,#0b11                 @ error if r10 = 3 7 11 and 15
    cmp r3,#3
    beq 80f
    add r2,r10,#1                    @ compute location
    b 90f
 
80:                                  @ move error
    ldr r0,iAdriCodeError
    mov r1,#1
    str r1,[r0]
    b 100f
90:                                  @ white box and move box inversion
    ldr r3,[r8,r2,lsl #2]
    str r3,[r8,r10,lsl #2]
    mov r10,r2
    mov r3,#0
    str r3,[r8,r10,lsl #2]
    add r9,#1                        @ increment move counter
100:
    pop {r1-r8,lr}                   @ restaur registers 
    bx lr                            @return
iAdriCodeError:             .int iCodeError
/******************************************************************/
/*     shuffle game                                       */ 
/******************************************************************/
/* r0 contains boxs address           */
shuffleGame:
    push {r1-r6,lr}                     @ save  registers
    mov r1,r0
    mov r0,#4
    bl genereraleas
    lsl r4,r0,#1
    mov r0,r8
1:
    mov r0,#14
    bl genereraleas
    add r6,r0,#1
    mov r0,#14
    bl genereraleas
    add r5,r0,#1
    ldr r2,[r1,r6,lsl #2]
    ldr r3,[r1,r5,lsl #2]
    str r2,[r1,r5,lsl #2]
    str r3,[r1,r6,lsl #2]
    subs r4,#1
    bgt 1b
 
100:
    pop {r1-r6,lr}                      @ restaur registers 
    bx lr                               @return
/******************************************************************/
/*     game Ok ?                                      */ 
/******************************************************************/
/* r0 contains boxs address           */
gameOK:
    push {r1-r8,lr}                     @ save  registers
    mov r8,r0
    mov r2,#0
    ldr r3,[r8,r2,lsl #2]
    add r2,#1
1:
    ldr r4,[r8,r2,lsl #2]
    cmp r4,r3
    movlt r0,#0                         @ game mot Ok
    blt 100f
    mov r3,r4
    add r2,#1
    cmp r2,#NBBOX -2
    ble 1b
    mov r0,#1                           @ game Ok
 
100:
    pop {r1-r8,lr}                      @ restaur registers 
    bx lr                               @return
/******************************************************************/
/*     display game                                       */ 
/******************************************************************/
/* r0 contains boxs address           */
displayGame:
    push {r1-r5,lr}                     @ save  registers
    @ clear !
    mov r4,r0
    ldr r0,iAdrszClear
    bl affichageMess 
    mov r2,#0
    ldr r1,iAdrsMessValeur
1:
    ldr r0,[r4,r2,lsl #2]
    cmp r0,#0
    ldreq r0,iSpaces                    @ store spaces
    streq r0,[r1]
    beq 2f
    bl conversion10                     @ call conversion decimal
    mov r0,#0
    strb r0,[r1,#3]                     @ zéro final
2:
 
    ldr r0,iAdrsMessResult
    bl affichageMess                    @ display message
    add r0,r2,#1
    tst r0,#0b11
    bne 3f
    ldr r0,iAdrszCarriageReturn
    bl affichageMess                    @ display message
3:
    add r2,#1
    cmp r2,#NBBOX - 1
    ble 1b
    ldr r0,iAdrszCarriageReturn
    bl affichageMess                    @ display line return
    ldr r0,iAdriCodeError               @ error detected ?
    ldr r1,[r0]
    cmp r1,#0
    beq 100f
    mov r1,#0                           @ raz error code
    str r1,[r0]
    ldr r0,iAdrszMessMoveError          @ display error message
    bl affichageMess
100:
    pop {r1-r5,lr}                      @ restaur registers 
    bx lr                               @return
iSpaces:                       .int 0x00202020       @ spaces
iAdrszClear:                   .int szClear          
iAdrszMessMoveError:           .int szMessMoveError
/******************************************************************/
/*     display text with size calculation                         */ 
/******************************************************************/
/* r0 contains the address of the message */
affichageMess:
    push {r0,r1,r2,r7,lr}                          @ save  registres
    mov r2,#0                                      @ counter length 
1:                                                 @ loop length calculation 
    ldrb r1,[r0,r2]                                @ read octet start position + index 
    cmp r1,#0                                      @ if 0 its over 
    addne r2,r2,#1                                 @ else add 1 in the length 
    bne 1b                                         @ and loop 
                                                   @ so here r2 contains the length of the message 
    mov r1,r0                                      @ address message in r1 
    mov r0,#STDOUT                                 @ code to write to the standard output Linux 
    mov r7, #WRITE                                 @ code call system "write" 
    svc #0                                         @ call systeme 
    pop {r0,r1,r2,r7,lr}                           @ restaur des  2 registres */ 
    bx lr                                          @ return  
/******************************************************************/
/*     Converting a register to a decimal unsigned                */ 
/******************************************************************/
/* r0 contains value and r1 address area   */
/* r0 return size of result (no zero final in area) */
/* area size => 11 bytes          */
.equ LGZONECAL,   10
conversion10:
    push {r1-r4,lr}                                 @ save registers 
    mov r3,r1
    mov r2,#LGZONECAL
1:                                                  @ start loop
    bl divisionpar10U                               @ unsigned  r0 <- dividende. quotient ->r0 reste -> r1
    add r1,#48                                      @ digit
    strb r1,[r3,r2]                                 @ store digit on area
    cmp r0,#0                                       @ stop if quotient = 0 
    subne r2,#1                                     @ else previous position
    bne 1b                                          @ and loop
                                                    @ and move digit from left of area
    mov r4,#0
2:
    ldrb r1,[r3,r2]
    strb r1,[r3,r4]
    add r2,#1
    add r4,#1
    cmp r2,#LGZONECAL
    ble 2b
                                                      @ and move spaces in end on area
    mov r0,r4                                         @ result length 
    mov r1,#' '                                       @ space
3:
    strb r1,[r3,r4]                                   @ store space in area
    add r4,#1                                         @ next position
    cmp r4,#LGZONECAL
    ble 3b                                            @ loop if r4 <= area size
 
100:
    pop {r1-r4,lr}                                    @ restaur registres 
    bx lr                                             @return
 
/***************************************************/
/*   division par 10   unsigned                    */
/***************************************************/
/* r0 dividende   */
/* r0 quotient    */
/* r1 remainder   */
divisionpar10U:
    push {r2,r3,r4, lr}
    mov r4,r0                                          @ save value
    ldr r3,iMagicNumber                                @ r3 <- magic_number    raspberry 1 2
    umull r1, r2, r3, r0                               @ r1<- Lower32Bits(r1*r0) r2<- Upper32Bits(r1*r0) 
    mov r0, r2, LSR #3                                 @ r2 <- r2 >> shift 3
    add r2,r0,r0, lsl #2                               @ r2 <- r0 * 5 
    sub r1,r4,r2, lsl #1                               @ r1 <- r4 - (r2 * 2)  = r4 - (r0 * 10)
    pop {r2,r3,r4,lr}
    bx lr                                              @ leave function 
iMagicNumber:  	.int 0xCCCCCCCD
/***************************************************/
/*   Generation random number                  */
/***************************************************/
/* r0 contains limit  */
genereraleas:
    push {r1-r4,lr}                                    @ save registers 
    ldr r4,iAdriGraine
    ldr r2,[r4]
    ldr r3,iNbDep1
    mul r2,r3,r2
    ldr r3,iNbDep1
    add r2,r2,r3
    str r2,[r4]                                        @ maj de la graine pour l appel suivant 
    cmp r0,#0
    beq 100f
    mov r1,r0                                          @ divisor
    mov r0,r2                                          @ dividende
    bl division
    mov r0,r3                                          @ résult = remainder
 
100:                                                   @ end function
    pop {r1-r4,lr}                                     @ restaur registers
    bx lr                                              @ return
/*****************************************************/
iAdriGraine: .int iGraine
iNbDep1: .int 0x343FD
iNbDep2: .int 0x269EC3 
/***************************************************/
/* integer division unsigned                       */
/***************************************************/
division:
    /* r0 contains dividend */
    /* r1 contains divisor */
    /* r2 returns quotient */
    /* r3 returns remainder */
    push {r4, lr}
    mov r2, #0                                         @ init quotient
    mov r3, #0                                         @ init remainder
    mov r4, #32                                        @ init counter bits
    b 2f
1:                                                     @ loop 
    movs r0, r0, LSL #1                                @ r0 <- r0 << 1 updating cpsr (sets C if 31st bit of r0 was 1)
    adc r3, r3, r3                                     @ r3 <- r3 + r3 + C. This is equivalent to r3 ? (r3 << 1) + C 
    cmp r3, r1                                         @ compute r3 - r1 and update cpsr 
    subhs r3, r3, r1                                   @ if r3 >= r1 (C=1) then r3 <- r3 - r1 
    adc r2, r2, r2                                     @ r2 <- r2 + r2 + C. This is equivalent to r2 <- (r2 << 1) + C 
2:
    subs r4, r4, #1                                    @ r4 <- r4 - 1 
    bpl 1b                                             @ if r4 >= 0 (N=0) then loop
    pop {r4, lr}
    bx lr
/***************************************************/
/* read touch                                      */
/***************************************************/
readKey:
    push {r1-r7,lr}
    mov r5,#0
    /* read terminal state */
    mov r0,#STDIN                                @ input console
    mov r1,#TCGETS
    ldr r2,iAdrstOldtio
    mov r7, #IOCTL                               @ call system Linux
    svc #0 
    cmp r0,#0                                    @ error ?
    beq 1f
    ldr r1,iAdrszMessErreur                      @ error message
    bl   displayError
    mov r0,#-1
    b 100f
1:
    adr r0,sighandler                            @ adresse routine traitement signal
    ldr r1,iAdrstSigAction                       @ adresse structure sigaction
    str r0,[r1,#sa_handler]                      @ maj handler
    mov r0,#SIGINT                               @ signal type
    ldr r1,iAdrstSigAction
    mov r2,#0                                    @ NULL
    mov r7, #SIGACTION                           @ call system
    svc #0 
    cmp r0,#0                                    @ error ?
    bne 97f
    mov r0,#SIGQUIT
    ldr r1,iAdrstSigAction
    mov r2,#0                                    @ NULL
    mov r7, #SIGACTION                           @ call system 
    svc #0 
    cmp r0,#0                                    @ error ?
    bne 97f
    mov r0,#SIGTERM
    ldr r1,iAdrstSigAction
    mov r2,#0                                    @ NULL
    mov r7, #SIGACTION                           @ appel systeme 
    svc #0 
    cmp r0,#0
    bne 97f
    @
    adr r0,iSIG_IGN                              @ address signal ignore function
    ldr r1,iAdrstSigAction1
    str r0,[r1,#sa_handler]
    mov r0,#SIGTTOU                              @invalidate other process signal
    ldr r1,iAdrstSigAction1
    mov r2,#0                                    @ NULL
    mov r7,#SIGACTION                            @ call system 
    svc #0 
    cmp r0,#0
    bne 97f
    @
    /* read terminal current state  */
    mov r0,#STDIN
    mov r1,#TCGETS
    ldr r2,iAdrstCurtio                          @ address current termio
    mov r7,#IOCTL                                @ call systeme 
    svc #0 
    cmp r0,#0                                    @ error ?
    bne 97f
    mov r2,#ICANON | ECHO                        @ no key pressed echo on display
    mvn r2,r2                                    @ and one key 
    ldr r1,iAdrstCurtio
    ldr r3,[r1,#term_c_lflag]
    and r3,r2                                    @ add flags 
    str r3,[r1,#term_c_lflag]                    @ and store
    mov r0,#STDIN                                @ maj terminal current state 
    mov r1,#TCSETS
    ldr r2,iAdrstCurtio
    mov r7, #IOCTL                               @ call system
    svc #0 
    cmp r0,#0
    bne 97f
    @
2:                                               @ loop waiting key
    ldr r0,iAdriEnd                              @ if signal ctrl-c  -> end
    ldr r0,[r0]
    cmp r0,#0
    movne r5,#-1
    bne 98f
    ldr r0,iAdrstPoll1                            @ address structure poll
    mov r1,#STDIN
    str r1,[r0,#poll_fd]                          @ maj FD
    mov r1,#POLLIN                                @ action code
    str r1,[r0,#poll_events]
    mov r1,#1                                     @ items number structure poll
    mov r2,#0                                     @ timeout = 0 
    mov r7,#SYSPOLL                               @ call system POLL
    svc #0 
    cmp r0,#0                                     @ key pressed ?
    ble 2b                                        @ no key pressed -> loop
                                                  @ read key
    mov r0,#STDIN                                 @ File Descriptor
    ldr r1,iAdriTouche                            @ buffer address
    mov r2,#TAILLEBUFFER                          @ buffer size
    mov r7,#READ                                  @ read key
    svc #0
    cmp r0,#0                                     @ error ?
    bgt 98f
 
97:                                               @ error detected
    ldr r1,iAdrszMessErreur                       @ error message
    bl   displayError
    mov r5,#-1
98:                                               @ end then restaur begin state terminal
    mov r0,#STDIN
    mov r1,#TCSETS
    ldr r2,iAdrstOldtio
    mov r7,#IOCTL                                 @ call system  
    svc #0
    cmp r0,#0
    beq 99f                                       @ restaur ok
    ldr r1,iAdrszMessErreur                       @ error message
    bl   displayError
    mov r0,#-1
    b 100f
99:
    cmp r5,#0                                     @ error or control-c
    ldreq r2,iAdriTouche                          @ key address
    ldreqb r0,[r2,#2]                             @ return key byte
    movne r0,r5                                   @ or error
100:
    pop {r1-r7, lr}
    bx lr
iSIG_IGN:                 .int 1
iAdriEnd:                 .int iEnd
iAdrstPoll1:              .int stPoll1
iAdriTouche:              .int iTouche
iAdrstOldtio:             .int stOldtio
iAdrstCurtio:             .int stCurtio
iAdrstSigAction:          .int stSigAction
iAdrstSigAction1:         .int stSigAction1
iAdrszMessErreur :        .int szMessErreur 
/******************************************************************/
/*     traitement du signal                                       */ 
/******************************************************************/
sighandler:
    push {r0,r1}
    ldr r0,iAdriEnd
    mov r1,#1                 @ maj zone end
    str r1,[r0]
    pop {r0,r1}
    bx lr
/***************************************************/
/*   display error message                         */
/***************************************************/
/* r0 contains error code  r1 : message address */
displayError:
    push {r0-r2,lr}                         @ save registers
    mov r2,r0                               @ save error code
    mov r0,r1
    bl affichageMess
    mov r0,r2                               @ error code
    ldr r1,iAdrsHexa
    bl conversion16                         @ conversion hexa
    mov r0,r2                               @ error code
    ldr r1,iAdrsDeci                        @ result address
    bl conversion10                         @ conversion decimale
    ldr r0,iAdrszMessErr                    @ display error message
    bl affichageMess
100:
    pop {r0-r2,lr}                          @ restaur registers
    bx lr                                   @ return 
iAdrszMessErr:                 .int szMessErr
iAdrsHexa:                     .int sHexa
iAdrsDeci:                     .int sDeci
/******************************************************************/
/*     Converting a register to hexadecimal                      */ 
/******************************************************************/
/* r0 contains value and r1 address area   */
conversion16:
    push {r1-r4,lr}                                    @ save registers
    mov r2,#28                                         @ start bit position
    mov r4,#0xF0000000                                 @ mask
    mov r3,r0                                          @ save entry value
1:                                                     @ start loop
    and r0,r3,r4                                       @value register and mask
    lsr r0,r2                                          @ move right 
    cmp r0,#10                                         @ compare value
    addlt r0,#48                                       @ <10  ->digit	
    addge r0,#55                                       @ >10  ->letter A-F
    strb r0,[r1],#1                                    @ store digit on area and + 1 in area address
    lsr r4,#4                                          @ shift mask 4 positions
    subs r2,#4                                         @  counter bits - 4 <= zero  ?
    bge 1b                                             @  no -> loop
 
100:
    pop {r1-r4,lr}                                     @ restaur registers 
    bx lr                                              @return
 
 