Marcus,
The 33s version does use the fact that you can fit 9*4 bits into a register, which is why I think it is a much cleaner version.
On the 15c, it is not that simple to access 36 bits in a register and trying to do so would slow things down and increase the code size, so I ended up using 9 more registers than I needed on the 33s. That is actually something that I am working on now - eliminating the need for those 9 extra registers. I want to use the memory freed up to put in an input and output loop, and do some speed optimizations.
The code can be *much* quicker and smaller on a machine with bit manipulation, so it might not be so slow on a 16c. Smaller code could also reduce the number of subroutine calls (which are mostly there to shrink the code size) and that would help speed it up too.
I don't have true pseudo-code, but I have a C version that I started with. There are some minor differences but it gives you a good idea of what the program does.
Unfortunately, because it is not really pseudo-code, it doesn't do a good job identifying the places where bit maniputlation would help. In other words, the integer math that replaces bit manipulation is baked in.
The 33s C code is below. I posted the 33s program earlier.
Marcel
// HP-33s version of sudoku solver. Microsoft Visual Studio 2010 dialect
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <math.h>
// C App Only - Simulated input - test cases - comment in the one you want to use
#if 0
static int start[9] = {
354000000,
0,
1700500,
800030000,
97800006,
6100090,
700000400,
8006950,
10040030,
};
#endif
#if 1
static int start[9] = {
6007000,
3005900,
40075,
40020000,
5801700,
30400060,
7062430,
0,
801000090,
};
#endif
// bit locations in the word: 36 bits used in a word.
#define BIT_X 0
#define BIT_Y 9
#define BIT_B 18
#define BIT_S 27
// The HP 15-c Registers and Flags
static bool flag[8];
static _int64 reg[26];
// definition of which Register is which variable
#define VAR_TMP1 0 // Z: temporary value used by calculations
#define VAR_I 1 // A: current index into 81 space solution array
#define VAR_X 2 // B: row of current index -
#define VAR_Y 3 // C: column of current index
#define VAR_B 4 // D: block # of current index
#define VAR_M 5 // E: power of 10 of current column in compressed form
#define VAR_CSOL 6 // F: value in solution at current index
#define VAR_CSTR 7 // G: value in starting clues at current index
#define VAR_UCOMP_START 8 // H-P: 9 elements - bit flags as to what is set
#define VAR_SOL_START 17 // Q-Y: 9 elements - input & current solution being evaluated
#define FLAG_SET 2
/************************************************************************
Not in 33s code - replaced with a RMDR operator
************************************************************************/
static _int64 mod(_int64 y, _int64 x)
{
return y % x;
}
/************************************************************************
LBL F
************************************************************************/
static _int64 getPart(int val)
{
return reg[VAR_UCOMP_START + val];
}
/************************************************************************
LBL G
************************************************************************/
static void setPart(int xind, _int64 yval)
{
reg[VAR_UCOMP_START + xind] = yval;
}
/***********************************************************************
LBL J
***********************************************************************/
static void setPow2(int val)
{
reg[VAR_TMP1] = (_int64)pow(2.0, val - 1);
}
/***********************************************************************
LBL O
***********************************************************************/
static void setU(int val)
{
setPow2(val + BIT_X);
setPart((int)reg[VAR_X], getPart((int)reg[VAR_X]) + reg[VAR_TMP1]);
setPow2(val + BIT_Y);
setPart((int)reg[VAR_Y], getPart((int)reg[VAR_Y]) + reg[VAR_TMP1]);
setPow2(val + BIT_B);
setPart((int)reg[VAR_B], getPart((int)reg[VAR_B]) + reg[VAR_TMP1]);
}
/***********************************************************************
LBL L
***********************************************************************/
static void putA(_int64 x)
{
int hoho = (int)reg[VAR_CSOL];
reg[VAR_CSOL] = x;
_int64 ov = reg[VAR_SOL_START + reg[VAR_X]];
_int64 nv = ov + reg[VAR_M] * (reg[VAR_CSOL] - hoho);
reg[VAR_SOL_START + reg[VAR_X]] = nv;
}
/***********************************************************************
LBL K
***********************************************************************/
static void change(int v)
{
reg[VAR_I] += v;
assert(reg[VAR_I] >= 0);
reg[VAR_X] = reg[VAR_I] / 9;
reg[VAR_Y] = mod(reg[VAR_I], 9);
reg[VAR_B] = reg[VAR_Y] / 3 + (reg[VAR_X] / 3) * 3;
reg[VAR_M] = (int)pow(10.0, 8.0 - reg[VAR_Y]);
reg[VAR_CSOL]= mod((reg[VAR_SOL_START + reg[VAR_X]] / reg[VAR_M]), 10);
setPow2((int)reg[VAR_Y] + BIT_S + 1);
if (mod((getPart((int)reg[VAR_X]) / reg[VAR_TMP1]), 2) > 0) {
reg[VAR_CSTR] = reg[VAR_CSOL];
}
else {
reg[VAR_CSTR] = 0;
}
}
/***********************************************************************
Not in 33s code
***********************************************************************/
static void output()
{
for(int j = 0;j < 9;j++) {
printf("%i\n",reg[VAR_SOL_START + j]);
}
printf("\n");
}
/***********************************************************************
LBL A
***********************************************************************/
int main()
{
// zero composite flags - different on 33s - just a clear
for (reg[VAR_TMP1] = 0;reg[VAR_TMP1] < 9;reg[VAR_TMP1]++){
reg[VAR_UCOMP_START + reg[VAR_TMP1]] = 0;
}
// enter data - different on 33s - user enters values
for (reg[VAR_TMP1] = 0;reg[VAR_TMP1] < 9;reg[VAR_TMP1]++){
reg[VAR_SOL_START + reg[VAR_TMP1]] = start[reg[VAR_TMP1]];
}
// reset counters to prepare for net increment to first position
reg[VAR_I] = -1;
// scan the starting data and set flags for initial values
for (int j = 0;j < 81;j++) {
change(1);
if(reg[VAR_CSOL] > 0){
setU((int)reg[VAR_CSOL]);
setPow2((int)(reg[VAR_Y] + BIT_S + 1));
setPart((int)reg[VAR_X], getPart((int)reg[VAR_X]) + reg[VAR_TMP1]);
}
}
// reset counters to prepare for solver
reg[VAR_I] = -1;
// LBL E
m1:
change(1);
if(reg[VAR_X] == 9){
output();
exit(0);
}
if(reg[VAR_CSTR] > 0) {
goto m1;
};
putA(reg[VAR_CSTR]);
// LBL X
m2:
if(reg[VAR_CSOL] == 9) {
goto m3;
}
putA(reg[VAR_CSOL]+1);
// check to see if flags are set
//isSet(reg[VAR_CSOL]);
int val = (int)reg[VAR_CSOL];
flag[FLAG_SET] = 0;
setPow2(val + BIT_X);
if (mod((getPart((int)reg[VAR_X]) / reg[VAR_TMP1]), 2) > 0)
flag[FLAG_SET] = 1;
if (flag[FLAG_SET])
goto m2;
setPow2(val + BIT_Y);
if (mod((getPart((int)reg[VAR_Y]) / reg[VAR_TMP1]), 2) > 0)
flag[FLAG_SET] = 1;
if (flag[FLAG_SET])
goto m2;
setPow2(val + BIT_B);
if (mod((getPart((int)reg[VAR_B]) / reg[VAR_TMP1]), 2) > 0)
flag[FLAG_SET] = 1;
if (flag[FLAG_SET])
goto m2;
setU((int)reg[VAR_CSOL]);
goto m1;
// LBL C
m3:
change(-1);
if(reg[VAR_CSTR] > 0)
goto m3;
val = (int)reg[VAR_CSOL];
setPow2(val + BIT_X);
setPart((int)reg[VAR_X], getPart((int)reg[VAR_X]) - reg[VAR_TMP1]);
setPow2(val + BIT_Y);
setPart((int)reg[VAR_Y], getPart((int)reg[VAR_Y]) - reg[VAR_TMP1]);
setPow2(val + BIT_B);
setPart((int)reg[VAR_B], getPart((int)reg[VAR_B]) - reg[VAR_TMP1]);
goto m2;
}
