hp41programs

Sudoku

Sudoku for the HP-41


Overview
 

 1°)  Focal Program
 2°)  M-Code Routine
 3°)  Creating a Grid
 

-A sudoku is a 81-cell grid with 9 rows, 9 columns and 9 regions of 3 x 3 cells.
-Each row, each column and each region must contain all the integers from 1 to 9 exactly once, for instance:

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

-Given a partially empty grid, the puzzle consists in finding the missing numbers.
-The sudoku above is the solution of the problem below, where the empty cells are replaced by zeros:

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

1°)  Focal Program
 

-"SDK"  solves a sudoku by backtracking.
-Though it could theoretically solve any - solvable - sudoku,  only a few can be solved, due to prohibitive execution times !
 

Data Registers:         R00 & R82 to R94:  temp           ( Registers R01 thru R81 are to be initialized before executing "SDK" )

                                •  R01 to •  R81 = the elements of the sudoku grid, in column order ( or row order ) with 0 in the empty cells.

Flags: /
Subroutines: /

-Lines 99-102-119 are 3-byte GTOs
 
 

  01  LBL "SDK"
  02  3
  03  STO 86
  04  6.009
  05  STO 87
  06  9
  07  STO 88
  08  7
  09  STO 89
  10  73.00009
  11  STO 90
  12  82
  13  STO 91
  14  STO 00
  15   E3
  16  STO 92
  17  SIGN
  18  STO 94
  19  LBL 01
  20  DSE 00
  21  X=0?
  22  RTN
  23  RCL IND 00
  24  X#0?
  25  GTO 01 
  26  VIEW 00
  27  RCL 88
  28  STO 82
  29  LBL 02
  30  RCL 00
  31  RCL 94
  32  -
  33  STO 85
  34  RCL 88
  35  ST/ 85
  36  MOD
  37  STO 83
  38  RCL 90
  39  +
  40  X<> 85
  41  INT
  42  STO 84
  43  RCL 94 
  44  +
  45  RCL 88
  46  *
  47  STO 93
  48  LBL 03
  49  RCL IND 93
  50  ABS
  51  RCL 82
  52  X=Y?
  53  GTO 05
  54  RCL IND 85
  55  ABS
  56  X=Y?
  57  GTO 05
  58  DSE 93
  59  CLX
  60  DSE 85
  61  GTO 03
  62  RCL 86
  63  X<> 83
  64  RCL 86
  65  /
  66  INT
  67  RCL 84
  68  RCL 86 
  69  /
  70  INT
  71  RCL 88
  72  *
  73  +
  74  RCL 89
  75  +
  76  RCL 86
  77  *
  78  STO 85
  79  RCL 86
  80  -
  81  RCL 92
  82  /
  83  ST+ 85
  84  LBL 04
  85  RCL IND 85
  86  ABS
  87  RCL 82
  88  X=Y?
  89  GTO 05
  90  DSE 85
  91  GTO 04
  92  RCL 87
  93  ST- 85
  94  DSE 83
  95  GTO 04
  96  X<>Y
  97  CHS
  98  STO IND 00
  99  GTO 01
100  LBL 05
101  DSE 82
102  GTO 02
103  LBL 06
104  RCL 00
105  RCL 94
106  +
107  STO 00
108  RCL 91
109  X=Y?
110  SF 41
111  RCL IND 00
112  X>0?
113  GTO 06
114  CHS
115  ST+ IND 00
116  STO 82
117  VIEW 00
118  DSE 82
119  GTO 02
120  GTO 06
121  END

 
     ( 214 bytes / SIZE 095 )
 
 

      STACK        INPUTS      OUTPUTS
           X             /             /

 
Example1:   Solve the following sudoku:

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

-Store the 81 elements into R01 to R81 in column order ( 0  STO 01  STO 02  2  STO 03  .......................  0  STO 81 )

  XEQ "SDK"  >>>>  the solution hereunder is returned in about 1h02mn (!)

  4  6  1  |  3  7  2  |  8  5  9
  9  3  5  |  4  8  6  |  1  7  2
  2  7  8  |  9  1  5  |  3  6  4
  ---------------------------
  7  9  4  |  2  3  1  |  5  8  6
  5  1  2  |  8  6  9  |  4  3  7       Actually, the digits found by the HP-41 are preceded by a "minus" sign
  6  8  3  |  5  4  7  |  9  2  1
  --------------------------
  8  4  6  |  7  9  3  |  2  1  5
  1  2  9  |  6  5  8  |  7  4  3
  3  5  7  |  1  2  4  |  6  9  8
 

Example2:    With the empty grid - which is not a "proper" sudoku - "SDK" gives the following solution:

  XEQ "CLRG"
  XEQ "SDK"   >>>>    ( in about 2h30mn )

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

Notes:

-Obviously, this program is very slow, all the more that these examples belong to the easy puzzles.
-However, if you are using a good emulator in turbo mode, the execution times become about 6 seconds and 15 seconds respectively.

-The address of the current register is displayed ( 81 80 .... )
-If line 110 is executed, displaying "NONEXISTENT", the puzzle has no solution.
 

2°)  M-Code Routine
 
 

-This M-Code routine uses a similar scheme to solve a sudoku.
-It is almost 200 times as fast as the focal program.
-So, much more puzzles can be solved in a "raisonnable" time.
 
 
 

08B  "K"                    @E347  in my ROM
004  "D"
013  "S"
3C8  CLRKEY
378   C=c
03C   RCR 3
106   A=C S&X
130   LDI S&X
012   012h=018d
146   A=A+C S&X
130   LDI S&X
200   200h=512d
306   ?A<C S&X
381   ?NCGO
00A   NONEXISTENT
378   C=c
0A6  A<>C S&X
106   A=C S&X
1BC  RCR 11
130   LDI S&X
009   009
246   C=A-C S&X
106   A=C S&X
27C  RCR 9
0A6  A<>C S&X
0BC  RCR 5
070   N=C ALL               here N contains  the addresses of  R09  R00  R18  R09  in nybbles   11-10-9  8-7-6  5-4-3  2-1-0  respectively
04E   C=0 ALL
19C   PT=11
050    LD@PT- 1
050    LD@PT- 1
050    LD@PT- 1
050    LD@PT- 1
050    LD@PT- 1            C = 111111111   in nybbles  11 to 3
050    LD@PT- 1
050    LD@PT- 1
050    LD@PT- 1
050    LD@PT- 1
268    Q=C
10E   A=C ALL
1EE   C=C+C  ALL
1EE   C=C+C  ALL
1EE   C=C+C   ALL
20E   C=A+C ALL
228   P=C                      P = 999999999   in nybbles  11 to 3
0A0  SLCT P
21C  PT=2                     loop 0
3DC  PT=PT+1             LOOP1 at the address  E376  in my ROM
0B0   C= N ALL
354   ?PT=12
063   JNC+12d
266   C=C-1 S&X
27A  C=C-1 M
070   N=C ALL
106   A=C S&X
17C  RCR 6
366   ?A#C S&X
3AF   JC-11d                goto loop 0
04E   C=0 ALL
270   RAMSLCT
228   P=C
3E0   RTN                     the routine stops here if a solution is found
270   RAMSLCT
038   READATA
2E2   ?C#0@PT
377   JC-18d                 goto loop 1
10E   A=C ALL
046   C=0 S&X
270   RAMSLCT
238   C=P
158   M=C ALL           LOOP2  at the address  E38D in my ROM
0E0   SLCT Q
01C   PT=3
362   ?A#C@PT                 we test if the digit is different from all the other digits in the same column
07B   JNC+15d
3DC  PT=PT+1
354   ?PT=12
3E3   JNC-04
0A0   SLCT P
130   LDI S&X
008   008
10E   A=C ALL
0B0   C=N ALL
17C   RCR 6
226    C=C+1 S&X
270   RAMSLCT
0E6   B<>C S&X
038   READATA
362   ?A#C@PT                   we test if the digit is different from all the other digits in the same row
1A3   JNC+52d
0E6   B<>C S&X
1A6   A=A-1 S&X
3C3   JNC-08
0B0   C=N ALL
10E   A=C ALL
1A6   A=A-1 S&X
17C   RCR 6
226   C=C+1 S&X
226   C=C+1 S&X
226   C=C+1 S&X
306   ?A<C S&X
03F   JC+07
226   C=C+1 S&X
226   C=C+1 S&X
226   C=C+1 S&X
306   ?A<C S&X
017   JC+02
03C  RCR 3
0E6   B<>C S&X                  here, B S&X contains the address of the register in the right lower corner of the 3x3 region ( R09 or R06 or R03 )
0E0   SLCT Q
01C  PT=3
0A0  SLCT P
014  ?PT=3
087  JC+16d
054  ?PT=4
077  JC+14d
094  ?PT=5
067   JC+12d
0E0  SLCT Q
15C  PT=6
0A0  SLCT P
154  ?PT=6
03F  JC+07
294  ?PT=7
02F  JC+05
114  ?PT=8
01F  JC+03
0E0  SLCT Q
25C  PT=9
0E0  SLCT Q               now, pointer Q points to the right lower corner of the 3x3 region ( 9 or 6 or 3 )
198  C=M
130  LDI S&X                the 4 instructions on the left prepare 2 loops that may be executed 3 times
002  002
23E  C=C+1 MS
23E  C=C+1 MS
10E  A=C ALL
0E6  B<>C S&X
270  RAMSLCT
0E6  B<>C S&X
038  READATA
362  ?A#C@PT              we test if the digit is different from all the other digits in the same 3x3 region
0BB  JNC+23d
3DC  PT=PT+1
1A6  A=A-1 S&X
3E3   JNC-04
166   A=A+1 S&X
3D4  PT=PT-1
166   A=A+1 S&X
3D4  PT=PT-1
166   A=A+1 S&X
3D4  PT=PT-1
0E6  B<>C S&X
266  C=C-1 S&X
0E6  B<>C S&X
1BE  A=A-1 MS
36B  JNC-19
0A0  SELCT P
0B0  C=N ALL                 if the candidate number has successfully passed all the tests, it replaces the zero in the empty cell
270   RAMSLCT
038   READATA
0A2  A<>C@PT
2F0  WRITDATA
1D9  ?NCGO                   Change these words written in red according to the address of LOOP1 in your own ROM
38E   LOOP1
0A0  SLCT P                    the execution jumps here if the digit has been rejected
198  C=M ALL
10E  A=C ALL
046  C=0 S&X
270  RAMSLCT
278  C=Q
1CE  A=A-C ALL           we started with 999999999 in M, then we try 888888888 in M , ...etc...
0B0  C=N ALL
270  RAMSLCT
038  READATA
0AE  A<>C ALL
2EE  ?C#0 ALL               ...  until we arrive at  000000000
235  ?CGO                   Change these words written in red according to the address of LOOP2 in your own ROM
38F   LOOP2
3D4  PT=PT-1                if all the digits are rejected for this cell, we go to the previous cell ( backtracking )
214  ?PT=12
10F  JC+33d                  we must also move to the previous register if we were at the left of a register
0B0  C=N ALL
03C  RCR 3
270   RAMSLCT            otherwise, we check in a register between R10 and R18 if the cell was empty or not
038   READATA
2E2  ?C#0@PT
3C7  JC-08                     If the cell was not empty, we go to the previous cell again
0B0  C=N ALL
270  RAMSLCT
038  READATA
10E  A=C ALL
04E  C=0 ALL
0A2  A<>C@PT
0AE  A<>C ALL
2F0   WRITDATA          the number in the non-fixed cell is replaced by 0
1A2  A=A-1@PT
342   ?A#0@PT
36B  JNC-19d                if the last tested digit was 1, we again go to the previous non-fixed cell
046  C=0 S&X
270  RAMSLCT
278  C=Q
08E  B=A ALL
10E  A=C ALL
322  ?A<B@PT
01B  JNC+03                  if the digit in the previous cell was, say 8, we must recreate 777777777 which will be stored in CPU register M ( loop2 )
14E  A=A+C ALL
3EB  JNC-03
0B0  C=N ALL
270  RAMSLCT
038  READATA
0AE  A<>C ALL
235  ?NCGO                   Change these words written in red according to the address of LOOP2 in your own ROM
38E   LOOP2
35C  PT=12                     we arrive here if we must go to the "previous" register ( R01->R02->R03 ... )
0B0  C=N ALL
226  C=C+1 S&X
23A  C=C+1 M
070  N=C ALL
27C  RCR 9
106  A=C S&X
0BC  RCR 5
160  ?LOWBAT                 the 4 instructions written in yellow on the left
360  ?C RTN                      will stop the routine if the batteries are low
3CC  ?KEY                        or if you press any key
360   ?CRTN                      They may be deleted if you have a "newest" HP-41:  simply press  ENTER^  ON   to stop the program
306  ?A<C S&X
283  JNC-48d                    Replace this line by    2A3  JNC-44d    if you don't key in the yellow instructions
0B5  ?NCGO
0A2  DATA ERROR         if the "previous" register is R10, the sudoku cannot be solved !      ( @E42B in my ROM )

( 229 words / SIZE 019 )
 
 

      STACK        INPUTS      OUTPUTS
           X             /             /

 
-To use the M-Code routine, we must place the cells in nybbles  11 to 3 of registers R01 to R09 and the same data in R10 to R18.
-So the cells of a row must be the fractional part of a real number whose integer part is between 1 and 9

-The short routine hereunder lets the HP-41 deal with the registers R10 to R18.
 
 

 01  LBL "SUD"
 02  1.010009
 03  REGMOVE
 04  SDK
 05  END

 
Examples:    The examples of the 1st paragraph are now solved in 22 seconds and 50 seconds respectively.

A more difficult example:    With the grid:

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

   1.090042010   STO 01
   1.005000000   STO 02
   1.300000904   STO 03
   1.000000193   STO 04
   1.520700006   STO 05
   1.000001000   STO 06
   1.900050060   STO 07
   1.000204007   STO 08
   1.000016800   STO 09     XEQ "SUD"  ( not SDK )  returns a solution in 42mn44s

-The same solution is returned in 1mn28s (!) if we store the columns instead of the rows.

   ( 1.003050900  STO 01  1.900020000  STO 02  ...............  1.004360070  STO 09 )

-The solution is in registers R01 thru R09:
 

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

Notes:

-R00 is unused. Synthetic registers P & Q are used. Register P is cleared at the end if a solution has been found.

-Of course, here again, a good emulator like V41 in turbo mode will reduce the execution times by a factor about 600.
-So, many more puzzles can be solved in this case.
-Several minutes may still be required however ( perhaps hours in very difficult cases ... )

-You can also help your HP-41 in many ways:
-For example, if the last row is empty and the 8th row is not, swap them ( R08 <> R09 )
 and swap these registers again when the solution is found.
-Remember that the search starts with the last digit of register R09 then the next to last ( i-e 8th ) digit of R09 and so on ...
 

3°)  Creating a Grid
 

-This program uses a solved sudoku ( lines 08 to 25 ),  then it randomly permutes raws and columns
  and stores this - solved - sudoku in registers R19 to R27 ( lines 127-128 ).
-Finally, cells are replaced by 0 to get a puzzle with N fixed cells, where N is to be specified by the user.

-Line 126 is a three-byte GTO 01.
 
 

  01  LBL "GRID"
  02  STO 00
  03  81
  04  RCL Z
  05  -
  06  INT
  07  STO 18        
  08  1.798642315
  09  STO 01
  10  1.415973628
  11  STO 02
  12  1.362185974
  13  STO 03
  14  1.674528193
  15  STO 04
  16  1.521739486
  17  STO 05
  18  1.839461752
  19  STO 06
  20  1.943857261
  21  STO 07
  22  1.186294537
  23  STO 08
  24  1.257316849
  25  STO 09
  26  7.00003
  27  STO 15
  28  5
  29  STO 16
  30  LBL 01
  31  RCL 15
  32  STO 10
  33  LBL 02
  34  RCL 00
  35  R-D
  36  FRC
  37  STO 00
  38  3
  39  *
  40  INT
  41  LBL 03
  42  RCL 00        
  43  R-D
  44  FRC
  45  STO 00
  46  3
  47  *
  48  INT
  49  X=Y?
  50  GTO 03
  51  RCL 10
  52  ST+ Z
  53  +
  54  RCL IND Y
  55  X<> IND Y
  56  STO IND Z
  57  DSE 10
  58  GTO 02
  59  RCL 15
  60  STO 10
  61  LBL 04
  62  RCL 00
  63  R-D
  64  FRC
  65  STO 00
  66  3
  67  *
  68  INT
  69  LBL 05
  70  RCL 00
  71  R-D
  72  FRC
  73  STO 00        
  74  3
  75  *
  76  INT
  77  X=Y?
  78  GTO 05
  79  RCL 10
  80  +
  81  INT
  82  10^X
  83  STO 11
  84  CLX
  85  RCL 10
  86  +
  87  INT
  88  10^X
  89  STO 12
  90  9
  91  STO 14
  92  LBL 06
  93  RCL IND 14
  94  RCL 11
  95  *
  96  STO Y
  97  10
  98  MOD
  99  INT
100  STO 13
101  -
102  RCL 12
103  RCL 11
104  /
105  STO 17        
106  *
107  STO Y
108  10
109  MOD
110  INT
111  ST- Y
112  X<> 13
113  +
114  RCL 17
115  /
116  RCL 13
117  +
118  RCL 11
119  /
120  STO IND 14
121  DSE 14
122  GTO 06
123  DSE 10
124  GTO 04
125  DSE 16
126  GTO 01
127  1.019009
128  REGMOVE
129  LBL 07
130  9
131  STO 11
132  LBL 08
133  RCL 00
134  R-D
135  FRC
136  STO 00
137  9
138  *
139  INT
140  1
141  +
142  10^X
143  STO 12        
144  RCL IND 11
145  1
146  X=Y?
147  GTO 09
148  RDN
149  *
150  STO Y
151  10
152  MOD
153  INT
154  X=0?
155  GTO 08
156  -
157  RCL 12
158  /
159  STO IND 11
160  DSE 18
161  X=0?
162  GTO 10
163  LBL 09
164  DSE 11
165  GTO 08
166  GTO 07
167  LBL 10
168  END

 
   ( 321 bytes / SIZE 028 )
 
 

      STACK        INPUTS      OUTPUTS
           Y             N             /
           X              r             /

  where   N is an integer between 1 and 81 to get a puzzle with N non-empty cells
   and      r  is a random seed

Example:    You want to get a sudoku with 28 non-empty cells, and you choose 1 as random seed.

     28   ENTER^
      1    XEQ "GRID"   and we get the grid in registers R01 thru R09

  R01 = 1.800600130
  R02 = 1.003050004
  R03 = 1.000900068
  R04 = 1.008016000
  R05 = 1.005003800            ( the integer part doesn't really matter )
  R06 = 1.006500003
  R07 = 1.000361000
  R08 = 1.600000307
  R09 = 1.000005601

-So, the puzzle is

  8  0  0  |  6  0  0  |  1  3  0
  0  0  3  |  0  5  0  |  0  0  4
  0  0  0  |  9  0  0  |  0  6  8
  ---------------------------
  0  0  8  |  0  1  6  |  0  0  0
  0  0  5  |  0  0  3  |  8  0  0
  0  0  6  |  5  0  0  |  0  0  3
  --------------------------
  0  0  0  |  3  6  1  |  0  0  0
  6  0  0  |  0  0  0  |  3  0  7
  0  0  0  |  0  0  5  |  6  0  1

-If you don't solve the grid, one solution is in registers  R19 thru R27
-In this example, "SDK" gives another solution.

Notes:

-Replace line 28 ( 5 )  by a larger integer if you think that the original grid is not enough shuffled.
-This routine does not always return a proper sudoku ( i-e with a unique solution ), especially if N is small.
-If it happens ... it's only by chance !

-If you have a "RAND" M-code function, replace all the  RCL 00   R-D   FRC  STO 00  by  RAND
    replace lines 02-03-04 by    81  X<>Y
    and simply put N in X-register before executing "GRID"