The Museum of HP Calculators

HP Articles Forum

Sudoku Solver for the HP-15c

Posted by Marcel Samek on 4 Feb 2013, 1:20 p.m.

This program uses a backtracking algorithm to find the first solution to a sudoku puzzle.

If you wish to try it, you have to save the starting puzzle in registers 8-16. Each row of the sudoku is represented as a single, 9 digit number, with 0 representing each blank. Once you have done that, you can run the program with a GSB A. When it is complete, you will find the solution to the sudoku puzzle in registers 17 to 25. Unfortunately, you will need to use the indirect register to get at the result, because there is no way to directly see the value of register 20 and above. I am working on making the program a little smaller so that I can put in a loop to print the result out line by line.

It is quite slow, depending on the complexity of the puzzle. The complexity of the puzzle (as far as this program is concerned) depends on the number of clues, and their placement in the puzzle. The more clues, the faster it will solve. The more clues towards the upper part of the puzzle (especially the upper left), the faster it will solve. Some puzzles can take many hours to solve, and some just a few minutes. I have only tried it on the 15C LE which is about 100 times faster than the original 15C.

If you want to make sure that it works after you have typed it in, enter a solved sudoku with just a few values missing and see if it finds them correctly. It should be able to do that in a few seconds and it acts as a quick sanity check to make sure you keyed the program in correctly.

This is a work in progress and I am still trying to squeeze it down to make it more user friendly. The latest version will always be found at: Sudoku Solver for the HP-15c

```; Sudoku Solver for HP 15C
; Special Thanks: To the MoHPC community for their many suggestions
;
; Before entering the program perform the following:
; 34 DIM (i)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; 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)
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
```