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.
wawachief
Posts: 30
Joined: Tue Dec 12, 2017 7:39 pm
Location: France, Normandie

Sudoku Solver

Post by wawachief »

I found a sudoku solver for HP-15C here :
http://www.hpmuseum.org/cgi-sys/cgiwrap ... ?read=1220

I transposed if for the DM42. Given the speed of this calculator, the solver is quite usable : solving an easy grid takes 10s and a medium grid, around a minute with USB power. I didn't tried hard grids yet...

I made a few modification:
- added a routine to clear variables before launching the main loop otherwise, the program would fail
- added a routine at the end to show the solution 3 lines by 3 lines : pres R/S to display the next lines.
- added a view to show the progression of the backtracking algorithm. The goal is to reach 80...

To use it :
1. Type in your grid using an integer for each line in registers 8 to 15. Use 0 for unknown cells.
2. Launch sudo15 and wait for the magic to happen (reg 01 reaches 80)
3. read the solution on the stack, 3 lines by 3 lines. press R/S to see next section. The solution is stored in registers 17 to 25.

Example : This is an easy grid that takes less than 10s with USB power
9 _ 3 | _ 6 8 | 5 _ 4 | --> store 903068504 in register 08
_ _ 6 | _ 3 5 | _ _ _ | --> store 6035000 in register 09
_ _ 8 | 1 _ _ | _ 3 _ | --> etc...

_ _ _ | _ 5 7 | . 6 9 |
8 _ _ | _ _ _ | _ _ 2 |
6 7 _ | 8 9 _ | _ _ _ |

_ 6 _ | _ _ 9 | 1 _ _ |
_ _ _ | 4 1 _ | 2 _ _ |
5 _ 1 | 3 7 _ | 6 _ 8 | --> store 501370608 in register 16

XEQ sudo15

and voila :)
9 1 3 | 7 6 8 | 5 2 4 |
4 2 6 | 9 3 5 | 7 8 1 |
7 5 8 | 1 2 4 | 9 3 6 |

1 3 4 | 2 5 7 | 8 6 9 |
8 9 5 | 6 4 1 | 3 7 2 |
6 7 2 | 8 9 3 | 4 1 5 |

2 6 7 | 5 8 9 | 1 4 3 |
3 8 9 | 4 1 6 | 2 5 7 |
5 4 1 | 3 7 2 | 6 9 8 |

Enjoy...

Code: Select all

00 { 402-Byte Prgm }
01▸LBL "SUDO15"
02 XEQ 00
03 CF 02
04 CF 03
05 -1
06 STO 01
07▸LBL 02
08 1
09 XEQ 06
10 RCL 07
11 XEQ 07
12 RCL 07
13 X>0?
14 XEQ D
15 80
16 RCL 01
17 X≠Y?
18 GTO 02
19 -1
20 STO 01
21▸LBL E
22 VIEW 01
23 80
24 RCL 01
25 X=Y?
26 GTO 12
27 1
28 XEQ 06
29 RCL 07
30 X>0?
31 GTO E
32 XEQ 07
33▸LBL 08
34 9
35 RCL 06
36 X=Y?
37 GTO C
38 1
39 +
40 XEQ 07
41 RCL 06
42 XEQ 05
43 CF 02
44 RCL 02
45 XEQ 09
46 FS? 02
47 GTO 08
48 RCL 03
49 XEQ 09
50 FS? 02
51 GTO 08
52 RCL 04
53 XEQ 09
54 FS? 02
55 GTO 08
56 RCL 06
57 XEQ D
58 GTO E
59▸LBL C
60 -1
61 XEQ 06
62 X>0?
63 GTO C
64 RCL 06
65 SF 03
66 XEQ D
67 CF 03
68 GTO 08
69▸LBL 09
70 XEQ 01
71 RCL÷ 00
72 IP
73 2
74 ÷
75 FP
76 X>0?
77 SF 02
78 R↓
79 R↓
80 9
81 +
82 GTO 05
83▸LBL 05
84 STO 00
85 1
86 -
87 2
88 X<>Y
89 Y↑X
90 X<> 00
91 RTN
92▸LBL 01
93 ENTER
94 ENTER
95 26
96 XEQ 03
97 RCL IND "I"
98 RTN
99▸LBL 03
100 +
101 STO "I"
102 R↓
103 RTN
104▸LBL D
105 XEQ 05
106 RCL 02
107 XEQ B
108 RCL 03
109 XEQ B
110 RCL 04
111▸LBL B
112 XEQ 01
113 RCL 00
114 FS? 03
115 +/-
116 +
117 X<>Y
118 26
119 XEQ 03
120 STO IND "I"
121 R↓
122 9
123 +
124 GTO 05
125▸LBL 07
126 X<> 06
127 STO 00
128 RCL 02
129 17
130 XEQ 03
131 RCL IND "I"
132 RCL 06
133 RCL- 00
134 RCL× 05
135 +
136 STO IND "I"
137 RTN
138▸LBL 06
139 STO+ 01
140 RCL 01
141 RCL 01
142 9
143 ÷
144 IP
145 STO 02
146 9
147 ×
148 -
149 STO 03
150 3
151 ÷
152 RCL 02
153 3
154 ÷
155 IP
156 3
157 ×
158 +
159 STO 04
160 8
161 RCL- 03
162 10↑X
163 STO 05
164 RCL 02
165 17
166 XEQ 04
167 STO 06
168 RCL 02
169 8
170 XEQ 04
171 STO 07
172 RTN
173▸LBL 04
174 XEQ 03
175 RCL IND "I"
176 RCL÷ 05
177 IP
178 10
179 ÷
180 FP
181 10
182 ×
183 RTN
184▸LBL 00
185 SIZE 35
186 7
187 STO "I"
188 CLX
189▸LBL 10
190 STO IND "I"
191 DSE "I"
192 GTO 10
193 34.016
194 STO "I"
195 CLX
196▸LBL 11
197 STO IND "I"
198 DSE "I"
199 GTO 11
200 RTN
201▸LBL 12
202 CLST
203 RCL 17
204 RCL 18
205 RCL 19
206 STOP
207 CLST
208 RCL 20
209 RCL 21
210 RCL 22
211 STOP
212 CLST
213 RCL 23
214 RCL 24
215 RCL 25
216 RTN
217 END
Attachments
sudoku.zip
(478 Bytes) Downloaded 314 times
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 »

Thanks. Very nice idea. :D May try later.

BTW, isn't there an opportunity for a graphical output? Easier requesting than making, of course ... ;)
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 »

That's a bit challenging but I think the dm42 is capable of such a thing. Maybe I will give it a try...
DM42 SN:00218
HP-11c - HP-19b - HP25 - HP 45 - HP42s - HP48gx
etn
Posts: 22
Joined: Sun Dec 10, 2017 2:14 pm

Re: Sudoku Solver

Post by etn »

Merci pour ce programme! Thanks for this great program!

I slightly modified it to take advantage of the multi-line stack display of the DM42:
in essence, I added 2 subroutines, LBL20 to get input data directly from the stack (Row 1 ENTER Row 2 ENTER Row 3 R/S etc.)
and LBL21 to display the contents of registers 08-16 (just to double-check). Remove Step 3 (XEQ 21) if you don't want this.
Not exactly a graphical output, but a first step.

20171229-10230032.png
20171229-10230032.png (2.67 KiB) Viewed 18967 times

Hope this helps :)

Etienne

Code: Select all

00 { 603-Byte Prgm }
01▸LBL "SUDO15"
02 XEQ 20
03 XEQ 21
04 XEQ 00
05 CF 02
06 CF 03
07 -1
08 STO 01
09▸LBL 02
10 1
11 XEQ 06
12 RCL 07
13 XEQ 07
14 RCL 07
15 X>0?
16 XEQ D
17 80
18 RCL 01
19 X≠Y?
20 GTO 02
21 -1
22 STO 01
23▸LBL E
24 VIEW 01
25 80
26 RCL 01
27 X=Y?
28 GTO 12
29 1
30 XEQ 06
31 RCL 07
32 X>0?
33 GTO E
34 XEQ 07
35▸LBL 08
36 9
37 RCL 06
38 X=Y?
39 GTO C
40 1
41 +
42 XEQ 07
43 RCL 06
44 XEQ 05
45 CF 02
46 RCL 02
47 XEQ 09
48 FS? 02
49 GTO 08
50 RCL 03
51 XEQ 09
52 FS? 02
53 GTO 08
54 RCL 04
55 XEQ 09
56 FS? 02
57 GTO 08
58 RCL 06
59 XEQ D
60 GTO E
61▸LBL C
62 -1
63 XEQ 06
64 X>0?
65 GTO C
66 RCL 06
67 SF 03
68 XEQ D
69 CF 03
70 GTO 08
71▸LBL 09
72 XEQ 01
73 RCL÷ 00
74 IP
75 2
76 ÷
77 FP
78 X>0?
79 SF 02
80 R↓
81 R↓
82 9
83 +
84 GTO 05
85▸LBL 05
86 STO 00
87 1
88 -
89 2
90 X<>Y
91 Y↑X
92 X<> 00
93 RTN
94▸LBL 01
95 ENTER
96 ENTER
97 26
98 XEQ 03
99 RCL IND "I"
100 RTN
101▸LBL 03
102 +
103 STO "I"
104 R↓
105 RTN
106▸LBL D
107 XEQ 05
108 RCL 02
109 XEQ B
110 RCL 03
111 XEQ B
112 RCL 04
113▸LBL B
114 XEQ 01
115 RCL 00
116 FS? 03
117 +/-
118 +
119 X<>Y
120 26
121 XEQ 03
122 STO IND "I"
123 R↓
124 9
125 +
126 GTO 05
127▸LBL 07
128 X<> 06
129 STO 00
130 RCL 02
131 17
132 XEQ 03
133 RCL IND "I"
134 RCL 06
135 RCL- 00
136 RCL× 05
137 +
138 STO IND "I"
139 RTN
140▸LBL 06
141 STO+ 01
142 RCL 01
143 RCL 01
144 9
145 ÷
146 IP
147 STO 02
148 9
149 ×
150 -
151 STO 03
152 3
153 ÷
154 RCL 02
155 3
156 ÷
157 IP
158 3
159 ×
160 +
161 STO 04
162 8
163 RCL- 03
164 10↑X
165 STO 05
166 RCL 02
167 17
168 XEQ 04
169 STO 06
170 RCL 02
171 8
172 XEQ 04
173 STO 07
174 RTN
175▸LBL 04
176 XEQ 03
177 RCL IND "I"
178 RCL÷ 05
179 IP
180 10
181 ÷
182 FP
183 10
184 ×
185 RTN
186▸LBL 00
187 SIZE 35
188 7
189 STO "I"
190 CLX
191▸LBL 10
192 STO IND "I"
193 DSE "I"
194 GTO 10
195 34.016
196 STO "I"
197 CLX
198▸LBL 11
199 STO IND "I"
200 DSE "I"
201 GTO 11
202 RTN
203▸LBL 12
204 "ROWS 1-3:"
205 CLST
206 RCL 17
207 RCL 18
208 RCL 19
209 AVIEW
210 STOP
211 "ROWS 4-6:"
212 CLST
213 RCL 20
214 RCL 21
215 RCL 22
216 AVIEW
217 STOP
218 "ROWS 7-9:"
219 CLST
220 RCL 23
221 RCL 24
222 RCL 25
223 AVIEW
224 RTN
225▸LBL 20
226 CLST
227 RCL 08
228 RCL 09
229 RCL 10
230 "INPUT ROWS 1-3 "
231 ├"IN ZYX"
232 AVIEW
233 STOP
234 STO 10
235 R↓
236 STO 09
237 R↓
238 STO 08
239 CLST
240 RCL 11
241 RCL 12
242 RCL 13
243 "INPUT ROWS 4-6 "
244 ├"IN ZYX"
245 AVIEW
246 STOP
247 STO 13
248 R↓
249 STO 12
250 R↓
251 STO 11
252 CLST
253 RCL 14
254 RCL 15
255 RCL 16
256 "INPUT ROWS 7-9 "
257 ├"IN ZYX"
258 AVIEW
259 STOP
260 STO 16
261 R↓
262 STO 15
263 R↓
264 STO 14
265 RTN
266▸LBL 21
267 "ROWS 1-3:"
268 CLST
269 RCL 08
270 RCL 09
271 RCL 10
272 AVIEW
273 STOP
274 "ROWS 4-6:"
275 CLST
276 RCL 11
277 RCL 12
278 RCL 13
279 AVIEW
280 STOP
281 "ROWS 7-9:"
282 CLST
283 RCL 14
284 RCL 15
285 RCL 16
286 AVIEW
287 STOP
288 RTN
289 END
Attachments
sudo42.zip
(598 Bytes) Downloaded 297 times
wawachief
Posts: 30
Joined: Tue Dec 12, 2017 7:39 pm
Location: France, Normandie

Re: Sudoku Solver

Post by wawachief »

Work in progress

It is hard to let this calculator in its pouch so...
It is far from finished, I only spent a couple hours on it

Image
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 »

Looking quite promising! :D
WP43 SN00000, 34S, and 31S for obvious reasons; HP-35, 45, ..., 35S, 15CE, DM16L S/N# 00093, DM42β SN:00041
Thomas_ER
Posts: 192
Joined: Mon Jul 24, 2017 3:19 pm
Location: Germany

Re: Sudoku Solver

Post by Thomas_ER »

Walter wrote:
Sat Dec 30, 2017 10:08 pm
Looking quite promising! :D
1 +
[ HP48/49/50/42S/WP34/HP Prime/ DM42 (#00185+00318) ]
wawachief
Posts: 30
Joined: Tue Dec 12, 2017 7:39 pm
Location: France, Normandie

Re: Sudoku Solver

Post by wawachief »

Here is a first version of my sudoku program.
Image

It is a completely new program that focuses on the graphical interface. For now, it doesn't check the user input. It is the equivalent of paper and pen, you can write whatever you want where you want.

Usage
1. Create a new grid
The grid is a 1x81 matrix that must be stored in a variable named "SudoGr" (mind the lower and upper cases). If you want to create a new grid, just type
1 ENTER 81 NEW STO "SudoGr"

2. XEQ "SUDOKU". It draws the grid stored in the SudoGr register. If it is a new grid, you can fill the numbers you want.
To do that,
* move the cursor to the desired position using up/down arrows (up and down) and ÷/x (left and right).
* type a number (0 to clear the cell)
* once you have filled in all the given numbers on the grid, press ENTER to protect the grid. By doing so you won't be able to change these numbers anymore, letting you focus on the empty cells.
* now you can complete the grid

At any time, you can make a backup of your grid in another variable if you want :
RCL "SudoGr" STO "myBackup"

If you prefer, you can input the grid manually using the matrix editor. Type 0 for empty cell or any digit, row by row in one line of 81 digits.

To be done
- add a clear button that clears the user inputs leaving the original grid
- add some validity checking for user inputs
- add a help function that displays all the possible numbers in a cell
- add a helper function that completes automatically all the cells in which there is only one possibility
and maybe later...
- write an efficient solver...

Enjoy

Files
In the zip attached, you will find
- sudoku.raw which contains the program
- sudoku.s42 : it is a state file which contains a grid and the program, ready to be used. BE CAREFUL by restoring this state file, you will erase your current state. Be sure you have made a backup state of your calculator if you want to use this clean state with just the sudoku.
manSudoku.txt : some informations about the different routines if you want to look into the code.

Edit : I forgot to join the listing in plain text :(

Code: Select all

00 { 702-Byte Prgm }
01▸LBL B
02 40
03 +
04 XEQ IND ST X
05 R↓
06 AGRAPH
07 RTN
08▸LBL 40
09 "÷÷÷÷÷÷÷"
10 RTN
11▸LBL 50
12 "÷>AAA>÷"
13 RTN
14▸LBL 41
15 "÷"
16 4
17 XTOA
18 ├"B"
19 CLX
20 127
21 XTOA
22 ├"@÷÷"
23 R↓
24 RTN
25▸LBL 42
26 "÷rIIIF÷"
27 RTN
28▸LBL 43
29 "÷"III6÷"
30 RTN
31▸LBL 44
32 "÷0($r!÷"
33 RTN
34▸LBL 45
35 "÷OIII1÷"
36 RTN
37▸LBL 46
38 "÷>III2÷"
39 RTN
40▸LBL 47
41 "÷×aμ"
42 13
43 XTOA
44 R↓
45 ├"∫÷"
46 RTN
47▸LBL 48
48 "÷6III6÷"
49 RTN
50▸LBL 49
51 "÷&III>÷"
52 RTN
53▸LBL 51
54 CLA
55 255
56 XTOA
57 XTOA
58 XTOA
59 XTOA
60 XTOA
61 XTOA
62 XTOA
63 R↓
64 RTN
65▸LBL H
66 R↓
67 1ᴇ3
68 ÷
69 +
70 R↑
71▸LBL 55
72 FS? 01
73 X<>Y
74 PIXEL
75 FS? 01
76 X<>Y
77 ISG ST Y
78 GTO 55
79 RTN
80▸LBL G
81 2
82 STO "GrMod"
83 CLLCD
84 10.1001
85 SF 01
86▸LBL 60
87 50
88 140
89 RCL ST Z
90 IP
91 XEQ H
92 R↓
93 R↓
94 ISG ST X
95 GTO 60
96 50.1401
97 CF 01
98▸LBL 61
99 10
100 100
101 RCL ST Z
102 IP
103 XEQ H
104 R↓
105 R↓
106 ISG ST X
107 GTO 61
108 SF 01
109 11.1013
110▸LBL 62
111 50
112 140
113 RCL ST Z
114 IP
115 XEQ H
116 R↓
117 R↓
118 ISG ST X
119 GTO 62
120 CF 01
121 51.1413
122▸LBL 63
123 10
124 100
125 RCL ST Z
126 IP
127 XEQ H
128 R↓
129 R↓
130 ISG ST X
131 GTO 63
132 RTN
133▸LBL D
134 1
135 -
136 81
137 MOD
138 ENTER
139 ENTER
140 9
141 MOD
142 10
143 ×
144 X<>Y
145 9
146 ÷
147 IP
148 10
149 ×
150 COMPLEX
151 52
152 ENTER
153 12
154 COMPLEX
155 +
156 X<>Y
157 ABS
158 GTO B
159▸LBL "SUDOKU"
160 XEQ G
161 INDEX "SudoGr"
162 81
163 STO 00
164 CF 34
165 SF 35
166▸LBL 80
167 RCLEL
168 RCLIJ
169 X<>Y
170 R↓
171 XEQ D
172 J+
173 DSE 00
174 GTO 80
175 1
176 STO 01
177▸LBL 90
178 SF 34
179 SF 35
180 11
181 RCL 01
182 XEQ D
183 GETKEY
184 18
185 X>Y?
186 GTO 91
187 CLX
188 34
189 X<Y?
190 GTO 91
191 R↓
192 GTO IND ST X
193▸LBL 91
194 CLX
195 13
196 X=Y?
197 GTO 93
198 CLX
199 GTO 90
200▸LBL 34
201 0
202 GTO 98
203▸LBL 19
204 7
205 GTO 98
206▸LBL 20
207 8
208 GTO 98
209▸LBL 21
210 9
211 GTO 98
212▸LBL 24
213 4
214 GTO 98
215▸LBL 25
216 5
217 GTO 98
218▸LBL 26
219 6
220 GTO 98
221▸LBL 29
222 1
223 GTO 98
224▸LBL 30
225 2
226 GTO 98
227▸LBL 31
228 3
229 GTO 98
230▸LBL 18
231 XEQ 99
232 9
233 STO- 01
234 GTO 90
235▸LBL 22
236 XEQ 99
237 1
238 STO- 01
239 GTO 90
240▸LBL 23
241 XEQ 99
242 9
243 STO+ 01
244 GTO 90
245▸LBL 27
246 XEQ 99
247 1
248 STO+ 01
249 GTO 90
250 GTO 99
251▸LBL 98
252 1
253 RCL 01
254 1
255 -
256 81
257 MOD
258 1
259 +
260 STOIJ
261 R↓
262 R↓
263 RCLEL
264 X<0?
265 GTO 95
266 R↓
267 STOEL
268 RCL ST Z
269 CF 34
270 SF 35
271 XEQ D
272 GTO 90
273▸LBL 95
274 XEQ 99
275 TONE 9
276 GTO 90
277▸LBL 99
278 11
279 RCL 01
280 XEQ D
281 RTN
282▸LBL 93
283 XEQ 99
284 TONE 2
285 1
286 1
287 STOIJ
288 81
289▸LBL 94
290 RCLEL
291 ABS
292 +/-
293 STOEL
294 J+
295 R↓
296 DSE ST X
297 GTO 94
298 GTO 90
299 END
Last edited by wawachief on Tue Jan 02, 2018 5:30 pm, edited 2 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 »

wawachief wrote:
Sun Dec 31, 2017 4:03 pm
Here is a first version of my sudoku program.
...
To be done
1 add a clear button that clears the user inputs leaving the original grid
2 add some validity checking for user inputs
3 add a help function that displays all the possible numbers in a cell
4 add a helper function that completes automatically all the cells in which there is only one possibility
and maybe later...
5 write an efficient solver...
Great step for mankind :)

Regarding tbd 3: I doubt that's viable even on this great display. :?
And tbd 4: That would solve 'easy' and 'normal' sudokus (instead of difficult ones) since there are always cells in which there is only one possibility.
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 »

Regarding tbd 3: I doubt that's viable even on this great display. :?
And tbd 4: That would solve 'easy' and 'normal' sudokus (instead of difficult ones) since there are always cells in which there is only one possibility.
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.
tbd4 : yes, that's the point :) Once I have the suggestion routine, it will not be very difficult.
the efficient solver would be for the difficult ones. The solver I found for the HP15 is not optimized. I let it run over a night on Free42 on my PC with no results so I don't think it would be a great idea to include it.
DM42 SN:00218
HP-11c - HP-19b - HP25 - HP 45 - HP42s - HP48gx
Post Reply