root/modules/games/gui_sudoku.c

/* [<][>][^][v][top][bottom][index][help] */

DEFINITIONS

This source file includes following definitions.
  1. get_dec_num
  2. one_plus_nums
  3. is_one_num
  4. del_numpad
  5. draw_numpad
  6. get_pad_num
  7. set_pad_num
  8. draw_menu
  9. draw_field
  10. redraw
  11. gui_sudoku_draw
  12. sudoku_finished
  13. sudoku_follows_rules
  14. sudoku_follows_rules_xy
  15. get_missing_nums_line
  16. get_missing_nums_column
  17. get_missing_nums_square
  18. sudoku_search_candidates
  19. sudoku_insert_lonely_numbers
  20. sudoku_solve
  21. exchange_row
  22. exchange_column
  23. exchangeSquareRow
  24. exchange_square_column
  25. remove_nums
  26. sudoku_new
  27. sudoku_menu_execute
  28. gui_sudoku_kbd_process
  29. gui_sudoku_init
  30. gui_module_menu_kbd_process
  31. exit_sudoku
  32. _run
  33. _module_can_unload
  34. _module_exit_alt

   1 /*      TODO:
   2         - somehow use the screenbuffer after a messagebox, so that nothing flickers?
   3         - draw_marker as a new draw function ->don't redraw entire field each time you move
   4         - adjustable Difficulty, maybe after optimization, because other START_NUMBERS are slower
   5         - compatibility with other cams?
   6         - highscore with time
   7         - battery and watch
   8 */
   9 
  10 #include "camera_info.h"
  11 #include "stdlib.h"
  12 #include "keyboard.h"
  13 #include "lang.h"
  14 #include "conf.h"
  15 #include "gui.h"
  16 #include "gui_draw.h"
  17 #include "gui_lang.h"
  18 #include "gui_batt.h"
  19 #include "gui_mbox.h"
  20 #include "modes.h"
  21 #include "fileutil.h"
  22 
  23 #include "module_def.h"
  24 #include "simple_module.h"
  25 
  26 void gui_module_menu_kbd_process();
  27 int gui_sudoku_kbd_process();
  28 void gui_sudoku_draw();
  29 void exit_sudoku();
  30 
  31 gui_handler GUI_MODE_SUDOKU =
  32     /*GUI_MODE_SUDOKU*/  { GUI_MODE_MODULE, gui_sudoku_draw, gui_sudoku_kbd_process, gui_module_menu_kbd_process, 0, GUI_MODE_FLAG_NODRAWRESTORE };
  33 
  34 static int running = 0;
  35 
  36 //-------------------------------------------------------------------
  37 #define SUDOKU_BG_COLOR         COLOR_WHITE
  38 #define MARKER_COLOR            COLOR_GREEN // green for all cameras in play mode
  39 #define TEXT_COLOR                      MAKE_COLOR(SUDOKU_BG_COLOR, COLOR_BLACK)
  40 #define MARKER_TEXT_COLOR       MAKE_COLOR(MARKER_COLOR, COLOR_WHITE)
  41 
  42 #define MODE_VIEW                       1
  43 #define MODE_EDIT                       2
  44 #define MODE_MENU                       4
  45 
  46 //for drawing
  47 #define BG                                      1
  48 #define FIELD                           2
  49 #define MENU                            4
  50 #define PAD                                     8
  51 
  52 #define START_NUMBERS           25
  53 #define MAX_START_NUMBERS       32
  54 #define MENU_ELEMENTS           8
  55 
  56 //this program uses a flag-format because it's necessary to save more than
  57 //one number in one array-Integer, f.e. for solving
  58 //There are 3 functions: get_dec_num(int), one_plus_nums(int), is_one_num(int)
  59 int flag[10]={0x0, 0x1,0x2,0x4,0x8,0x10,0x20,0x40,0x80,0x100};
  60                         // 0    1   2   3   4    5    6    7    8     9
  61 int xPos, yPos, xMenuPos;
  62 int xPosOld, yPosOld;
  63 int fieldLineDistance;
  64 int fieldLineLength;
  65 int mode;  //MODE_VIEW, MODE_EDIT, MODE_MENU
  66 int xFieldBorder;
  67 int yFieldBorder;
  68 int menuPos;
  69 int draw;       //with flags, for drawing
  70 int xPadStart, yPadStart, padLineDistance; //number pad X, Y and distance, for entering a number
  71 int xPosPad, yPosPad;
  72 
  73 int field[9][9];
  74 
  75 //Will contain both numbers entered by the user and default numbers
  76 int user[9][9];
  77 
  78 //Here, the computer tries to solve sudokus
  79 int mess[9][9];
  80 
  81 
  82 /////////////////////Flag format specific functions///////////////////////////////
  83 
  84 int get_dec_num(int number)
  85 {
  86         int i;
  87         for (i=1; i<10; i++)
  88         {
  89                 if (number&flag[i])return i;
  90         }
  91         return 0;
  92 }
  93 
  94 //Checks whether more than one flag(=number) is set
  95 int one_plus_nums(int number)
  96 {
  97         if (number==0)return 0;
  98         int counter=0;
  99         int i;
 100         for (i=1; i<10; i++)
 101         {
 102                 if (number & flag[i])
 103                 {
 104                         if (counter==1)return 1;
 105                         counter++;
 106                 }
 107         }
 108         return 0;
 109 }
 110 
 111 //Checks, if one flag is set
 112 int is_one_num(int number)
 113 {
 114         if (number==0)return 0;
 115         int counter=0;
 116         int i;
 117         for (i=1; i<10; i++)
 118         {
 119                 if (number & flag[i])
 120                 {
 121                         if (counter==1)return 0;
 122                         counter++;
 123                 }
 124         }
 125         return 1;
 126 }
 127 
 128 
 129 /////////////////////Draw functions/////////////////////////////////////////
 130 
 131 void del_numpad()
 132 {
 133         draw_rectangle(xPadStart, yPadStart-padLineDistance, xPadStart+padLineDistance*3, yPadStart+padLineDistance*4, MAKE_COLOR(SUDOKU_BG_COLOR,SUDOKU_BG_COLOR), RECT_BORDER0|DRAW_FILLED);
 134 }
 135 
 136 void draw_numpad()
 137 {
 138         int i, y, x;
 139         static char str[16];
 140         del_numpad();
 141 
 142         //horizontal
 143         draw_line(xPadStart+padLineDistance, yPadStart-padLineDistance, xPadStart+2*padLineDistance, yPadStart-padLineDistance, COLOR_BLACK);
 144         for (i=0; i<4; i++) draw_line(xPadStart, yPadStart+padLineDistance*i, xPadStart+padLineDistance*3, yPadStart+padLineDistance*i, COLOR_BLACK);
 145 
 146         //vertical
 147         draw_line(xPadStart, yPadStart, xPadStart, yPadStart+3*padLineDistance, COLOR_BLACK);
 148         draw_line(xPadStart+padLineDistance, yPadStart-padLineDistance, xPadStart+padLineDistance, yPadStart+3*padLineDistance, COLOR_BLACK);
 149         draw_line(xPadStart+2*padLineDistance, yPadStart-padLineDistance, xPadStart+2*padLineDistance, yPadStart+3*padLineDistance, COLOR_BLACK);
 150         draw_line(xPadStart+3*padLineDistance, yPadStart, xPadStart+3*padLineDistance, yPadStart+3*padLineDistance, COLOR_BLACK);
 151 
 152         //numbers
 153         i=0;
 154         for (y=0; y<3; y++)for (x=0; x<3; x++)
 155         {
 156                 i++;
 157                 sprintf(str, "%i", i);
 158                 draw_string(xPadStart+padLineDistance*x+(padLineDistance-FONT_WIDTH)/2, yPadStart+padLineDistance*y+(padLineDistance-FONT_HEIGHT)/2, str, MAKE_COLOR(SUDOKU_BG_COLOR, COLOR_BLACK));
 159         }
 160         sprintf(str, "%i", 0);
 161         draw_string(xPadStart+padLineDistance+(padLineDistance-FONT_WIDTH)/2, yPadStart+padLineDistance*(-1)+(padLineDistance-FONT_HEIGHT)/2, str, MAKE_COLOR(SUDOKU_BG_COLOR, COLOR_BLACK));
 162 
 163         //marker
 164         draw_rectangle(xPadStart+xPosPad*padLineDistance, yPadStart+yPosPad*padLineDistance,
 165                        xPadStart+(xPosPad+1)*padLineDistance, yPadStart+(yPosPad+1)*padLineDistance, MAKE_COLOR(MARKER_COLOR,MARKER_COLOR), RECT_BORDER1);
 166         draw_rectangle(xPadStart+xPosPad*padLineDistance+1, yPadStart+yPosPad*padLineDistance+1,
 167                        xPadStart+(xPosPad+1)*padLineDistance-1, yPadStart+(yPosPad+1)*padLineDistance-1, MAKE_COLOR(MARKER_COLOR,MARKER_COLOR), RECT_BORDER1);
 168         draw_rectangle(xPadStart+xPosPad*padLineDistance+2, yPadStart+yPosPad*padLineDistance+2,
 169                        xPadStart+(xPosPad+1)*padLineDistance-2, yPadStart+(yPosPad+1)*padLineDistance-2, MAKE_COLOR(MARKER_COLOR,MARKER_COLOR), RECT_BORDER1);
 170 }
 171 
 172 int get_pad_num()
 173 {
 174         if (xPosPad==1 && yPosPad==-1)return 0;
 175         else return flag[xPosPad+yPosPad*3+1];
 176 }
 177 
 178 void set_pad_num(int number)
 179 {
 180         if (number==0)xPosPad=yPosPad=0;
 181         else
 182         {
 183                 xPosPad=(number-1)%3;
 184                 yPosPad=(number-1)/3;
 185         }
 186 }
 187 
 188 void draw_menu()
 189 {
 190         int i;
 191 
 192         for (i=0; i<MENU_ELEMENTS; i++)
 193         {
 194                 draw_string(xMenuPos, FONT_HEIGHT*i+4, lang_str(LANG_SUDOKU_MENU_START+i), (menuPos==i && mode==MODE_MENU) ? MARKER_TEXT_COLOR : TEXT_COLOR);
 195         }
 196 }
 197 
 198 void draw_field()
 199 {
 200         int i, x, y;
 201         static char str[16];
 202 
 203         //redraw last field to remove the marker
 204         draw_rectangle(xFieldBorder+xPosOld*fieldLineDistance, yFieldBorder+yPosOld*fieldLineDistance, xFieldBorder+(xPosOld+1)*fieldLineDistance, yFieldBorder+(yPosOld+1)*fieldLineDistance, MAKE_COLOR(SUDOKU_BG_COLOR, COLOR_BLACK), RECT_BORDER1|DRAW_FILLED);
 205         xPosOld=xPos;
 206         yPosOld=yPos;
 207 
 208         //Lines
 209         for (i=0; i<10; ++i){
 210                 //vertical lines
 211                 draw_line(xFieldBorder+fieldLineDistance*i, yFieldBorder, xFieldBorder+fieldLineDistance*i, yFieldBorder+fieldLineLength, COLOR_BLACK);
 212                 //horizontal lines
 213                 draw_line(xFieldBorder, yFieldBorder+fieldLineDistance*i, xFieldBorder+fieldLineLength, yFieldBorder+fieldLineDistance*i, COLOR_BLACK);
 214         }
 215         //draw thick vertical lines
 216         draw_line(xFieldBorder+fieldLineDistance*3-1, yFieldBorder, xFieldBorder+fieldLineDistance*3-1, yFieldBorder+fieldLineLength, COLOR_BLACK);
 217         draw_line(xFieldBorder+fieldLineDistance*3+1, yFieldBorder, xFieldBorder+fieldLineDistance*3+1, yFieldBorder+fieldLineLength, COLOR_BLACK);
 218 
 219         draw_line(xFieldBorder+fieldLineDistance*6-1, yFieldBorder, xFieldBorder+fieldLineDistance*6-1, yFieldBorder+fieldLineLength, COLOR_BLACK);
 220         draw_line(xFieldBorder+fieldLineDistance*6+1, yFieldBorder, xFieldBorder+fieldLineDistance*6+1, yFieldBorder+fieldLineLength, COLOR_BLACK);
 221 
 222         //draw thick horizontal lines
 223         draw_line(xFieldBorder, yFieldBorder+fieldLineDistance*3-1, xFieldBorder+fieldLineLength, yFieldBorder+fieldLineDistance*3-1, COLOR_BLACK);
 224         draw_line(xFieldBorder, yFieldBorder+fieldLineDistance*3+1, xFieldBorder+fieldLineLength, yFieldBorder+fieldLineDistance*3+1, COLOR_BLACK);
 225 
 226         draw_line(xFieldBorder, yFieldBorder+fieldLineDistance*6-1, xFieldBorder+fieldLineLength, yFieldBorder+fieldLineDistance*6-1, COLOR_BLACK);
 227         draw_line(xFieldBorder, yFieldBorder+fieldLineDistance*6+1, xFieldBorder+fieldLineLength, yFieldBorder+fieldLineDistance*6+1, COLOR_BLACK);
 228 
 229         //cursor
 230         if (mode==MODE_VIEW){
 231                 draw_rectangle(xFieldBorder+xPos*fieldLineDistance, yFieldBorder+yPos*fieldLineDistance,
 232                                xFieldBorder+(xPos+1)*fieldLineDistance, yFieldBorder+(yPos+1)*fieldLineDistance, MAKE_COLOR(MARKER_COLOR,MARKER_COLOR), RECT_BORDER1);
 233                 draw_rectangle(xFieldBorder+xPos*fieldLineDistance+1, yFieldBorder+yPos*fieldLineDistance+1,
 234                                xFieldBorder+(xPos+1)*fieldLineDistance-1, yFieldBorder+(yPos+1)*fieldLineDistance-1, MAKE_COLOR(MARKER_COLOR,MARKER_COLOR), RECT_BORDER1);
 235                 draw_rectangle(xFieldBorder+xPos*fieldLineDistance+2, yFieldBorder+yPos*fieldLineDistance+2,
 236                                xFieldBorder+(xPos+1)*fieldLineDistance-2, yFieldBorder+(yPos+1)*fieldLineDistance-2, MAKE_COLOR(MARKER_COLOR,MARKER_COLOR), RECT_BORDER1);
 237         }
 238         if (mode==MODE_EDIT){
 239                 draw_ellipse(xFieldBorder+(xPos+1)*fieldLineDistance-fieldLineDistance/2, yFieldBorder+(yPos+1)*fieldLineDistance-fieldLineDistance/2, fieldLineDistance/2-3, fieldLineDistance/2-1, MARKER_COLOR, DRAW_FILLED);
 240                 sprintf(str, "%i", get_dec_num(user[yPos][xPos]));
 241                 draw_string(xFieldBorder+fieldLineDistance*xPos+(fieldLineDistance-FONT_WIDTH)/2, yFieldBorder+fieldLineDistance*yPos+(fieldLineDistance-FONT_HEIGHT)/2, str, MAKE_COLOR(MARKER_COLOR, COLOR_WHITE));
 242         }
 243 
 244         //Numbers
 245         for (y=0; y<9; y++){
 246                 for (x=0; x<9; x++){
 247                         /*im editmode wird an der cursorposition keine Zahl angezeigt, 0 wird auch nicht angezeigt*/
 248                         if (user[y][x]==0) continue;
 249                         if (mode==MODE_EDIT && x==xPos && y==yPos) continue;
 250                         sprintf(str, "%i", get_dec_num(user[y][x]));
 251                         if (field[y][x]!=0)
 252                                 draw_string(xFieldBorder+fieldLineDistance*x+(fieldLineDistance-FONT_WIDTH)/2, yFieldBorder+fieldLineDistance*y+(fieldLineDistance-FONT_HEIGHT)/2, str, MAKE_COLOR(SUDOKU_BG_COLOR, COLOR_BLACK));
 253                         else draw_string(xFieldBorder+fieldLineDistance*x+(fieldLineDistance-FONT_WIDTH)/2, yFieldBorder+fieldLineDistance*y+(fieldLineDistance-FONT_HEIGHT)/2, str, MAKE_COLOR(SUDOKU_BG_COLOR, MARKER_COLOR));
 254                 }
 255         }
 256 }
 257 
 258 //how to redraw without flickering?
 259 void redraw()
 260 {
 261         draw_rectangle(camera_screen.disp_left, 0, camera_screen.disp_right, camera_screen.height-1, MAKE_COLOR(SUDOKU_BG_COLOR,SUDOKU_BG_COLOR), RECT_BORDER0|DRAW_FILLED);
 262         draw_menu();
 263         draw_field();
 264         if (mode==MODE_EDIT)draw_numpad();
 265 }
 266 
 267 void gui_sudoku_draw()
 268 {
 269         //battery and watch?
 270         if (draw&BG)redraw();
 271         else
 272         {
 273                 if (draw&FIELD)draw_field();
 274                 if (draw&MENU)draw_menu();
 275                 if (draw&PAD)draw_numpad();
 276         }
 277         draw=0;
 278 }
 279 
 280 
 281 ///////////////////////Sudoku logic/////////////////////////////////////////////
 282 
 283 int sudoku_finished(int *pointer)       //Flag, for user and mess
 284 {       //ist das Sudoku voll?
 285         int i;
 286         for (i=1; i<=81; i++)
 287         {
 288                 if (*pointer==0 || one_plus_nums(*pointer))
 289                         return 0;
 290                 pointer++;
 291         }
 292         return 1;
 293 }
 294 
 295 //checks, that there are no duplicate numbers in row, column and squares
 296 int sudoku_follows_rules(int *pointer)  //for user and mess
 297 {
 298         int counter, chkflag, x, y, xs, ys, linenum, columnnum;
 299 
 300         //lines
 301         for (linenum=0; linenum<=8; linenum++)
 302         {
 303         for (chkflag=1; chkflag<10; chkflag++)
 304         {
 305                 counter=0;
 306                 for (x=0; x<=8; x++)
 307                 {
 308                         if (*(pointer+linenum*9+x)&flag[chkflag])
 309                         {
 310                                 counter++;
 311                                 if (counter>1) return 0;
 312                         }
 313                 }
 314         }
 315         }
 316 
 317 
 318         //columns
 319         for (columnnum=0; columnnum<=8; columnnum++)
 320         {
 321                 for (chkflag=1; chkflag<10; chkflag++)
 322                 {
 323                         counter=0;
 324                         for (y=0; y<=8; y++)
 325                         {
 326                                 if (*(pointer+y*9+columnnum)&flag[chkflag])
 327                                 {
 328                                         counter++;
 329                                         if (counter>1) return 0;
 330                                 }
 331                         }
 332                 }
 333         }
 334 
 335 
 336         //squares
 337         for (chkflag=1; chkflag<10; chkflag++)
 338         {
 339                 //Select the square
 340                 for (ys=0; ys<3; ys++)
 341                 {
 342                         for (xs=0; xs<3; xs++)
 343                         {
 344                                 counter=0;
 345                                 //Check each number in that square
 346                                 for (y=ys*3; y<ys*3+3; y++)
 347                                 {
 348                                         for (x=xs*3; x<xs*3+3; x++)
 349                                         {
 350                                                 if (*(pointer+y*9+x)&flag[chkflag])
 351                                                 {
 352                                                         counter++;
 353                                                         if (counter>1)return 0;
 354                                                 }
 355                                         }
 356                                 }
 357                         }
 358                 }
 359         }
 360 
 361         //Sudoku has right syntax when it didn't return before
 362         return 1;
 363 }
 364 
 365 //is the sudoku still right if i insert number at x, y?
 366 //works with flags defined in flag[]
 367 int sudoku_follows_rules_xy(int x, int y, int number)   //for field
 368 {
 369         int yc, xc;
 370         for (xc=0; xc<9; xc++) if (field[y][xc]&(number)) return 0;
 371         for (yc=0; yc<9; yc++) if (field[yc][x]&(number)) return 0;
 372 
 373         //printf("xq=%d, yq=%d\n", xq, yq);
 374         for (yc = y/3 * 3; yc < y/3 * 3 + 3; yc++)
 375                 for (xc = x/3 * 3; xc < x/3 * 3 + 3; xc++)
 376                         if (field[yc][xc]& number) return 0;
 377         return 1;
 378 }
 379 
 380 //missing numbers in lines, columns and squares
 381 //from the return number you can extract the missing numbers with & and flag[x], work in mess[][]
 382 int get_missing_nums_line(int lineNum)  //Flag
 383 {
 384         int returnnum=0;
 385         int x;
 386         for (x=0; x<9; x++)
 387         {
 388                 if (is_one_num(mess[lineNum][x]))returnnum |= mess[lineNum][x];
 389         }
 390         return ~returnnum;
 391 }
 392 
 393 int get_missing_nums_column(int columnNumber)   //Flag
 394 {
 395         int returnnum=0;
 396         int y;
 397         for (y=0; y<9; y++)
 398         {
 399                 if (is_one_num(mess[y][columnNumber]))returnnum |= mess[y][columnNumber];
 400         }
 401         return ~returnnum;
 402 }
 403 
 404 int get_missing_nums_square(int squareX, int squareY)   //Flag
 405 {
 406         int returnnum=0;
 407         int y, x;
 408         for (y=squareY*3; y<squareY*3+3; y++)
 409         {
 410                 for (x=squareX*3; x<squareX*3+3; x++)
 411                 {
 412                         if (is_one_num(mess[y][x]))returnnum |= mess[y][x];
 413                 }
 414         }
 415         return ~returnnum;
 416 }
 417 
 418 //The first solving algorithm:
 419 //The missing numbers in each zone of a cell get AND-ed
 420 //so that only the possible numbers are saved in each cell
 421 //1234, 2345, 3456 -> 34
 422 int sudoku_search_candidates()
 423 {
 424         int temp, leftnums;
 425         int x, y, xs, ys;
 426         int change=0;
 427         //columns
 428         for (x=0; x<=8; x++)
 429         {
 430                 leftnums=get_missing_nums_column(x);
 431                 for (y=0; y<=8; y++)
 432                 {
 433                         if (one_plus_nums(mess[y][x]))
 434                         {
 435                                 temp=mess[y][x];
 436                                 mess[y][x]&=leftnums;
 437                                 if (temp !=mess[y][x])
 438                                         change=1;
 439                         }
 440                 }
 441         }
 442 
 443         //squares
 444         for(xs=0; xs<3; xs++)for(ys=0; ys<3; ys++)
 445         {
 446                 leftnums=get_missing_nums_square(xs, ys);
 447                 for(x=xs*3; x<xs*3+3; x++)for (y=ys*3; y<ys*3+3; y++)
 448                 {
 449                         if (one_plus_nums(mess[y][x]))
 450                         {
 451                                 temp=mess[y][x];
 452                                 mess[y][x]&=leftnums;
 453                                 if (temp != mess[y][x])
 454                                         change=1;
 455                         }
 456                 }
 457         }
 458 
 459         //lines
 460         for (y=0; y<9; y++)
 461         {
 462                 leftnums=get_missing_nums_line(y);
 463                 for (x=0; x<9; x++)
 464                 {
 465                         if (one_plus_nums(mess[y][x]))
 466                         {
 467                                 temp=mess[y][x];
 468                                 mess[y][x]&=leftnums;
 469                                 if (temp != mess[y][x])
 470                                         change=1;
 471                         }
 472                 }
 473         }
 474         return change;
 475 }
 476 
 477 //Second solving function:
 478 //It detects, if there is only one place where some number can be
 479 //1234, 1234, 12345 -> 5 in the 3rd cell
 480 int sudoku_insert_lonely_numbers()
 481 {
 482         int x, y, xs, ys, num, count;
 483         int xtemp=0;
 484         int ytemp=0;
 485         int change=0;
 486 
 487         //check squares
 488         for (ys=0; ys<3; ys++) for (xs=0; xs<3;xs++)for (num=1; num<10; num++)
 489         {
 490                         count=0;
 491                         for (y=ys*3; y<ys*3+3; y++)     for (x=xs*3; x<xs*3+3; x++)
 492                         {
 493                                 if (field[y][x] > 0 || mess[y][x]==0 || is_one_num(mess[y][x]))
 494                                         continue;
 495                                 else if (mess[y][x] & flag[num])
 496                                 {
 497                                         if (count == 1)
 498                                                 goto nextnumS;
 499                                         else
 500                                         {
 501                                                 count++;
 502                                                 xtemp = x;
 503                                                 ytemp = y;
 504                                         }
 505                                 }
 506                         }
 507                         if (count==1)
 508                         {
 509                                 mess[ytemp][xtemp]=flag[num];
 510                                 change=1;
 511                         }
 512                         nextnumS:;
 513         }
 514 
 515         //check lines
 516         for (y=0; y<9; y++)for (num=1; num<10; num++)
 517         {
 518                         count=0;
 519                         for (x=0; x<9; x++)
 520                         {
 521                                 if (field[y][x] > 0 || mess[y][x]==0 || is_one_num(mess[y][x]))
 522                                         continue;
 523                                 else if (mess[y][x] & flag[num])
 524                                 {
 525                                         if (count == 1)
 526                                                 goto nextnumL;
 527                                         else
 528                                         {
 529                                                 count++;
 530                                                 xtemp = x;
 531                                                 ytemp = y;
 532                                         }
 533                                 }
 534                         }
 535                         if (count==1)
 536                         {
 537                                 mess[ytemp][xtemp]=flag[num];
 538                                 change=1;
 539                         }
 540                         nextnumL:;
 541         }
 542 
 543         //check columns
 544         for (x=0; x<9; x++)for (num=1; num<10; num++)
 545         {
 546                         count=0;
 547                         for (y=0; y<9; y++)
 548                         {
 549                                 if (field[y][x] > 0 || mess[y][x]==0 || is_one_num(mess[y][x]))
 550                                         continue;
 551                                 else if (mess[y][x] & flag[num])
 552                                 {
 553                                         if (count == 1)
 554                                                 goto nextnumC;
 555                                         else
 556                                         {
 557                                                 count++;
 558                                                 xtemp = x;
 559                                                 ytemp = y;
 560                                         }
 561                                 }
 562                         }
 563                         if (count==1)
 564                         {
 565                                 mess[ytemp][xtemp]=flag[num];
 566                                 change=1;
 567                         }
 568                         nextnumC:;
 569         }
 570 
 571         return change;
 572 }
 573 
 574 //Tries to solve the sudoku pointed at. Returns:
 575 //1, if it does its job
 576 //0, if it didn't complete the sudoku
 577 //              This could be because we know not enough to solve it
 578 //              or the algorithm is not intelligent enough to solve the sudoku.
 579 //-1, if the sudoku can't be solved because of errors in the sudoku or in the algorithm ;(
 580 int sudoku_solve(int *pointer)
 581 {
 582         //copies array from *pointer in mess -> we're solving in mess[][]
 583         memcpy(mess, pointer, sizeof(mess));
 584         int change=0;
 585         int leftnums;
 586         int x, y;
 587 
 588         //fill empty cells
 589         for (y=0; y<=8; y++)
 590         {
 591                 leftnums=get_missing_nums_line(y);
 592                 for (x=0; x<=8; x++)if (mess[y][x]==0)mess[y][x]=leftnums;
 593         }
 594 
 595         //solve!!
 596         do
 597         {
 598                 change=sudoku_search_candidates();
 599                 if (!change)
 600                 {
 601                         if (!sudoku_follows_rules(*mess))return -1;
 602                         else change=sudoku_insert_lonely_numbers();
 603                 }
 604         }while(change);
 605 
 606         //now the code above has filled in every number it could think about
 607         if (sudoku_finished(*mess))
 608         {
 609                 if (sudoku_follows_rules(*mess))
 610                         return 1;
 611                 else return -1;
 612         }
 613         else return 0;
 614 }
 615 
 616 //-------------------------------------------------------------------
 617 //exchange-functions for sudoku_new(), operate on field[][]
 618 //these exchanges will shuffle the sudoku, but won't influence
 619 //solvability or create conflicts
 620 void exchange_row(int r1, int r2)
 621 {
 622         int temp, i;
 623         for (i=0; i<9; i++)
 624         {
 625                 temp=field[r1][i];
 626                 field[r1][i]=field[r2][i];
 627                 field[r2][i]=temp;
 628         }
 629 }
 630 
 631 void exchange_column(int c1, int c2)
 632 {
 633         int temp, i;
 634         for (i=0; i<9; i++)
 635         {
 636                 temp=field[i][c1];
 637                 field[i][c1]=field[i][c2];
 638                 field[i][c2]=temp;
 639         }
 640 }
 641 
 642 void exchangeSquareRow(int sr1, int sr2)
 643 {
 644         int i;
 645         for (i=0; i<3; i++)exchange_row(sr1*3+i, sr2*3+i);
 646 }
 647 
 648 void exchange_square_column(int sc1, int sc2)
 649 {
 650         int i;
 651         for (i=0; i<3; i++)exchange_column(sc1*3+i, sc2*3+i);
 652 }
 653 
 654 //recursive function, tries to remove numbers until START_NUMBERS are reached
 655 //If no solvable sudoku was found, the removed numbers are reinserted.
 656 //count means the count of numbers still in the sudoku
 657 //return value says, if a solvable sudoku was found.
 658 int remove_nums(int count)
 659 {
 660         int ry, rx;
 661         int temp;
 662         int foundone=0;
 663         while (!foundone)
 664         {
 665                 ry=rand()%9;
 666                 rx=rand()%9;
 667                 if (field[ry][rx]!=0)
 668                 {
 669                         foundone=1;
 670                         temp=field[ry][rx];
 671                         field[ry][rx]=0;
 672                 }
 673         }
 674         if (count>START_NUMBERS)
 675         {
 676                 if (remove_nums(count-1)==1)return 1;
 677                 else
 678                 {
 679                         field[ry][rx]=temp;
 680                         if (count<=MAX_START_NUMBERS)return sudoku_solve(*field);
 681                         else return -1;
 682                 }
 683         }
 684         else if (count<=START_NUMBERS)
 685         {
 686                 if (sudoku_solve(*field)==1)return 1;
 687                 else
 688                 {
 689                         field[ry][rx]=temp;
 690                         return -1;
 691                 }
 692         }
 693         //the program shouldn't come to this point, but my compiler is always angry
 694         //because there's a missing return value...
 695         else return -1;
 696 }
 697 
 698 int sudoku_new(void)
 699 {
 700         int foundone=0;
 701         int x, y, i, j;
 702 
 703         srand((unsigned)time(NULL));
 704         while (!foundone)
 705         {
 706                 //reset field[][] to 0 everywhere
 707                 for (x = 0; x < 9; x++) for (y = 0; y < 9; y++) field[y][x] = 0;
 708 
 709                 //fill in the first line
 710                 for (x=0; x<9; x++)field[0][x]=flag[x+1];
 711 
 712                 //shuffling
 713                 for (i=1; i<=10; i++)
 714                 {
 715                         int rdm1=rand()%9+1;
 716                         int rdm2=rand()%9+1;
 717                         if (rdm1==rdm2)rdm2=(rdm2+1)%9;
 718                         rdm1=flag[rdm1];
 719                         rdm2=flag[rdm2];
 720 
 721                         for (j=0; j<9; j++)
 722                         {
 723                                 if (field[0][j]==rdm1)field[0][j]=rdm2;
 724                                 else if (field[0][j]==rdm2)field[0][j]=rdm1;
 725                         }
 726                 }
 727 
 728                 //now, we have to fill the rest of the cells
 729                 //by repeating the pattern just created
 730                 //we start at the second row
 731                 int xnum=2;
 732                 for (y=1; y<9; y++)
 733                 {
 734                         for (x=0; x<9; x++)
 735                         {
 736                                 //%9 so it jumps from the end back to the beginning
 737                                 xnum=(xnum+1)%9;
 738                                 field[y][x]=field[0][xnum];
 739                         }
 740                         if ((y+1)%3==0)xnum=(xnum+4)%9;
 741                         else xnum=(xnum+3)%9;
 742                 }
 743 
 744                 //Okay now, the field is filled with numbers.
 745                 //Now shuffle them a bit so that it won't get too easy!
 746                 int rdm1;
 747                 int rdm2;
 748                 int rdm3;
 749                 for (i=1; i<=10; i++)
 750                 {
 751                         rdm1=rand()%3;
 752                         rdm2=rand()%3;
 753                         if (rdm1==rdm2)rdm2=(rdm2+1)%3;
 754                         exchangeSquareRow(rdm1, rdm2);
 755 
 756                         rdm1=rand()%3;
 757                         rdm2=rand()%3;
 758                         if (rdm1==rdm2)rdm2=(rdm2+1)%3;
 759                         exchange_square_column(rdm1, rdm2);
 760 
 761                         for (j=1; j<=3; j++)
 762                         {
 763                                 rdm1=rand()%3;
 764                                 rdm2=rand()%3;
 765                                 //rdm3 defines in which 3 squares we are shuffling
 766                                 rdm3=rand()%3;
 767                                 if (rdm1==rdm2)rdm2=(rdm2+1)%3;
 768                                 exchange_row(rdm3*3+rdm1, rdm3*3+rdm2);
 769 
 770                                 rdm1=rand()%3;
 771                                 rdm2=rand()%3;
 772                                 rdm3=rand()%3;
 773                                 if (rdm1==rdm2)rdm2=(rdm2+1)%3;
 774                                 exchange_column(rdm3*3+rdm1, rdm3*3+rdm2);
 775                         }
 776                 }
 777 
 778                 //a lot of times, we are not able to find the right numbers to remove,
 779                 //then we just generate a new fully filled sudoku
 780                 //74 tries to remove numbers before going to the next sudoku results in the best speed.
 781                 for (i=1; i<=74; i++)
 782                 {
 783                         if (remove_nums(9*9)==1) {
 784                                 foundone=1;
 785                                 break;
 786                         }
 787                 }
 788 
 789         //end while(!foundone)
 790         }
 791         return 1;
 792 }
 793 
 794 
 795 ///////////////////////////High level functions//////////////////////////////////
 796 
 797 //Chooses, which action to execute in the menu
 798 void sudoku_menu_execute()
 799 {
 800         int y, x;
 801         switch (menuPos)
 802         {
 803                 case 0: //check Sudoku
 804                         if (sudoku_follows_rules(&user[0][0]))  gui_mbox_init(LANG_SUDOKU_TADA, LANG_SUDOKU_0_MISTAKES, MBOX_TEXT_CENTER, NULL);
 805                         else gui_mbox_init(LANG_SUDOKU_INFO, LANG_SUDOKU_NUMBER_OCCURS_TWICE, MBOX_TEXT_CENTER, NULL);
 806                         break;
 807                 case 1: //solve Sudoku
 808                         switch (sudoku_solve(&user[0][0]))
 809                         {
 810                                 case 1:
 811                                         gui_mbox_init(LANG_SUDOKU_INFO, LANG_SUDOKU_SOLVED, MBOX_TEXT_CENTER, NULL);
 812                                         memcpy(user, mess, sizeof(user));       //copies mess[][] in user[][]
 813                                         break;
 814                                 case 0:
 815                                         gui_mbox_init(LANG_SUDOKU_INFO, LANG_SUDOKU_NOT_COMPLETE, MBOX_TEXT_CENTER, NULL);
 816                                         //copy only known numbers
 817                                         for (y=0; y<9; y++)     for (x=0; x<9; x++)     if (is_one_num(mess[y][x]))user[y][x]=mess[y][x];
 818                                         break;
 819                                 case -1:
 820                                         gui_mbox_init(LANG_SUDOKU_INFO, LANG_SUDOKU_NOT_SOLVABLE, MBOX_TEXT_CENTER, NULL);
 821                                         for (y=0; y<9; y++)     for (x=0; x<9; x++)     if (is_one_num(mess[y][x]))user[y][x]=mess[y][x];
 822                                         break;
 823                         }
 824                         break;
 825                 case 2: //new sudoku
 826                         //sprintf(str, "%i tries", sudoku_new());
 827                         //gui_mbox_init((int)"Info", (int)str, MBOX_TEXT_CENTER, NULL);
 828                         sudoku_new();
 829                         memcpy(user, field, sizeof(user));      //field in user kopieren
 830                         break;
 831                 case 3: //own sudoku
 832                         for (x = 0; x < 9; x++)for (y = 0; y < 9; y++)
 833                         {
 834                                 field[y][x] = 0;
 835                                 user[y][x]=0;
 836                         }
 837                         break;
 838                 case 4: //Info
 839                         gui_mbox_init(LANG_SUDOKU_INFO, (int)("(c)Frank, 2012, V 0.5"), MBOX_TEXT_CENTER, NULL);
 840                         break;
 841         case 5:
 842             exit_sudoku(0); //exit without save
 843             break;
 844         case 6:
 845             exit_sudoku(1); //save and exit
 846             break;
 847         case 7:
 848             if (stat("A/CHDK/GAMES/SUDOKU.SAV", 0)==0) {
 849                 remove("A/CHDK/GAMES/SUDOKU.SAV");
 850             }
 851             break;
 852         }
 853         mode=MODE_VIEW;
 854 }
 855 //-------------------------------------------------------------------
 856 //Which keys do what?
 857 int gui_sudoku_kbd_process()
 858 {
 859         int key=kbd_get_autoclicked_key();
 860 
 861         switch (key) {
 862                 //Keys that are always the same
 863                 case KEY_ZOOM_IN:
 864                         if (mode==MODE_VIEW)mode=MODE_MENU;
 865                         else mode=MODE_VIEW;
 866                         draw|=FIELD|MENU;
 867                         break;
 868                 case KEY_ZOOM_OUT:
 869                         mode=MODE_VIEW;
 870                         draw|=FIELD|MENU;
 871                         break;
 872                 case KEY_ERASE:
 873                 case KEY_SHOOT_HALF:
 874                         if (mode & (MODE_VIEW | MODE_EDIT))
 875                         {
 876                                 if (field[yPos][xPos]==0)user[yPos][xPos]=0;
 877                                 if (mode==MODE_EDIT)
 878                                 {
 879                                         mode=MODE_VIEW;
 880                                         del_numpad();
 881                                         xPosPad=1;
 882                                         yPosPad=1;
 883                                 }
 884                                 draw|=FIELD;
 885                         }
 886                         break;
 887 
 888                 case KEY_DISPLAY:
 889                         if (sudoku_follows_rules(*user) & sudoku_finished(*user)) gui_mbox_init(LANG_SUDOKU_CONGRATULATIONS, LANG_SUDOKU_YOU_DID_IT, MBOX_TEXT_CENTER, NULL);
 890                         else if (sudoku_follows_rules(*user)) gui_mbox_init(LANG_SUDOKU_INFO, LANG_SUDOKU_COULDNT_FIND_MISTAKE, MBOX_TEXT_CENTER, NULL);
 891                         else gui_mbox_init(LANG_SUDOKU_INFO, LANG_SUDOKU_SOMETHING_WRONG, MBOX_TEXT_CENTER, NULL);
 892                         draw|=BG;
 893                         break;
 894         }
 895         switch (mode)
 896         {
 897                 case MODE_VIEW:
 898                         if (key & (KEY_UP | KEY_DOWN))
 899                         {
 900                                 yPosOld=yPos;
 901                                 if (key==KEY_UP)yPos--;
 902                                 if (key==KEY_DOWN)yPos++;
 903                                 yPos=(yPos+9)%9;        //so that we don't get beyond the borders
 904                                 draw|=FIELD;
 905                         }
 906                         if (key & (KEY_LEFT | KEY_RIGHT))
 907                         {
 908                                 xPosOld=xPos;
 909                                 if (key==KEY_LEFT)xPos--;
 910                                 if (key==KEY_RIGHT)xPos++;
 911                                 xPos=(xPos+9)%9;        //so that we don't get beyond the borders
 912                                 draw|=FIELD;
 913                         }
 914                         if (key==KEY_SET && field[yPos][xPos]==0)
 915                         {
 916                                 mode=MODE_EDIT;
 917                                 if (user[yPos][xPos]==0)user[yPos][xPos]=get_pad_num();
 918                                 else set_pad_num(get_dec_num(user[yPos][xPos]));
 919                                 draw|=PAD|FIELD;
 920                         }
 921                 break;
 922 
 923                 case MODE_EDIT:
 924                         if (key &(KEY_LEFT | KEY_RIGHT) && yPosPad>=0)
 925                         {
 926                                 if (key==KEY_LEFT)xPosPad--;
 927                                 if (key==KEY_RIGHT)xPosPad++;
 928                                 xPosPad=(xPosPad+3)%3;
 929                                 user[yPos][xPos]=get_pad_num();
 930                                 draw|=FIELD|PAD;
 931                         }
 932                         if (key &(KEY_UP | KEY_DOWN))
 933                         {
 934                                 if (key==KEY_UP)yPosPad--;
 935                                 if (key==KEY_DOWN)yPosPad++;
 936                                 if (xPosPad==1)yPosPad=((yPosPad+5)%4)-1;
 937                                 else yPosPad=(yPosPad+3)%3;
 938                                 user[yPos][xPos]=get_pad_num();
 939                                 draw|=FIELD|PAD;
 940                         }
 941                         if (key==KEY_SET)
 942                         {
 943                                 mode=MODE_VIEW;
 944                                 draw=FIELD;
 945                                 del_numpad();
 946                                 xPosPad=1;
 947                                 yPosPad=1;
 948                                 if (sudoku_finished(&user[0][0])){
 949                                         if (sudoku_follows_rules(&user[0][0]))
 950                                                 gui_mbox_init(LANG_SUDOKU_CONGRATULATIONS, LANG_SUDOKU_EVERYTHINGS_CORRECT, MBOX_TEXT_CENTER, NULL);
 951                                         else
 952                                                 gui_mbox_init(LANG_SUDOKU_INFO, LANG_SUDOKU_SOMETHING_WRONG, MBOX_TEXT_CENTER, NULL);
 953                                         draw|=BG;
 954                                 }
 955                         }
 956                 break;
 957 
 958                 case MODE_MENU:  //Keys in Menumode
 959                         key |= get_jogdial_direction();
 960                         if (key & (KEY_UP | KEY_DOWN | JOGDIAL_LEFT | JOGDIAL_RIGHT))
 961                         {
 962                                 if (key==KEY_UP || key==JOGDIAL_LEFT)menuPos--;
 963                                 if (key==KEY_DOWN || key==JOGDIAL_RIGHT)menuPos++;
 964                                 menuPos=(menuPos+MENU_ELEMENTS)%MENU_ELEMENTS;
 965                                 draw|=MENU;
 966                         }
 967                         switch (key) {
 968                                 case KEY_SET:
 969                                         sudoku_menu_execute();
 970                                         draw|=BG;
 971                                         break;
 972                                 case KEY_LEFT:
 973                                 case KEY_RIGHT:
 974                                         mode=MODE_VIEW;
 975                                         draw|=FIELD|MENU;
 976                                         break;
 977                         }
 978                 break;
 979         }
 980     return 0;
 981 }
 982 //-------------------------------------------------------------------
 983 
 984 int gui_sudoku_init()
 985 {
 986         int x, y;
 987         xFieldBorder = 12 + camera_screen.disp_left;
 988         yFieldBorder = 12;
 989     xMenuPos = camera_screen.disp_right - FONT_WIDTH*15 + 1;
 990         xPos=4;
 991         yPos=4;
 992     if (camera_screen.height-yFieldBorder*2 > xMenuPos-xFieldBorder)
 993     {
 994         fieldLineDistance=(xMenuPos-xFieldBorder)/9;
 995     }
 996     else
 997     {
 998         fieldLineDistance=(camera_screen.height-yFieldBorder*2)/9;
 999     }
1000         fieldLineLength=fieldLineDistance*9;
1001         mode=MODE_VIEW;
1002         menuPos=0;
1003         padLineDistance=fieldLineDistance;
1004         xPadStart = xMenuPos;
1005         yPadStart = padLineDistance*6 + 20;
1006         xPosPad=1;
1007         yPosPad=1;
1008         for (x = 0; x < 9; x++) for (y = 0; y < 9; y++)
1009         {
1010                 field[y][x] = 0;
1011                 user[y][x]=0;
1012         }
1013         draw|=BG;
1014         gui_sudoku_draw(0);
1015 
1016     char *buf = load_file("A/CHDK/GAMES/SUDOKU.SAV", 0, 0);
1017         if (buf) { //load last sudoku
1018         memcpy(user, buf, sizeof(user));
1019         memcpy(field, buf+sizeof(user), sizeof(field));
1020         free(buf);
1021         } else {
1022         sudoku_new();
1023         memcpy(user, field, sizeof(user));      //copies field[][] in user[][]
1024         }
1025         gui_mbox_init(LANG_SUDOKU_CONGRATULATIONS, LANG_SUDOKU_EVERYTHINGS_CORRECT, MBOX_TEXT_CENTER, NULL);
1026         draw|=FIELD;
1027         gui_sudoku_draw(0);
1028         gui_set_mode(&GUI_MODE_SUDOKU);
1029         return 1;
1030 }
1031 
1032 void gui_module_menu_kbd_process()
1033 {
1034         if (mode==MODE_VIEW)mode=MODE_MENU;
1035     else mode=MODE_VIEW;
1036     draw|=FIELD|MENU;
1037 }
1038 
1039 void exit_sudoku(int save)
1040 {
1041     if (save!=0)
1042     {
1043         save = open("A/CHDK/GAMES/SUDOKU.SAV", O_WRONLY|O_CREAT|O_TRUNC, 0777);
1044         if (save>=0)
1045         {
1046             write(save, user, sizeof(user));
1047             write(save, field, sizeof(field));
1048             close(save);
1049         }
1050     }
1051     running = 0;
1052     gui_default_kbd_process_menu_btn();
1053 }
1054 
1055 // =========  MODULE INIT =================
1056 
1057 /***************** BEGIN OF AUXILARY PART *********************
1058   ATTENTION: DO NOT REMOVE OR CHANGE SIGNATURES IN THIS SECTION
1059  **************************************************************/
1060 
1061 int _run()
1062 {
1063     if (!camera_info.state.mode_play)
1064     {
1065         gui_mbox_init(LANG_MSG_INFO_TITLE, LANG_MSG_SWITCH_TO_PLAY_MODE, MBOX_FUNC_RESTORE|MBOX_TEXT_CENTER, 0);
1066     }
1067     else
1068     {
1069         running = 1;
1070         gui_sudoku_init();
1071     }
1072 
1073     return 0;
1074 }
1075 
1076 int _module_can_unload()
1077 {
1078     return running == 0;
1079 }
1080 
1081 int _module_exit_alt()
1082 {
1083     running = 0;
1084     return 0;
1085 }
1086 
1087 /*************** END OF AUXILARY PART *******************/
1088 
1089 /******************** Module Information structure ******************/
1090 
1091 libsimple_sym _librun =
1092 {
1093     {
1094          0, 0, _module_can_unload, _module_exit_alt, _run
1095     }
1096 };
1097 
1098 ModuleInfo _module_info =
1099 {
1100     MODULEINFO_V1_MAGICNUM,
1101     sizeof(ModuleInfo),
1102     SIMPLE_MODULE_VERSION,              // Module version
1103 
1104     ANY_CHDK_BRANCH, 0, OPT_ARCHITECTURE,                       // Requirements of CHDK version
1105     ANY_PLATFORM_ALLOWED,               // Specify platform dependency
1106 
1107     -LANG_MENU_GAMES_SUDOKU,    // Module name
1108     MTYPE_GAME,
1109 
1110     &_librun.base,
1111 
1112     ANY_VERSION,                // CONF version
1113     CAM_SCREEN_VERSION,         // CAM SCREEN version
1114     ANY_VERSION,                // CAM SENSOR version
1115     ANY_VERSION,                // CAM INFO version
1116 };

/* [<][>][^][v][top][bottom][index][help] */