Sudoku Solver

Description

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

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. 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.

Before entering the program perform the following:
3 4 DIM (i)

Program Resources

Labels

Name Description Name Description
 A Sudoku Solver Main  3 Set the indirect register and remove the parameters from the stack
 B Utility subroutine for setting flag matrix values  4 Extract value at the current column from the matrix indirectly specified by x&y
 C Backs up to the previous position  5 Sets the utility temp register to 2^(x-1). Leaves x in place.
 D Set/clear flag matrix values  6 Increments or decrements the current position in the trial solution.
 E Main solution loop  7 Set the value x into the current row/column in the trial solution.
 1 Returns the integer representing the entire Xth row of the flag matrix  8 Check the possible digits in order 1-9
 2 Set the flags to show the input values are set  9 Get the appropriate row (x) from the flag matrix

Storage Registers

Name Description Name Description
 0 General purpose variable used for miscelaneous purposes  5 Power of 10 of current column index
 1 Current index (0-80) in the pseudo-recursion  6 Value in the test solution at current index
 2 Row (0-8) of current index  7 Value of start clue at current index (0 if not set)
 3 Column (0-8) of current index (i)
 4 Block # (0-8) of current index I

Flags

Number Description
2 Indicates that a digit has been used in cur row/column/block
3 Input to Subroutine B (whether to set or clear flags)

Program

Line Display Key Sequence Line Display Key Sequence Line Display Key Sequence
000 065 7 7 130 43. 5. 2 g CF 2
001 42.21.14 f LBL D 066 32 4 GSB 4 131 45 2 RCL 2
002 32 5 GSB 5 067 44 6 STO 6 132 32 9 GSB 9
003 45 2 RCL 2 068 45 2 RCL 2 133 43. 6. 2 g F? 2
004 32 12 GSB B 069 8 8 134 22 8 GTO 8
005 45 3 RCL 3 070 32 4 GSB 4 135 45 3 RCL 3
006 32 12 GSB B 071 44 7 STO 7 136 32 9 GSB 9
007 45 4 RCL 4 072 43 32 g RTN 137 43. 6. 2 g F? 2
008 42.21.12 f LBL B 073 42.21. 4 f LBL 4 138 22 8 GTO 8
009 32 1 GSB 1 074 32 3 GSB 3 139 45 4 RCL 4
010 45 0 RCL 0 075 45 24 RCL (i) 140 32 9 GSB 9
011 43. 6. 3 g F? 3 076 45.10. 5 RCL ÷ 5 141 43. 6. 2 g F? 2
012 16 CHS 077 43 44 g INT 142 22 8 GTO 8
013 40 + 078 1 1 143 45 6 RCL 6
014 34 x↔y 079 0 0 144 32 14 GSB D
015 2 2 080 10 ÷ 145 22 15 GTO E
016 6 6 081 42 44 f FRAC 146 42.21.13 f LBL C
017 32 3 GSB 3 082 1 1 147 1 1
018 44 24 STO (i) 083 0 0 148 16 CHS
019 33 R⬇ 084 20 × 149 32 6 GSB 6
020 9 9 085 43 32 g RTN 150 43.30. 1 g TEST x>0
021 40 + 086 42.21.11 f LBL A 151 22 13 GTO C
022 22 5 GTO 5 087 43. 5. 2 g CF 2 152 45 6 RCL 6
023 42.21. 7 f LBL 7 088 43. 5. 3 g CF 3 153 43. 4. 3 g SF 3
024 42. 4. 6 f x↔ 6 089 1 1 154 32 14 GSB D
025 44 0 STO 0 090 16 CHS 155 43. 5. 3 g CF 3
026 45 2 RCL 2 091 44 1 STO 1 156 22 8 GTO 8
027 1 1 092 42.21. 2 f LBL 2 157 42.21. 9 f LBL 9
028 7 7 093 1 1 158 32 1 GSB 1
029 32 3 GSB 3 094 32 6 GSB 6 159 45.10. 0 RCL ÷ 0
030 45 24 RCL (i) 095 45 7 RCL 7 160 43 44 g INT
031 45 6 RCL 6 096 32 7 GSB 7 161 2 2
032 45.30. 0 RCL 0 097 45 7 RCL 7 162 10 ÷
033 45.20. 5 RCL × 5 098 43.30. 1 g TEST x>0 163 42 44 f FRAC
034 40 + 099 32 14 GSB D 164 43.30. 1 g TEST x>0
035 44 24 STO (i) 100 8 8 165 43. 4. 2 g SF 2
036 43 32 g RTN 101 0 0 166 33 R⬇
037 42.21. 6 f LBL 6 102 45 1 RCL 1 167 33 R⬇
038 44.40. 1 STO + 1 103 43.30. 6 g TEST x≠y 168 9 9
039 45 1 RCL 1 104 22 2 GTO 2 169 40 +
040 45 1 RCL 1 105 1 1 170 22 5 GTO 5
041 9 9 106 16 CHS 171 42.21. 5 f LBL 5
042 10 ÷ 107 44 1 STO 1 172 44 0 STO 0
043 43 44 g INT 108 42.21.15 f LBL E 173 1 1
044 44 2 STO 2 109 8 8 174 30
045 9 9 110 0 0 175 2 2
046 20 × 111 45 1 RCL 1 176 34 x↔y
047 30 112 43.30. 5 g TEST x=y 177 14
048 44 3 STO 3 113 43 32 g RTN 178 42. 4. 0 f x↔ 0
049 3 3 114 1 1 179 43 32 g RTN
050 10 ÷ 115 32 6 GSB 6 180 42.21. 1 f LBL 1
051 45 2 RCL 2 116 45 7 RCL 7 181 36 ENTER
052 3 3 117 43.30. 1 g TEST x>0 182 36 ENTER
053 10 ÷ 118 22 15 GTO E 183 2 2
054 43 44 g INT 119 32 7 GSB 7 184 6 6
055 3 3 120 42.21. 8 f LBL 8 185 32 3 GSB 3
056 20 × 121 9 9 186 45 24 RCL (i)
057 40 + 122 45 6 RCL 6 187 43 32 g RTN
058 44 4 STO 4 123 43.30. 5 g TEST x=y 188 42.21. 3 f LBL 3
059 8 8 124 22 13 GTO C 189 40 +
060 45.30. 3 RCL 3 125 1 1 190 44 25 STO I
061 13 10ˣ 126 40 + 191 33 R⬇
062 44 5 STO 5 127 32 7 GSB 7 192 43 32 g RTN
063 45 2 RCL 2 128 45 6 RCL 6
064 1 1 129 32 5 GSB 5