From 6afb017642a82aabbcd6f4ea5c31ec5d3945f5f8 Mon Sep 17 00:00:00 2001 From: Dave Chapman Date: Thu, 22 Sep 2005 08:53:04 +0000 Subject: First version of Sudoku plugin git-svn-id: svn://svn.rockbox.org/rockbox/trunk@7532 a1c6a512-1295-4272-9138-f99709370657 --- apps/plugins/SOURCES | 1 + apps/plugins/sudoku.c | 1180 +++++++++++++++++++++++++++++++++++++++++++ apps/plugins/viewers.config | 1 + 3 files changed, 1182 insertions(+) create mode 100644 apps/plugins/sudoku.c (limited to 'apps') diff --git a/apps/plugins/SOURCES b/apps/plugins/SOURCES index 254324164a..598eef03a9 100644 --- a/apps/plugins/SOURCES +++ b/apps/plugins/SOURCES @@ -40,6 +40,7 @@ snake2.c sokoban.c solitaire.c star.c +sudoku.c #if CONFIG_LCD == LCD_SSD1815 video.c #endif diff --git a/apps/plugins/sudoku.c b/apps/plugins/sudoku.c new file mode 100644 index 0000000000..4bd23e8394 --- /dev/null +++ b/apps/plugins/sudoku.c @@ -0,0 +1,1180 @@ +/*************************************************************************** + * __________ __ ___. + * 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" +#include "button.h" +#include "lcd.h" + +#ifdef HAVE_LCD_BITMAP + +#define STATE_FILE PLUGIN_DIR "/sudoku.state" +#define GAMES_FILE PLUGIN_DIR "/sudoku.levels" + +/* variable button definitions */ +#if CONFIG_KEYPAD == RECORDER_PAD +#define SUDOKU_BUTTON_QUIT BUTTON_OFF +#define SUDOKU_BUTTON_TOGGLE BUTTON_PLAY +#define SUDOKU_BUTTON_MENU BUTTON_F3 + +#elif CONFIG_KEYPAD == ONDIO_PAD +#define SUDOKU_BUTTON_QUIT BUTTON_OFF +#define SUDOKU_BUTTON_TOGGLE BUTTON_MENU +#define SUDOKU_BUTTON_MENU (BUTTON_MENU | BUTTON_OFF) + +#elif (CONFIG_KEYPAD == IRIVER_H100_PAD) || \ + (CONFIG_KEYPAD == IRIVER_H300_PAD) +#define SUDOKU_BUTTON_QUIT BUTTON_OFF +#define SUDOKU_BUTTON_TOGGLE BUTTON_SELECT +#define SUDOKU_BUTTON_MENU BUTTON_MODE + +#elif + #error SUDOKU: Unsupported keypad +#endif + +#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) +#define YOFS ((LCD_HEIGHT-BOARD_HEIGHT)/2) + +/* 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 }; + +/* Normal numbers - 12z12 including a 1-pixel margin all around */ +static unsigned char num[10][36]= { + /* Blank cell */ + {0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00, + 0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00, + 0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00 + }, + /* Numeral 1 */ + {0x00,0x00,0x00,0xc0,0xf0,0xfc,0xfc,0x00,0x00,0x00,0x00,0x00, + 0x00,0x00,0x00,0x00,0x00,0xff,0xff,0x00,0x00,0x00,0x00,0x00, + 0x00,0x00,0x00,0x30,0x30,0x3f,0x3f,0x30,0x30,0x00,0x00,0x00 + }, + /* Numeral 2 */ + {0x00,0x00,0xf0,0xfc,0x0c,0x0c,0x0c,0xfc,0xf0,0x00,0x00,0x00, + 0x00,0x00,0x00,0x00,0xc0,0xf0,0x3c,0x0f,0x03,0x00,0x00,0x00, + 0x00,0x00,0x3c,0x3f,0x33,0x30,0x30,0x30,0x30,0x00,0x00,0x00 + }, + /* Numeral 3 */ + {0x00,0x00,0x0c,0x0c,0x0c,0x0c,0xcc,0xfc,0x3c,0x00,0x00,0x00, + 0x00,0x00,0x00,0x00,0x0c,0x0f,0x0f,0xfc,0xf0,0x00,0x00,0x00, + 0x00,0x00,0x0c,0x3c,0x30,0x30,0x30,0x3f,0x0f,0x00,0x00,0x00 + }, + /* Numeral 4 */ + {0x00,0x00,0x00,0x00,0xc0,0xf0,0xfc,0xfc,0x00,0x00,0x00,0x00, + 0x00,0x00,0xfc,0xff,0xc3,0xc0,0xff,0xff,0xc0,0x00,0x00,0x00, + 0x00,0x00,0x00,0x00,0x00,0x00,0x3f,0x3f,0x00,0x00,0x00,0x00 + }, + /* Numeral 5 */ + {0x00,0x00,0xfc,0xfc,0x0c,0x0c,0x0c,0x0c,0x0c,0x00,0x00,0x00, + 0x00,0x00,0x0f,0x0f,0x0f,0x03,0x03,0xff,0xfc,0x00,0x00,0x00, + 0x00,0x00,0x0c,0x3c,0x30,0x30,0x30,0x3f,0x0f,0x00,0x00,0x00 + }, + /* Numeral 6 */ + {0x00,0x00,0xc0,0xf0,0x3c,0x0c,0x0c,0x0c,0x00,0x00,0x00,0x00, + 0x00,0x00,0xff,0xff,0x3c,0x0c,0x0c,0xfc,0xf0,0x00,0x00,0x00, + 0x00,0x00,0x0f,0x3f,0x3c,0x30,0x30,0x3f,0x0f,0x00,0x00,0x00 + }, + /* Numeral 7 */ + {0x00,0x00,0x0c,0x0c,0x0c,0x0c,0x0c,0xfc,0xfc,0x00,0x00,0x00, + 0x00,0x00,0x00,0x00,0xc0,0xfc,0x3f,0x03,0x00,0x00,0x00,0x00, + 0x00,0x00,0x00,0x00,0x3f,0x3f,0x00,0x00,0x00,0x00,0x00,0x00 + }, + /* Numeral 8 */ + {0x00,0x00,0xf0,0xfc,0x0c,0x0c,0x0c,0xfc,0xf0,0x00,0x00,0x00, + 0x00,0x00,0xf3,0xff,0x0c,0x0c,0x0c,0xff,0xf3,0x00,0x00,0x00, + 0x00,0x00,0x0f,0x3f,0x30,0x30,0x30,0x3f,0x0f,0x00,0x00,0x00 + }, + /* Numeral 9 */ + {0x00,0x00,0xf0,0xfc,0x0c,0x0c,0x3c,0xfc,0xf0,0x00,0x00,0x00, + 0x00,0x00,0x0f,0x3f,0x30,0x30,0x3c,0xff,0xff,0x00,0x00,0x00, + 0x00,0x00,0x00,0x30,0x30,0x30,0x3c,0x0f,0x03,0x00,0x00,0x00 + }, +}; + +/* Starting numbers - on iriver this is with light-grey background */ + +static unsigned char num_start[10][36]= { + /* Blank cell */ + {0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00, + 0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00, + 0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00 + }, + /* Numeral 1 */ + {0x55,0x55,0x55,0xd5,0xf5,0xfd,0xfd,0x55,0x55,0x55,0x55,0x55, + 0x55,0x55,0x55,0x55,0x55,0xff,0xff,0x55,0x55,0x55,0x55,0x55, + 0x55,0x55,0x55,0x75,0x75,0x7f,0x7f,0x75,0x75,0x55,0x55,0x55 + }, + /* Numeral 2 */ + {0x55,0x55,0xf5,0xfd,0x5d,0x5d,0x5d,0xfd,0xf5,0x55,0x55,0x55, + 0x55,0x55,0x55,0x55,0xd5,0xf5,0x7d,0x5f,0x57,0x55,0x55,0x55, + 0x55,0x55,0x7d,0x7f,0x77,0x75,0x75,0x75,0x75,0x55,0x55,0x55 + }, + /* Numeral 3 */ + {0x55,0x55,0x5d,0x5d,0x5d,0x5d,0xdd,0xfd,0x7d,0x55,0x55,0x55, + 0x55,0x55,0x55,0x55,0x5d,0x5f,0x5f,0xfd,0xf5,0x55,0x55,0x55, + 0x55,0x55,0x5d,0x7d,0x75,0x75,0x75,0x7f,0x5f,0x55,0x55,0x55 + }, + /* Numeral 4 */ + {0x55,0x55,0x55,0x55,0xd5,0xf5,0xfd,0xfd,0x55,0x55,0x55,0x55, + 0x55,0x55,0xfd,0xff,0xd7,0xd5,0xff,0xff,0xd5,0x55,0x55,0x55, + 0x55,0x55,0x55,0x55,0x55,0x55,0x7f,0x7f,0x55,0x55,0x55,0x55 + }, + /* Numeral 5 */ + {0x55,0x55,0xfd,0xfd,0x5d,0x5d,0x5d,0x5d,0x5d,0x55,0x55,0x55, + 0x55,0x55,0x5f,0x5f,0x5f,0x57,0x57,0xff,0xfd,0x55,0x55,0x55, + 0x55,0x55,0x5d,0x7d,0x75,0x75,0x75,0x7f,0x5f,0x55,0x55,0x55 + }, + /* Numeral 6 */ + {0x55,0x55,0xd5,0xf5,0x7d,0x5d,0x5d,0x5d,0x55,0x55,0x55,0x55, + 0x55,0x55,0xff,0xff,0x7d,0x5d,0x5d,0xfd,0xf5,0x55,0x55,0x55, + 0x55,0x55,0x5f,0x7f,0x7d,0x75,0x75,0x7f,0x5f,0x55,0x55,0x55 + }, + /* Numeral 7 */ + {0x55,0x55,0x5d,0x5d,0x5d,0x5d,0x5d,0xfd,0xfd,0x55,0x55,0x55, + 0x55,0x55,0x55,0x55,0xd5,0xfd,0x7f,0x57,0x55,0x55,0x55,0x55, + 0x55,0x55,0x55,0x55,0x7f,0x7f,0x55,0x55,0x55,0x55,0x55,0x55 + }, + /* Numeral 8 */ + {0x55,0x55,0xf5,0xfd,0x5d,0x5d,0x5d,0xfd,0xf5,0x55,0x55,0x55, + 0x55,0x55,0xf7,0xff,0x5d,0x5d,0x5d,0xff,0xf7,0x55,0x55,0x55, + 0x55,0x55,0x5f,0x7f,0x75,0x75,0x75,0x7f,0x5f,0x55,0x55,0x55 + }, + /* Numeral 9 */ + {0x55,0x55,0xf5,0xfd,0x5d,0x5d,0x7d,0xfd,0xf5,0x55,0x55,0x55, + 0x55,0x55,0x5f,0x7f,0x75,0x75,0x7d,0xff,0xff,0x55,0x55,0x55, + 0x55,0x55,0x55,0x75,0x75,0x75,0x7d,0x5f,0x57,0x55,0x55,0x55 + }, +}; + +static unsigned char num_inverse[10][36]= { + /* Blank cell */ + {0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff, + 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff, + 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff + }, + /* Numeral 1 */ + {0xff,0xff,0xff,0x3f,0x0f,0x03,0x03,0xff,0xff,0xff,0xff,0xff, + 0xff,0xff,0xff,0xff,0xff,0x00,0x00,0xff,0xff,0xff,0xff,0xff, + 0xff,0xff,0xff,0xcf,0xcf,0xc0,0xc0,0xcf,0xcf,0xff,0xff,0xff + }, + /* Numeral 2 */ + {0xff,0xff,0x0f,0x03,0xf3,0xf3,0xf3,0x03,0x0f,0xff,0xff,0xff, + 0xff,0xff,0xff,0xff,0x3f,0x0f,0xc3,0xf0,0xfc,0xff,0xff,0xff, + 0xff,0xff,0xc3,0xc0,0xcc,0xcf,0xcf,0xcf,0xcf,0xff,0xff,0xff + }, + /* Numeral 3 */ + {0xff,0xff,0xf3,0xf3,0xf3,0xf3,0x33,0x03,0xc3,0xff,0xff,0xff, + 0xff,0xff,0xff,0xff,0xf3,0xf0,0xf0,0x03,0x0f,0xff,0xff,0xff, + 0xff,0xff,0xf3,0xc3,0xcf,0xcf,0xcf,0xc0,0xf0,0xff,0xff,0xff + }, + /* Numeral 4 */ + {0xff,0xff,0xff,0xff,0x3f,0x0f,0x03,0x03,0xff,0xff,0xff,0xff, + 0xff,0xff,0x03,0x00,0x3c,0x3f,0x00,0x00,0x3f,0xff,0xff,0xff, + 0xff,0xff,0xff,0xff,0xff,0xff,0xc0,0xc0,0xff,0xff,0xff,0xff + }, + /* Numeral 5 */ + {0xff,0xff,0x03,0x03,0xf3,0xf3,0xf3,0xf3,0xf3,0xff,0xff,0xff, + 0xff,0xff,0xf0,0xf0,0xf0,0xfc,0xfc,0x00,0x03,0xff,0xff,0xff, + 0xff,0xff,0xf3,0xc3,0xcf,0xcf,0xcf,0xc0,0xf0,0xff,0xff,0xff + }, + /* Numeral 6 */ + {0xff,0xff,0x3f,0x0f,0xc3,0xf3,0xf3,0xf3,0xff,0xff,0xff,0xff, + 0xff,0xff,0x00,0x00,0xc3,0xf3,0xf3,0x03,0x0f,0xff,0xff,0xff, + 0xff,0xff,0xf0,0xc0,0xc3,0xcf,0xcf,0xc0,0xf0,0xff,0xff,0xff + }, + /* Numeral 7 */ + {0xff,0xff,0xf3,0xf3,0xf3,0xf3,0xf3,0x03,0x03,0xff,0xff,0xff, + 0xff,0xff,0xff,0xff,0x3f,0x03,0xc0,0xfc,0xff,0xff,0xff,0xff, + 0xff,0xff,0xff,0xff,0xc0,0xc0,0xff,0xff,0xff,0xff,0xff,0xff + }, + /* Numeral 8 */ + {0xff,0xff,0x0f,0x03,0xf3,0xf3,0xf3,0x03,0x0f,0xff,0xff,0xff, + 0xff,0xff,0x0c,0x00,0xf3,0xf3,0xf3,0x00,0x0c,0xff,0xff,0xff, + 0xff,0xff,0xf0,0xc0,0xcf,0xcf,0xcf,0xc0,0xf0,0xff,0xff,0xff + }, + /* Numeral 9 */ + {0xff,0xff,0x0f,0x03,0xf3,0xf3,0xc3,0x03,0x0f,0xff,0xff,0xff, + 0xff,0xff,0xf0,0xc0,0xcf,0xcf,0xc3,0x00,0x00,0xff,0xff,0xff, + 0xff,0xff,0xff,0xcf,0xcf,0xcf,0xc3,0xf0,0xfc,0xff,0xff,0xff + }, +}; + +#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) +#define YOFS ((LCD_HEIGHT-BOARD_HEIGHT)/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 }; + +static unsigned char num[10][8]= { + /* Blank */ + {0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00}, + /* Numeral 1 */ + {0x00,0x00,0x00,0x22,0x3e,0x20,0x00,0x00}, + /* Numeral 2 */ + {0x00,0x00,0x24,0x32,0x2a,0x24,0x00,0x00}, + /* Numeral 3 */ + {0x00,0x00,0x22,0x2a,0x2a,0x14,0x00,0x00}, + /* Numeral 4 */ + {0x00,0x00,0x0e,0x08,0x38,0x08,0x00,0x00}, + /* Numeral 5 */ + {0x00,0x00,0x2e,0x2a,0x2a,0x12,0x00,0x00}, + /* Numeral 6 */ + {0x00,0x00,0x1c,0x2a,0x2a,0x12,0x00,0x00}, + /* Numeral 7 */ + {0x00,0x00,0x22,0x12,0x0a,0x06,0x00,0x00}, + /* Numeral 8 */ + {0x00,0x00,0x14,0x2a,0x2a,0x14,0x00,0x00}, + /* Numeral 9 */ + {0x00,0x00,0x24,0x2a,0x2a,0x1c,0x00,0x00}, + }; + +/* TODO: How do I differentiate between starting and user numbers? */ + +static unsigned char num_start[10][8]= { + /* Blank */ + {0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00}, + /* Numeral 1 */ + {0x00,0x00,0x00,0x22,0x3e,0x20,0x00,0x00}, + /* Numeral 2 */ + {0x00,0x00,0x24,0x32,0x2a,0x24,0x00,0x00}, + /* Numeral 3 */ + {0x00,0x00,0x22,0x2a,0x2a,0x14,0x00,0x00}, + /* Numeral 4 */ + {0x00,0x00,0x0e,0x08,0x38,0x08,0x00,0x00}, + /* Numeral 5 */ + {0x00,0x00,0x2e,0x2a,0x2a,0x12,0x00,0x00}, + /* Numeral 6 */ + {0x00,0x00,0x1c,0x2a,0x2a,0x12,0x00,0x00}, + /* Numeral 7 */ + {0x00,0x00,0x22,0x12,0x0a,0x06,0x00,0x00}, + /* Numeral 8 */ + {0x00,0x00,0x14,0x2a,0x2a,0x14,0x00,0x00}, + /* Numeral 9 */ + {0x00,0x00,0x24,0x2a,0x2a,0x1c,0x00,0x00}, +}; + +static unsigned char num_inverse[10][8]= { + /* Numeral 0 */ + {0x3f,0x3f,0x3f,0x3f,0x3f,0x3f,0x3f,0x3f}, + /* Numeral 1 */ + {0x3f,0x3f,0x3f,0x1d,0x01,0x1f,0x3f,0x3f}, + /* Numeral 2 */ + {0x3f,0x3f,0x1b,0x0d,0x15,0x1b,0x3f,0x3f}, + /* Numeral 3 */ + {0x3f,0x3f,0x1d,0x15,0x15,0x2b,0x3f,0x3f}, + /* Numeral 4 */ + {0x3f,0x3f,0x31,0x37,0x07,0x37,0x3f,0x3f}, + /* Numeral 5 */ + {0x3f,0x3f,0x11,0x15,0x15,0x2d,0x3f,0x3f}, + /* Numeral 6 */ + {0x3f,0x3f,0x23,0x15,0x15,0x2d,0x3f,0x3f}, + /* Numeral 7 */ + {0x3f,0x3f,0x1d,0x2d,0x35,0x39,0x3f,0x3f}, + /* Numeral 8 */ + {0x3f,0x3f,0x2b,0x15,0x15,0x2b,0x3f,0x3f}, + /* Numeral 9 */ + {0x3f,0x3f,0x1b,0x15,0x15,0x23,0x3f,0x3f}, +}; +#elif + #error SUDOKU: Unsupported LCD size +#endif + +#if LCD_DEPTH > 1 +#if HAVE_LCD_COLOR +#define LIGHT_GRAY ((struct rgb){2*LCD_MAX_RED/3, 2*LCD_MAX_GREEN/3, 2*LCD_MAX_BLUE/3}) +#define DARK_GRAY ((struct rgb){LCD_MAX_RED/3, LCD_MAX_GREEN/3, LCD_MAX_BLUE/3}) +#else +#define LIGHT_GRAY (2*LCD_MAX_LEVEL/3) +#define DARK_GRAY (LCD_MAX_LEVEL/3) +#endif +#endif + +/* here is a global api struct pointer. while not strictly necessary, + it's nice not to have to pass the api pointer in all function calls + in the plugin */ +static struct plugin_api* rb; + +struct sudoku_state_t { + char* filename; /* Filename */ + 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 */ + int x,y; /* Cursor position */ +}; + +/****** 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 */ +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 ret; +} + + +void clear_state(struct sudoku_state_t* state) +{ + int r,c; + + for (r=0;r<9;r++) { + for (c=0;c<9;c++) { + state->startboard[r][c]='0'; + state->currentboard[r][c]='0'; + } + } + + state->x=0; + state->y=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) { + rb->splash(HZ*2, true, "Can not open"); + LOGF("Invalid sudoku file: %s\n",filename); + return(false); + } + + state->filename=filename; + n=rb->read(fd,buf,300); + if (n <= 0) { + return(false); + } + rb->close(fd); + + clear_state(state); + + r=0; + c=0; + i=0; + while ((i < n) && (r < 9)) { + switch (buf[i]){ + case ' ': case '\t': + valid=1; + break; + 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[]="...|...|...\r\n"; + char sep[]="-----------\r\n"; + + if (state->filename==NULL) { + 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)-1); + if ((r==2) || (r==5)) { + rb->write(fd,sep,sizeof(sep)-1); + } + } + /* 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(num_inverse[state->currentboard[r][c]-'0'], + XOFS+cellxpos[c],YOFS+cellypos[r],CELL_WIDTH,CELL_HEIGHT); + } else { + if (state->startboard[r][c]!='0') { + rb->lcd_bitmap(num_start[state->startboard[r][c]-'0'], + XOFS+cellxpos[c],YOFS+cellypos[r],CELL_WIDTH,CELL_HEIGHT); + } else { + rb->lcd_bitmap(num[state->currentboard[r][c]-'0'], + 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==128) + /* 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) + 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 + + /* 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(num_inverse[state->currentboard[r][c]-'0'], + XOFS+cellxpos[c],YOFS+cellypos[r],CELL_WIDTH,CELL_HEIGHT); + } else { + if (state->startboard[r][c]!='0') { + rb->lcd_bitmap(num_start[state->startboard[r][c]-'0'], + XOFS+cellxpos[c],YOFS+cellypos[r],CELL_WIDTH,CELL_HEIGHT); + } else { + rb->lcd_bitmap(num[state->currentboard[r][c]-'0'], + 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; +} + +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 }, + }; + + 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; + + 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; + long ticks; + struct sudoku_state_t state; + + /* plugin init */ + TEST_PLUGIN_API(api); + rb = api; + /* end of plugin init */ + + if (parameter==NULL) { + return(PLUGIN_ERROR); + } 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 */ + case SUDOKU_BUTTON_TOGGLE | BUTTON_REPEAT: + /* Slow down the repeat speed to 1/3 second */ + if ((*rb->current_tick-ticks) < (HZ/3)) { + break; + } + + case SUDOKU_BUTTON_TOGGLE: + /* Increment digit */ + ticks=*rb->current_tick; + if (state.startboard[state.y][state.x]=='0') { + if (state.currentboard[state.y][state.x]=='0') { + state.currentboard[state.y][state.x]='1'; + } else 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 BUTTON_UP: + case (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 BUTTON_DOWN: + case (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: + /* 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 (sudoku_menu(&state)) { + return PLUGIN_USB_CONNECTED; + } + } + break; + + default: + if (rb->default_event_handler(button) == SYS_USB_CONNECTED) { + /* Quit if USB has been connected */ + return PLUGIN_USB_CONNECTED; + } + break; + } + + display_board(&state); + } + + return PLUGIN_OK; +} + +#endif diff --git a/apps/plugins/viewers.config b/apps/plugins/viewers.config index ddb80cd06a..717f203662 100644 --- a/apps/plugins/viewers.config +++ b/apps/plugins/viewers.config @@ -20,5 +20,6 @@ m3u,iriverify.rock,00 00 00 00 00 00 mpc,mpc2wav.rock, 00 00 00 00 00 00 mid,midi2wav.rock, 20 70 70 3F 00 00 rsp,searchengine.rock, 0e 11 11 31 7e 60 +ss,sudoku.rock, 55 55 55 55 55 55 wav,wav2wv.rock, 00 00 00 00 00 00 -- cgit v1.2.3