The Museum of HP Calculators

HP Forum Archive 19

 SudokuMessage #1 Posted by KC on 7 Sept 2010, 1:11 a.m. 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

 Re: SudokuMessage #2 Posted by Ivan Nejgebauer on 7 Sept 2010, 8:26 a.m.,in response to message #1 by 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 ```

 Re: SudokuMessage #3 Posted by Norman Dziedzic on 7 Sept 2010, 2:02 p.m.,in response to message #1 by KC 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.

 Re: SudokuMessage #4 Posted by Norman Dziedzic on 7 Sept 2010, 5:23 p.m.,in response to message #3 by Norman Dziedzic The program I posted does have the limitation of only recognizing the first 12 digits entered.

 Re: SudokuMessage #5 Posted by Katie Wasserman on 7 Sept 2010, 7:09 p.m.,in response to message #4 by Norman Dziedzic Here's my 12C code. Start with a , 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 . 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

 Re: SudokuMessage #6 Posted by KC on 7 Sept 2010, 9:15 p.m.,in response to message #5 by Katie Wasserman All you guys are so helpful. Thanks. KC

 Re: SudokuMessage #7 Posted by David Hayden on 11 Sept 2010, 4:41 p.m.,in response to message #1 by 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]); } ``` Experienced C programmers will recognize that this can be further simplified by using the "|=" operator. 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; ``` Note that this sets the bits that don't represent digits (e.g. bit 12).

 Re: SudokuMessage #8 Posted by Norman Dziedzic on 12 Sept 2010, 12:56 a.m.,in response to message #7 by David Hayden 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 >> >> ```

 Re: SudokuMessage #9 Posted by David Hayden on 12 Sept 2010, 10:28 a.m.,in response to message #7 by David Hayden 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 #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; } ```

 Re: SudokuMessage #10 Posted by Norman Dziedzic on 13 Sept 2010, 1:03 p.m.,in response to message #9 by David Hayden David, Can I use hpgcc on a 48gii or only on a 50g? Thanks

 HPGCC on a 48giiMessage #11 Posted by David Hayden on 13 Sept 2010, 10:22 p.m.,in response to message #10 by Norman Dziedzic 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 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 && asat_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; } ``` Copy the above text into c:\arm-hp\sources\hplib\Saturn\sat_createtemp.c, replacing the existing file. Edit c:\arm-hp\sources\hplib\hpmath.h and replace this line: ``` #define _fabs(x) ( (x) < 0.0 ? (-x) : (x) ) ``` with this: ` #define _fabs(x) ( (x) < 0.0 ? -(x) : (x) ) ` also replace this: ` #define abs(a) ((a) < 0 ? (-a) : (a)) ` with this: ` #define abs(a) ((a) < 0 ? -(a) : (a)) ` Now rebuild the libraries as follows: Start a command window. Cd c:\arm-hp\ Run env.bat to set up environment variables to use hpgcc Cd c:\arm-hp\sources\hplib Type “make clean” Type “make”. This will rebuild the libraries, including the new copy of sat_createtemp.c Type “make install” to copy the new version of libhplib.a to the right place. There are separate versions of the ARMToolbox for the HP48 and HP 49. You need to install c:\arm-hp\ARMToolbox\LIB275-48.lib on your calculator. Note that you'll want to rename this library first because LIB275-48.LIB is an invalid variable name on the calculator. 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.

Go back to the main exhibit hall