path: root/apps/plugins/sudoku.c

/***************************************************************************
 *             __________               __   ___.
 *   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_ALTTOGGLE BUTTON_ON
#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 <shackell@cs.york.ac.uk>

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(&copy,sud,sizeof(Sudoku));
  sudoku_set(&copy, x, y, num, false);
  stats->numTries += 1;
  if (solve(&copy, stats, options)){
    if (!options->allSolutions && stats->solutionFound){
      rb->memcpy(sud,&copy,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;

  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;c<XOFS+BOARD_WIDTH;c+=2) {
        rb->lcd_drawpixel(c,YOFS+cellypos[r]-1);
      }
      for (c=YOFS;c<YOFS+BOARD_HEIGHT;c+=2) {
        rb->lcd_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;r<r1+3;r++) {
    for (c=c1;c<c1+3;c++) {
      cell=state->currentboard[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 */
#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:
        /* 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