Sudoku



#5

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


#6

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
#7

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.


#8

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


#9

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


#10

All you guys are so helpful. Thanks.

KC

#11

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).

#12

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

#13

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;
}


#14

David,

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

Thanks


#15

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;
}

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:

  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.
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.


Possibly Related Threads…
Thread Author Replies Views Last Post
  Sudoku 50G Gilles Carpentier 6 2,231 05-13-2012, 06:32 AM
Last Post: Gilles Carpentier
  Sudoku Solver for HP-33s Marcel Samek 3 1,535 05-11-2012, 03:01 PM
Last Post: Lode
  HP-30b key assignment trick -- Sudoku helper revisited Katie Wasserman 2 1,316 09-27-2010, 11:25 AM
Last Post: Katie Wasserman
  Two additional articles online: Minimax & Sudoku Valentin Albillo 4 1,394 07-27-2006, 04:03 AM
Last Post: Valentin Albillo
  For the Sudoku crowd Eric Smith 22 5,303 07-11-2006, 04:11 AM
Last Post: Valentin Albillo
  SUDOKU GAME Fabio Albonico 5 2,087 06-15-2006, 04:03 PM
Last Post: Ed Look

Forum Jump: