diff options
-rw-r--r-- | apps/plugins/sudoku/sudoku.c | 286 |
1 files changed, 0 insertions, 286 deletions
diff --git a/apps/plugins/sudoku/sudoku.c b/apps/plugins/sudoku/sudoku.c index 4a7fbd93a8..02615caac1 100644 --- a/apps/plugins/sudoku/sudoku.c +++ b/apps/plugins/sudoku/sudoku.c | |||
@@ -286,292 +286,6 @@ static unsigned int cellypos[9]={ | |||
286 | #define BLOCK 3 | 286 | #define BLOCK 3 |
287 | #define SIZE (BLOCK*BLOCK) | 287 | #define SIZE (BLOCK*BLOCK) |
288 | 288 | ||
289 | #if 0 | ||
290 | /****** Solver routine by Tom Shackell <shackell@cs.york.ac.uk> | ||
291 | |||
292 | Downloaded from: | ||
293 | |||
294 | http://www-users.cs.york.ac.uk/~shackell/sudoku/Sudoku.html | ||
295 | |||
296 | Released under GPLv2 | ||
297 | |||
298 | */ | ||
299 | |||
300 | typedef unsigned int Bitset; | ||
301 | |||
302 | #define true 1 | ||
303 | #define false 0 | ||
304 | |||
305 | typedef struct _Sudoku { | ||
306 | Bitset table[SIZE][SIZE]; | ||
307 | }Sudoku; | ||
308 | |||
309 | typedef struct _Stats { | ||
310 | int numTries; | ||
311 | int backTracks; | ||
312 | int numEmpty; | ||
313 | bool solutionFound; | ||
314 | }Stats; | ||
315 | |||
316 | typedef struct _Options { | ||
317 | bool allSolutions; | ||
318 | bool uniquenessCheck; | ||
319 | }Options; | ||
320 | |||
321 | void sudoku_init(Sudoku* sud); | ||
322 | void sudoku_set(Sudoku* sud, int x, int y, int num, bool original); | ||
323 | int sudoku_get(Sudoku* sud, int x, int y, bool* original); | ||
324 | |||
325 | #define BIT(n) ((Bitset)BIT_N(n)) | ||
326 | #define BIT_TEST(v,n) ((((Bitset)v) & BIT(n)) != 0) | ||
327 | #define BIT_CLEAR(v,n) (v) &= ~BIT(n) | ||
328 | #define MARK_BIT BIT(0) | ||
329 | #define ORIGINAL_BIT BIT(SIZE+1) | ||
330 | |||
331 | #define ALL_BITS (BIT(1) | BIT(2) | BIT(3) | BIT(4) | BIT(5) | BIT(6) | BIT(7) | BIT(8) | BIT(9)) | ||
332 | |||
333 | /* initialize a sudoku problem, should be called before using set or get */ | ||
334 | void sudoku_init(Sudoku* sud) | ||
335 | { | ||
336 | int y, x; | ||
337 | for (y = 0; y < SIZE; y++){ | ||
338 | for (x = 0; x < SIZE; x++){ | ||
339 | sud->table[x][y] = ALL_BITS; | ||
340 | } | ||
341 | } | ||
342 | } | ||
343 | |||
344 | /* set the number at a particular x and y column */ | ||
345 | void sudoku_set(Sudoku* sud, int x, int y, int num, bool original) | ||
346 | { | ||
347 | int i, j; | ||
348 | int bx, by; | ||
349 | Bitset orig; | ||
350 | |||
351 | /* clear the row and columns */ | ||
352 | for (i = 0; i < SIZE; i++){ | ||
353 | BIT_CLEAR(sud->table[i][y], num); | ||
354 | BIT_CLEAR(sud->table[x][i], num); | ||
355 | } | ||
356 | /* clear the block */ | ||
357 | bx = x - (x % BLOCK); | ||
358 | by = y - (y % BLOCK); | ||
359 | for (i = 0; i < BLOCK; i++){ | ||
360 | for (j = 0; j < BLOCK; j++){ | ||
361 | BIT_CLEAR(sud->table[bx+j][by+i], num); | ||
362 | } | ||
363 | } | ||
364 | /* mark the table */ | ||
365 | orig = original ? ORIGINAL_BIT : 0; | ||
366 | sud->table[x][y] = BIT(num) | MARK_BIT | orig; | ||
367 | } | ||
368 | |||
369 | /* get the number at a particular x and y column, if this | ||
370 | is not unique return 0 */ | ||
371 | int sudoku_get(Sudoku* sud, int x, int y, bool* original) | ||
372 | { | ||
373 | Bitset val = sud->table[x][y]; | ||
374 | int result = 0; | ||
375 | int i; | ||
376 | |||
377 | if (original) { | ||
378 | *original = val & ORIGINAL_BIT; | ||
379 | } | ||
380 | for (i = 1; i <= SIZE; i++){ | ||
381 | if (BIT_TEST(val, i)){ | ||
382 | if (result != 0){ | ||
383 | return 0; | ||
384 | } | ||
385 | result = i; | ||
386 | } | ||
387 | } | ||
388 | return result; | ||
389 | } | ||
390 | |||
391 | /* returns true if this is a valid problem, this is necessary because the input | ||
392 | problem might be degenerate which breaks the solver algorithm. */ | ||
393 | static bool is_valid(const Sudoku* sud) | ||
394 | { | ||
395 | int x, y; | ||
396 | |||
397 | for (y = 0; y < SIZE; y++){ | ||
398 | for (x = 0; x < SIZE; x++){ | ||
399 | if ((sud->table[x][y] & ALL_BITS) == 0){ | ||
400 | return false; | ||
401 | } | ||
402 | } | ||
403 | } | ||
404 | return true; | ||
405 | } | ||
406 | |||
407 | /* scan the table for the most constrained item, giving all it's options, sets | ||
408 | the best x and y coordinates, the number of options and the options for | ||
409 | that coordinate and returns true if the puzzle is finished */ | ||
410 | static bool scan(const Sudoku* sud, int* rX, int* rY, int *num, int* options) | ||
411 | { | ||
412 | int x, y, i, j; | ||
413 | int bestCount = SIZE+1; | ||
414 | Bitset val; | ||
415 | bool allMarked = true; | ||
416 | |||
417 | for (y = 0; y < SIZE; y++){ | ||
418 | for (x = 0; x < SIZE; x++){ | ||
419 | Bitset val = sud->table[x][y]; | ||
420 | int i; | ||
421 | int count = 0; | ||
422 | |||
423 | if (val & MARK_BIT) { | ||
424 | /* already set */ | ||
425 | continue; | ||
426 | } | ||
427 | allMarked = false; | ||
428 | for (i = 1; i <= SIZE; i++){ | ||
429 | if (BIT_TEST(val, i)){ | ||
430 | count++; | ||
431 | } | ||
432 | } | ||
433 | if (count < bestCount){ | ||
434 | bestCount = count; | ||
435 | *rX = x; | ||
436 | *rY = y; | ||
437 | if (count == 0){ | ||
438 | /* can't possibly be beaten */ | ||
439 | *num = 0; | ||
440 | return false; | ||
441 | } | ||
442 | } | ||
443 | } | ||
444 | } | ||
445 | /* now copy into options */ | ||
446 | *num = bestCount; | ||
447 | val = sud->table[*rX][*rY]; | ||
448 | for (i = 1, j = 0; i <= SIZE; i++){ | ||
449 | if (BIT_TEST(val, i)){ | ||
450 | options[j++] = i; | ||
451 | } | ||
452 | } | ||
453 | return allMarked; | ||
454 | } | ||
455 | |||
456 | static bool solve(Sudoku* sud, Stats* stats, const Options* options); | ||
457 | |||
458 | /* try a particular option and return true if that gives a solution or false | ||
459 | if it doesn't, restores board on backtracking */ | ||
460 | static bool spawn_option(Sudoku* sud, Stats* stats, const Options* options, | ||
461 | int x, int y, int num) | ||
462 | { | ||
463 | Sudoku copy; | ||
464 | |||
465 | rb->memcpy(©,sud,sizeof(Sudoku)); | ||
466 | sudoku_set(©, x, y, num, false); | ||
467 | stats->numTries += 1; | ||
468 | if (solve(©, stats, options)){ | ||
469 | if (!options->allSolutions && stats->solutionFound){ | ||
470 | rb->memcpy(sud,©,sizeof(Sudoku)); | ||
471 | } | ||
472 | return true; | ||
473 | }else{ | ||
474 | stats->backTracks++; | ||
475 | } | ||
476 | return false; | ||
477 | } | ||
478 | |||
479 | /* solve a sudoku problem, returns true if there is a solution and false | ||
480 | otherwise. stats is used to track statisticss */ | ||
481 | static bool solve(Sudoku* sud, Stats* stats, const Options* options) | ||
482 | { | ||
483 | while (true){ | ||
484 | int x = 0; | ||
485 | int y = 0; | ||
486 | int i, num; | ||
487 | int places[SIZE]; | ||
488 | |||
489 | if (scan(sud, &x, &y, &num, places)){ | ||
490 | /* a solution was found! */ | ||
491 | if (options->uniquenessCheck && stats->solutionFound){ | ||
492 | /*printf("\n\t... But the solution is not unique!\n"); */ | ||
493 | return true; | ||
494 | } | ||
495 | stats->solutionFound = true; | ||
496 | if (options->allSolutions || options->uniquenessCheck){ | ||
497 | /*printf("\n\tSolution after %d iterations\n", stats->numTries); */ | ||
498 | /*sudoku_print(sud); */ | ||
499 | return false; | ||
500 | } | ||
501 | else{ | ||
502 | return true; | ||
503 | } | ||
504 | } | ||
505 | if (num == 0){ | ||
506 | /* can't be satisfied */ | ||
507 | return false; | ||
508 | } | ||
509 | /* try all the places (except the last one) */ | ||
510 | for (i = 0; i < num-1; i++){ | ||
511 | if (spawn_option(sud, stats, options, x, y, places[i])){ | ||
512 | /* solution found! */ | ||
513 | if (!options->allSolutions && stats->solutionFound){ | ||
514 | return true; | ||
515 | } | ||
516 | } | ||
517 | } | ||
518 | /* take the last place ourself */ | ||
519 | stats->numTries += 1; | ||
520 | sudoku_set(sud, x, y, places[num-1], false); | ||
521 | } | ||
522 | } | ||
523 | |||
524 | /******** END OF IMPORTED CODE */ | ||
525 | |||
526 | |||
527 | /* A wrapper function between the Sudoku plugin and the above solver code */ | ||
528 | void sudoku_solve(struct sudoku_state_t* state) | ||
529 | { | ||
530 | bool ret; | ||
531 | Stats stats; | ||
532 | Options options; | ||
533 | Sudoku sud; | ||
534 | bool original; | ||
535 | int r,c; | ||
536 | |||
537 | /* Initialise the parameters */ | ||
538 | sudoku_init(&sud); | ||
539 | rb->memset(&stats,0,sizeof(stats)); | ||
540 | options.allSolutions=false; | ||
541 | options.uniquenessCheck=false; | ||
542 | |||
543 | /* Convert Rockbox format into format for solver */ | ||
544 | for (r=0;r<9;r++) { | ||
545 | for (c=0;c<9;c++) { | ||
546 | if (state->startboard[r][c]!='0') { | ||
547 | sudoku_set(&sud, c, r, state->startboard[r][c]-'0', true); | ||
548 | } | ||
549 | } | ||
550 | } | ||
551 | |||
552 | /* need to check for degenerate input problems ... */ | ||
553 | if (is_valid(&sud)){ | ||
554 | ret = solve(&sud, &stats, &options); | ||
555 | } else { | ||
556 | ret = false; | ||
557 | } | ||
558 | |||
559 | if (ret) { | ||
560 | /* Populate the board with the solution. */ | ||
561 | for (r=0;r<9;r++) { | ||
562 | for (c=0;c<9;c++) { | ||
563 | state->currentboard[r][c]='0'+ | ||
564 | sudoku_get(&sud, c, r, &original); | ||
565 | } | ||
566 | } | ||
567 | } else { | ||
568 | rb->splash(HZ*2, "Solve failed"); | ||
569 | } | ||
570 | |||
571 | return; | ||
572 | } | ||
573 | #endif /* 0 */ | ||
574 | |||
575 | void sudoku_solve(struct sudoku_state_t* state) | 289 | void sudoku_solve(struct sudoku_state_t* state) |
576 | { | 290 | { |
577 | bool ret = sudoku_solve_board(state); | 291 | bool ret = sudoku_solve_board(state); |