From 0f619c65bab2465ffa84eb64cc62fe56506121f8 Mon Sep 17 00:00:00 2001 From: Dave Chapman Date: Sat, 1 Apr 2006 18:38:34 +0000 Subject: Move Sudoku plugin into its own subdirectory and add a random game generator. git-svn-id: svn://svn.rockbox.org/rockbox/trunk@9407 a1c6a512-1295-4272-9138-f99709370657 --- apps/plugins/sudoku/sudoku.c | 1124 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1124 insertions(+) create mode 100644 apps/plugins/sudoku/sudoku.c (limited to 'apps/plugins/sudoku/sudoku.c') diff --git a/apps/plugins/sudoku/sudoku.c b/apps/plugins/sudoku/sudoku.c new file mode 100644 index 0000000000..798936b384 --- /dev/null +++ b/apps/plugins/sudoku/sudoku.c @@ -0,0 +1,1124 @@ +/*************************************************************************** + * __________ __ ___. + * Open \______ \ ____ ____ | | _\_ |__ _______ ___ + * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / + * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < + * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ + * \/ \/ \/ \/ \/ + * $Id$ + * + * Copyright (C) 2005 Dave Chapman + * + * All files in this archive are subject to the GNU General Public License. + * See the file COPYING in the source tree root for full license agreement. + * + * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY + * KIND, either express or implied. + * + ****************************************************************************/ + +/*** +Sudoku by Dave Chapman + +User instructions +----------------- + +Use the arrow keys to move cursor, and press SELECT/ON/F2 to increment +the number under the cursor. + +At any time during the game, press On to bring up the game menu with +further options: + + Save + Reload + Clear + Solve + +Sudoku is implemented as a "viewer" for a ".ss" file, as generated by +Simple Sudoku and other applications - http://angusj.com/sudoku/ + +In-progress game positions are saved in the original .ss file, with +A-I used to indicate numbers entered by the user. + +Example ".ss" file, and one with a saved state: + +...|...|... ...|...|... +2..|8.4|9.1 2.C|8.4|9.1 +...|1.6|32. E..|1.6|32. +----------- ----------- +...|..5|.4. ...|..5|.4. +8..|423|..6 8..|423|..6 +.3.|9..|... .3D|9..|A.. +----------- ----------- +.63|7.9|... .63|7.9|... +4.9|5.2|..8 4.9|5.2|.C8 +...|...|... ...|...|... + +*/ + +#include "plugin.h" + +#ifdef HAVE_LCD_BITMAP + +#include "sudoku.h" +#include "generator.h" + +PLUGIN_HEADER + +struct plugin_api* rb; + +/* The bitmaps */ +extern const fb_data sudoku_normal[]; +extern const fb_data sudoku_start[]; +extern const fb_data sudoku_inverse[]; + +#if (LCD_HEIGHT==128) && (LCD_WIDTH==160) +/* For iriver H1x0 - 160x128, 9 cells @ 12x12 with 14 border lines*/ + +/* Internal dimensions of a cell */ +#define CELL_WIDTH 12 +#define CELL_HEIGHT 12 + +#define BOARD_WIDTH (CELL_WIDTH*9+10+4) +#define BOARD_HEIGHT (CELL_HEIGHT*9+10+4) + +#define XOFS (((LCD_WIDTH-BOARD_WIDTH)/2)+10) +#define YOFS ((LCD_HEIGHT-BOARD_HEIGHT)/2) + +#define XOFSSCRATCHPAD 3 + +/* Locations of each cell */ +static unsigned char cellxpos[9]={ 2, 15, 28, 42, 55, 68, 82, 95, 108 }; +static unsigned char cellypos[9]={ 2, 15, 28, 42, 55, 68, 82, 95, 108 }; + +/* The height of one cell in the bitmap */ +#define BITMAP_HEIGHT 12 +#define BITMAP_STRIDE 12 + +#elif (LCD_HEIGHT==64) && (LCD_WIDTH==112) +/* For Archos Recorder, FM and Ondio (112x64): + 9 cells @ 8x6 with 10 border lines +*/ + +/* Internal dimensions of a cell */ +#define CELL_WIDTH 8 +#define CELL_HEIGHT 6 + +#define BOARD_WIDTH (CELL_WIDTH*9+10) +#define BOARD_HEIGHT (CELL_HEIGHT*9+10) + +#define XOFS (((LCD_WIDTH-BOARD_WIDTH)/2)+7) +#define YOFS ((LCD_HEIGHT-BOARD_HEIGHT)/2) + +#define XOFSSCRATCHPAD 2 + +/* Locations of each cell */ +static unsigned char cellxpos[9]={ 1, 10, 19, 28, 37, 46, 55, 64, 73 }; +static unsigned char cellypos[9]={ 1, 8, 15, 22, 29, 36, 43, 50, 57 }; + +/* The height of one cell in the bitmap */ +#define BITMAP_HEIGHT 8 +#define BITMAP_STRIDE 8 + +#elif (LCD_HEIGHT>=176) && (LCD_WIDTH>=220) +/* iriver h300 */ + +/* Internal dimensions of a cell */ +#define CELL_WIDTH 16 +#define CELL_HEIGHT 16 + +#define BOARD_WIDTH (CELL_WIDTH*9+10+4) +#define BOARD_HEIGHT (CELL_HEIGHT*9+10+4) + +#define XOFS (((LCD_WIDTH-BOARD_WIDTH)/2)+15) +#define YOFS ((LCD_HEIGHT-BOARD_HEIGHT)/2) + +#define XOFSSCRATCHPAD 10 + +/* Locations of each cell */ +static unsigned char cellxpos[9]={ 2, 19, 36, 54, 71, 88, 106, 123, 140 }; +static unsigned char cellypos[9]={ 2, 19, 36, 54, 71, 88, 106, 123, 140 }; + +/* The height of one cell in the bitmap */ +#define BITMAP_HEIGHT 16 +#define BITMAP_STRIDE 16 + +#else + #error SUDOKU: Unsupported LCD size +#endif + +/****** Solver routine by Tom Shackell + +Downloaded from: + +http://www-users.cs.york.ac.uk/~shackell/sudoku/Sudoku.html + +Released under GPLv2 + +*/ + +typedef unsigned int Bitset; + +#define BLOCK 3 +#define SIZE (BLOCK*BLOCK) + +#define true 1 +#define false 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; + } + } +} + +/* 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); + } + } + /* 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; +} + +/* 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; +} + +/* 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; + } + } + } + } + /* now copy into options */ + *num = bestCount; + val = sud->table[*rX][*rY]; + for (i = 1, j = 0; i <= SIZE; i++){ + if (BIT_TEST(val, i)){ + options[j++] = i; + } + } + return allMarked; +} + +static bool solve(Sudoku* sud, Stats* stats, const Options* options); + +/* 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; +} + +/* 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; + } + } + } + /* 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 */ + 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); + } + } + } + + /* need to check for degenerate input problems ... */ + if (is_valid(&sud)){ + ret = solve(&sud, &stats, &options); + } else { + ret = false; + } + + if (ret) { + /* 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); + } + } + } else { + rb->splash(HZ*2, true, "Solve failed"); + } + + return; +} + + +void clear_state(struct sudoku_state_t* state) +{ + int r,c; + + state->filename[0]=0; + for (r=0;r<9;r++) { + for (c=0;c<9;c++) { + state->startboard[r][c]='0'; + state->currentboard[r][c]='0'; +#ifdef SUDOKU_BUTTON_POSSIBLE + state->possiblevals[r][c]=0; +#endif + } + } + + state->x=0; + state->y=0; + state->editmode=0; +} + +/* Load game - only ".ss" is officially supported, but any sensible + text representation (one line per row) may load. +*/ +bool load_sudoku(struct sudoku_state_t* state, char* filename) +{ + int fd; + size_t n; + int r = 0, c = 0; + unsigned int i; + int valid=0; + char buf[300]; /* A buffer to read a sudoku board from */ + + fd=rb->open(filename, O_RDONLY); + if (fd < 0) { + LOGF("Invalid sudoku file: %s\n",filename); + return(false); + } + + rb->strncpy(state->filename,filename,MAX_PATH); + n=rb->read(fd,buf,300); + if (n <= 0) { + return(false); + } + rb->close(fd); + + r=0; + c=0; + i=0; + while ((i < n) && (r < 9)) { + switch (buf[i]){ + case ' ': case '\t': + if (c > 0) + valid=1; + break; + case '|': + case '*': + case '-': + case '\r': + break; + case '\n': + if (valid) { + r++; + valid=0; + } + c = 0; + break; + case '_': case '.': + valid=1; + if (c >= SIZE || r >= SIZE){ + LOGF("ERROR: sudoku problem is the wrong size (%d,%d)\n", + c, r); + return(false); + } + c++; + break; + default: + if (((buf[i]>='A') && (buf[i]<='I')) || + ((buf[i]>='0') && (buf[i]<='9'))) { + valid=1; + if (r >= SIZE || c >= SIZE){ + LOGF("ERROR: sudoku problem is the wrong size " + "(%d,%d)\n", c, r); + return(false); + } + if ((buf[i]>='0') && (buf[i]<='9')) { + state->startboard[r][c]=buf[i]; + state->currentboard[r][c]=buf[i]; + } else { + state->currentboard[r][c]='1'+(buf[i]-'A'); + } + c++; + } + /* Ignore any other characters */ + break; + } + i++; + } + + /* Save a copy of the saved state - so we can reload without using the + disk */ + rb->memcpy(state->savedboard,state->currentboard,81); + return(true); +} + +bool save_sudoku(struct sudoku_state_t* state) +{ + int fd; + int r,c; + int i; + char line[13]; + char sep[13]; + + rb->memcpy(line,"...|...|...\r\n",13); + rb->memcpy(sep,"-----------\r\n",13); + + if (state->filename[0]==0) { + return false; + } + + fd=rb->open(state->filename, O_WRONLY|O_CREAT); + if (fd >= 0) { + for (r=0;r<9;r++) { + i=0; + for (c=0;c<9;c++) { + if (state->startboard[r][c]!='0') { + line[i]=state->startboard[r][c]; + } else if (state->currentboard[r][c]!='0') { + line[i]='A'+(state->currentboard[r][c]-'1'); + } else { + line[i]='.'; + } + i++; + if ((c==2) || (c==5)) { + i++; + } + } + rb->write(fd,line,sizeof(line)); + if ((r==2) || (r==5)) { + rb->write(fd,sep,sizeof(sep)); + } + } + /* Add a blank line at end */ + rb->write(fd,"\r\n",2); + rb->close(fd); + /* Save a copy of the saved state - so we can reload without + using the disk */ + rb->memcpy(state->savedboard,state->currentboard,81); + return true; + } else { + return false; + } +} + +void restore_state(struct sudoku_state_t* state) +{ + rb->memcpy(state->currentboard,state->savedboard,81); +} + +void clear_board(struct sudoku_state_t* state) +{ + int r,c; + + for (r=0;r<9;r++) { + for (c=0;c<9;c++) { + state->currentboard[r][c]=state->startboard[r][c]; + } + } + state->x=0; + state->y=0; +} + +void update_cell(struct sudoku_state_t* state, int r, int c) +{ + /* We have four types of cell: + 1) User-entered number + 2) Starting number + 3) Cursor in cell + */ + + if ((r==state->y) && (c==state->x)) { + rb->lcd_bitmap_part(sudoku_inverse,0, + BITMAP_HEIGHT*(state->currentboard[r][c]-'0'), + BITMAP_STRIDE, + XOFS+cellxpos[c],YOFS+cellypos[r],CELL_WIDTH, + CELL_HEIGHT); + } else { + if (state->startboard[r][c]!='0') { + rb->lcd_bitmap_part(sudoku_start,0, + BITMAP_HEIGHT*(state->startboard[r][c]-'0'), + BITMAP_STRIDE, + XOFS+cellxpos[c],YOFS+cellypos[r], + CELL_WIDTH,CELL_HEIGHT); + } else { + rb->lcd_bitmap_part(sudoku_normal,0, + BITMAP_HEIGHT*(state->currentboard[r][c]-'0'), + BITMAP_STRIDE, + XOFS+cellxpos[c],YOFS+cellypos[r], + CELL_WIDTH,CELL_HEIGHT); + } + } + + rb->lcd_update_rect(cellxpos[c],cellypos[r],CELL_WIDTH,CELL_HEIGHT); +} + + +void display_board(struct sudoku_state_t* state) +{ + int r,c; + + /* Clear the display buffer */ + rb->lcd_clear_display(); + + /* Draw the gridlines - differently for different targets */ + +#if LCD_HEIGHT > 64 + /* Large targets - draw single/double lines */ + for (r=0;r<9;r++) { + rb->lcd_hline(XOFS,XOFS+BOARD_WIDTH-1,YOFS+cellypos[r]-1); + rb->lcd_vline(XOFS+cellxpos[r]-1,YOFS,YOFS+BOARD_HEIGHT-1); + if ((r % 3)==0) { + rb->lcd_hline(XOFS,XOFS+BOARD_WIDTH-1,YOFS+cellypos[r]-2); + rb->lcd_vline(XOFS+cellxpos[r]-2,YOFS,YOFS+BOARD_HEIGHT-1); + } + } + rb->lcd_hline(XOFS,XOFS+BOARD_WIDTH-1,YOFS+cellypos[8]+CELL_HEIGHT); + rb->lcd_hline(XOFS,XOFS+BOARD_WIDTH-1,YOFS+cellypos[8]+CELL_HEIGHT+1); + rb->lcd_vline(XOFS+cellxpos[8]+CELL_WIDTH,YOFS,YOFS+BOARD_HEIGHT-1); + rb->lcd_vline(XOFS+cellxpos[8]+CELL_WIDTH+1,YOFS,YOFS+BOARD_HEIGHT-1); +#elif (LCD_HEIGHT==64) + /* Small targets - draw dotted/single lines */ + for (r=0;r<9;r++) { + if ((r % 3)==0) { + /* Solid Line */ + rb->lcd_hline(XOFS,XOFS+BOARD_WIDTH-1,YOFS+cellypos[r]-1); + rb->lcd_vline(XOFS+cellxpos[r]-1,YOFS,YOFS+BOARD_HEIGHT-1); + } else { + /* Dotted line */ + for (c=XOFS;clcd_drawpixel(c,YOFS+cellypos[r]-1); + } + for (c=YOFS;clcd_drawpixel(XOFS+cellxpos[r]-1,c); + } + } + } + rb->lcd_hline(XOFS,XOFS+BOARD_WIDTH-1,YOFS+cellypos[8]+CELL_HEIGHT); + rb->lcd_vline(XOFS+cellxpos[8]+CELL_WIDTH,YOFS,YOFS+BOARD_HEIGHT-1); +#else +#error SUDOKU: Unsupported LCD height +#endif + +#ifdef SUDOKU_BUTTON_POSSIBLE + rb->lcd_vline(XOFSSCRATCHPAD,YOFS,YOFS+BOARD_HEIGHT-1); + rb->lcd_vline(XOFSSCRATCHPAD+CELL_WIDTH+1,YOFS,YOFS+BOARD_HEIGHT-1); + for (r=0;r<9;r++) { +#if LCD_HEIGHT > 64 + /* Large targets - draw single/double lines */ + rb->lcd_hline(XOFSSCRATCHPAD,XOFSSCRATCHPAD+CELL_WIDTH+1, + YOFS+cellypos[r]-1); + if ((r % 3)==0) + rb->lcd_hline(XOFSSCRATCHPAD,XOFSSCRATCHPAD+CELL_WIDTH+1, + YOFS+cellypos[r]-2); +#elif LCD_HEIGHT == 64 + /* Small targets - draw dotted/single lines */ + if ((r % 3)==0) { + /* Solid Line */ + rb->lcd_hline(XOFSSCRATCHPAD,XOFSSCRATCHPAD+CELL_WIDTH+1, + YOFS+cellypos[r]-1); + } else { + /* Dotted line */ + for (c=XOFSSCRATCHPAD;clcd_drawpixel(c,YOFS+cellypos[r]-1); + } + } +#endif + if ((r>0) && state->possiblevals[state->y][state->x]&(1<<(r))) + rb->lcd_bitmap_part(sudoku_normal,0,BITMAP_HEIGHT*r,BITMAP_STRIDE, + XOFSSCRATCHPAD+1,YOFS+cellypos[r-1], + CELL_WIDTH,CELL_HEIGHT); + } + rb->lcd_hline(XOFSSCRATCHPAD,XOFSSCRATCHPAD+CELL_WIDTH+1, + YOFS+cellypos[8]+CELL_HEIGHT); +#if LCD_HEIGHT > 64 + rb->lcd_hline(XOFSSCRATCHPAD,XOFSSCRATCHPAD+CELL_WIDTH+1, + YOFS+cellypos[8]+CELL_HEIGHT+1); +#endif + if (state->possiblevals[state->y][state->x]&(1<<(r))) + rb->lcd_bitmap_part(sudoku_normal,0,BITMAP_HEIGHT*r,BITMAP_STRIDE, + XOFSSCRATCHPAD+1,YOFS+cellypos[8], + CELL_WIDTH,CELL_HEIGHT); +#endif + + /* Draw the numbers */ + for (r=0;r<9;r++) { + for (c=0;c<9;c++) { + /* We have four types of cell: + 1) User-entered number + 2) Starting number + 3) Cursor in cell + */ + + if ((r==state->y) && (c==state->x)) { + rb->lcd_bitmap_part(sudoku_inverse,0, + BITMAP_HEIGHT*(state->currentboard[r][c]- + '0'), + BITMAP_STRIDE, + XOFS+cellxpos[c],YOFS+cellypos[r], + CELL_WIDTH,CELL_HEIGHT); + } else { + if (state->startboard[r][c]!='0') { + rb->lcd_bitmap_part(sudoku_start,0, + BITMAP_HEIGHT*(state->startboard[r][c]- + '0'), + BITMAP_STRIDE, + XOFS+cellxpos[c],YOFS+cellypos[r], + CELL_WIDTH,CELL_HEIGHT); + } else { + rb->lcd_bitmap_part(sudoku_normal,0, + BITMAP_HEIGHT* + (state->currentboard[r][c]-'0'), + BITMAP_STRIDE, + XOFS+cellxpos[c],YOFS+cellypos[r], + CELL_WIDTH,CELL_HEIGHT); + } + } + } + } + + /* update the screen */ + rb->lcd_update(); +} + +/* Check the status of the board, assuming a change at the cursor location */ +bool check_status(struct sudoku_state_t* state) +{ + int check[9]; + int r,c; + int r1,c1; + int cell; + + /* First, check the column */ + for (cell=0;cell<9;cell++) { + check[cell]=0; + } + for (r=0;r<9;r++) { + cell=state->currentboard[r][state->x]; + if (cell!='0') { + if (check[cell-'1']==1) { + return true; + } + check[cell-'1']=1; + } + } + + /* Second, check the row */ + for (cell=0;cell<9;cell++) { + check[cell]=0; + } + for (c=0;c<9;c++) { + cell=state->currentboard[state->y][c]; + if (cell!='0') { + if (check[cell-'1']==1) { + return true; + } + check[cell-'1']=1; + } + } + + /* Finally, check the 3x3 sub-grid */ + for (cell=0;cell<9;cell++) { + check[cell]=0; + } + r1=(state->y/3)*3; + c1=(state->x/3)*3; + for (r=r1;rcurrentboard[r][c]; + if (cell!='0') { + if (check[cell-'1']==1) { + return true; + } + check[cell-'1']=1; + } + } + } + + /* We passed all the checks :) */ + + return false; +} + +void sudoku_generate(struct sudoku_state_t* state) +{ + char* difficulty; + char str[80]; + + clear_state(state); + display_board(state); + rb->splash(0, true, "Generating..."); + + sudoku_generate_board(state,&difficulty); + + rb->snprintf(str,sizeof(str),"Difficulty: %s",difficulty); + display_board(state); + rb->splash(3*HZ, true, str); + rb->strncpy(state->filename,GAME_FILE,MAX_PATH); +} + +int sudoku_menu_cb(int key, int m) +{ + (void)m; + switch(key) + { +#ifdef MENU_ENTER2 + case MENU_ENTER2: +#endif + case MENU_ENTER: + key = BUTTON_NONE; /* eat the downpress, next menu reacts on release */ + break; + +#ifdef MENU_ENTER2 + case MENU_ENTER2 | BUTTON_REL: +#endif + case MENU_ENTER | BUTTON_REL: + key = MENU_ENTER; /* fake downpress, next menu doesn't like release */ + break; + } + + return key; +} + +bool sudoku_menu(struct sudoku_state_t* state) +{ + int m; + int result; + + static const struct menu_item items[] = { + { "Save", NULL }, + { "Reload", NULL }, + { "Clear", NULL }, + { "Solve", NULL }, + { "Generate", NULL }, + { "New", NULL }, + { "Quit", NULL }, + }; + + m = rb->menu_init(items, sizeof(items) / sizeof(*items), + sudoku_menu_cb, NULL, NULL, NULL); + + result=rb->menu_show(m); + + switch (result) { + case 0: /* Save state */ + save_sudoku(state); + break; + + case 1: /* Restore state */ + restore_state(state); + break; + + case 2: /* Clear all */ + clear_board(state); + break; + + case 3: /* Solve */ + sudoku_solve(state); + break; + + case 4: /* Generate Game */ + sudoku_generate(state); + break; + + case 5: /* Create a new game manually */ + clear_state(state); + state->editmode=1; + break; + + case 6: /* Quit */ + save_sudoku(state); + rb->menu_exit(m); + return true; + break; + + default: + break; + } + + rb->menu_exit(m); + + return (result==MENU_ATTACHED_USB); +} + +void move_cursor(struct sudoku_state_t* state, int newx, int newy) +{ + int oldx, oldy; + + /* Check that the character at the cursor position is legal */ + if (check_status(state)) { + rb->splash(HZ*2, true, "Illegal move!"); + /* Ignore any button presses during the splash */ + rb->button_clear_queue(); + return; + } + + /* Move Cursor */ + oldx=state->x; + oldy=state->y; + state->x=newx; + state->y=newy; + + /* Redraw current and old cells */ + update_cell(state,oldx,oldy); + update_cell(state,newx,newy); +} + +/* plugin entry point */ +enum plugin_status plugin_start(struct plugin_api* api, void* parameter) +{ + bool exit; + int button; + int lastbutton = BUTTON_NONE; + long ticks; + struct sudoku_state_t state; + + /* plugin init */ + rb = api; + /* end of plugin init */ + + clear_state(&state); + + if (parameter==NULL) { + /* We have been started as a plugin - try default sudoku.ss */ + if (!load_sudoku(&state,GAME_FILE)) { + /* No previous game saved, generate one */ + sudoku_generate(&state); + } + } else { + if (!load_sudoku(&state,(char*)parameter)) { + rb->splash(HZ*2, true, "Load error"); + return(PLUGIN_ERROR); + } + } + + display_board(&state); + + /* The main game loop */ + exit=false; + ticks=0; + while(!exit) { + button = rb->button_get(true); + + switch(button){ + /* Exit game */ + case SUDOKU_BUTTON_QUIT: + exit=1; + break; + + /* Increment digit */ +#ifdef SUDOKU_BUTTON_ALTTOGGLE + case SUDOKU_BUTTON_ALTTOGGLE | BUTTON_REPEAT: +#endif + case SUDOKU_BUTTON_TOGGLE | BUTTON_REPEAT: + /* Slow down the repeat speed to 1/3 second */ + if ((*rb->current_tick-ticks) < (HZ/3)) { + break; + } + +#ifdef SUDOKU_BUTTON_ALTTOGGLE + case SUDOKU_BUTTON_ALTTOGGLE: +#endif + case SUDOKU_BUTTON_TOGGLE: +#ifdef SUDOKU_BUTTON_TOGGLE_PRE + if ((button == SUDOKU_BUTTON_TOGGLE) + && (lastbutton != SUDOKU_BUTTON_TOGGLE_PRE)) + break; +#endif + /* Increment digit */ + ticks=*rb->current_tick; + if (state.editmode) { + if (state.startboard[state.y][state.x]=='9') { + state.startboard[state.y][state.x]='0'; + state.currentboard[state.y][state.x]='0'; + } else { + state.startboard[state.y][state.x]++; + state.currentboard[state.y][state.x]++; + } + } else { + if (state.startboard[state.y][state.x]=='0') { + if (state.currentboard[state.y][state.x]=='9') { + state.currentboard[state.y][state.x]='0'; + } else { + state.currentboard[state.y][state.x]++; + } + } + } + update_cell(&state,state.y,state.x); + break; + + /* move cursor left */ + case BUTTON_LEFT: + case (BUTTON_LEFT | BUTTON_REPEAT): + if (state.x==0) { + move_cursor(&state,8,state.y); + } else { + move_cursor(&state,state.x-1,state.y); + } + break; + + /* move cursor right */ + case BUTTON_RIGHT: + case (BUTTON_RIGHT | BUTTON_REPEAT): + if (state.x==8) { + move_cursor(&state,0,state.y); + } else { + move_cursor(&state,state.x+1,state.y); + } + break; + + /* move cursor up */ + case SUDOKU_BUTTON_UP: + case (SUDOKU_BUTTON_UP | BUTTON_REPEAT): + if (state.y==0) { + move_cursor(&state,state.x,8); + } else { + move_cursor(&state,state.x,state.y-1); + } + break; + + /* move cursor down */ + case SUDOKU_BUTTON_DOWN: + case (SUDOKU_BUTTON_DOWN | BUTTON_REPEAT): + if (state.y==8) { + move_cursor(&state,state.x,0); + } else { + move_cursor(&state,state.x,state.y+1); + } + break; + + case SUDOKU_BUTTON_MENU: +#ifdef SUDOKU_BUTTON_MENU_PRE + if (lastbutton != SUDOKU_BUTTON_MENU_PRE) + break; +#endif + /* Don't let the user leave a game in a bad state */ + if (check_status(&state)) { + rb->splash(HZ*2, true, "Illegal move!"); + /* Ignore any button presses during the splash */ + rb->button_clear_queue(); + } else { + if (state.editmode) { + rb->kbd_input(state.filename,MAX_PATH); + if (save_sudoku(&state)) { + state.editmode=0; + } else { + rb->splash(HZ*2, true, "Save failed"); + } + } else { + if (sudoku_menu(&state)) { + return PLUGIN_USB_CONNECTED; + } + } + } + break; +#ifdef SUDOKU_BUTTON_POSSIBLE + case SUDOKU_BUTTON_POSSIBLE: + /* Toggle current number in the possiblevals structure */ + if (state.currentboard[state.y][state.x]!='0') { + state.possiblevals[state.y][state.x]^= + (1 << (state.currentboard[state.y][state.x] - '0')); + } + break; +#endif + default: + if (rb->default_event_handler(button) == SYS_USB_CONNECTED) { + /* Quit if USB has been connected */ + return PLUGIN_USB_CONNECTED; + } + break; + } + if (button != BUTTON_NONE) + lastbutton = button; + + display_board(&state); + } + + return PLUGIN_OK; +} + +#endif -- cgit v1.2.3