Sudoku Solver

Contributions to this software library are always welcome. Please ensure that you post program listings rather than .raw files. They give a reasonable idea of what your program does without having to load them into a DM42 and you can also include comments in your code. Check out the following link for a decoder/encoder: https://technical.swissmicros.com/decoders/dm42/

You can then copy/paste the listing and post it in "code" tags.
User avatar
Mark Hardman
Posts: 118
Joined: Wed May 03, 2017 3:26 am
Location: Houston, TX

Re: Sudoku Solver

Post by Mark Hardman »

wawachief wrote:
Sun Dec 31, 2017 5:00 pm
tbd 3 : in fact, there is plenty o space under the grid to display the possibilities for the active cell, I think that would do the trick.
I remember a version of Sudoku on PalmOS that displayed the possibilities in the open cells using a 3 x 3 grid of dots. For example, if the possible numbers were 1,2,5 and 9 it was represented as:

Code: Select all

• •
  •
    •
This provides a visualization of all possible values for all open cells at the same time.

Might I also suggest that you make the validity checking optional?

Terrific work!

Mark Hardman
DM42: β00043, β00065, 00357 / DM41X: β00054, 00445 / DM32: β00278
DM10L: 017/100, DM11L: 00121, DM12L: 02005, DM15L: 00523, DM16L: 00008, DM41L: 00111
wawachief
Posts: 30
Joined: Tue Dec 12, 2017 7:39 pm
Location: France, Normandie

Re: Sudoku Solver

Post by wawachief »

Here is a new version with a light solver
New features
- ability to remove all the numbers excepts those given at the beginning (del key)
- ability to show all the possibilities for the active cell (. key)
- auto completion of all the cells for which a unique choice is possible (+ key)

by repeating the + key several times, you will be able to solve the easiest grids nearly automatically...

todo : marking the non editable cells
Last edited by wawachief on Tue Jan 02, 2018 5:29 pm, edited 2 times in total.
DM42 SN:00218
HP-11c - HP-19b - HP25 - HP 45 - HP42s - HP48gx
wawachief
Posts: 30
Joined: Tue Dec 12, 2017 7:39 pm
Location: France, Normandie

Re: Sudoku Solver

Post by wawachief »

Version 1.0 :)
Edit : Added comments on the listing and a README file in the archive with updated documentation.

This time I think I am done...

This version includes
- the marking for the fixed cells that needed to be done
and the following programs
- the solver ported from hp15 that I already posted
- M2R (Matrix to Register)
- R2M (Register to Matrix)

The solver is provided as an external tool because the gui program is long enough... and I think it could be greatly optimized. If you have a grid in the GUI you want to solve with the solver, just proceed as follow:
XEQ M2R : loads the grid into the registers
XEQ SdSlv : Solves the grid... if it can !
XEQ R2M : reads the result into the matrix
XEQ SUDOKU : see the result in graphical form

The program is usable and does what I planned in the beginning. The DM42 is definitively a very pleasant calc to play with :)

Enjoy

Here is the complete code, with comments

Code: Select all

00 { 1715-Byte Prgm }
@
@ (BUFL) : display digit to coords x,y
@

01▸LBL B            
02 STO ST Z         @  Input Z:y Y:x X: Digit or Y:complex(x,y) X:Digit
03 ABS              
04 40               
05 +                @  uses LBL 40->51 + stack + alpha reg
06 XEQ IND ST X
07 R↓
08 AGRAPH
09 X<>Y
10 X≥0?
11 RTN
12 SF 34
13 SF 35
14 "÷÷÷÷÷÷"
15 CLX
16 128
17 XTOA
18 CLX
19 192
20 XTOA
21 R↓
22 AGRAPH
23 CF 34
24 SF 35
25 RTN
26▸LBL 40       @ 0 displays blank space
27 "÷÷÷÷÷÷÷"
28 RTN
29▸LBL 50       @ 10 displays 0
30 "÷>AAA>÷"
31 RTN
32▸LBL 41
33 "÷"
34 4
35 XTOA
36 ├"B"
37 CLX
38 127
39 XTOA
40 ├"@÷÷"
41 R↓
42 RTN
43▸LBL 42
44 "÷rIIIF÷"
45 RTN
46▸LBL 43
47 "÷"III6÷"
48 RTN
49▸LBL 44
50 "÷0($r!÷"
51 RTN
52▸LBL 45
53 "÷OIII1÷"
54 RTN
55▸LBL 46
56 "÷>III2÷"
57 RTN
58▸LBL 47
59 "÷×aμ"
60 13
61 XTOA
62 R↓
63 ├"∫÷"
64 RTN
65▸LBL 48
66 "÷6III6÷"
67 RTN
68▸LBL 49
69 "÷&III>÷"
70 RTN
71▸LBL 51       @ 11 displays black cursor
72 CLA
73 255
74 XTOA
75 XTOA
76 XTOA
77 XTOA
78 XTOA
79 XTOA
80 XTOA
81 R↓
82 RTN

@
@   (LineHV) : draw horizontal/vertical line
@

83▸LBL H 
84 R↓               @ Input : T:x1 Y:x2 X:y
85 1ᴇ3          @ FS?01 : Horizontal
86 ÷            @ FC?01 : vertical
87 +            @ uses LBL 55 + stack + Flag01
88 R↑
89▸LBL 55       @ Loop
90 FS? 01
91 X<>Y
92 PIXEL
93 FS? 01
94 X<>Y
95 ISG ST Y
96 GTO 55
97 RTN

@
@ (GRILLE) : Draw sudoku grid
@

98▸LBL G            @ uses LBL 60->63 + stack
99 2
100 STO "GrMod"
101 CLLCD
102 10.1001
103 SF 01
104▸LBL 60
105 50
106 140
107 RCL ST Z
108 IP
109 XEQ H
110 R↓
111 R↓
112 ISG ST X
113 GTO 60
114 50.1401
115 CF 01
116▸LBL 61
117 10
118 100
119 RCL ST Z
120 IP
121 XEQ H
122 R↓
123 R↓
124 ISG ST X
125 GTO 61
126 SF 01
127 11.1013
128▸LBL 62
129 50
130 140
131 RCL ST Z
132 IP
133 XEQ H
134 R↓
135 R↓
136 ISG ST X
137 GTO 62
138 CF 01
139 51.1413
140▸LBL 63
141 10
142 100
143 RCL ST Z
144 IP
145 XEQ H
146 R↓
147 R↓
148 ISG ST X
149 GTO 63
150 RTN

@
@ (DisnNb) : Display number in the grid
@

151▸LBL D           @ Input : Y:N X:j 
152 1               @ N : number to display
153 -               @ j : index in the grid
154 81
155 MOD
156 ENTER
157 ENTER
158 9
159 MOD
160 10
161 ×
162 X<>Y
163 9
164 ÷
165 IP
166 10
167 ×
168 COMPLEX
169 52
170 ENTER
171 12
172 COMPLEX
173 +
174 X<>Y
175 GTO B

@
@ Main program
@

176▸LBL "SUDOKU"            @ Needs to find a register named SudoGr
177 CF 00                   @ Flag 00 : enable/disable bip when writing into protected cells
178 XEQ G                   @ which contains a 1x81 matrix
179▸LBL 59                  @ -> Display numbers in the grid
180 INDEX "SudoGr"
181 81
182 STO 00
183 CF 34
184 SF 35
185▸LBL 80                  @ Loop to display the numbers in the grid
186 RCLEL
187 RCLIJ
188 X<>Y
189 R↓
190 XEQ D
191 J+
192 DSE 00
193 GTO 80
194 1
195 STO 01
196▸LBL 90                  @ Main loop. Wait for a Key  
197 SF 34                   @ and take appropriate actions
198 SF 35
199 11
200 RCL 01
201 XEQ D
202 GETKEY
203 17                      @ keys from 17(del) to 37 (+)
204 X>Y?                    @ are handled via indirect adressing
205 GTO 91                  @ other (ENTER) are handled in LBL 91 routine
206 CLX
207 37
208 X<Y?
209 GTO 91
210 R↓
211 GTO IND ST X
212▸LBL 91
213 CLX
214 13
215 X=Y?
216 GTO 93
217 CLX
218 GTO 90
219▸LBL 17                  @ Handles keys 17 to 35
220 SF 00
221 XEQ 99
222 81
223 STO 01
224▸LBL 96
225 CLX
226 XEQ 98
227 DSE 01
228 GTO 96
229 CF 00
230 GTO 90
231▸LBL 34
232 0
233 XEQ 98
234 GTO 90
235▸LBL 19
236 7
237 XEQ 98
238 GTO 90
239▸LBL 20
240 8
241 XEQ 98
242 GTO 90
243▸LBL 21
244 9
245 XEQ 98
246 GTO 90
247▸LBL 24
248 4
249 XEQ 98
250 GTO 90
251▸LBL 25
252 5
253 XEQ 98
254 GTO 90
255▸LBL 26
256 6
257 XEQ 98
258 GTO 90
259▸LBL 29
260 1
261 XEQ 98
262 GTO 90
263▸LBL 30
264 2
265 XEQ 98
266 GTO 90
267▸LBL 31
268 3
269 XEQ 98
270 GTO 90
271▸LBL 18
272 XEQ 99
273 9
274 STO- 01
275 GTO 90
276▸LBL 22
277 XEQ 99
278 1
279 STO- 01
280 GTO 90
281▸LBL 23
282 XEQ 99
283 9
284 STO+ 01
285 GTO 90
286▸LBL 27
287 XEQ 99
288 1
289 STO+ 01
290 GTO 90
291 GTO 99
292▸LBL 98
293 1
294 RCL 01
295 1
296 -
297 81
298 MOD
299 1
300 +
301 STOIJ
302 R↓
303 R↓
304 RCLEL
305 X<0?
306 GTO 95
307 R↓
308 STOEL
309 RCL ST Z
310 CF 34
311 SF 35
312 XEQ D
313 RTN
314▸LBL 95              @ Try to write in a protected cell
315 FS? 00
316 RTN
317 XEQ 99
318 TONE 9
319 RTN
320▸LBL 99              @ Erases cursor
321 11
322 RCL 01
323 XEQ D
324 RTN
325▸LBL 93              @ Locks the cells in the grid
326 XEQ 99              @ a locked cell is represented in the matrix
327 TONE 2              @ by a negative number
328 1
329 1
330 STOIJ
331 81
332▸LBL 94              @ Loop that goes through the grid
333 RCLEL
334 ABS
335 +/-
336 STOEL
337 J+
338 R↓
339 DSE ST X
340 GTO 94
341 GTO 59              @ Forces the display to show marks for locked cells

@
@ returns all connected cells into alpha
@

342▸LBL 70              @ No inputs. OUtput via alpha
343 CLA
344 RCL 01              @ uses 71 72 73 74 for internal loops
345 1                   @ uses Reg 02 as temporary variable
346 -
347 81
348 MOD
349 STO 01
350 27
351 ÷
352 IP
353 27
354 ×
355 RCL 01
356 9
357 MOD
358 3
359 ÷
360 IP
361 3
362 ×
363 +
364 1
365 +
366 STO 02
367 2ᴇ-3
368 0
369▸LBL 71              @ Get the current 3x3 block around the cell
370 CLX
371 2ᴇ-3
372▸LBL 72
373 RCL ST Y
374 IP
375 9
376 ×
377 RCL ST Y
378 IP
379 +
380 RCL+ 02
381 1
382 X<>Y
383 STOIJ
384 R↓
385 R↓
386 RCLEL
387 ABS
388 AIP
389 R↓
390 ISG ST X
391 GTO 72
392 ISG ST Y
393 GTO 71
394 RCL 01
395 9
396 ÷
397 IP
398 9
399 ×
400 1
401 +
402 RCL ST X
403 8
404 +
405 1ᴇ3
406 ÷
407 +
408▸LBL 73              @ Get the current line
409 1
410 RCL ST Y
411 STOIJ
412 R↓
413 R↓
414 RCLEL
415 ABS
416 AIP
417 R↓
418 ISG ST X
419 GTO 73
420 RCL 01
421 9
422 MOD
423 1
424 +
425 0.08109
426 +
427▸LBL 74              @ Get the current colomn
428 1
429 RCL ST Y
430 IP
431 STOIJ
432 R↓
433 R↓
434 RCLEL
435 ABS
436 AIP
437 R↓
438 ISG ST X
439 GTO 74
440 1
441 STO+ 01
442 RTN

@
@ find and fill all the cells with only one choice
@

443▸LBL 37
444 XEQ 99          @ Flag 01 : display possibilities
445 CF 01
446 81
447 STO 01
448▸LBL 65          @ LBL 65 (loop)  67
449 1
450 RCL 01
451 STOIJ
452 RCLEL
453 X≠0?
454 GTO 67
455 0
456 STO 05
457 XEQ 70
458 9
459 XEQ 75
460 RCL 05
461 10
462 X>Y?
463 XEQ 66          
464▸LBL 67          @ end of loop
465 DSE 01
466 GTO 65
467 GTO 90
468▸LBL 66          @ 1 possibility found
469 RCL 05
470 X=0?
471 RTN
472 XEQ 98
473 RTN
474 GTO 90

@
@ Display possibilities for a cell
@

475▸LBL 35
476 SF 01           @ Uses Lbl 75 76 77 78
477 XEQ 99          @ Reg 04 03 05 : tmp var
478 CF 34
479 SF 35
480 50
481 STO 04          @ Reg 04 : position
482 0
483 STO 05          @ Reg 05 : all possibilities in one number
484 1
485 RCL 01
486 1
487 -
488 81
489 MOD
490 1
491 +
492 STOIJ
493 STO 01
494 RCLEL
495 X<0?
496 GTO 77
497 XEQ 70
498 9
499▸LBL 75          @ Loop
500 RCL ST X
501 48
502 +
503 POSA
504 1
505 +
506 X=0?
507 XEQ 76
508 R↓
509 DSE ST X
510 GTO 75
511 FS? 01
512 GTO 77
513 GTO 79
514▸LBL 76          @ number available
515 R↓
516 RCL 05
517 10
518 ×
519 RCL ST Y
520 +
521 STO 05
522 RTN
523▸LBL 77          @ end of list
524 9
525 STO 03          @ Reg 03 : number to test
526▸LBL 78          @ Loop
527 RCL 04
528 105
529 COMPLEX
530 RCL 05
531 10
532 MOD
533 XEQ B
534 15
535 STO+ 04
536 RCL 05
537 10
538 ÷
539 IP
540 STO 05
541 DSE 03
542 GTO 78
543 GTO 90
544▸LBL 32              @ [ - ] key. Does nothing. Future usage ?
545 XEQ 99
546 GTO 90
547▸LBL 79
548 RCL 05
549 RTN
550 END

@
@ Matrix to Register
@ loads the grid into the registers
@ ready to be used by the solving program
@

551▸LBL "M2R"
552 8.016
553 STO 00
554 INDEX "SudoGr"
555▸LBL 20
556 9
557 1
558▸LBL 21
559 10
560 ×
561 RCLEL
562 ABS
563 +
564 J+
565 DSE ST Y
566 GTO 21
567 1ᴇ9
568 -
569 STO IND 00
570 ISG 00
571 GTO 20
572 RTN

@
@ Register to Matrix
@ load the result of the solving program into the matrix
@ ready to be used by the gui program
@

573▸LBL "R2M"
574 17.025
575 STO 00
576 INDEX "SudoGr"
577▸LBL 30
578 1ᴇ9
579 9
580▸LBL 31
581 RCL IND 00
582 RCL÷ ST Z
583 FP
584 10
585 ×
586 IP
587 STOEL
588 J+
589 R↓
590 10
591 STO÷ ST Z
592 R↓
593 DSE ST X
594 GTO 31
595 ISG 00
596 GTO 30
597 RTN

@
@ Solving program
@ http://www.hpmuseum.org/cgi-sys/cgiwrap/hpmuseum/articles.cgi?read=1220
@;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;       
@ 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)
@        Reg "I" : Indirect register

598▸LBL "SdSlv"
599 CLV "I"
600 XEQ 00
601 CF 02
602 CF 03
603 -1
604 STO 01
605▸LBL 02
606 1
607 XEQ 06
608 RCL 07
609 XEQ 07
610 RCL 07
611 X>0?
612 XEQ D
613 80
614 RCL 01
615 X≠Y?
616 GTO 02
617 -1
618 STO 01
619▸LBL E
620 VIEW 01
621 80
622 RCL 01
623 X=Y?
624 GTO 12
625 1
626 XEQ 06
627 RCL 07
628 X>0?
629 GTO E
630 XEQ 07
631▸LBL 08
632 9
633 RCL 06
634 X=Y?
635 GTO C
636 1
637 +
638 XEQ 07
639 RCL 06
640 XEQ 05
641 CF 02
642 RCL 02
643 XEQ 09
644 FS? 02
645 GTO 08
646 RCL 03
647 XEQ 09
648 FS? 02
649 GTO 08
650 RCL 04
651 XEQ 09
652 FS? 02
653 GTO 08
654 RCL 06
655 XEQ D
656 GTO E
657▸LBL C
658 -1
659 XEQ 06
660 X>0?
661 GTO C
662 RCL 06
663 SF 03
664 XEQ D
665 CF 03
666 GTO 08
667▸LBL 09
668 XEQ 01
669 RCL÷ 00
670 IP
671 2
672 ÷
673 FP
674 X>0?
675 SF 02
676 R↓
677 R↓
678 9
679 +
680 GTO 05
681▸LBL 05
682 STO 00
683 1
684 -
685 2
686 X<>Y
687 Y↑X
688 X<> 00
689 RTN
690▸LBL 01
691 ENTER
692 ENTER
693 26
694 XEQ 03
695 RCL IND "I"
696 RTN
697▸LBL 03
698 +
699 STO "I"
700 R↓
701 RTN
702▸LBL D
703 XEQ 05
704 RCL 02
705 XEQ B
706 RCL 03
707 XEQ B
708 RCL 04
709▸LBL B
710 XEQ 01
711 RCL 00
712 FS? 03
713 +/-
714 +
715 X<>Y
716 26
717 XEQ 03
718 STO IND "I"
719 R↓
720 9
721 +
722 GTO 05
723▸LBL 07
724 X<> 06
725 STO 00
726 RCL 02
727 17
728 XEQ 03
729 RCL IND "I"
730 RCL 06
731 RCL- 00
732 RCL× 05
733 +
734 STO IND "I"
735 RTN
736▸LBL 06
737 STO+ 01
738 RCL 01
739 RCL 01
740 9
741 ÷
742 IP
743 STO 02
744 9
745 ×
746 -
747 STO 03
748 3
749 ÷
750 RCL 02
751 3
752 ÷
753 IP
754 3
755 ×
756 +
757 STO 04
758 8
759 RCL- 03
760 10↑X
761 STO 05
762 RCL 02
763 17
764 XEQ 04
765 STO 06
766 RCL 02
767 8
768 XEQ 04
769 STO 07
770 RTN
771▸LBL 04
772 XEQ 03
773 RCL IND "I"
774 RCL÷ 05
775 IP
776 10
777 ÷
778 FP
779 10
780 ×
781 RTN
782▸LBL 00
783 SIZE 35
784 7
785 STO "I"
786 CLX
787▸LBL 10
788 STO IND "I"
789 DSE "I"
790 GTO 10
791 34.016
792 STO "I"
793 CLX
794▸LBL 11
795 STO IND "I"
796 DSE "I"
797 GTO 11
798 RTN
799▸LBL 12
800 CLST
801 RCL 17
802 RCL 18
803 RCL 19
804 STOP
805 CLST
806 RCL 20
807 RCL 21
808 RCL 22
809 STOP
810 CLST
811 RCL 23
812 RCL 24
813 RCL 25
814 RTN
815 END
Attachments
sudoku.zip
(6.84 KiB) Downloaded 331 times
Last edited by wawachief on Tue Jan 02, 2018 12:05 pm, edited 3 times in total.
DM42 SN:00218
HP-11c - HP-19b - HP25 - HP 45 - HP42s - HP48gx
User avatar
Walter
Posts: 3070
Joined: Tue May 02, 2017 11:13 am
Location: On a mission close to DRS, Germany

Re: Sudoku Solver

Post by Walter »

Gosh, more than 800 steps! Thanks for the hard work, wawachief, and thanks to SM we don't have to key that in step by step! :D
WP43 SN00000, 34S, and 31S for obvious reasons; HP-35, 45, ..., 35S, 15CE, DM16L S/N# 00093, DM42β SN:00041
wawachief
Posts: 30
Joined: Tue Dec 12, 2017 7:39 pm
Location: France, Normandie

Re: Sudoku Solver

Post by wawachief »

well... I did ... but I won't do it twice !
now it is 600 steps "only" for the gui, the solver is not mine, I just ported it from 15c to 42, not a big deal...

but, yes I am grateful to SM to offer tools like fat disk, usb, backups and states, a gorgeous display and so much memory ! It would not have been possible on the original 42. This device opens new horizons.
DM42 SN:00218
HP-11c - HP-19b - HP25 - HP 45 - HP42s - HP48gx
Post Reply