Task

Solve a partially filled-in normal   9x9   Sudoku grid   and display the result in a human-readable format.

references

 Algorithmics of Sudoku   may help implement this.
 Python Sudoku Solver Computerphile video.


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;       
; Register And Flag Usage        
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;       
;        0        General purpose variable used for miscelaneous purposes
;        1        Current index (0-80) in the pseudo-recursion 
;        2        Row (0-8) of current index
;        3        Column (0-8) of current index
;        4        Block # (0-8) of current index
;        5        Power of 10 of current column index
;        6        Value in the test solution at current index
;        7        Value of start clue at current index (0 if not set)
;        8 – 16   Starting row data
;        17 – 25  Current test solution
;        26 – 34  Flag matrix (bit set if digit used in a row/column/block)
;
;        Flag 2   Indicates that a digit has been used in cur row/column/block
;        Flag 3   Input to Subroutine B (whether to set or clear flags)
        
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;       
; setU(x)        
; Set/clear flag matrix values (show that x is used in a row/column/block)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;       
LBL D        
        GSB 5       ; calc bit value we need to set/clear in existing row
        RCL 2       ; Get the current row index into x
        GSB B       ; set flag matrix value and calc new bit value for the column
        RCL 3       ; Get the current column index into x
        GSB B       ; set flag matrix values and calc new bit value for the block
        RCL 4       ; Get the current block index into x
        
; MUST IMMEDIATELY FOLLOW PRECEEDING SUBROUTINE        
; utility subroutine for setting flag matrix values         

LBL B        
        GSB 1       ; get the current flag matrix row at index x
        
        RCL 0       ; get temp register (holds the bit value we will be setting)
        F? 3        ; flag 3 indicates if we are setting or clearing the flag
        CHS         ; if we are clearing, we will do a subtraction instead
        +           ; set/clear the flag
        
        X<>Y        ; bring the row index back into x
        2           ; 26 is the starting register for the flag matrix
        6        
        GSB 3       ; set I so that we are ready to store the new value
        STO (i)     ; store the new value into the flag matrix
        RDN         ; get rid of the new value to restore the stack
        9           ; the next bit value will be 9 bits to the left
        +           ; set the next bit index
        GTO 5       ; calculate the value with that bit set
                    ; we GTO instead of GSB and it will do the RTN
        
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;       
; putA(x)        
; Set the value x into the current row/column in the trial solution.         
; Does it by subtracting the previous value and adding the new one.        
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;       
LBL 7        
        X<>6        ; swap new value with register that holds current value
        STO 0       ; store the old value in the temp register
        RCL 2       ; Get the current row index into x
        1           ; 17 is the starting register for the current trial solution
        7        
        GSB 3       ; Set the indirect register
        RCL (i)     ; Get the current value for the entire row
        RCL 6       ; Get the new value
        RCL- 0      ; subtract the old value from the new value
        RCL* 5      ; shift the power of 10 to the appropriate column
        +           ; add to the old value
        STO (i)     ; store the new row value from where we got it
        RTN        
        
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;       
; change(x)        
; Increments or decrements the current position in the trial solution.        
; Updates the registers containing the current row, column and block index,
; and the one with the power of 10 factor for the current column and others
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;       
LBL 6        
        STO+ 1      ; x holds +1 or -1; Register 1 is the current index
        
        RCL 1       ; get the current index (0 to 80)
        RCL 1       ; get the current index (0 to 80)
        9           ; integer divide by 9 to get the row index (0 to 8)
        /           ; no integer divide on 15c so do a floating point divide
        INT         ; use the INT operator to finish of the integer divide
        STO 2       ; register 2 contains the current row index
        
        9        
        *        
        -           ; col = index - 9 * row
        STO 3       ; register 3 contains the current column index
        
        3           ; calculate the block index from the row & column indexes
        /           ; TODO: save a couple of bytes in this section of code
        RCL 2        
        3        
        /        
        INT          
        3        
        *        
        +        
        STO 4       ; register 4 holds the block index
        
        8           ; now calculate the power of 10 of the current column
        RCL- 3      ; Get the digit (from right) based on the column
        10^X        ; calculate the exponent
        STO 5       ; save in register 5 which is used throughout the code
        
        RCL 2       ; get the current row
        1           ; 17 is the start register of the current trial solution
        7        
        GSB 4       ; extract the value at the current column
        STO 6       ; reg 6: the current trial value at the current row/column
        
        RCL 2       ; get the current row
        8           ; 8 is the start register of the input data from the user
        GSB 4       ; extract the value at the current column
        STO 7       ; reg 7: starting value at the current row/column (0 if none)
        RTN        
        
; Extract value at the current column from the matrix indirectly specified by x&y
LBL 4        
        GSB 3       ; set the indirect register based on x & y
        RCL (i)     ; get the row from the matrix passed in
        RCL / 5     ; shift the row to the right
        INT         ; trim off the digits shifted to the right of the decimal
        1           ; we will do a modulus 10 to extract the last digit
        0        
        /           ; do the equivalent of a mod 10
        FRAC                
        1
        0
        *
        RTN
        
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;       
;  main()        
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;       
LBL A        
        CF 2        ; make sure flag 2 is unset - CLR REG does not do this
        CF 3        ; make sure flag 3 is unset - CLR REG does not do this
        1           ; start with a index in register 1 of -1 (0 to 80)
        CHS         ; that way we can start with an increment operation
        STO 1       ; and actually start at 0 where we want.
        
LBL 2               ; set the flags to show the input values are set
        1           ; go forward one position at a time
        GSB 6       ; go to the next position in the trial solution
        
        RCL 7       ; get the starting input value at this row/col 
        GSB 7       ; set the value in the trial solution
        RCL 7       ; get starting input value because the last call destroyed it
        TEST 1      ; if > 0 then the user input a value for this row/col
        GSB D       ; set the flags to indicate this value is set
        
        8           ; 80 is the upper bound of the indexes (9x9 = 80 = 0:80)
        0        
        RCL 1       ; get the current index
        TEST 6      ; if the current index hasn't reached 80
        GTO 2       ; do the next value
        1           ; reset the starting value
        CHS         ; to -1 as we did at the beginning of the program
        STO 1       ; register 1 holds the current index
        
LBL E               ; main solution loop
        8           ; when we reach the last index (80) we are done
        0        
        RCL 1       ; register 1 holds the current index
        TEST 5      ; see if we are at the end
        RTN         ;  finished        ; woohoo - we are done!
        1           ; Go forward one spot
        GSB 6       ; Do the position increment
        RCL 7       ; get the starting input value at this row/col 
        TEST 1      ; if it's > 0, the user specified a value here
        GTO E       ; go forward, since this value was specified by the user
        GSB 7       ; Set the value in the trial solution
        
LBL 8          
        9           ; check the possible digits in order 1-9.
        RCL 6       ; Get the current trial solution value
        TEST 5      ; Check to see if it is 9
        GTO C       ; If it is, backup one step
        1           ; We weren't at 9 yet, so increment the value by 1
        +        
        GSB 7       ; Set the value in the trial solution
        
        RCL 6       ; Get the current trial solution value
        GSB 5       ; Calc 2^x-1 to get the bit mask
        CF 2        ; Clear the flag thats used as a return value
        RCL 2       ; Get the current row index into x
        GSB 9       ; see if the current value has already been used in the row
        F? 2        ; If number has been used in the block, try the next value
        GTO 8        
        RCL 3       ; Get the current column index into x
        GSB 9       ; see if current value has already been used in the column
        F? 2        ; If number has been used in the block, try the next value
        GTO 8        
        RCL 4       ; Get the current block index into x
        GSB 9       ; see if the current value has already been used in the block
        F? 2        ; If number has been used in the block, try the next value
        GTO 8        
        RCL 6       ; Get the current trial solution value
        GSB D       ; set the flags to indicate this value is set
        GTO E       ; move on to the next position in the puzzle
        
LBL C               ; Come here to back up to the previous position
        1           ; We will go one spot backwards
        CHS        
        GSB 6       ; Set the new current position and all temp values
        TEST 1      ; previous call leaves the starting value in X
        GTO C       ; if value is > 0, it was set, backup one more spot
        RCL 6       ; Get the current trial solution value
        
        SF 3        ; flag 3: clear the flag matrix bits, instead of setting them
        GSB D       ; Set/Clear the flag matrix bits
        CF 3        ; unset the 3 flag
        GTO 8       ; check the next digit
        
LBL 9        
        GSB 1       ; get the appropriate row (x) from the flag matrix
        RCL /  0    ; divide by the temp register - right shifts value
        INT        
        2           ; if bit is set, fractional part will be non 0 when / 2
        /        
        FRAC        
        TEST 1      ; if bit is set, set flag 2 which is used as a return value
        SF 2        
        RDN         ; move the stack down to prepare the caller for the next call
        RDN         ; move the stack down to prepare the caller for the next call
        9           ; bit flags for row/col/block are << by 9 from each other
        +           ; calculates the appropriate bit offset for the next call
        GTO 5       ; calc 2^x-1 to get the bit mask
                    ; do a GTO instead of GSB and it will return for us

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;       
; setPow2(x)        
; Sets the utility temp register to 2^(x-1). Leaves x in place.        
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;       
LBL 5        
        STO 0       ; store the input X in the temp register
        1           ; we want to subtract 1 from the exponent
        -           ; calculate x-1
        2           ; set the base as 2
        X<>Y        ; the y^x function wants x and y reversed
        y^x         ; calculate the value
        X<>0        ; stuff result in temp register and restore the input x
        RTN        
        
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;       
; getPart(x)        
; Returns the integer representing the entire Xth row of the flag matrix        
; Row numbers start at 0.        
; returns value in x - input parameter x ends up in y        
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;       
LBL 1        
        ENTER        
        ENTER       ; duplicate the parameter so we can leave it for the caller
        2           ; 26 is the starting register for the flag matrix
        6        
        GSB 3       ; set the indirect register to the row specified by x
        RCL (i)     ; retrieve the entire row from the flag matrix
        RTN        
        
; Set the indirect register and remove the parameters from the stack
LBL 3        
        +           ; x+y is the memory offset we want
        STO I       ; put it in the indirect register
        RDN         ; get rid of the sum from the stack
        RTN        
