HP Forums

No, I am not talking about sophisticated programming techniques to solve sudoku puzzles. I like to solve by myself, but what I find out is that most of my solving time is "wasted" on figuring out what numbers are still available to be used on a particular cell. For example, if the row has 1 3 5, column has 1 4 6, the 9-square cell has 1 5 7, then I know that 2 8 9 is still available. One day I was sitting and thinking about writing an rpn program that, when I input those numbers already appeared (i.e. 135146157) (bear in mind that the same number may appear more than once), the program would return 289. I intially thought it would be easy (just counting numbers,right?), but then after some thoughts, I found it was not as easy as I originally thought!

If somebody thinks it is just simple programming stuff and have some of your precious time to spare, would you please help me by providing me the program codes? Thanks a lot.

KC

Quote:

---

One day I was sitting and thinking about writing an rpn program that, when I input those numbers already appeared (i.e. 135146157) (bear in mind that the same number may appear more than once), the program would return 289. I intially thought it would be easy (just counting numbers,right?), but then after some thoughts, I found it was not as easy as I originally thought!

---

Quick'n'dirty: accumulate the sum of 10^(every digit of the input number); zeroes in the result denote unoccupied positions. The program is for the 15C, but won't work for arbitrary input values, since you simply can't enter a number longer than 10 digits.

LBL B

0

STO 0

STO 1

Rv

LBL 0

x=0?

GTO 1

10

/

ENTER

FRAC

10

*

10^x

STO+0

Rv

INT

GTO 0

LBL 1

.009

STO I

RCL 0

LBL 2

10

/

ENTER

FRAC

TEST 0

GTO 3

Rv

10

STO*1

Rv

RCL I

INT

STO+1

LBL 3

Rv

INT

ISG I

GTO 2

RCL 1

RTN

This is what I came up with on the 35s.

The test number is stored in A and B is cleared. B will hold the result number.
Then indirect registers 1 through 9 are zeroed.

Divide the test number modulo 10 to get the last digit and increment the indirect register based on this digit. Then divide the test number by 10, take the integer part and store back in A.

At this point, indirect registers are filled with the frequencies of digits in the test number.

Then loop through the indirect registers adding a digit to the output if the frequency is > 0. Use multiplies by 10 to shift left a digit.

001 LBL S

002 STO A

003 0

004 STO B

005 1.009

006 STO I

007 0

008 STO(I)

009 ISG I

010 GTO S008

011 RCL A

012 10

013 RMDR

014 STO J

015 1

016 STO+(J)

017 RCL A

018 10

019 /

020 IP

021 STO A

022 X>0?

023 GTO S011

024 0.009

025 STO I

026 ISG I

027 GTO S029

028 GTO S038

029 RCL(I)

030 X>0?

031 GTO S026

032 RCL I

033 IP

034 STO+B

035 10

036 STO* B

037 GTO S026

038 10

039 STO/ B

040 VIEW B

041 RTN

Edited: 7 Sept 2010, 2:05 p.m.

The program I posted does have the limitation of only recognizing the first 12 digits entered.

Here's my 12C code.

Start with a <Clear Reg>, then enter numbers and hit R/S. You can enter at most 10 numbers at a time but you can keep running it and marking off more numbers, as long as you don't do a <Clear Reg>. It should work on any model 12C or 12C clone.

01 STO 0

02 x=0

03 GTO 16

04 1

05 0

06 STO / 0

07 RCL 0

08 FRAC

09 x

10 STO n

11 0

12 STO Nj

13 RCL 0

14 INTG

15 GTO 01

16 1

17 +

18 STO n

19 RCL Nj

20 x=0

21 GTO 27

22 1

23 0

24 STO x 0

25 RCL n

26 STO + 0

27 8

28 RCL n

29 x<=y

30 GTO 16

31 RCL 0

32 GTO 00

[edited September 8: Tony(nz) found that two lines can be removed -- 10 is already in the Y register when (now) line 09 is executed.]

[edited September 15: Tony(nz) found that three lines can be saved by rearranging the 2nd part of the code a bit and making use of a zero left in X from the 1st part of the code.]

Edited: 15 Sept 2010, 9:06 p.m. after one or more responses were posted

All you guys are so helpful. Thanks.

KC

Here's a version in user RPL. You put a number containing the existing digits on the stack and then run the program. It replaces the top of stack with a number containing the digits not in the input number:

@ Given a number N, create a number with all

@ digits not in N

« STR 0.  N result «

  1 9 FOR i @ for each digit

    IF N i STR POS NOT THEN

      result 10. * i + 'result' STO

    END

  NEXT

  result

  »

»

Note that in a real sudoku solver it's much faster to store the possibilities as bits in a binary number and then use binary operations for logic like this. For example, in C code, you can gather up digits that are in a row like this:

int i;

int existingDigits = 0;

for (i=0; i < 9; ++i) {

    /* row[i] contains the digit in cell i of the row.

       zero means no digit in that cell.  "=" is the

       assignment operator. "|" is binary "OR" operator

       "<<" is arithmetic shift left operator.

    existingDigits = existingDigits | (1<< row[i]);

}

Now that you have existingDigits, it's easy to get the missing digits, it's just the binary NOT of the existingDigits:

int missingDigits = ~existingDigits;

David,

You blew me away for efficiency. I haven't done any RPL programming so as an exercise, I put together a version of the 35s program that works with integers so no 12 digit limitation. I'll post it anyway for yucks. Start with a number on the stack, returns digits not in that number.

<< 0 -> n s

   << 9 1 ->LIST 0 COM

      WHILE n 0 > REPEAT

         n 10 MOD 1 PUT

         n 10 IQUOT 'n' STO

      END

      1 9 FOR k

         IF 0 == THEN

            10 's' STO*

            k 's' STO+

         END

      NEXT

      DROP

      's' RCL

   >>

>>

Here it is in C code for HPGCC. This takes a real or integer number on level 1 and replaces it with an integer containing the digits that aren't in the input number. Because it converts the number to a 64 bit binary number internally, integer inputs can be no more than 19 digits.

Mostly, this is just a plug for the hpobjects library :).

// C program to figure the digits missing from a sudoku row/column/box.

// Given a number on level 1, this replaces it with an integer containing

// the digits not in the number.

#include <hpgcc49.h>

#include "hpobjects.h"

// Given a Saturn integer or real, return a C long long. Minimal error checking

long long  getInt(SatAddr obj)

{

    long long result = 0;

    if (isREAL(obj)) {

	double d;

	REALdecode(obj, &d);

	result = d;

    } else if (isZINT(obj)) {

	ZINTdecodell(obj, &result);

    }

    return result;

}



int main()

{

    long long N;		/* number of primes to find */

    int i;			/* counter variable */

    int digits=0;		/* If bit X is set, then digit X is in N */

    int result = 0;		/* the resulting number */

    // pop the stack and convert the ZINT or REAL to a long long.

    N = getInt(STACKpop());

    // Set "digits" to indicate which digits appear in N.

    while (N) {

	i = N % 10;

	digits |= (1 << i);

	N /= 10;

    }

    // Flip the bits in "digits" so it indicates if a digit is NOT in N:

    digits = ~digits;

    // Now set "result" to indicate digits not in N. Note that we don't

    // care if zero appears since it isn't a valid in sodoku

    for (i = 1; i < 10; ++i) {

	if (digits & (1 << i)) {

	    result = 10*result + i;

	}

    }

    // Convert "result" to a ZINT in tempOb and push it on the stack

    STACKpush(ZINTencodell(result, 0));

    return 0;

}

David,

Can I use hpgcc on a 48gii or only on a 50g?

Thanks

Hi Norman,

Yes, you can get HPGCC to generate programs for a 48gii! If you do, then you and I will probably be the only people on the planet to have done it successfully. Here is how you do it:

First, you need HPGCC version 1.1. You can get it from the
sourceforge page here

Install HPGCC 1.1 on your computer. In the rest of this message, I've assumed that you installed it into c:\arm-hp.

I had to add c:\arm-hp\libexec\gcc\arm-elf\3.4.6 to my path so the
compiler could find cc1.exe. I'm not sure if that was a problem with my installation. To make this easy, I created the following file called env.bat in the directory where I installed hpgcc (c:\arm-hp):

set HPGCC=C:\HPGCC1-1

PATH %HPGCC%\bin;%HPGCC%\libexec\gcc\arm-elf\3.4.6;%HPGCC%\arm-elf\bin;%PATH%

The sat_createtemp() function that comes with HPGCC 1.1 doesn't work properly so you need to replace it with the one from HPGCC2.0 and rebuild the libraries. Here is the replacement file:

// These functions replace sat_create_tempob() in HPGCC 1.1.  They are taken

// from HPGCC 2.0.  The ones in 1.1 don't work with the 48gii.

// Copy this file over c:\hp-arm\sources\hplib\saturn\sat_createtemp.c

// and then rebuild the library.

#include <hpgcc49.h>

unsigned int

sat_map_a2s(unsigned int arm_addr)

{    

    int f;

    unsigned int a=arm_addr&0xfffff800;

    for(f=0;f<256;++f) {

        if(_saturn_cpu->Read[f]==a) return (f<<12)+((arm_addr&0x7ff)<<1);

    }

    return 0xffffffff;

}

// AUXILIARY FUNCTION

// FINDS PAGE CLOSEST TO RSKTOP USED BY HPGCC

// RETURN 0xffffffff IF NONE.

unsigned __find_main_ram_start(int rsktop)

{

  int f;

  extern unsigned _mmu_table_addr,_mmu_table_entries;

  int *ptr=(int *)_mmu_table_addr;

  int minaddr=sat_map_s2a(rsktop);

  unsigned int page=0xffffffff,a;

  for(f=0;f<_mmu_table_entries;++f) {

      a=ptr[f]&0xfffff000;

      if(a>minaddr && a<page) page=a;

  }

  return page;

}


// AUXILIARY FUNCTION, RETURNS THE AMOUNT OF USEABLE TEMPOB IN NIBBLES

int sat_getfreetempob()

{

    int rstk=sat_peek(SAT_RSKTOP,5);

    int freeend;

    freeend=__find_main_ram_start(rstk);

    if(freeend==0xffffffff) {

	// C PROGRAM IS NOT USING MAIN RAM

	return sat_peek(SAT_DSKTOP,5)-rstk-11;

    }

    freeend=sat_map_a2s(freeend);

    return freeend-rstk-11;

}




int

sat_createtemp(int objsize)

{

    // CREATETEMP IMPLEMENTATION

    // objsize=size of object including prolog

    // in nibbles

    int ttop=sat_peek(SAT_TEMPTOP,5);

    int rstk=sat_peek(SAT_RSKTOP,5);

    int size=rstk-ttop;

    int freemem;

    int ptr;

    // check for enough room here

    if(objsize>sat_getfreetempob()) {

	// insufficient memory to create object

	return 0;

    }

    // make room in memory

    sat_moveup(ttop,ttop+objsize+6,size);



    // adjust tempob chain

    ptr=ttop+1+objsize;

    sat_poke(ptr,objsize+6,5);

    // adjust pointers

    // RSKTOP

    sat_poke(SAT_RSKTOP,sat_peek(SAT_RSKTOP,5)+objsize+6,5);

    // TEMPTOP

    sat_poke(SAT_TEMPTOP,sat_peek(SAT_TEMPTOP,5)+objsize+6,5);

    // adjust free memory

    freemem=sat_peek(SAT_DSKTOP,5)-sat_peek(SAT_RSKTOP,5);

    freemem/=5;

    sat_poke(SAT_AVMEM,freemem,5);

    // return addr to prolog of new object

    return ttop+1;

}

Edit c:\arm-hp\sources\hplib\hpmath.h and replace this line:

	#define _fabs(x) ( (x) < 0.0 ? (-x) : (x) ) 

	#define _fabs(x) ( (x) < 0.0 ? -(x) : (x) ) 

	#define abs(a) ((a) < 0 ? (-a) : (a)) 

	#define abs(a) ((a) < 0 ? -(a) : (a)) 

Now rebuild the libraries as follows:

1. Start a command window.
   
2. Cd c:\arm-hp\
   
3. Run env.bat to set up environment variables to use hpgcc
   
4. Cd c:\arm-hp\sources\hplib
   
5. Type “make clean”
   
6. Type “make”. This will rebuild the libraries, including the new copy of sat_createtemp.c
   
7. Type “make install” to copy the new version of libhplib.a to the right place.
   

It looks like the ArmToolbox's "S->exe" command isn't supported on the 48gii. You can only run programs via the PrRUN command. This means you can't create stand-alone programs on the HP48 - they require the ARMToolbox to be installed.