The Museum of HP CalculatorsHP Articles Forum
[Return to the Index ]
[ Previous | Next ]
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) 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
Go back to the main exhibit hall