c problem 96 (haskell try)

1 files changed, 169 insertions, 0 deletions

diff --git a/c/096-su_doku.c b/c/096-su_doku.c
new file mode 100644
index 0000000..6a958fa
--- /dev/null
+++ b/c/096-su_doku.c
@@ -0,0 +1,169 @@
+/*
+ *
+ * Su Doku (Japanese meaning number place) is the name given to a popular puzzle concept.
+ * Its origin is unclear, but credit must be attributed to Leonhard Euler who invented a
+ * similar, and much more difficult, puzzle idea called Latin Squares. The objective of
+ * Su Doku puzzles, however, is to replace the blanks (or zeros) in a 9 by 9 grid in such
+ * that each row, column, and 3 by 3 box contains each of the digits 1 to 9. Below is an
+ * example of a typical starting puzzle grid and its solution grid.
+ *
+ * https://projecteuler.net/problem=96
+ *
+ * A well constructed Su Doku puzzle has a unique solution and can be solved by logic,
+ * although it may be necessary to employ "guess and test" methods in order to eliminate
+ * options (there is much contested opinion over this). The complexity of the search
+ * determines the difficulty of the puzzle; the example above is considered easy because
+ * it can be solved by straight forward direct deduction.
+ *
+ * The 6K text file, sudoku.txt (right click and 'Save Link/Target As...'), contains
+ * fifty different Su Doku puzzles ranging in difficulty, but all with unique solutions
+ * (the first puzzle in the file is the example above).
+ *
+ * By solving all fifty puzzles find the sum of the 3-digit numbers found in the top left
+ * corner of each solution grid; for example, 483 is the 3-digit number found in the top
+ */
+
+#include <stdio.h>
+#include <stdbool.h>
+
+bool solve(int square[9][9]);
+bool find_next_unassigned(int square[9][9], int *row, int *col);
+bool is_alone(int square[9][9], int value, int row, int col);
+void parse_data(FILE *f, int sudokus[50][9][9]);
+
+int main(void)
+{
+    /* int sudoku[9][9] = { */
+    /*     {0, 0, 3, 0, 2, 0, 6, 0, 0}, */
+    /*     {9, 0, 0, 3, 0, 5, 0, 0, 1}, */
+    /*     {0, 0, 1, 8, 0, 6, 4, 0, 0}, */
+    /*     {0, 0, 8, 1, 0, 2, 9, 0, 0}, */
+    /*     {7, 0, 0, 0, 0, 0, 0, 0, 8}, */
+    /*     {0, 0, 6, 7, 0, 8, 2, 0, 0}, */
+    /*     {0, 0, 2, 6, 0, 9, 5, 0, 0}, */
+    /*     {8, 0, 0, 2, 0, 3, 0, 0, 9}, */
+    /*     {0, 0, 5, 0, 1, 0, 3, 0, 0} */
+    /* }; */
+    /* for (int i = 0; i < 9; i++) */
+    /* { */
+    /*     for (int j = 0; j < 9; j++) */
+    /*         printf("%d ", sudoku[i][j]); */
+    /*     printf("\n"); */
+    /* } */
+    /* printf("%d\n", solve(sudoku)); */
+    /* for (int i = 0; i < 9; i++) */
+    /* { */
+    /*     for (int j = 0; j < 9; j++) */
+    /*         printf("%d ", sudoku[i][j]); */
+    /*     printf("\n"); */
+    /* } */
+    int sudokus[50][9][9];
+    char *filename = "../data/096_sudoku.txt";
+    FILE *f = fopen(filename, "r");
+    if (f == NULL)
+    {
+        fprintf(stderr, "Error: cannot open %s", filename);
+        return 1;
+    }
+    parse_data(f, sudokus);
+    for (int i = 0; i < 50; i++)
+        printf("%d %d\n", i, solve(sudokus[i]));
+
+    for (int k = 0; k < 50; k++)
+    {
+        for (int i = 0; i < 9; i++)
+        {
+            for (int j = 0; j < 9; j++)
+                printf("%d ", sudokus[k][i][j]);
+            printf("\n");
+        }
+        printf("\n");
+    }
+    int total = 0;
+    for (int i = 0; i < 50; i++)
+        total += 100 * sudokus[i][0][0] + 10 * sudokus[i][0][1] + sudokus[i][0][2];
+    printf("total = %d", total);
+    fclose(f);
+    return 0;
+}
+
+bool solve(int square[9][9])
+{
+	int row, col;
+
+	if (!find_next_unassigned(square, &row, &col))
+		return true;
+    for (int i = 1; i <= 9; i++)
+	{
+		if (!is_alone(square, i, row, col))
+			continue ;
+		square[row][col] = i;
+		if (solve(square))
+			return true;
+		square[row][col] = 0;
+	}
+	return false;
+}
+
+bool find_next_unassigned(int square[9][9], int *row, int *col)
+{
+    for (*row = 0; *row < 9; (*row)++)
+    {
+        for (*col = 0; *col < 9; (*col)++)
+			if (square[*row][*col] == 0)
+				return true;
+    }
+	return false;
+}
+
+bool is_alone(int square[9][9], int value, int row, int col)
+{
+    int i, j;
+    for (i = 0; i < 9; i++)
+		if (i != col && square[row][i] == value)
+			return false;
+    for (i = 0; i < 9; i++)
+		if (i != row && square[i][col] == value)
+			return false;
+    int sub_i = row / 3;
+    int sub_j = col / 3;
+    for (i = 0; i < 3; i++)
+        for (j = 0; j < 3; j++)
+            if (square[sub_i * 3 + i][sub_j * 3 + j] == value)
+                return false;
+	return true;
+}
+
+void parse_data(FILE *f, int sudokus[50][9][9])
+{
+    char c;
+    int sudoku_i = 0;
+    int i = 0;
+    int j = 0;
+    fseek(f, 8, SEEK_SET);
+    /* printf("%d\n", ftell(f)); */
+    while ((c = fgetc(f)) != EOF)
+    {
+        /* printf("%c\n", c); */
+        /* printf("i%d, j%d\n", i, j); */
+        /* if (i == 2) */
+        /*     break; */
+        if (c == '\n')
+        {
+            j = 0;
+            i++;
+        }
+        else if (c == 'G')
+        {
+            fseek(f, 7, SEEK_CUR);
+            sudoku_i++;
+            i = 0;
+            j = 0;
+        }
+        else
+        {
+            sudokus[sudoku_i][i][j] = c - '0';
+            j++;
+        }
+    }
+}