diff options
author | Gregory Nutt <gnutt@nuttx.org> | 2014-08-11 19:27:48 -0600 |
---|---|---|
committer | Gregory Nutt <gnutt@nuttx.org> | 2014-08-11 19:27:48 -0600 |
commit | dd6bca4b13853bacfce798d176a123e72f765437 (patch) | |
tree | 51f8899203353c533652d2785745c520c0390448 /apps/system/sudoku/sudoku.c | |
parent | 78789700a2f4a7e6580b63e0ede824615f586456 (diff) | |
download | nuttx-dd6bca4b13853bacfce798d176a123e72f765437.tar.gz nuttx-dd6bca4b13853bacfce798d176a123e72f765437.tar.bz2 nuttx-dd6bca4b13853bacfce798d176a123e72f765437.zip |
Add a Sudoku game
Diffstat (limited to 'apps/system/sudoku/sudoku.c')
-rwxr-xr-x | apps/system/sudoku/sudoku.c | 573 |
1 files changed, 573 insertions, 0 deletions
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; + } + } + } + } + } + } + } +} |