Re: A Replacement Calculator for Casio's with RPN! Message #16 Posted by Marcus von Cube, Germany on 26 Feb 2009, 11:33 a.m., in response to message #15 by hugh steers
I've tried it on my Casio Z-1GR (8088, C interpreter). Some modifications were (and still are) necessary because:
1) No ANSI prototypes.
2) memset, memcpy are missing.
3) sizeof works on variables only, not on types.
3) The output scrolls off the display.
I plugged in an external power supply and started the program with the hard to solve puzzle as input. I had to enter the numbers manually, there is no input redirection, but at least the solver started.
A few hours later, the solution was on the screen (scrolled off but obviously found). The program was still working, trying to find more solutions. I stopped it...
Memory wasn't a problem, at least on my system with some 40k free RAM, but execution times could be considerably improved by adding a few heuristics.
Here is the modified code:
/* Sudoku solver by Paul Guertin <pg@sff.net>, August 2008 */
/* Casio-C (non ANSI) MvC, Feb 2009 */
/*
#include <stdio.h>
#include <string.h>
*/
int neighbor[81][20]; /* lists of all 20 neighbors of each cell 0..80 */
int popcnt[512]; /* count of 1-bits in 0<=i<512 written in binary */
int nbsol, nbcalls;
memset( buff, val, size )
char *buff;
int val, size;
{
while( size-- ) *buff++ = (char) val;
}
memcpy( dest, src, size )
char *dest, *src;
int size;
{
while( size-- ) *dest++ = *src++;
}
init_tables()
/* Initializes the neighbor[][] and popcnt[] tables. */
{
int i, j, p, n[81];
for( p=0; p<81; p++ ) {
memset( n, 0, 81*sizeof(i) );
for( i=0; i<9; i++ )
n[p/9*9+i] = n[p%9+9*i] = n[p/27*27+p/3%3*3+i/3*9+i%3] = 1;
for( i=j=0; i<81; i++ ) {
if( (n[i] == 1) && (i != p) )
neighbor[p][j++] = i;
}
}
for( i=0; i<512; i++ ) {
for( j=popcnt[i]=0; j<9; j++ )
popcnt[i] += (i>>j) & 1;
}
}
set( board, pos, val )
int *board, pos, val;
/* Puts the value (1..9) in entry pos (0..80) and updates neighbors. */
{
int i;
board[pos] |= val<<9;
for( i=0; i<20; i++ )
board[neighbor[pos][i]] |= 1<<(val-1);
}
int input_board( board )
int *board;
/* Reads a sudoku board from stdin.
Returns 0 if OK, 1 if EOF, -(1..81) if invalid entry found. */
{
int c, n;
n = 0;
memset( board, 0, 81*sizeof(n) );
while( n<81 && (c=getchar()) != EOF ) {
if( c>='1' && c<='9' ) {
if( board[n] & 1 << (c-'1') )
return -n-1;
else
set( board, n++, c-'0' );
}
else if( c == '.' || c == '0' )
n++;
}
return n<81;
}
print_board( board )
int *board;
/* Pretty-prints a sudoku board to stdout. */
{
int i;
for( i=0; i<81; i++ ) {
if( i==27 || i==54 )
puts( "\n---------+---------+---------" );
else if( !(i%3) )
putchar( i%9 ? '|' : '\n');
printf( " %c ", board[i]>0x200 ? '0'+(board[i]>>9) : '.' );
}
putchar( '\n' );
}
solve( board )
int *board;
/* Prints all solutions to a sudoku problem. */
{
int i, maxblock, maxpos, keepboard[81];
nbcalls++;
for( i=maxblock=0; i<81; i++ ) {
if( board[i] < 0x200 && popcnt[board[i]] > maxblock ) {
maxpos = i;
maxblock = popcnt[board[maxpos]];
}
}
if( maxblock == 0 ) {
print_board( board );
nbsol++;
}
else if( maxblock < 9 ) {
for( i=0; i<9; i++ ) {
if( !(board[maxpos] & 1<<i) ) {
memcpy( keepboard, board, 81*sizeof(i) );
set( board, maxpos, i+1 );
solve( board );
memcpy( board, keepboard, 81*sizeof(i) );
}
}
}
}
int main()
{
int board[81], error;
/* Each item in the board[] array represents an entry.
The low 9 bits are used to keep track of impossible digits
for that entry (low kth bit is 1 iff digit k+1 is impossible),
and higher bits are used to write a digit in the entry (e.g.,
to set the first entry to 5, use board[0] |= 5<<9). So this
code assumes ints are at least 13 bits. */
init_tables();
if( error = input_board( board ) )
printf( "Illegal input position %d.\n", -error );
else {
print_board( board );
nbsol = nbcalls = 0;
solve( board );
printf( "\n%d solution%s found. ", nbsol, nbsol>1 ? "s" : "" );
printf( "Difficulty level (number of calls): %d\n", nbcalls );
}
return error;
}
Marcus
|