Add a Sudoku game

6 files changed, 727 insertions, 3 deletions

diff --git a/apps/system/Kconfig b/apps/system/Kconfig
index ed16af860..d2434afab 100644
--- a/apps/system/Kconfig
+++ b/apps/system/Kconfig
@@ -63,6 +63,10 @@ menu "SD Card"
 source "$APPSDIR/system/sdcard/Kconfig"
 endmenu
 
+menu "Sudoku"
+source "$APPSDIR/system/sudoku/Kconfig"
+endmenu
+
 menu "Sysinfo"
 source "$APPSDIR/system/sysinfo/Kconfig"
 endmenu
diff --git a/apps/system/Make.defs b/apps/system/Make.defs
index bdfde4503..125a2ffec 100644
--- a/apps/system/Make.defs
+++ b/apps/system/Make.defs
@@ -98,6 +98,10 @@ ifeq ($(CONFIG_SYSTEM_SDCARD),y)
 CONFIGURED_APPS += system/sdcard
 endif
 
+ifeq ($(CONFIG_SYSTEM_SUDOKU),y)
+CONFIGURED_APPS += system/sudoku
+endif
+
 ifeq ($(CONFIG_SYSTEM_SYSINFO),y)
 CONFIGURED_APPS += system/sysinfo
 endif
diff --git a/apps/system/Makefile b/apps/system/Makefile
index ed7b64dff..f5d35bfc6 100644
--- a/apps/system/Makefile
+++ b/apps/system/Makefile
@@ -38,9 +38,8 @@
 # Sub-directories containing system task
 
 SUBDIRS  = cdcacm cle composite flash_eraseall free i2c hex2bin inifile
-SUBDIRS += install nxplayer poweroff ramtest ramtron readline sdcard
-SUBDIRS += stackmonitor sysinfo usbmonitor usbmsc vi zmodem
-SUBDIRS += mdio
+SUBDIRS += install mdio nxplayer poweroff ramtest ramtron readline sdcard
+SUBDIRS += stackmonitor sudoku sysinfo usbmonitor usbmsc vi zmodem
 
 # Create the list of installed runtime modules (INSTALLED_DIRS)
 
diff --git a/apps/system/sudoku/Kconfig b/apps/system/sudoku/Kconfig
new file mode 100644
index 000000000..cdb28f4f3
--- /dev/null
+++ b/apps/system/sudoku/Kconfig
@@ -0,0 +1,27 @@
+#
+# For a description of the syntax of this configuration file,
+# see misc/tools/kconfig-language.txt.
+#
+
+config SYSTEM_SUDOKU
+	bool "Sudoku"
+	default n
+	select SYSTEM_READLINE
+	---help---
+		Enable the sudoku game.
+
+if SYSTEM_SUDOKU
+
+config SYSTEM_SUDOKU_STACKSIZE
+	int "Sudoku stack size"
+	default 1536
+	---help---
+		The size of stack allocated for the Sudoku task.
+
+config SYSTEM_SUDOKU_PRIORITY
+	int "Sudoku priority"
+	default 100
+	---help---
+		The priority of the Sudoku task.
+
+endif
diff --git a/apps/system/sudoku/Makefile b/apps/system/sudoku/Makefile
new file mode 100644
index 000000000..c0500f371
--- /dev/null
+++ b/apps/system/sudoku/Makefile
@@ -0,0 +1,117 @@
+############################################################################
+# apps/system/sudoku/Makefile
+#
+#   Copyright (C) 2014 Gregory Nutt. All rights reserved.
+#   Author: Gregory Nutt <gnutt@nuttx.org>
+#
+# Redistribution and use in source and binary forms, with or without
+# modification, are permitted provided that the following conditions
+# are met:
+#
+# 1. Redistributions of source code must retain the above copyright
+#    notice, this list of conditions and the following disclaimer.
+# 2. Redistributions in binary form must reproduce the above copyright
+#    notice, this list of conditions and the following disclaimer in
+#    the documentation and/or other materials provided with the
+#    distribution.
+# 3. Neither the name NuttX nor the names of its contributors may be
+#    used to endorse or promote products derived from this software
+#    without specific prior written permission.
+#
+# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+# FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+# COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+# INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+# BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
+# OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
+# AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+# LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+# ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+# POSSIBILITY OF SUCH DAMAGE.
+#
+############################################################################
+
+-include $(TOPDIR)/.config
+-include $(TOPDIR)/Make.defs
+include $(APPDIR)/Make.defs
+
+ifeq ($(WINTOOL),y)
+INCDIROPT = -w
+endif
+
+# Sudoku Application
+
+CONFIG_SYSTEM_SUDOKU_STACKSIZE ?= 1536
+CONFIG_SYSTEM_SUDOKU_PRIORITY ?= 100
+
+STACKSIZE = $(CONFIG_SYSTEM_SUDOKU_STACKSIZE)
+PRIORITY = $(CONFIG_SYSTEM_SUDOKU_PRIORITY)
+
+ASRCS =
+CSRCS = sudoku.c
+
+AOBJS = $(ASRCS:.S=$(OBJEXT))
+COBJS = $(CSRCS:.c=$(OBJEXT))
+
+SRCS = $(ASRCS) $(CSRCS)
+OBJS = $(AOBJS) $(COBJS)
+
+ifeq ($(CONFIG_WINDOWS_NATIVE),y)
+  BIN = ..\..\libapps$(LIBEXT)
+else
+ifeq ($(WINTOOL),y)
+  BIN = ..\\..\\libapps$(LIBEXT)
+else
+  BIN = ../../libapps$(LIBEXT)
+endif
+endif
+
+ROOTDEPPATH = --dep-path .
+
+# Common build
+
+VPATH =
+
+all: .built
+.PHONY: context depend clean distclean
+
+$(AOBJS): %$(OBJEXT): %.S
+	$(call ASSEMBLE, $<, $@)
+
+$(COBJS): %$(OBJEXT): %.c
+	$(call COMPILE, $<, $@)
+
+.built: $(OBJS)
+	$(call ARCHIVE, $(BIN), $(OBJS))
+	$(Q) touch .built
+
+# Register application
+
+ifeq ($(CONFIG_NSH_BUILTIN_APPS),y)
+$(BUILTIN_REGISTRY)$(DELIM)sudoku.bdat: $(DEPCONFIG) Makefile
+	$(call REGISTER,"sudoku",$(PRIORITY),$(STACKSIZE),sudoku_main)
+
+context: $(BUILTIN_REGISTRY)$(DELIM)sudoku.bdat
+else
+context:
+endif
+
+# Create dependencies
+
+.depend: Makefile $(SRCS)
+	$(Q) $(MKDEP) $(ROOTDEPPATH) "$(CC)" -- $(CFLAGS) -- $(SRCS) >Make.dep
+	$(Q) touch $@
+
+depend: .depend
+
+clean:
+	$(call DELFILE, .built)
+	$(call CLEAN)
+
+distclean: clean
+	$(call DELFILE, Make.dep)
+	$(call DELFILE, .depend)
+
+-include Make.dep
diff --git a/apps/system/sudoku/sudoku.c b/apps/system/sudoku/sudoku.c
new file mode 100755
index 000000000..80fbfbc82
--- /dev/null
+++ b/apps/system/sudoku/sudoku.c
@@ -0,0 +1,573 @@
+/****************************************************************************
+ * apps/system/sudoku/sudoku.c
+ *
+ *   Copyright (C) 2014 Gregory Nutt. All rights reserved.
+ *   Author: Gregory Nutt <gnutt@nuttx.org>
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in
+ *    the documentation and/or other materials provided with the
+ *    distribution.
+ * 3. Neither the name NuttX nor the names of its contributors may be
+ *    used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
+ * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
+ * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ ****************************************************************************/
+
+/****************************************************************************
+ * Included Files
+ ****************************************************************************/
+
+#include <stdint.h>
+#include <stdio.h>
+#include <string.h>
+
+#include <apps/readline.h>
+
+/****************************************************************************
+ * Pre-processor Definitions
+ ****************************************************************************/
+
+#define NHISTORY 16
+
+/****************************************************************************
+ * Private Types
+ ****************************************************************************/
+
+struct sudoku_s
+{
+  uint16_t canbe;
+  uint16_t is;
+};
+typedef struct sudoku_s sudoku_t[81];
+
+/****************************************************************************
+ * Private Data
+ ****************************************************************************/
+
+static sudoku_t history[NHISTORY];
+static sudoku_t working;
+static int first;
+static int last;
+static int current;
+
+static const char *r1[8] =
+  {"   ", "1  ", " 2 ", "12 ", "  3", "1 3", " 23", "123" };
+static const char *r2[8] =
+  {"   ", "4  ", " 5 ", "45 ", "  6", "4 6", " 56", "456" };
+static const char *r3[8] =
+  {"   ", "7  ", " 8 ", "78 ", "  9", "7 9", " 89", "789" };
+static char line[256];
+static int nis = 0;
+
+/****************************************************************************
+ * Private Functions
+ ****************************************************************************/
+
+static inline void init_array(void)
+{
+  int i;
+
+  first = 0;
+  last = 0;
+  current = 0;
+
+  for (i = 0; i < 81; i++)
+    {
+      working[i].canbe = 0x1ff;
+      working[i].is    = 0x000;
+    }
+}
+
+static inline void push(void)
+{
+  int next = current + 1;
+  if (next >= NHISTORY) next = 0;
+
+  if (current == last)
+    {
+      last = next;
+    }
+
+  if (first == next)
+  {
+    if (++first >= NHISTORY) first = 0;
+  }
+
+  memcpy (history[current], working, sizeof(sudoku_t));
+  current = next;
+}
+
+static inline void undo(void)
+{
+  if (current == first)
+    {
+      printf("Cannot undo\n");
+    }
+  else
+    {
+      if (--current < 0) current = NHISTORY-1;
+      memcpy (working, history[current], sizeof(sudoku_t));
+    }
+}
+
+static inline void redo(void)
+{
+  if (current == last)
+    {
+      printf("Cannot redo\n");
+    }
+  else
+    {
+      if (++current >= NHISTORY) current = 0;
+      memcpy(working, history[current], sizeof(sudoku_t));
+    }
+}
+
+static inline void show_row(int row)
+{
+  printf("    |%3s|%3s|%3s| |%3s|%3s|%3s| |%3s|%3s|%3s|\n",
+         r1[working[9*row + 0].canbe & 0x007],
+         r1[working[9*row + 1].canbe & 0x007],
+         r1[working[9*row + 2].canbe & 0x007],
+         r1[working[9*row + 3].canbe & 0x007],
+         r1[working[9*row + 4].canbe & 0x007],
+         r1[working[9*row + 5].canbe & 0x007],
+         r1[working[9*row + 6].canbe & 0x007],
+         r1[working[9*row + 7].canbe & 0x007],
+         r1[working[9*row + 8].canbe & 0x007]);
+  printf(" %2d |%3s|%3s|%3s| |%3s|%3s|%3s| |%3s|%3s|%3s|\n", row + 1,
+         r2[(working[9*row + 0].canbe >> 3) & 0x007],
+         r2[(working[9*row + 1].canbe >> 3) & 0x007],
+         r2[(working[9*row + 2].canbe >> 3) & 0x007],
+         r2[(working[9*row + 3].canbe >> 3) & 0x007],
+         r2[(working[9*row + 4].canbe >> 3) & 0x007],
+         r2[(working[9*row + 5].canbe >> 3) & 0x007],
+         r2[(working[9*row + 6].canbe >> 3) & 0x007],
+         r2[(working[9*row + 7].canbe >> 3) & 0x007],
+         r2[(working[9*row + 8].canbe >> 3) & 0x007]);
+  printf("    |%3s|%3s|%3s| |%3s|%3s|%3s| |%3s|%3s|%3s|\n",
+         r3[(working[9*row + 0].canbe >> 6) & 0x007],
+         r3[(working[9*row + 1].canbe >> 6) & 0x007],
+         r3[(working[9*row + 2].canbe >> 6) & 0x007],
+         r3[(working[9*row + 3].canbe >> 6) & 0x007],
+         r3[(working[9*row + 4].canbe >> 6) & 0x007],
+         r3[(working[9*row + 5].canbe >> 6) & 0x007],
+         r3[(working[9*row + 6].canbe >> 6) & 0x007],
+         r3[(working[9*row + 7].canbe >> 6) & 0x007],
+         r3[(working[9*row + 8].canbe >> 6) & 0x007]);
+}
+
+static inline void show_array(void)
+{
+  int row;
+  int i;
+
+  printf("    +===+===+===+ +===+===+===+ +===+===+===+\n");
+  printf("    | 1 | 2 | 3 | | 4 | 5 | 6 | | 7 | 8 | 9 |\n");
+  printf("    +===+===+===+ +===+===+===+ +===+===+===+\n");
+
+  row = 0;
+  for (i = 0; i < 3; i++)
+    {
+      show_row(row++);
+      printf("    +---+---+---+ +---+---+---+ +---+---+---+\n");
+      show_row(row++);
+      printf("    +---+---+---+ +---+---+---+ +---+---+---+\n");
+      show_row(row++);
+      printf("    +===+===+===+ +===+===+===+ +===+===+===+\n");
+    }
+}
+
+static inline int is_unique(unsigned int val)
+{
+  switch (val)
+    {
+    case 0x001:
+    case 0x002:
+    case 0x004:
+    case 0x008:
+    case 0x010:
+    case 0x020:
+    case 0x040:
+    case 0x080:
+    case 0x100:
+      return 1;
+    default:
+      return 0;
+    }
+}
+
+static inline int impossible(void)
+{
+  int nchanges = 0;
+  unsigned int val;
+  int row1, col1;
+  int row2, col2;
+  int i, j;
+  int ndx1, ndx2;
+
+  for (row1 = 0; row1 < 9; row1++)
+    {
+      row2 = row1 / 3;
+      for (col1 = 0; col1 < 9; col1++)
+        {
+          col2 = col1 / 3;
+          ndx1 = row1*9 + col1;
+          val = working[ndx1].canbe;
+
+          for (i = 0; i < 9; i++)
+            {
+              ndx2 = i*9 + col1;
+              if (ndx1 != ndx2)
+                {
+                  val &= ~working[ndx2].is;
+                }
+            }
+
+          for (j = 0; j < 9; j++)
+            {
+              ndx2 = row1*9 + j;
+              if (ndx1 != ndx2)
+                {
+                  val &= ~working[ndx2].is;
+                }
+            }
+
+          for (i = 0; i < 3; i++)
+            {
+              for (j = 0; j < 3; j++)
+                {
+                  ndx2 = (row2*3 + i)*9 + (col2*3 + j);
+                  if (ndx1 != ndx2)
+                    {
+                      val &= ~working[ndx2].is;
+                    }
+                }
+            }
+
+          if (val == 0)
+            {
+              return -1;
+            }
+
+          if (val != working[ndx1].canbe)
+            {
+              nchanges++;
+              working[ndx1].canbe = val;
+
+              if (is_unique(val))
+                {
+                  working[ndx1].is = val;
+                }
+            }
+        }
+    }
+
+  return nchanges;
+}
+
+static inline int unique(void)
+{
+  int noccurences[9];
+  int lastndx[9];
+  int nchanges = 0;
+  unsigned int mask;
+  unsigned int val;
+  int row1, col1;
+  int row2, col2;
+  int ndx;
+  int i;
+
+  for (row1 = 0; row1 < 9; row1++)
+    {
+      for (i = 0; i < 9; i++)
+        {
+          noccurences[i] = 0;
+          lastndx[i] = -1;
+        }
+
+      for (i = 0; i < 9; i++)
+        {
+          mask = 1 << i;
+          for (col1 = 0; col1 < 9; col1++)
+            {
+              ndx = row1 * 9 + col1;
+              if (working[ndx].canbe & mask)
+                {
+                  noccurences[i]++;
+                  lastndx[i] = ndx;
+                }
+            }
+
+          for (i = 0; i < 9; i++)
+            {
+              if (noccurences[i] == 1)
+                {
+                  val = 1 << i;
+                  ndx = lastndx[i];
+                  if (working[ndx].is != val)
+                    {
+                      working[ndx].is = val;
+                      working[ndx].canbe = val;
+                      nchanges++;
+                    }
+                }
+            }
+        }
+    }
+
+  for (col1 = 0; col1 < 9; col1++)
+    {
+      for (i = 0; i < 9; i++)
+        {
+          noccurences[i] = 0;
+          lastndx[i] = -1;
+        }
+
+      for (i = 0; i < 9; i++)
+        {
+          mask = 1 << i;
+          for (row1 = 0; row1 < 9; row1++)
+            {
+              ndx = row1 * 9 + col1;
+              if (working[ndx].canbe & mask)
+                {
+                  noccurences[i]++;
+                  lastndx[i] = ndx;
+                }
+            }
+
+          for (i = 0; i < 9; i++)
+            {
+              if (noccurences[i] == 1)
+                {
+                  val = 1 << i;
+                  ndx = lastndx[i];
+                  if (working[ndx].is != val)
+                    {
+                      working[ndx].is = val;
+                      working[ndx].canbe = val;
+                      nchanges++;
+                    }
+                }
+            }
+        }
+    }
+
+  for (row2 = 0; row2 < 3; row2++)
+    {
+      for (col2 = 0; col2 < 3; col2++)
+        {
+          for (i = 0; i < 9; i++)
+            {
+              noccurences[i] = 0;
+              lastndx[i] = -1;
+            }
+
+          for (i = 0; i < 9; i++)
+            {
+              mask = 1 << i;
+              for ( row1 = 0; row1 < 3; row1++)
+                {
+                  for ( col1 = 0; col1 < 3; col1++)
+                    {
+                      ndx = (row2*3 + row1)*9 + (col2*3 + col1);
+                      if (working[ndx].canbe & mask)
+                        {
+                          noccurences[i]++;
+                          lastndx[i] = ndx;
+                        }
+                    }
+                }
+            }
+
+          for (i = 0; i < 9; i++)
+            {
+              if (noccurences[i] == 1)
+                {
+                  val = 1 << i;
+                  ndx = lastndx[i];
+                  if (working[ndx].is != val)
+                    {
+                      working[ndx].is = val;
+                      working[ndx].canbe = val;
+                      nchanges++;
+                    }
+                }
+            }
+        }
+    }
+
+  return nchanges;
+}
+
+static inline int getcell(int *pndx, int *pval)
+{
+  int row, col, ndx;
+  unsigned int val;
+  int i = 0;
+
+  while ((line[i] == ' ' || line[i] == '\t') && (line[i] != '\0') && (line[i] != '\n')) i++;
+
+  if (line[i] < '1' || line[i] > '9')
+    {
+      printf("Bad row: %c\n", line[i]);
+      return -1;
+    }
+  row = line[i++] -'0' - 1;
+
+  while ((line[i] == ' ' || line[i] == '\t') && (line[i] != '\0') && (line[i] != '\n')) i++;
+
+  if (line[i] < '1' || line[i] > '9')
+    {
+      printf("Bad col: %c\n", line[i]);
+      return -1;
+    }
+  col = line[i++] -'0' - 1;
+  ndx = row*9 + col;
+
+  while ((line[i] == ' ' || line[i] == '\t') && (line[i] != '\0') && (line[i] != '\n')) i++;
+
+  if (line[i] < '1' || line[i] > '9')
+    {
+      printf("Bad value: %c\n", line[i]);
+      return -1;
+    }
+
+  val = 1 << ((line[i] - '0') - 1);
+  if (( val & working[ndx].canbe) == 0)
+    {
+      printf("Impossible value: %c\n", line[i]);
+      return -1;
+    }
+
+  *pndx = ndx;
+  *pval = val;
+  return 0;
+}
+
+static inline int get_command(void)
+{
+  printf("%d of 81> ", nis);
+  fflush(stdout);
+  (void)readline(line, 256, stdin, stdout);
+
+  int i = 0;
+
+  while ((line[i] == ' ' || line[i] == '\t') && (line[i] != '\0') && (line[i] != '\n')) i++;
+
+  return line[i];
+}
+
+static inline void show_usage(void)
+{
+  printf("ABC - Set cell[A,B] to C where A,B, and C are in {1..9}\n");
+  printf("U   - Undo last cell assignment\n");
+  printf("R   - Redo last cell assignment\n");
+  printf("H|? - Show this message\n");
+  printf("Q   - Quit\n");
+}
+
+static inline void count_cells(void)
+{
+  int i;
+
+  nis = 0;
+  for (i = 0; i < 81; i++) if (working[i].is > 0) nis++;
+}
+
+/****************************************************************************
+ * Private Functions
+ ****************************************************************************/
+
+int sudoku_main(int argc, char **argv, char **envp)
+{
+  int cmd;
+  int nchanged;
+  int val;
+  int ndx;
+
+  init_array();
+  for (;;)
+    {
+      count_cells();
+      show_array();
+      if (nis == 81)
+        {
+          printf("GAME OVER: 81 of 81 assigned\n");
+          return 0;
+        }
+      else
+        {
+          cmd = get_command();
+          switch (cmd)
+            {
+            case 'U':
+            case 'u':
+              undo();
+              break;
+
+            case 'R':
+            case 'r':
+              redo();
+              break;
+
+            case 'H':
+            case 'h':
+            case '?':
+              show_usage();
+              break;
+
+            case 'Q':
+            case 'q':
+              return 0;
+
+            default:
+              if (getcell(&ndx, &val) == 0)
+                {
+                  push();
+                  working[ndx].is    = val;
+                  working[ndx].canbe = val;
+                  for (;;)
+                    {
+                      nchanged = impossible();
+                      if (nchanged < 0)
+                        {
+                          printf("This move is not possible\n");
+                          undo();
+                          break;
+                        }
+                      else if (nchanged == 0)
+                        {
+                          nchanged = unique();
+                          if (nchanged == 0)
+                            {
+                              break;
+                            }
+                        }
+                    }
+                }
+            }
+        }
+    }
+}