1 * I wrote this program, and placed it in the public domain. 2 * -- Scott Hemphill 23 June 2006 3 4 * Modified 06/26/06 by Michael Mahon to integrate with 5 * Applesoft BASIC front-end program. 6 * 7 * 06/28/06 - Added grid consistency check and return code. 8 * 07/10/06 - Fixed 'bits' push extra byte and optimized. 9 * 07/12/06 - Removed 65C02 ops & improved grid init code 10 * 07/13/06 - Added CLRBOT routine to clear bottom of screen 11 * Added fast screen paint routine 12 * 07/14/06 - Optimized 'setbox', 'unsetbox', and 'select' 13 15 16 * Zero page variables 17 18 bits = $06 19 vars = $08 20 p = $EE 21 22 * Stackable zero page vars 23 24 var0 = $FA 25 best = var0 26 bstcnt = var0+1 27 digit = var0+2 28 bit = var0+3 29 sqbits = var0+4 30 nvars = sqbits+1-var0 31 32 * Communication variables with BASIC program 33 * The puzzle grid: contains digits "1" through "9", or 0 34 * if a digit hasn't been chosen. Set up by BASIC program. 35 36 rc = $300 ; Return code to BASIC prog 37 num = $301 ; Number of solutions (8 bytes) 38 grid = $309 ; Comm area with BASIC prog 39 40 * ROM equates 41 42 ch = $24 ; Horizontal cursor position 43 cv = $25 ; Vertical cursor position 44 45 linprt = $ED24 ; Print X,A in decimal 46 prbl2 = $F94A ; Print (X) blanks 47 vtab = $FC22 ; VTAB to line CV 48 crout1 = $FD8B ; CR & clear to EOL 49 crout = $FD8E ; Output a carriage return 50 cout = $FDED ; Print char in A 51 52 * Hardware equates 53 54 kbd = $C000 ; Keyboard port 55 kbstr = $C010 ; Keyboard strobe 56 57 * Macro definitions 58 59 align mac ; Align 0 mod arg 60 ds *+]1-1/]1*]1-* 61 eom 62 63 org $2000 64 2000: 4C 56 21 65 SOLVER jmp main ; Solver entry point 2003: 4C C3 20 66 DRWGRID jmp drawgrd ; Draw the grid on the screen 2006: 4C 43 21 67 CLRBOT jmp clearbot ; Clear bottom 3 lines of screen 68 69 * Text tables for drawing grid 70 71 txtpag equ */256*256 ; Text must all fit on 1 page. 72 2009: 2C 2D 2D 73 line db ls,lb,lb,lx,lb,lb,lx,lb,lb,le,0 ===== Page 2 - *** July 15, 2006 *** ===== 2014: 1F 20 20 74 box db gs,gb,gb,gx,gb,gb,gx,gb,gb,ge,0 75 201F: A0 76 gs asc " " ; Starting blank 2020: FC A0 A0 77 gb asc "| ",00 ; Repeating grid cell 2025: 20 78 gx inv " " ; Inverse blank 2026: A0 A0 A0 79 asc " ",00 202A: FC 00 80 ge asc "|",00 ; end 202C: A0 81 ls asc " " ; Starting blank 202D: AB AD AD 82 lb asc "+---",00 ; Repeating line cell 2032: 20 83 lx inv " " ; Inverse blank 2033: AD AD AD 84 asc "---",00 2037: AB 00 85 le asc "+",00 ; Line end 86 2039: A0 87 sep asc " " 203A: 20 20 20 88 inv " " 205F: A0 A0 00 89 asc " ",00 2062: D3 A0 D5 90 title asc "S U D O K U v2.0",00 2074: A0 C3 F4 91 helplns asc " Ctl-X Clear Ctl-L Load Ctl-S Save " 209C: A0 D2 E5 92 asc " Retrn Solve Esc Quit ? Help",00 93 94 * Draw grid on Apple screen 95 20C3: A2 0B 96 drawgrd ldx #11 ; Blanks before title 20C5: 20 4A F9 97 jsr prbl2 20C8: 20 27 2A 98 jsr ascout ; Print title 20CB: 62 20 99 dw title 20CD: 20 8B FD 100 jsr crout1 ; CR & clear to EOL 20D0: 20 8B FD 101 jsr crout1 20D3: A2 09 102 ldx #line ; Print first grid line 20D5: 20 29 21 103 jsr prtxt 20D8: 20 17 21 104 jsr pblblb ; Print first 3 grid rows 20DB: 20 27 2A 105 jsr ascout ; Print inverse separator 20DE: 39 20 106 dw sep 20E0: 20 17 21 107 jsr pblblb ; Middle 3 grid rows 20E3: 20 27 2A 108 jsr ascout ; Print inverse separator 20E6: 39 20 109 dw sep 20E8: 20 17 21 110 jsr pblblb ; last 3 grid rows 20EB: A2 09 111 ldx #line ; Print last grid line 20ED: 20 29 21 112 jsr prtxt 20F0: 20 27 2A 113 jsr ascout ; Print help lines 20F3: 74 20 114 dw helplns 20F5: A0 50 115 ldy #80 ; Set screen digits 20F7: B9 09 03 116 :dloop lda grid,y 20FA: F0 17 117 beq :skip 20FC: BE D5 21 118 ldx x2,y ; 'best' * two 20FF: BD 1C 29 119 lda scrn,x ; Animate the grid 2102: 8D 11 21 120 sta :scrn+1 ; while solving. 2105: BD 1D 29 121 lda scrn+1,x 2108: 8D 12 21 122 sta :scrn+2 210B: B9 09 03 123 lda grid,y 210E: 09 80 124 ora #$80 ; Set hi bit 2110: 8D 00 00 125 :scrn staa 0*0 ; Store to screen 2113: 88 126 :skip dey 2114: 10 E1 127 bpl :dloop 2116: 60 128 rts 129 130 * Print grid rows: box, line, box, line, box. 131 2117: A2 14 132 pblblb ldx #box ; Print grid box 2119: 20 29 21 133 jsr prtxt 211C: 20 1F 21 134 jsr :lblb ; Do it twice. 211F: A2 09 135 :lblb ldx #line ; Print grid line 2121: 20 29 21 136 jsr prtxt 2124: A2 14 137 ldx #box ; Print grid box 2126: 4C 29 21 138 jmp prtxt ; ..and return. 139 140 * Print text strings indexed by text table at (X) 141 * Text tables and all strings must fit in 'txt' page 142 2129: 86 FA 143 prtxt stx best ; Pointer to txt table ===== Page 3 - *** July 15, 2006 *** ===== 212B: BC 00 20 144 ldy txtpag,x 212E: F0 10 145 beq :done ; 0 is sentinel 2130: B9 00 20 146 :chrloop lda txtpag,y ; Move characters 2133: F0 06 147 beq :nxt ; get next index 2135: 20 ED FD 148 jsr cout 2138: C8 149 iny 2139: D0 F5 150 bne :chrloop ; (always) 151 213B: A6 FA 152 :nxt ldx best 213D: E8 153 inx 213E: D0 E9 154 bne prtxt ; (always) 155 2140: 4C 8B FD 156 :done jmp crout1 ; Clear to EOL and return. 157 158 * Clear bottom 3 lines of Apple screen 159 2143: A9 A0 160 clearbot lda #" " 2145: A2 27 161 ldx #39 2147: 9D D0 06 162 :clrbot sta line22,x 214A: 9D 50 07 163 sta line23,x 214D: 9D D0 07 164 sta line24,x 2150: CA 165 dex 2151: 10 F4 166 bpl :clrbot 2153: 4C 8E FD 167 jmp crout 168 169 * Main program. Calls "select" to recursively enumerate 170 * solution(s). 171 2156: BA 172 main tsx ; Mark stack for fast return 2157: 8E CB 21 173 stx bstack ; to BASIC. 215A: A9 00 174 lda #bitmap 215C: 85 06 175 sta bits 215E: A9 2F 176 lda #>bitmap 2160: 85 07 177 sta bits+1 2162: 8D F6 29 178 sta b1+2 ; Init addresses 2165: 8D FB 29 179 sta b2+2 2168: 8D 07 2A 180 sta b3+2 216B: 8D D9 2A 181 sta b4+2 216E: 8D E3 2A 182 sta b5+2 2171: A9 C0 183 lda #varstk 2173: 85 08 184 sta vars 2175: A9 2B 185 lda #>varstk 2177: 85 09 186 sta vars+1 2179: A0 08 187 ldy #8 ; Set rc and num = 0 217B: A9 00 188 lda #0 217D: 99 00 03 189 :clear sta rc,y 2180: 88 190 dey 2181: 10 FA 191 bpl :clear 2183: A0 A1 192 ldy #161 ; Clear all bits 2185: 91 06 193 :clrbits sta (bits),y 2187: 88 194 dey 2188: D0 FB 195 bne :clrbits 218A: 91 06 196 sta (bits),y ; Clear 0th byte 218C: A0 50 197 ldy #80 ; Set bits from grid 218E: BE 09 03 198 :setloop ldx grid,y 2191: F0 0E 199 beq :skip ; Skip if empty 2193: 86 FC 200 stx digit ; Save digit (ASCII) 2195: BD 9B 21 201 lda bittab-'1',x 2198: 85 FD 202 sta bit 219A: 84 FA 203 sty best 219C: 20 BE 29 204 jsr setbox ; Set all 'bits' 219F: A4 FA 205 ldy best 21A1: 88 206 :skip dey 21A2: 10 EA 207 bpl :setloop 21A4: A2 50 208 ldx #80 ; Check grid consistency 21A6: BD 09 03 209 :chkloop lda grid,x 21A9: F0 14 210 beq :blank 21AB: BC D5 21 211 ldy x2,x ; 'best' * 2 21AE: 86 FA 212 stx best 21B0: AA 213 tax ===== Page 4 - *** July 15, 2006 *** ===== 21B1: BD 9B 21 214 lda bittab-'1',x 21B4: D0 03 215 bne :<9 21B6: A9 01 216 lda #1 21B8: C8 217 iny 21B9: 31 06 218 :<9 and (bits),y 21BB: D0 08 219 bne :nggrid ; Inconsistent 21BD: A6 FA 220 ldx best 21BF: CA 221 :blank dex 21C0: 10 E4 222 bpl :chkloop 21C2: 4C C9 2A 223 jmp select ; Find solutions & back to BASIC 224 21C5: A9 01 225 :nggrid lda #1 21C7: 8D 00 03 226 sta rc ; Inconsistent return code 21CA: 60 227 rts 228 21CB: 00 229 bstack db 0 ; Stack pointer on entry 21CC: 01 02 04 230 bittab db 1,2,4,8,16,32,64,128,256 ; digit masks 231 232 * Table of indices multiplied by 2 (0..80) ==> (0..160) 233 234 x2 lup 81 21D5: 00 235 db *-x2*2 21D6: 02 235 db *-x2*2 21D7: 04 235 db *-x2*2 21D8: 06 235 db *-x2*2 21D9: 08 235 db *-x2*2 21DA: 0A 235 db *-x2*2 21DB: 0C 235 db *-x2*2 21DC: 0E 235 db *-x2*2 21DD: 10 235 db *-x2*2 21DE: 12 235 db *-x2*2 21DF: 14 235 db *-x2*2 21E0: 16 235 db *-x2*2 21E1: 18 235 db *-x2*2 21E2: 1A 235 db *-x2*2 21E3: 1C 235 db *-x2*2 21E4: 1E 235 db *-x2*2 21E5: 20 235 db *-x2*2 21E6: 22 235 db *-x2*2 21E7: 24 235 db *-x2*2 21E8: 26 235 db *-x2*2 21E9: 28 235 db *-x2*2 21EA: 2A 235 db *-x2*2 21EB: 2C 235 db *-x2*2 21EC: 2E 235 db *-x2*2 21ED: 30 235 db *-x2*2 21EE: 32 235 db *-x2*2 21EF: 34 235 db *-x2*2 21F0: 36 235 db *-x2*2 21F1: 38 235 db *-x2*2 21F2: 3A 235 db *-x2*2 21F3: 3C 235 db *-x2*2 21F4: 3E 235 db *-x2*2 21F5: 40 235 db *-x2*2 21F6: 42 235 db *-x2*2 21F7: 44 235 db *-x2*2 21F8: 46 235 db *-x2*2 21F9: 48 235 db *-x2*2 21FA: 4A 235 db *-x2*2 21FB: 4C 235 db *-x2*2 21FC: 4E 235 db *-x2*2 21FD: 50 235 db *-x2*2 21FE: 52 235 db *-x2*2 21FF: 54 235 db *-x2*2 2200: 56 235 db *-x2*2 2201: 58 235 db *-x2*2 2202: 5A 235 db *-x2*2 2203: 5C 235 db *-x2*2 2204: 5E 235 db *-x2*2 2205: 60 235 db *-x2*2 ===== Page 5 - *** July 15, 2006 *** ===== 2206: 62 235 db *-x2*2 2207: 64 235 db *-x2*2 2208: 66 235 db *-x2*2 2209: 68 235 db *-x2*2 220A: 6A 235 db *-x2*2 220B: 6C 235 db *-x2*2 220C: 6E 235 db *-x2*2 220D: 70 235 db *-x2*2 220E: 72 235 db *-x2*2 220F: 74 235 db *-x2*2 2210: 76 235 db *-x2*2 2211: 78 235 db *-x2*2 2212: 7A 235 db *-x2*2 2213: 7C 235 db *-x2*2 2214: 7E 235 db *-x2*2 2215: 80 235 db *-x2*2 2216: 82 235 db *-x2*2 2217: 84 235 db *-x2*2 2218: 86 235 db *-x2*2 2219: 88 235 db *-x2*2 221A: 8A 235 db *-x2*2 221B: 8C 235 db *-x2*2 221C: 8E 235 db *-x2*2 221D: 90 235 db *-x2*2 221E: 92 235 db *-x2*2 221F: 94 235 db *-x2*2 2220: 96 235 db *-x2*2 2221: 98 235 db *-x2*2 2222: 9A 235 db *-x2*2 2223: 9C 235 db *-x2*2 2224: 9E 235 db *-x2*2 2225: A0 235 db *-x2*2 237 238 * For each square, an array of 20 "other" locations 239 * affected by this square. For example, if there is a "6" 240 * in square 0, there are 20 other squares we know can't 241 * contain a six: 242 * 1,2,3,4,5,6,7,8 (horizontal row) 243 * 9,18,27,36,45,54,63,72 (vertcal column) 244 * 1,2,9,10,11,18,19,20 (3x3 square) 245 * That's a total of 24 square numbers, but 4 of them 246 * are duplicates, so only the unique 20 are kept. 247 * Each index is stored multiplied by 2 to make indexing 248 * into 'bits' faster. 249 2226: 02 04 06 250 others db 2,4,6,8,10,12,14,16,18,20,22 2231: 24 26 28 251 db 36,38,40,54,72,90,108,126,144 223A: 00 04 06 252 db 0,4,6,8,10,12,14,16,18,20,22 2245: 24 26 28 253 db 36,38,40,56,74,92,110,128,146 224E: 00 02 06 254 db 0,2,6,8,10,12,14,16,18,20,22 2259: 24 26 28 255 db 36,38,40,58,76,94,112,130,148 2262: 00 02 04 256 db 0,2,4,8,10,12,14,16,24,26,28 226D: 2A 2C 2E 257 db 42,44,46,60,78,96,114,132,150 2276: 00 02 04 258 db 0,2,4,6,10,12,14,16,24,26,28 2281: 2A 2C 2E 259 db 42,44,46,62,80,98,116,134,152 228A: 00 02 04 260 db 0,2,4,6,8,12,14,16,24,26,28 2295: 2A 2C 2E 261 db 42,44,46,64,82,100,118,136,154 229E: 00 02 04 262 db 0,2,4,6,8,10,14,16,30,32,34 22A9: 30 32 34 263 db 48,50,52,66,84,102,120,138,156 22B2: 00 02 04 264 db 0,2,4,6,8,10,12,16,30,32,34 22BD: 30 32 34 265 db 48,50,52,68,86,104,122,140,158 22C6: 00 02 04 266 db 0,2,4,6,8,10,12,14,30,32,34 22D1: 30 32 34 267 db 48,50,52,70,88,106,124,142,160 22DA: 00 02 04 268 db 0,2,4,20,22,24,26,28,30,32,34 22E5: 24 26 28 269 db 36,38,40,54,72,90,108,126,144 22EE: 00 02 04 270 db 0,2,4,18,22,24,26,28,30,32,34 22F9: 24 26 28 271 db 36,38,40,56,74,92,110,128,146 2302: 00 02 04 272 db 0,2,4,18,20,24,26,28,30,32,34 230D: 24 26 28 273 db 36,38,40,58,76,94,112,130,148 2316: 06 08 0A 274 db 6,8,10,18,20,22,26,28,30,32,34 ===== Page 6 - *** July 15, 2006 *** ===== 2321: 2A 2C 2E 275 db 42,44,46,60,78,96,114,132,150 232A: 06 08 0A 276 db 6,8,10,18,20,22,24,28,30,32,34 2335: 2A 2C 2E 277 db 42,44,46,62,80,98,116,134,152 233E: 06 08 0A 278 db 6,8,10,18,20,22,24,26,30,32,34 2349: 2A 2C 2E 279 db 42,44,46,64,82,100,118,136,154 2352: 0C 0E 10 280 db 12,14,16,18,20,22,24,26,28,32,34 235D: 30 32 34 281 db 48,50,52,66,84,102,120,138,156 2366: 0C 0E 10 282 db 12,14,16,18,20,22,24,26,28,30,34 2371: 30 32 34 283 db 48,50,52,68,86,104,122,140,158 237A: 0C 0E 10 284 db 12,14,16,18,20,22,24,26,28,30,32 2385: 30 32 34 285 db 48,50,52,70,88,106,124,142,160 238E: 00 02 04 286 db 0,2,4,18,20,22,38,40,42,44,46 2399: 30 32 34 287 db 48,50,52,54,72,90,108,126,144 23A2: 00 02 04 288 db 0,2,4,18,20,22,36,40,42,44,46 23AD: 30 32 34 289 db 48,50,52,56,74,92,110,128,146 23B6: 00 02 04 290 db 0,2,4,18,20,22,36,38,42,44,46 23C1: 30 32 34 291 db 48,50,52,58,76,94,112,130,148 23CA: 06 08 0A 292 db 6,8,10,24,26,28,36,38,40,44,46 23D5: 30 32 34 293 db 48,50,52,60,78,96,114,132,150 23DE: 06 08 0A 294 db 6,8,10,24,26,28,36,38,40,42,46 23E9: 30 32 34 295 db 48,50,52,62,80,98,116,134,152 23F2: 06 08 0A 296 db 6,8,10,24,26,28,36,38,40,42,44 23FD: 30 32 34 297 db 48,50,52,64,82,100,118,136,154 2406: 0C 0E 10 298 db 12,14,16,30,32,34,36,38,40,42,44 2411: 2E 32 34 299 db 46,50,52,66,84,102,120,138,156 241A: 0C 0E 10 300 db 12,14,16,30,32,34,36,38,40,42,44 2425: 2E 30 34 301 db 46,48,52,68,86,104,122,140,158 242E: 0C 0E 10 302 db 12,14,16,30,32,34,36,38,40,42,44 2439: 2E 30 32 303 db 46,48,50,70,88,106,124,142,160 2442: 00 12 24 304 db 0,18,36,56,58,60,62,64,66,68,70 244D: 48 4A 4C 305 db 72,74,76,90,92,94,108,126,144 2456: 02 14 26 306 db 2,20,38,54,58,60,62,64,66,68,70 2461: 48 4A 4C 307 db 72,74,76,90,92,94,110,128,146 246A: 04 16 28 308 db 4,22,40,54,56,60,62,64,66,68,70 2475: 48 4A 4C 309 db 72,74,76,90,92,94,112,130,148 247E: 06 18 2A 310 db 6,24,42,54,56,58,62,64,66,68,70 2489: 4E 50 52 311 db 78,80,82,96,98,100,114,132,150 2492: 08 1A 2C 312 db 8,26,44,54,56,58,60,64,66,68,70 249D: 4E 50 52 313 db 78,80,82,96,98,100,116,134,152 24A6: 0A 1C 2E 314 db 10,28,46,54,56,58,60,62,66,68,70 24B1: 4E 50 52 315 db 78,80,82,96,98,100,118,136,154 24BA: 0C 1E 30 316 db 12,30,48,54,56,58,60,62,64,68,70 24C5: 54 56 58 317 db 84,86,88,102,104,106,120,138,156 24CE: 0E 20 32 318 db 14,32,50,54,56,58,60,62,64,66,70 24D9: 54 56 58 319 db 84,86,88,102,104,106,122,140,158 24E2: 10 22 34 320 db 16,34,52,54,56,58,60,62,64,66,68 24ED: 54 56 58 321 db 84,86,88,102,104,106,124,142,160 24F6: 00 12 24 322 db 0,18,36,54,56,58,74,76,78,80,82 2501: 54 56 58 323 db 84,86,88,90,92,94,108,126,144 250A: 02 14 26 324 db 2,20,38,54,56,58,72,76,78,80,82 2515: 54 56 58 325 db 84,86,88,90,92,94,110,128,146 251E: 04 16 28 326 db 4,22,40,54,56,58,72,74,78,80,82 2529: 54 56 58 327 db 84,86,88,90,92,94,112,130,148 2532: 06 18 2A 328 db 6,24,42,60,62,64,72,74,76,80,82 253D: 54 56 58 329 db 84,86,88,96,98,100,114,132,150 2546: 08 1A 2C 330 db 8,26,44,60,62,64,72,74,76,78,82 2551: 54 56 58 331 db 84,86,88,96,98,100,116,134,152 255A: 0A 1C 2E 332 db 10,28,46,60,62,64,72,74,76,78,80 2565: 54 56 58 333 db 84,86,88,96,98,100,118,136,154 256E: 0C 1E 30 334 db 12,30,48,66,68,70,72,74,76,78,80 2579: 52 56 58 335 db 82,86,88,102,104,106,120,138,156 2582: 0E 20 32 336 db 14,32,50,66,68,70,72,74,76,78,80 258D: 52 54 58 337 db 82,84,88,102,104,106,122,140,158 2596: 10 22 34 338 db 16,34,52,66,68,70,72,74,76,78,80 25A1: 52 54 56 339 db 82,84,86,102,104,106,124,142,160 25AA: 00 12 24 340 db 0,18,36,54,56,58,72,74,76,92,94 25B5: 60 62 64 341 db 96,98,100,102,104,106,108,126,144 25BE: 02 14 26 342 db 2,20,38,54,56,58,72,74,76,90,94 25C9: 60 62 64 343 db 96,98,100,102,104,106,110,128,146 25D2: 04 16 28 344 db 4,22,40,54,56,58,72,74,76,90,92 ===== Page 7 - *** July 15, 2006 *** ===== 25DD: 60 62 64 345 db 96,98,100,102,104,106,112,130,148 25E6: 06 18 2A 346 db 6,24,42,60,62,64,78,80,82,90,92 25F1: 5E 62 64 347 db 94,98,100,102,104,106,114,132,150 25FA: 08 1A 2C 348 db 8,26,44,60,62,64,78,80,82,90,92 2605: 5E 60 64 349 db 94,96,100,102,104,106,116,134,152 260E: 0A 1C 2E 350 db 10,28,46,60,62,64,78,80,82,90,92 2619: 5E 60 62 351 db 94,96,98,102,104,106,118,136,154 2622: 0C 1E 30 352 db 12,30,48,66,68,70,84,86,88,90,92 262D: 5E 60 62 353 db 94,96,98,100,104,106,120,138,156 2636: 0E 20 32 354 db 14,32,50,66,68,70,84,86,88,90,92 2641: 5E 60 62 355 db 94,96,98,100,102,106,122,140,158 264A: 10 22 34 356 db 16,34,52,66,68,70,84,86,88,90,92 2655: 5E 60 62 357 db 94,96,98,100,102,104,124,142,160 265E: 00 12 24 358 db 0,18,36,54,72,90,110,112,114,116,118 2669: 78 7A 7C 359 db 120,122,124,126,128,130,144,146,148 2672: 02 14 26 360 db 2,20,38,56,74,92,108,112,114,116,118 267D: 78 7A 7C 361 db 120,122,124,126,128,130,144,146,148 2686: 04 16 28 362 db 4,22,40,58,76,94,108,110,114,116,118 2691: 78 7A 7C 363 db 120,122,124,126,128,130,144,146,148 269A: 06 18 2A 364 db 6,24,42,60,78,96,108,110,112,116,118 26A5: 78 7A 7C 365 db 120,122,124,132,134,136,150,152,154 26AE: 08 1A 2C 366 db 8,26,44,62,80,98,108,110,112,114,118 26B9: 78 7A 7C 367 db 120,122,124,132,134,136,150,152,154 26C2: 0A 1C 2E 368 db 10,28,46,64,82,100,108,110,112,114,116 26CD: 78 7A 7C 369 db 120,122,124,132,134,136,150,152,154 26D6: 0C 1E 30 370 db 12,30,48,66,84,102,108,110,112,114,116 26E1: 76 7A 7C 371 db 118,122,124,138,140,142,156,158,160 26EA: 0E 20 32 372 db 14,32,50,68,86,104,108,110,112,114,116 26F5: 76 78 7C 373 db 118,120,124,138,140,142,156,158,160 26FE: 10 22 34 374 db 16,34,52,70,88,106,108,110,112,114,116 2709: 76 78 7A 375 db 118,120,122,138,140,142,156,158,160 2712: 00 12 24 376 db 0,18,36,54,72,90,108,110,112,128,130 271D: 84 86 88 377 db 132,134,136,138,140,142,144,146,148 2726: 02 14 26 378 db 2,20,38,56,74,92,108,110,112,126,130 2731: 84 86 88 379 db 132,134,136,138,140,142,144,146,148 273A: 04 16 28 380 db 4,22,40,58,76,94,108,110,112,126,128 2745: 84 86 88 381 db 132,134,136,138,140,142,144,146,148 274E: 06 18 2A 382 db 6,24,42,60,78,96,114,116,118,126,128 2759: 82 86 88 383 db 130,134,136,138,140,142,150,152,154 2762: 08 1A 2C 384 db 8,26,44,62,80,98,114,116,118,126,128 276D: 82 84 88 385 db 130,132,136,138,140,142,150,152,154 2776: 0A 1C 2E 386 db 10,28,46,64,82,100,114,116,118,126,128 2781: 82 84 86 387 db 130,132,134,138,140,142,150,152,154 278A: 0C 1E 30 388 db 12,30,48,66,84,102,120,122,124,126,128 2795: 82 84 86 389 db 130,132,134,136,140,142,156,158,160 279E: 0E 20 32 390 db 14,32,50,68,86,104,120,122,124,126,128 27A9: 82 84 86 391 db 130,132,134,136,138,142,156,158,160 27B2: 10 22 34 392 db 16,34,52,70,88,106,120,122,124,126,128 27BD: 82 84 86 393 db 130,132,134,136,138,140,156,158,160 27C6: 00 12 24 394 db 0,18,36,54,72,90,108,110,112,126,128 27D1: 82 92 94 395 db 130,146,148,150,152,154,156,158,160 27DA: 02 14 26 396 db 2,20,38,56,74,92,108,110,112,126,128 27E5: 82 90 94 397 db 130,144,148,150,152,154,156,158,160 27EE: 04 16 28 398 db 4,22,40,58,76,94,108,110,112,126,128 27F9: 82 90 92 399 db 130,144,146,150,152,154,156,158,160 2802: 06 18 2A 400 db 6,24,42,60,78,96,114,116,118,132,134 280D: 88 90 92 401 db 136,144,146,148,152,154,156,158,160 2816: 08 1A 2C 402 db 8,26,44,62,80,98,114,116,118,132,134 2821: 88 90 92 403 db 136,144,146,148,150,154,156,158,160 282A: 0A 1C 2E 404 db 10,28,46,64,82,100,114,116,118,132,134 2835: 88 90 92 405 db 136,144,146,148,150,152,156,158,160 283E: 0C 1E 30 406 db 12,30,48,66,84,102,120,122,124,138,140 2849: 8E 90 92 407 db 142,144,146,148,150,152,154,158,160 2852: 0E 20 32 408 db 14,32,50,68,86,104,120,122,124,138,140 285D: 8E 90 92 409 db 142,144,146,148,150,152,154,156,160 2866: 10 22 34 410 db 16,34,52,70,88,106,120,122,124,138,140 2871: 8E 90 92 411 db 142,144,146,148,150,152,154,156,158 412 413 * Table of pointers to 'others' array rows 414 ===== Page 8 - *** July 15, 2006 *** ===== 415 otherptr lup 81 287A: 26 22 416 dw *-otherptr*10+others ; (index * 20) 287C: 3A 22 416 dw *-otherptr*10+others ; (index * 20) 287E: 4E 22 416 dw *-otherptr*10+others ; (index * 20) 2880: 62 22 416 dw *-otherptr*10+others ; (index * 20) 2882: 76 22 416 dw *-otherptr*10+others ; (index * 20) 2884: 8A 22 416 dw *-otherptr*10+others ; (index * 20) 2886: 9E 22 416 dw *-otherptr*10+others ; (index * 20) 2888: B2 22 416 dw *-otherptr*10+others ; (index * 20) 288A: C6 22 416 dw *-otherptr*10+others ; (index * 20) 288C: DA 22 416 dw *-otherptr*10+others ; (index * 20) 288E: EE 22 416 dw *-otherptr*10+others ; (index * 20) 2890: 02 23 416 dw *-otherptr*10+others ; (index * 20) 2892: 16 23 416 dw *-otherptr*10+others ; (index * 20) 2894: 2A 23 416 dw *-otherptr*10+others ; (index * 20) 2896: 3E 23 416 dw *-otherptr*10+others ; (index * 20) 2898: 52 23 416 dw *-otherptr*10+others ; (index * 20) 289A: 66 23 416 dw *-otherptr*10+others ; (index * 20) 289C: 7A 23 416 dw *-otherptr*10+others ; (index * 20) 289E: 8E 23 416 dw *-otherptr*10+others ; (index * 20) 28A0: A2 23 416 dw *-otherptr*10+others ; (index * 20) 28A2: B6 23 416 dw *-otherptr*10+others ; (index * 20) 28A4: CA 23 416 dw *-otherptr*10+others ; (index * 20) 28A6: DE 23 416 dw *-otherptr*10+others ; (index * 20) 28A8: F2 23 416 dw *-otherptr*10+others ; (index * 20) 28AA: 06 24 416 dw *-otherptr*10+others ; (index * 20) 28AC: 1A 24 416 dw *-otherptr*10+others ; (index * 20) 28AE: 2E 24 416 dw *-otherptr*10+others ; (index * 20) 28B0: 42 24 416 dw *-otherptr*10+others ; (index * 20) 28B2: 56 24 416 dw *-otherptr*10+others ; (index * 20) 28B4: 6A 24 416 dw *-otherptr*10+others ; (index * 20) 28B6: 7E 24 416 dw *-otherptr*10+others ; (index * 20) 28B8: 92 24 416 dw *-otherptr*10+others ; (index * 20) 28BA: A6 24 416 dw *-otherptr*10+others ; (index * 20) 28BC: BA 24 416 dw *-otherptr*10+others ; (index * 20) 28BE: CE 24 416 dw *-otherptr*10+others ; (index * 20) 28C0: E2 24 416 dw *-otherptr*10+others ; (index * 20) 28C2: F6 24 416 dw *-otherptr*10+others ; (index * 20) 28C4: 0A 25 416 dw *-otherptr*10+others ; (index * 20) 28C6: 1E 25 416 dw *-otherptr*10+others ; (index * 20) 28C8: 32 25 416 dw *-otherptr*10+others ; (index * 20) 28CA: 46 25 416 dw *-otherptr*10+others ; (index * 20) 28CC: 5A 25 416 dw *-otherptr*10+others ; (index * 20) 28CE: 6E 25 416 dw *-otherptr*10+others ; (index * 20) 28D0: 82 25 416 dw *-otherptr*10+others ; (index * 20) 28D2: 96 25 416 dw *-otherptr*10+others ; (index * 20) 28D4: AA 25 416 dw *-otherptr*10+others ; (index * 20) 28D6: BE 25 416 dw *-otherptr*10+others ; (index * 20) 28D8: D2 25 416 dw *-otherptr*10+others ; (index * 20) 28DA: E6 25 416 dw *-otherptr*10+others ; (index * 20) 28DC: FA 25 416 dw *-otherptr*10+others ; (index * 20) 28DE: 0E 26 416 dw *-otherptr*10+others ; (index * 20) 28E0: 22 26 416 dw *-otherptr*10+others ; (index * 20) 28E2: 36 26 416 dw *-otherptr*10+others ; (index * 20) 28E4: 4A 26 416 dw *-otherptr*10+others ; (index * 20) 28E6: 5E 26 416 dw *-otherptr*10+others ; (index * 20) 28E8: 72 26 416 dw *-otherptr*10+others ; (index * 20) 28EA: 86 26 416 dw *-otherptr*10+others ; (index * 20) 28EC: 9A 26 416 dw *-otherptr*10+others ; (index * 20) 28EE: AE 26 416 dw *-otherptr*10+others ; (index * 20) 28F0: C2 26 416 dw *-otherptr*10+others ; (index * 20) 28F2: D6 26 416 dw *-otherptr*10+others ; (index * 20) 28F4: EA 26 416 dw *-otherptr*10+others ; (index * 20) 28F6: FE 26 416 dw *-otherptr*10+others ; (index * 20) 28F8: 12 27 416 dw *-otherptr*10+others ; (index * 20) 28FA: 26 27 416 dw *-otherptr*10+others ; (index * 20) 28FC: 3A 27 416 dw *-otherptr*10+others ; (index * 20) 28FE: 4E 27 416 dw *-otherptr*10+others ; (index * 20) 2900: 62 27 416 dw *-otherptr*10+others ; (index * 20) 2902: 76 27 416 dw *-otherptr*10+others ; (index * 20) ===== Page 9 - *** July 15, 2006 *** ===== 2904: 8A 27 416 dw *-otherptr*10+others ; (index * 20) 2906: 9E 27 416 dw *-otherptr*10+others ; (index * 20) 2908: B2 27 416 dw *-otherptr*10+others ; (index * 20) 290A: C6 27 416 dw *-otherptr*10+others ; (index * 20) 290C: DA 27 416 dw *-otherptr*10+others ; (index * 20) 290E: EE 27 416 dw *-otherptr*10+others ; (index * 20) 2910: 02 28 416 dw *-otherptr*10+others ; (index * 20) 2912: 16 28 416 dw *-otherptr*10+others ; (index * 20) 2914: 2A 28 416 dw *-otherptr*10+others ; (index * 20) 2916: 3E 28 416 dw *-otherptr*10+others ; (index * 20) 2918: 52 28 416 dw *-otherptr*10+others ; (index * 20) 291A: 66 28 416 dw *-otherptr*10+others ; (index * 20) 418 419 * Apple screen addresses 420 421 line22 equ $6D0 422 line23 equ $750 423 line24 equ $7D0 424 425 * "scrn" is an array of pointers into screen memory. Each 426 * pointer locates the corresponding grid box on the screen 427 * drawn by the BASIC program. 428 429 scrow mac ; Define a row of grid boxes 430 dw ]1+3,]1+7,]1+11,]1+15,]1+19 431 dw ]1+23,]1+27,]1+31,]1+35 432 eom 433 434 scrn scrow $580 ; Row 3 291C: 83 05 87 434 dw $580+3,$580+7,$580+11,$580+15,$580+19 2926: 97 05 9B 434 dw $580+23,$580+27,$580+31,$580+35 434 eom 435 scrow $680 ; Row 5 292E: 83 06 87 435 dw $680+3,$680+7,$680+11,$680+15,$680+19 2938: 97 06 9B 435 dw $680+23,$680+27,$680+31,$680+35 435 eom 436 scrow $780 ; Row 7 2940: 83 07 87 436 dw $780+3,$780+7,$780+11,$780+15,$780+19 294A: 97 07 9B 436 dw $780+23,$780+27,$780+31,$780+35 436 eom 437 scrow $4A8 ; Row 9 2952: AB 04 AF 437 dw $4A8+3,$4A8+7,$4A8+11,$4A8+15,$4A8+19 295C: BF 04 C3 437 dw $4A8+23,$4A8+27,$4A8+31,$4A8+35 437 eom 438 scrow $5A8 ; Row 11 2964: AB 05 AF 438 dw $5A8+3,$5A8+7,$5A8+11,$5A8+15,$5A8+19 296E: BF 05 C3 438 dw $5A8+23,$5A8+27,$5A8+31,$5A8+35 438 eom 439 scrow $6A8 ; ROW 13 2976: AB 06 AF 439 dw $6A8+3,$6A8+7,$6A8+11,$6A8+15,$6A8+19 2980: BF 06 C3 439 dw $6A8+23,$6A8+27,$6A8+31,$6A8+35 439 eom 440 scrow $7A8 ; Row 15 2988: AB 07 AF 440 dw $7A8+3,$7A8+7,$7A8+11,$7A8+15,$7A8+19 2992: BF 07 C3 440 dw $7A8+23,$7A8+27,$7A8+31,$7A8+35 440 eom 441 scrow $4D0 ; Row 17 299A: D3 04 D7 441 dw $4D0+3,$4D0+7,$4D0+11,$4D0+15,$4D0+19 29A4: E7 04 EB 441 dw $4D0+23,$4D0+27,$4D0+31,$4D0+35 441 eom 442 scrow $5D0 ; Row 19 29AC: D3 05 D7 442 dw $5D0+3,$5D0+7,$5D0+11,$5D0+15,$5D0+19 29B6: E7 05 EB 442 dw $5D0+23,$5D0+27,$5D0+31,$5D0+35 442 eom 443 444 * "setbox" is used to place a digit in the grid, whether 445 * it is known, or a guess. It also updates all the 446 * bitmasks for all the associated squares to indicate that 447 * they can't contain this digit. 448 ===== Page 10 - *** July 15, 2006 *** ===== 29BE: A4 FA 449 setbox ldy best 29C0: BE D5 21 450 ldx x2,y ; 'best' * two 29C3: BD 1C 29 451 lda scrn,x ; Animate the grid 29C6: 8D D7 29 452 sta stscrn+1 ; while solving. 29C9: BD 1D 29 453 lda scrn+1,x 29CC: 8D D8 29 454 sta stscrn+2 29CF: A5 FC 455 lda digit 29D1: 99 09 03 456 sta grid,y 29D4: 09 80 457 ora #$80 ; Set hi bit 29D6: 8D 00 00 458 stscrn staa 0*0 ; Store to screen 29D9: BD 7A 28 459 lda otherptr,x ; Get pointer to others 29DC: 8D F2 29 460 sta otherlp+1 ; and modify addresses 29DF: 8D 03 2A 461 sta ninelp+1 29E2: BD 7B 28 462 lda otherptr+1,x 29E5: 8D F3 29 463 sta otherlp+2 29E8: 8D 04 2A 464 sta ninelp+2 29EB: A2 13 465 ldx #20-1 ; Loop over others 29ED: A5 FD 466 lda bit ; <9 or =9 case? 29EF: F0 0F 467 beq setnine ; do =9 loop. 29F1: BC 00 00 468 otherlp ldya 0*0,x ; Other index * 2 29F4: B9 00 2F 469 b1 lda bitmap,y ; Update other's 'bits' 29F7: 05 FD 470 ora bit 29F9: 99 00 2F 471 b2 sta bitmap,y 29FC: CA 472 dex 29FD: 10 F2 473 bpl otherlp 29FF: 60 474 rts 475 2A00: A9 01 476 setnine lda #1 2A02: BC 00 00 477 ninelp ldya 0*0,x ; Other index * 2 2A05: 99 01 2F 478 b3 sta bitmap+1,y ; Update other's 9-bit 2A08: CA 479 dex 2A09: 10 F7 480 bpl ninelp 2A0B: 60 481 rts 482 483 * "unsetbox" is used to remove a digit from the grid. 484 * Zero is stored to indicate an unused square. It is too 485 * complicated to calculate what the bitmask ought to now 486 * contain, so it is up to the calling program to restore 487 * the bitmask from a previously saved value. 488 2A0C: A6 FA 489 unsetbox ldx best 2A0E: A9 00 490 lda #0 2A10: 9D 09 03 491 sta grid,x 2A13: BC D5 21 492 ldy x2,x ; 'best' * 2 2A16: B9 1C 29 493 lda scrn,y ; Animate the grid 2A19: 85 EE 494 sta p ; while solving. 2A1B: B9 1D 29 495 lda scrn+1,y 2A1E: 85 EF 496 sta p+1 2A20: A9 A0 497 lda #" " 2A22: A0 00 498 ldy #0 2A24: 91 EE 499 sta (p),y 2A26: 60 500 rts 501 502 * Print null-terminated ASCII string 503 * jsr ascout 504 * dw string 505 2A27: 18 506 ascout clc 2A28: 68 507 pla 2A29: 8D 43 2A 508 sta :1+1 2A2C: 8D 49 2A 509 sta :2+1 2A2F: 69 03 510 adc #3 2A31: 8D 5A 2A 511 sta :4+1 2A34: 68 512 pla 2A35: 8D 44 2A 513 sta :1+2 2A38: 8D 4A 2A 514 sta :2+2 2A3B: 69 00 515 adc #0 2A3D: 8D 5B 2A 516 sta :4+2 2A40: A0 01 517 ldy #1 2A42: B9 42 2A 518 :1 lda *,y ===== Page 11 - *** July 15, 2006 *** ===== 2A45: 85 EE 519 sta p 2A47: C8 520 iny 2A48: B9 48 2A 521 :2 lda *,y 2A4B: 85 EF 522 sta p+1 2A4D: A0 00 523 ldy #0 2A4F: B1 EE 524 :3 lda (p),y 2A51: F0 06 525 beq :4 2A53: 20 ED FD 526 jsr cout 2A56: C8 527 iny 2A57: D0 F6 528 bne :3 ; limit string len to 256 2A59: 4C 59 2A 529 :4 jmp * 530 531 * Solution found. Print message and pause. 532 2A5C: D3 EF EC 533 found asc "Solution ",00 2A66: AC A0 F0 534 found1 asc ", press key for next",8D 2A7B: A0 EF F2 535 asc " or ESC to quit.",87,00 536 2A8D: EE 01 03 537 prtsol inc num ; Increment solution num 2A90: D0 03 538 bne :print 2A92: EE 02 03 539 inc num+1 2A95: A9 15 540 :print lda #21 2A97: 85 25 541 sta cv 2A99: 20 22 FC 542 jsr vtab 2A9C: A9 00 543 lda #0 2A9E: 85 24 544 sta ch 2AA0: 20 27 2A 545 jsr ascout 2AA3: 5C 2A 546 dw found 2AA5: AE 01 03 547 ldx num ; Print number of solution 2AA8: AD 02 03 548 lda num+1 2AAB: 20 24 ED 549 jsr linprt 2AAE: 20 27 2A 550 jsr ascout 2AB1: 66 2A 551 dw found1 2AB3: AD 00 C0 552 :pause lda kbd ; Wait for keypress 2AB6: 10 FB 553 bpl :pause 2AB8: 8D 10 C0 554 sta kbstr ; Clear strobe 2ABB: C9 9B 555 cmp #$9B ; ESC? 2ABD: D0 09 556 bne rts ; -No, return for more. 2ABF: AE CB 21 557 ldx bstack ; -Yes, restore stack 2AC2: 9A 558 txs ; to return to BASIC 2AC3: A9 02 559 lda #2 ; "incomplete" return code 2AC5: 8D 00 03 560 sta rc 2AC8: 60 561 rts rts 562 563 * "select" is the heart of the algorithm. It works this 564 * way: First, the grid is searched for an empty square. If 565 * there isn't one, then the grid contains a solution, so it 566 * is printed. If an empty square is found, then it is 567 * compared with all other empty squares to see which one of 568 * them has the maximum number of 1-bits in its bitmask. 569 * That square is the one selected, and each of the possible 570 * values are tried in return, calling "select" recursively 571 * to search for a solution. Note that if a square has 9 572 * 1-bits in its bitmask, then there are no possible values, 573 * and "select" will return without any further recursion. 574 * Otherwise, if a square has 8 1-bits in its bitmask, then 575 * it has a forced choice, and only that choice will be 576 * taken at this level in the recursion. 577 * 578 * best (the square index) is to be stored at 0(vars) 579 * the (low ASCII) number is to be stored at 1(vars) 580 * the bit is to be stored at 2(vars) 581 2AC9: A9 FF 582 select lda #-1 ; initialize bstcnt to -1 2ACB: 85 FB 583 sta bstcnt ; the bit count for any free 584 ; square is nonnegative, so if 585 ; bstcnt is still -1 at the end 586 ; of the scan then the grid is 587 ; full, and we've encountered a 588 ; solution ===== Page 12 - *** July 15, 2006 *** ===== 2ACD: A2 50 589 ldx #80 2ACF: BD 09 03 590 scan lda grid,x ; scan grid for best bit count 2AD2: D0 1A 591 bne skipsq ; square already occupied 2AD4: BC D5 21 592 ldy x2,x 2AD7: B9 00 2F 593 b4 lda bitmap,y ; bits 2ADA: 8D DE 2A 594 sta :cnt+1 2ADD: AD 00 2E 595 :cnt lda count ; bit count (lo byte modified) 2AE0: 18 596 clc 2AE1: 79 01 2F 597 b5 adc bitmap+1,y ; bits+1 2AE4: C5 FB 598 cmp bstcnt ; Current box better? 2AE6: 30 06 599 bmi skipsq ; -no, worse. 2AE8: F0 04 600 beq skipsq ; -no, same. 2AEA: 86 FA 601 stx best ; Save new box index. 2AEC: 85 FB 602 sta bstcnt ; Save new best count. 2AEE: CA 603 skipsq dex 2AEF: 10 DE 604 bpl scan 605 2AF1: A5 FB 606 lda bstcnt ; If bstcnt still -1, tail 2AF3: 30 98 607 bmi prtsol ; recurse to print solution 608 2AF5: C9 09 609 cmp #9 ; If best count =9 then logical 2AF7: F0 CF 610 beq rts ; contradiction and we are done 611 2AF9: A9 31 612 lda #'1' 2AFB: 85 FC 613 sta digit 2AFD: A2 01 614 ldx #1 2AFF: 86 FD 615 stx bit 2B01: A5 FA 616 lda best 2B03: 0A 617 asl 2B04: A8 618 tay 2B05: B1 06 619 lda (bits),y 2B07: 85 FE 620 sta sqbits 621 2B09: 25 FD 622 :3 and bit ; can we use this digit? 2B0B: D0 29 623 bne :6 ; no, go to loop end 2B0D: A5 FB 624 lda bstcnt ; how many digits ruled out? 2B0F: C9 08 625 cmp #8 ; is it all but one? 2B11: D0 2E 626 bne :exp ; -No, do expensive recursion. 2B13: A0 00 627 :7 ldy #0 ; -Yes, do cheap recursion. 2B15: A5 FA 628 lda best ; save only "best" on var stack 2B17: 91 08 629 sta (vars),y 2B19: E6 08 630 inc vars 2B1B: D0 02 631 bne :8 2B1D: E6 09 632 inc vars+1 2B1F: 20 BE 29 633 :8 jsr setbox 2B22: 20 C9 2A 634 jsr select 2B25: A5 08 635 lda vars 2B27: D0 02 636 bne :nobor 2B29: C6 09 637 dec vars+1 2B2B: C6 08 638 :nobor dec vars 2B2D: A0 00 639 ldy #0 2B2F: B1 08 640 lda (vars),y 2B31: 85 FA 641 sta best 2B33: 4C 0C 2A 642 jmp unsetbox 643 2B36: E6 FC 644 :6 inc digit ; loop end: try next digit 2B38: 06 FD 645 asl bit ; move bit to next place 2B3A: F0 D7 646 beq :7 ; do a cheap call to try bit 9 2B3C: A5 FE 647 lda sqbits 2B3E: 4C 09 2B 648 jmp :3 649 650 * Begin expensive recursion 651 2B41: E6 FB 652 :exp inc bstcnt ; one more digit considered 2B43: A0 04 653 ldy #nvars-1 ; save variables 2B45: B9 FA 00 654 :35 lda var0,y 2B48: 91 08 655 sta (vars),y 2B4A: 88 656 dey 2B4B: 10 F8 657 bpl :35 2B4D: 18 658 clc ===== Page 13 - *** July 15, 2006 *** ===== 2B4E: A5 08 659 lda vars 2B50: 69 05 660 adc #nvars 2B52: 85 08 661 sta vars 2B54: A5 09 662 lda vars+1 2B56: 69 00 663 adc #0 2B58: 85 09 664 sta vars+1 665 2B5A: A9 00 666 lda #0 ; Push bits (page aligned) 2B5C: 85 EE 667 sta p 2B5E: A5 07 668 lda bits+1 2B60: 85 EF 669 sta p+1 2B62: 8D 7F 2B 670 sta :4+2 2B65: 69 01 671 adc #1 2B67: 85 07 672 sta bits+1 2B69: 8D F6 29 673 sta b1+2 2B6C: 8D FB 29 674 sta b2+2 2B6F: 8D 07 2A 675 sta b3+2 2B72: 8D D9 2A 676 sta b4+2 2B75: 8D E3 2A 677 sta b5+2 2B78: 8D 82 2B 678 sta :b6+2 2B7B: A0 A1 679 ldy #161 ; Copy loop 2B7D: B9 00 00 680 :4 ldaa 0*0,y 2B80: 99 00 2F 681 :b6 sta bitmap,y ; bits 2B83: 88 682 dey 2B84: D0 F7 683 bne :4 2B86: B1 EE 684 lda (p),y ; Copy 0th byte 2B88: 91 06 685 sta (bits),y 686 2B8A: 20 BE 29 687 jsr setbox 2B8D: 20 C9 2A 688 jsr select 689 2B90: C6 07 690 dec bits+1 ; restore bits 2B92: A5 07 691 lda bits+1 2B94: 8D F6 29 692 sta b1+2 2B97: 8D FB 29 693 sta b2+2 2B9A: 8D 07 2A 694 sta b3+2 2B9D: 8D D9 2A 695 sta b4+2 2BA0: 8D E3 2A 696 sta b5+2 697 2BA3: 38 698 sec ; restore variables 2BA4: A5 08 699 lda vars 2BA6: E9 05 700 sbc #nvars 2BA8: 85 08 701 sta vars 2BAA: A5 09 702 lda vars+1 2BAC: E9 00 703 sbc #0 2BAE: 85 09 704 sta vars+1 2BB0: A0 04 705 ldy #nvars-1 2BB2: B1 08 706 :5 lda (vars),y 2BB4: 99 FA 00 707 sta var0,y 2BB7: 88 708 dey 2BB8: 10 F8 709 bpl :5 710 2BBA: 20 0C 2A 711 jsr unsetbox 2BBD: 4C 36 2B 712 jmp :6 713 714 * The variable stack. 81 recursion levels allowed with 715 * space for "nvars" number of zero page variables. 716 2BC0: 00 00 00 717 varstk ds 81*nvars 718 719 * Count of number of 1-bits in a bitmap. Values are only 720 * given for a single byte, which therefore has a maximum 721 * of 8 bits. The ninth bit (in the high order byte) is 722 * accounted for by simply adding the high order byte to 723 * the count obtained from this table. 724 725 align 256 ; Page align for easy access 2D55: 00 00 00 725 ds *+256-1/256*256-* 725 eom 726 ===== Page 14 - *** July 15, 2006 *** ===== 2E00: 00 01 01 727 count db 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4 2E10: 01 02 02 728 db 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5 2E20: 01 02 02 729 db 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5 2E30: 02 03 03 730 db 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6 2E40: 01 02 02 731 db 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5 2E50: 02 03 03 732 db 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6 2E60: 02 03 03 733 db 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6 2E70: 03 04 04 734 db 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7 2E80: 01 02 02 735 db 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5 2E90: 02 03 03 736 db 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6 2EA0: 02 03 03 737 db 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6 2EB0: 03 04 04 738 db 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7 2EC0: 02 03 03 739 db 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6 2ED0: 03 04 04 740 db 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7 2EE0: 03 04 04 741 db 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7 2EF0: 04 05 05 742 db 4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8 743 744 * The bitmap stack. 81 recursion levels, and two bytes 745 * per square. $01 means that "1" is not possible, $02 746 * means that "2" is not possible, $04 means that "3" is 747 * not possible, ..., $80 means that "8" is not possible, 748 * and $100 (the low bit in the high order byte) means that 749 * "9" is not possible. The routines that access the bitmap 750 * typically are passed a bit mask. A mask of zero is a 751 * special case, corresponding to $100, the only bit stored 752 * in the high order byte. 753 754 align 256 ; Page aligned 754 ds *+256-1/256*256-* 754 eom 755 756 bitmap ds 0 757 758 sav sudoku.solver Object saved as sudoku.solver,A$2000,L$0F00,BIN --End assembly, 3840 bytes, Errors: 0 Symbol table - alphabetical order: ? CLRBOT =$2006 ? DRWGRID =$2003 ? SOLVER =$2000 MD align =$8000 ascout =$2A27 b1 =$29F4 b2 =$29F9 b3 =$2A05 b4 =$2AD7 b5 =$2AE1 best =$FA bit =$FD bitmap =$2F00 bits =$06 bittab =$21CC box =$2014 bstack =$21CB bstcnt =$FB ch =$24 clearbot=$2143 count =$2E00 cout =$FDED crout =$FD8E crout1 =$FD8B cv =$25 digit =$FC drawgrd =$20C3 found =$2A5C found1 =$2A66 gb =$2020 ge =$202A grid =$0309 gs =$201F gx =$2025 helplns =$2074 kbd =$C000 kbstr =$C010 lb =$202D le =$2037 line =$2009 line22 =$06D0 line23 =$0750 line24 =$07D0 linprt =$ED24 ls =$202C lx =$2032 main =$2156 ninelp =$2A02 num =$0301 nvars =$05 otherlp =$29F1 otherptr=$287A others =$2226 p =$EE pblblb =$2117 prbl2 =$F94A prtsol =$2A8D prtxt =$2129 rc =$0300 rts =$2AC8 scan =$2ACF scrn =$291C MD scrow =$8000 select =$2AC9 sep =$2039 setbox =$29BE setnine =$2A00 skipsq =$2AEE sqbits =$FE stscrn =$29D6 title =$2062 txtpag =$2000 unsetbox=$2A0C var0 =$FA vars =$08 varstk =$2BC0 vtab =$FC22 x2 =$21D5 Symbol table - numerical order: nvars =$05 bits =$06 vars =$08 ch =$24 cv =$25 p =$EE var0 =$FA best =$FA ===== Page 15 - *** July 15, 2006 *** ===== bstcnt =$FB digit =$FC bit =$FD sqbits =$FE rc =$0300 num =$0301 grid =$0309 line22 =$06D0 line23 =$0750 line24 =$07D0 MD align =$8000 ? SOLVER =$2000 txtpag =$2000 ? DRWGRID =$2003 ? CLRBOT =$2006 line =$2009 box =$2014 gs =$201F gb =$2020 gx =$2025 ge =$202A ls =$202C lb =$202D lx =$2032 le =$2037 sep =$2039 title =$2062 helplns =$2074 drawgrd =$20C3 pblblb =$2117 prtxt =$2129 clearbot=$2143 main =$2156 bstack =$21CB bittab =$21CC x2 =$21D5 others =$2226 otherptr=$287A scrn =$291C setbox =$29BE stscrn =$29D6 otherlp =$29F1 b1 =$29F4 b2 =$29F9 setnine =$2A00 ninelp =$2A02 b3 =$2A05 unsetbox=$2A0C ascout =$2A27 found =$2A5C found1 =$2A66 prtsol =$2A8D rts =$2AC8 select =$2AC9 scan =$2ACF b4 =$2AD7 b5 =$2AE1 skipsq =$2AEE varstk =$2BC0 count =$2E00 bitmap =$2F00 MD scrow =$8000 kbd =$C000 kbstr =$C010 linprt =$ED24 prbl2 =$F94A vtab =$FC22 crout1 =$FD8B crout =$FD8E cout =$FDED