Re: SUDOKU solver for HP48
- From: Scott Hemphill <hemphill@xxxxxxxxxxxxx>
- Date: 26 Jul 2005 15:27:38 -0400
"stefanmo_hp48" <stefanmo@xxxxxxxxx> writes:
> Scott, would you consider sharing it with the group? Perhaps the
> joined brains of this group can come up with the best solution.
Sure. My approach was to write the simplest program I could think of that
was consistent with rapid calculation. I think my algorithm shows promise,
because I tested it against the one at:
http://www.users.waitrose.com/~nihilist/sudoku.html
I used the fairly difficult problem (sample9.txt) from the above website:
.2.......
...6....3
.74.8....
.....3..2
.8..4..1.
6..5.....
....1.78.
5....9...
.......4.
(or, if you prefer)
0 2 0 0 0 0 0 0 0
0 0 0 6 0 0 0 0 3
0 7 4 0 8 0 0 0 0
0 0 0 0 0 3 0 0 2
0 8 0 0 4 0 0 1 0
6 0 0 5 0 0 0 0 0
0 0 0 0 1 0 7 8 0
5 0 0 0 0 9 0 0 0
0 0 0 0 0 0 0 4 0
On a PC, I compiled my C program and the one from this website, and found
that I could solve this puzzle 100 times in 0.54 seconds, while the other
program solved it 100 times in 4.46 seconds.
The main differences between my algorithm and the other one are:
. mine is much simpler (I think)
. if there are no forced choices, I will always pick the square with the
fewest number of choices. (This is very important to reduce the size
of the search tree.)
. precomputed relationships between squares in the "others" array.
. precomputed count of bits in a bitmask in "count" array.
. economical implementation.
If my program is compiled normally, it will find *all* the solutions for the
given puzzle. If compiled with -DONEONLY, it will stop after it finds the
first solution.
Now about my RPL version:
The ten minutes I reported was for a simple puzzle. The complicated puzzle
above would take a lot more time. There's still a lot of hope for
improvement, though, because my RPL version is just a prototype, and is a
very slow implementation. I used global variables where I could keep things
(like the bitmask) on the stack. I also use some very slow list manipulations.
But I don't have a lot of time right now, so I'm happy to let other people
hack on my code, if they feel so inclined. Note: The "INIT" function is
meant to be called once to set up "COUNT" and "OTHERS". Then you don't have
to call it again. Sorry I don't have a native HP48 source file. Note that
I used =/ for notequal.
------------------------------------------------------------------------
/* I wrote this program, and placed it in the public domain.
* -- Scott Hemphill, 26 July 2005
*/
#include <stdio.h>
#include <stdlib.h>
int grid[81]; /* The puzzle grid: contains numbers 1 */
/* through 9, or 0 if a number hasn't */
/* been chosen. */
int bits[81]; /* Bitmap for each square: 0x01 means */
/* that "1" is not possible, 0x02 means */
/* that "2" is not possible, 0x04 means */
/* that "3" is not possible, ..., 0x100 */
/* that "9" is not possible. */
int count[512]; /* Count of number of 1-bits in a bitmap */
int others[81][24]; /* For each square, an array of 20 "other" */
/* locations affect by this square. For */
/* example, if there is a "6" in square 0, */
/* there are 20 other squares we know */
/* can't contain a six: */
/* 1,2,3,4,5,6,7,8 (horizontal row) */
/* 9,18,27,36,45,54,63,72 (vertcal column) */
/* 1,2,9,10,11,18,19,20 (3x3 square) */
/* That's a total of 24 square numbers, */
/* but 4 of them are duplicates. The */
/* "others" array is big enough to hold */
/* 24 numbers while it is being built, but */
/* will only 20 numbers will be used when
/* it is complete. */
void usage(char *prog)
{
fprintf(stderr, "usage: %s [sudoko input file]\n", prog);
exit(1);
}
/*
* Used only in initialization, addgroup takes an array of 9 associated
* square numbers, and adds then to each others entries in the "others"
* array. A "group" consistes of the nine square numbers in a row, column
* or 3x3 square. No check is made for duplicates; that will be taken
* care of when the others array is sorted. The others array is assumed
* to be initialized to negative numbers; valid square numbers are 0 through
* 80.
*/
void addgroup(int group[9])
{
int i, j, k;
for (i = 0; i < 9; i++) {
for (j = 0; others[group[i]][j] >= 0; j++) ;
for (k = 0; k < 9; k++) {
if (k != i) others[group[i]][j++] = group[k];
}
}
}
/*
* Used only in initialization, sortgroups (should be called sortothers,
* actually) sorts the 81 arrays which are elements of the "others" array.
* Each of these subarrays contains 24 square numbers, although only
* 20 of them are unique. Each time a duplicate is found, it is changed
* to "99", which makes it sort to the end of the array, where it won't
* be used.
*/
void sortgroups(void)
{
int i, j, k, tmp;
for (i = 0; i < 81; i++) {
for (j = 0; j < 23; j++) {
for (k = j+1; k < 24; k++) {
if (others[i][j] == others[i][k]) {
others[i][k] = 99;
} else if (others[i][j] > others[i][k]) {
tmp = others[i][j];
others[i][j] = others[i][k];
others[i][k] = tmp;
}
}
}
}
}
/* Used to initialize the "count" array and the "others" array. "count"
* contains the number of 1-bits in a bitmask. Consider the bitmask
* 0x153 (which is 101010011 in binary and 339 in decimal). Therefore
* the entry count[339] will contain the value 5. The "others" array is
* initialized to "-1"s, then groups of 9 associated square numbers are
* added one at a time, using the "addgroup" function.
*/
void init(void)
{
int group[9];
int i, j;
for (i = 1; i < 512; i<<=1) {
for (j = 0; j < 512; j++) {
if (i & j) count[j]++;
}
}
for (i = 0; i < 81; i++) {
for (j = 0; j < 24; j++) {
others[i][j] = -1; /* negative numbers mean unused */
}
}
for (i = 0; i < 9; i++) {
for (j = 0; j < 9; j++) {
group[j] = 9*i + j;
}
addgroup(group); /* add a row of square numbers */
}
for (i = 0; i < 9; i++) {
for (j = 0; j < 9; j++) {
group[j] = 9*j + i; /* add a column of square numbers */
}
addgroup(group);
}
for (i = 0; i < 9; i++) {
for (j = 0; j < 9; j++) {
group[j] = 27*(i/3) + 9*(j/3) + 3*(i%3) + (j%3);
}
addgroup(group); /* add a 3x3 square of square numbers */
}
sortgroups(); /* sort others array, removing duplicates */
}
/*
* "setbox" is used to place a number in the grid, whether it is known,
* or a guess. It also updates all the bitmasks for all the associated
* squares to indicate that they can't contain this number.
*/
void setbox(int n, int x)
{
int i, j;
grid[n] = x;
j = 1 << (x-1);
for (i = 0; i < 20; i++) bits[others[n][i]] |= j;
}
/*
* "unsetbox" is used to remove a number from the grid. Zero is stored
* to indicate an unused square. It is too complicated to calculate
* what the bitmask ought to now contain, so it is up to the calling
* program to restore the bitmask from a previously saved value.
*/
void unsetbox(int n, int x)
{
grid[n] = 0;
// it's up to calling program to restore bits
}
/*
* "readgrid" is used to read the initial data for the grid from a file.
* The initial bitmask is calculated at the same time (by calling "setbox").
*/
void readgrid(FILE *f)
{
char buf[BUFSIZ];
int i, j;
for (i = 0; i < 9; i++) {
if (!fgets(buf, BUFSIZ, f)) {
fprintf(stderr, "premature end of input\n");
exit(1);
}
if (strlen(buf) < 10) {
fprintf(stderr, "invalid input line %d\n", i+1);
exit(1);
}
for (j = 0; j < 9; j++) {
if ('1' <= buf[j] && buf[j] <= '9') setbox(9*i+j, buf[j]-'0');
}
}
for (i = 0; i < 81; i++) {
if (!grid[i]) continue;
if (bits[i] & (1<<(grid[i]-1))) {
fprintf(stderr, "inconsistent input data for box (%d,%d)\n", (i/9)+1, (i%9)+1);
exit(1);
}
}
}
static long long int num = 0; /* count of number of solutions found */
void printsolution(void)
{
int i, j;
if (num++) printf("\n"); /* if more than one solution, separate them */
for (i = 0; i < 9; i++) {
for (j = 0; j < 9; j++) {
printf("%2d", grid[9*i+j]);
}
printf("\n");
}
}
/* "selectbox" is the heart of the algorithm. It works this way:
* First, the grid is searched for an empty square. If there isn't one,
* then the grid contains a solution, so it is printed. If an empty
* square is found, then it is compared with all other empty squares to
* see which one of them has the maximum number of 1-bits in its bitmask.
* That square is the one selected, and each of the possible values are
* tried in return, calling "selectbox" recursively to search for a
* solution. Note that if a square has 9 1-bits in its bitmask, then
* there are no possible values, and "selectbox" will return without any
* further recursion. Otherwise, if a square has 8 1-bits in its bitmask,
* then it has a forced choice, and only that choice will be taken at this
* level in the recursion.
*
* Note: compile with -DONEONLY to stop recursion if a solution has already
* been found.
*/
void selectbox(void)
{
int bitsave[81];
int i, j;
int best, bestcount;
#ifdef ONEONLY
if (num == 0) { /* allow recursion only if no solutions so far */
#endif
for (best = 0; best < 81; best++) { /* see if there are any empty squares */
if (!grid[best]) break;
}
if (best == 81) { /* 81 indicates no empty squares */
printsolution();
return;
}
bestcount = count[bits[best]]; /* count of bits for the square we found */
for (i = best+1; i < 81; i++) { /* find the biggest count over all squares */
if (grid[i]) continue; /* only consider empty squares */
j = count[bits[i]];
if (j > bestcount) {
best = i;
bestcount = j;
}
}
for (i = 0; i < 9; i++) { /* Try all numbers for this square */
j = 1 << i;
if ((bits[best] & j) == 0) { /* if the number is possible, recurse */
memcpy(bitsave, bits, sizeof bits); /* save bitmask */
setbox(best, i+1); /* place number in square, update bitmask */
selectbox(); /* recurse */
unsetbox(best, i+1); /* unplace number in square */
memcpy(bits, bitsave, sizeof bits); /* restore bitmask */
}
}
#ifdef ONEONLY
}
#endif
}
/*
* main program. Calls "init" to initialize "count" and "others" arrays.
* Calls "readgrid" to read initial grid from a file, and calculate initial
* bitmask. Calls "selectbox" to recursively enumerate solution(s). Outputs
* summary to "stderr".
*/
int main(int argc, char *argv[])
{
FILE *f = stdin;
if (argc > 2) usage(argv[0]);
if (argc == 2) f = fopen(argv[1], "r");
if (!f) usage(argv[0]);
init();
readgrid(f);
selectbox();
#ifdef ONEONLY
if (num == 0) fprintf(stderr, "no solutions found\n");
#else
fprintf(stderr, "%lld solution%s found\n", num, num==1?"":"s");
#endif
return 0;
}
------------------------------------------------------------------------
SORTGROUPS:
<<
1 81 FOR i
OTHERS i GET SORT @ {2,2,3,3,...} {} 0
{} 0 WHILE ROT DUP SIZE @ {} 0 {2,2,3,3,...}
REPEAT
DUP TAIL 4 ROLLD HEAD @ {2,3,3,...} {} 0 2
IF DUP2 ==
THEN
DROP
ELSE
ROT OVER + ROT DROP SWAP
END
END
DROP2
NEXT
81 ->LIST
'OTHERS' STO
>>
ADDGROUP:
<<
-> g
<<
OTHERS {{..} {..} .. {..}}
1 9 FOR i
g i GET DUP2 GET {{..} {..} .. {..}} 73 {..}
1 9 FOR j
IF i j =/
THEN
g j GET +
END
NEXT
PUT
NEXT
'OTHERS' STO
>>
>>
INIT:
<<
#0
WHILE DUP #512d <
REPEAT
0
IF OVER #1d AND #0 == THEN 1 + END
IF OVER #2d AND #0 == THEN 1 + END
IF OVER #4d AND #0 == THEN 1 + END
IF OVER #8d AND #0 == THEN 1 + END
IF OVER #16d AND #0 == THEN 1 + END
IF OVER #32d AND #0 == THEN 1 + END
IF OVER #64d AND #0 == THEN 1 + END
IF OVER #128d AND #0 == THEN 1 + END
IF OVER #256d AND #0 == THEN 1 + END
SWAP
#1 +
END
DROP
512 ->LIST 'COUNT' STO
1 81 START {} NEXT 81 ->LIST 'OTHERS' STO
1 81 FOR i i NEXT
1 9 START 9 ->LIST ADDGROUP NEXT
0 8 FOR i 0 8 FOR j j 9 * i + 1 + NEXT NEXT
1 9 START 9 ->LIST ADDGROUP NEXT
0 8 FOR i 0 8 FOR j
i 3 / IP 27 * j 3 / IP 9 * + i 3 MOD 3 * + j 3 MOD + 1 +
NEXT NEXT
1 9 START 9 ->LIST ADDGROUP NEXT
SORTGROUPS
>>
SETBOX:
<<
DUP2 GRID 3 ROLLD PUT 'GRID' STO
OTHERS ROT GET
SWAP 1 - 2 SWAP ^ R->B @ {k} bit
BITS @ {k} bit BITS
WHILE ROT DUP SIZE
REPEAT
DUP TAIL 4 ROLLD HEAD @ {..} bit BITS k
DUP2 GET 4 PICK OR PUT @ {..} bit BITS
END
DROP 'BITS' STO DROP
>>
UNSETBOX:
<<
GRID SWAP 0 PUT 'GRID' STO
>>
READGRID:
<<
IF DUP TYPE 3 ==
THEN
IF DUP SIZE {9 9} ==
THEN
OBJ-> DROP
81 ->ARRY 'GRID' STO
1 81 START #0 NEXT 81 ->LIST 'BITS' STO
1 81 FOR i
i GRID i GET
IF DUP
THEN
SETBOX
ELSE
DROP2
END
NEXT
ELSE
"Array not 9x9" HALT
END
ELSE
"No array specified" HALT
END
>>
ADDSOLUTION:
<<
GRID
OBJ-> DROP
{9 9} ->ARRY
'SOLUTION' STO+
>>
SELECTBOX:
<<
0 1 DO
IF GRID OVER GET NOT
THEN
SWAP DROP 82
ELSE
1 +
END
UNTIL DUP 81 >
END
DROP
IF DUP NOT
THEN
DROP
ADDSOLUTION
ELSE
BITS OVER GET B->R 1 + COUNT SWAP GET
OVER 1 +
WHILE DUP 81 <=
REPEAT
IF GRID OVER GET NOT
THEN
BITS OVER GET B->R 1 + COUNT SWAP GET
IF 3 PICK OVER <
THEN
4 ROLL 4 ROLL DROP2 OVER
ELSE
DROP
END
END
1 +
END
DROP2
0 WHILE DUP 9 <
REPEAT
IF BITS 3 PICK GET 2 3 PICK ^ R->B AND #0 ==
THEN
DUP2 BITS 3 ROLLD 1 + SETBOX
SELECTBOX
'BITS' STO
OVER UNSETBOX
END
1 +
END
DROP2
END
>>
MAIN:
<<
READGRID
{} 'SOLUTION' STO
SELECTBOX
SOLUTION
IF DUP SIZE 1 ==
THEN
1 GET
END
>>
------------------------------------------------------------------------
Scott
--
Scott Hemphill hemphill@xxxxxxxxxxxxxxxxxx
"This isn't flying. This is falling, with style." -- Buzz Lightyear
.
- References:
- SUDOKU solver for HP48
- From: stefanmo_hp48
- Re: SUDOKU solver for HP48
- From: Scott Hemphill
- Re: SUDOKU solver for HP48
- From: stefanmo_hp48
- SUDOKU solver for HP48
- Prev by Date: Re: User define key
- Next by Date: Past HP Conference "Goodies" / HHC2005 Info
- Previous by thread: Re: SUDOKU solver for HP48
- Next by thread: HP48GX Sudden Memory Loss
- Index(es):
Relevant Pages
|
Loading
