--- ./apps/plugins/sudoku.old 2005-10-05 05:00:18.000000000 +0100 +++ ./apps/plugins/sudoku.c 2005-10-09 08:46:40.840043200 +0100 @@ -92,6 +92,8 @@ #if (LCD_HEIGHT==128) && (LCD_WIDTH==160) /* For iriver H1x0 - 160x128, 9 cells @ 12x12 with 14 border lines*/ +#define BLOCK 3 +#define SIZE (BLOCK*BLOCK) /* Internal dimensions of a cell */ #define CELL_WIDTH 12 @@ -382,275 +384,201 @@ char startboard[9][9]; /* The initial state of the game */ char currentboard[9][9]; /* The current state of the game */ char savedboard[9][9]; /* Cached copy of saved state */ + char solverboard[9][9]; /* Copy of the board for the solver */ int x,y; /* Cursor position */ int editmode; /* We are editing the start board */ }; -/****** Solver routine by Tom Shackell - -Downloaded from: - -http://www-users.cs.york.ac.uk/~shackell/sudoku/Sudoku.html - -Released under GPLv2 - +/****** Solver routine by Multiplex ******/ +/* +** we represent otions using the bits of an int */ +int num_mask[9]={0x001, 0x002, 0x004, 0x008, 0x010, 0x020, 0x040, 0x080, 0x100}; -typedef unsigned int Bitset; - -#define BLOCK 3 -#define SIZE (BLOCK*BLOCK) +/* +** return an int representing the possible values +** - 0 means none 0x1FF means all 9 +** or in the bits as values are found, then invert the bits before returning +*/ +int find_possible_values(int row, int col, char grid[9][9]) +{ +int result, count, block_row, block_col; -#define true 1 -#define false 0 + result=0; -typedef struct _Sudoku { - Bitset table[SIZE][SIZE]; -}Sudoku; - -typedef struct _Stats { - int numTries; - int backTracks; - int numEmpty; - bool solutionFound; -}Stats; - -typedef struct _Options { - bool allSolutions; - bool uniquenessCheck; -}Options; - -void sudoku_init(Sudoku* sud); -void sudoku_set(Sudoku* sud, int x, int y, int num, bool original); -int sudoku_get(Sudoku* sud, int x, int y, bool* original); - -#define BIT(n) ((Bitset)(1<<(n))) -#define BIT_TEST(v,n) ((((Bitset)v) & BIT(n)) != 0) -#define BIT_CLEAR(v,n) (v) &= ~BIT(n) -#define MARK_BIT BIT(0) -#define ORIGINAL_BIT BIT(SIZE+1) - -#define ALL_BITS (BIT(1) | BIT(2) | BIT(3) | BIT(4) | BIT(5) | BIT(6) | BIT(7) | BIT(8) | BIT(9)) - -/* initialize a sudoku problem, should be called before using set or get */ -void sudoku_init(Sudoku* sud){ - int y, x; - for (y = 0; y < SIZE; y++){ - for (x = 0; x < SIZE; x++){ - sud->table[x][y] = ALL_BITS; - } +/* check what is already in the row and column */ + for (count=0; count<9; count++) + { + if (grid[row][count]!=0) result |= num_mask[grid[row][count]-1]; + if (grid[count][col]!=0) result |= num_mask[grid[count][col]-1]; } -} -/* set the number at a particular x and y column */ -void sudoku_set(Sudoku* sud, int x, int y, int num, bool original){ - int i, j; - int bx, by; - Bitset orig; - - // clear the row and columns - for (i = 0; i < SIZE; i++){ - BIT_CLEAR(sud->table[i][y], num); - BIT_CLEAR(sud->table[x][i], num); - } - // clear the block - bx = x - (x % BLOCK); - by = y - (y % BLOCK); - for (i = 0; i < BLOCK; i++){ - for (j = 0; j < BLOCK; j++){ - BIT_CLEAR(sud->table[bx+j][by+i], num); - } +/* check what is already in the block */ + block_row=3*(row / 3); + block_col=3*(col / 3); + for (count=block_row; count<(block_row+3); count++) + { + if (grid[count][block_col]!=0) result |= num_mask[grid[count][block_col]-1]; + if (grid[count][block_col+1]!=0) result |= num_mask[grid[count][block_col+1]-1]; + if (grid[count][block_col+2]!=0) result |= num_mask[grid[count][block_col+2]-1]; } - // mark the table - orig = original ? ORIGINAL_BIT : 0; - sud->table[x][y] = BIT(num) | MARK_BIT | orig; -} - -/* get the number at a particular x and y column, if this - is not unique return 0 */ -int sudoku_get(Sudoku* sud, int x, int y, bool* original){ - Bitset val = sud->table[x][y]; - int result = 0; - int i; - if (original){ - *original = val & ORIGINAL_BIT; - } - for (i = 1; i <= SIZE; i++){ - if (BIT_TEST(val, i)){ - if (result != 0){ - return 0; - } - result = i; - } - } - return result; + return(result^0x1FF); } -/* returns true if this is a valid problem, this is necessary because the input - problem might be degenerate which breaks the solver algorithm. */ -static bool is_valid(const Sudoku* sud){ - int x, y; - - for (y = 0; y < SIZE; y++){ - for (x = 0; x < SIZE; x++){ - if ((sud->table[x][y] & ALL_BITS) == 0){ - return false; - } - } - } - return true; -} +/* +** find the most constrained value +** -1 means no blanks - we must have solved it +** otherwise return the number of values that can fit into the most +** constrained value - this may be zero. +*/ -/* scan the table for the most constrained item, giving all it's options, - sets the best x and y coordinates, the number of options and the options for that coordinate and - returns true if the puzzle is finished */ -static bool scan(const Sudoku* sud, int* rX, int* rY, int *num, int* options){ - int x, y, i, j; - int bestCount = SIZE+1; - Bitset val; - bool allMarked = true; - - for (y = 0; y < SIZE; y++){ - for (x = 0; x < SIZE; x++){ - Bitset val = sud->table[x][y]; - int i; - int count = 0; - - if (val & MARK_BIT){ - // already set - continue; - } - allMarked = false; - for (i = 1; i <= SIZE; i++){ - if (BIT_TEST(val, i)){ - count++; - } - } - if (count < bestCount){ - bestCount = count; - *rX = x; - *rY = y; - if (count == 0){ - // can't possibly be beaten - *num = 0; - return false; - } +unsigned int find_most_constrained(char grid[9][9]) +{ +int row, col, result, count, tmp, tmp_count, low_row, low_col; + + result=10; + low_row=0; + low_col=0; + + for(row=0; row<9; row++) + { + for(col=0; col<9; col++) + { + if (grid[row][col]=='\0') + { + tmp=find_possible_values(row, col, grid); + + /* this means there is something wrong + - there is a blank that can't be filled, + so we'll have to back track */ + if (tmp==0) return(0); + + tmp_count=0; + for(count=0; count<9; count++) + { + if ((tmp & num_mask[count])!=0) tmp_count++; + } + if (tmp_counttable[*rX][*rY]; - for (i = 1, j = 0; i <= SIZE; i++){ - if (BIT_TEST(val, i)){ - options[j++] = i; - } + if (result==10) + { + return(-1); + } else { + return((low_row<<8) | (low_col<<4) | result); } - return allMarked; } -static bool solve(Sudoku* sud, Stats* stats, const Options* options); +bool solve(char solver[9][9]) +{ +unsigned int history[81]; +int depth, result, tmp, potentials, row, col; +unsigned int count; +enum {advancing, backtracking} state; + + state=advancing; + depth=0; + + while (true) + { + switch (state) + { + case advancing: + result=find_most_constrained(solver); -/* try a particular option and return true if that gives a solution - or false if it doesn't, restores board on backtracking */ -static bool spawn_option(Sudoku* sud, Stats* stats, const Options* options, int x, int y, int num){ - Sudoku copy; - - rb->memcpy(©,sud,sizeof(Sudoku)); - sudoku_set(©, x, y, num, false); - stats->numTries += 1; - if (solve(©, stats, options)){ - if (!options->allSolutions && stats->solutionFound){ - rb->memcpy(sud,©,sizeof(Sudoku)); - } - return true; - }else{ - stats->backTracks++; - } - return false; -} + /* -1 means that we've solved it */ + if (result==-1) + { + return(true); + break; + } + + /* 0 means that there is a space where nothing will fit - backtrack */ + if (result==0) + { + state=backtracking; + break; + } + + /* so we have some potential values for the square */ + /* find the first value for this position */ + row=(result>>8)&0x0F; + col=(result>>4)&0x0F; + potentials=find_possible_values(row, col, solver); + + tmp=0; + while ((potentials&num_mask[tmp]) == 0) tmp++; + solver[row][col]=tmp+1; +// gotoxy(1+col+(col/3), 1+row+(row/3)); putch('1'+tmp); + history[depth++]=0x1000 | result; + break; -/* solve a sudoku problem, returns true if there is a solution and false otherwise. - stats is used to track statisticss */ -static bool solve(Sudoku* sud, Stats* stats, const Options* options){ - while (true){ - int x, y, i, num; - int places[SIZE]; - - if (scan(sud, &x, &y, &num, places)){ - // a solution was found! - if (options->uniquenessCheck && stats->solutionFound){ - //printf("\n\t... But the solution is not unique!\n"); - return true; - } - stats->solutionFound = true; - if (options->allSolutions || options->uniquenessCheck){ - //printf("\n\tSolution after %d iterations\n", stats->numTries); - //sudoku_print(sud); - return false; - }else{ - return true; - } - } - if (num == 0){ - // can't be satisfied - return false; - } - // try all the places (except the last one) - for (i = 0; i < num-1; i++){ - if (spawn_option(sud, stats, options, x, y, places[i])){ - // solution found! - if (!options->allSolutions && stats->solutionFound){ - return true; + case backtracking: + /* see if we have used up the potential values at this place */ + row=(history[depth-1]>>8)&0x0F; + col=(history[depth-1]>>4)&0x0F; + /* clear out the old value */ +// gotoxy(1+col+(col/3), 1+row+(row/3)); putch(' '); + solver[row][col]=0; + + if (((history[depth-1]>>12)&0x0F)==(history[depth-1]&0x0F)) + { + if (depth>0) + { + depth--; + break; + } else { + return(false); + break; + } } - } + potentials=find_possible_values(row, col, solver); + + tmp=-1; + count=0; + while (count<=(history[depth-1]>>12)) + { + tmp++; + while ((potentials&num_mask[tmp]) == 0) + { + tmp++; + } + count++; + } +// gotoxy(1+col+(col/3), 1+row+(row/3)); putch('1'+tmp); + solver[row][col]=tmp+1; + tmp=history[depth-1]; + history[depth-1]=(tmp&0x0FFF) | ((tmp&0xF000) + 0x1000); + state=advancing; + break; } - // take the last place ourself - stats->numTries += 1; - sudoku_set(sud, x, y, places[num-1], false); } } -/******** END OF IMPORTED CODE */ - /* A wrapper function between the Sudoku plugin and the above solver code */ void sudoku_solve(struct sudoku_state_t* state) { - bool ret; - Stats stats; - Options options; - Sudoku sud; - bool original; int r,c; - /* Initialise the parameters */ - sudoku_init(&sud); - rb->memset(&stats,0,sizeof(stats)); - options.allSolutions=false; - options.uniquenessCheck=false; - - /* Convert Rockbox format into format for solver */ + /* Copy start board in to solver array */ for (r=0;r<9;r++) { for (c=0;c<9;c++) { - if (state->startboard[r][c]!='0') { - sudoku_set(&sud, c, r, state->startboard[r][c]-'0', true); - } + state->solverboard[r][c]=state->startboard[r][c]-'0'; } } - // need to check for degenerate input problems ... - if (is_valid(&sud)){ - ret = solve(&sud, &stats, &options); - } else { - ret = false; - } - - if (ret) { + if (solve(state->solverboard)) { /* Populate the board with the solution. */ for (r=0;r<9;r++) { for (c=0;c<9;c++) { - state->currentboard[r][c]='0'+sudoku_get(&sud, c, r, &original); + state->currentboard[r][c]='0'+state->solverboard[r][c]; } } } else {