summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--Makefile6
-rw-r--r--cell.h13
-rw-r--r--debug.h15
-rw-r--r--display.h5
-rw-r--r--solve.c118
-rw-r--r--update.c34
-rw-r--r--update.h8
7 files changed, 146 insertions, 53 deletions
diff --git a/Makefile b/Makefile
index 09fc878..07b5fea 100644
--- a/Makefile
+++ b/Makefile
@@ -2,7 +2,11 @@ CFLAGS += -Werror -Wall
all: solve
-solve: display.o
+solve: display.o update.o cell.h
+
+display.o: display.c cell.h display.h
+
+update.o: update.c cell.h display.h
clean:
rm -f *.o solve
diff --git a/cell.h b/cell.h
index 76ecd90..fc5f467 100644
--- a/cell.h
+++ b/cell.h
@@ -1,7 +1,16 @@
+#ifndef SUDOKU_CELL_H
+#define SUDOKU_CELL_H
+
+/* Description of a single cell on a sudoku board */
struct cell
{
+ /* Sovled value of this cell */
char val;
- char not[9];
-} cell;
+ /* Array used to determine which values this cell can NOT be.
+ * A non-zero value at index N indicates that this cell cannot have the
+ * value N + 1 */
+ char not[9];
+};
+#endif /* SUDOKU_CELL_H */
diff --git a/debug.h b/debug.h
new file mode 100644
index 0000000..df0fcba
--- /dev/null
+++ b/debug.h
@@ -0,0 +1,15 @@
+#ifndef SUDOKU_DEBUG_H
+#define SUDOKU_DEBUG_H
+
+#include <stdio.h>
+
+#define NAME_CELL(x,y) ("ABCDEFGHI"[(x)]), ("123456789"[(y)])
+
+//#define DEBUG
+#ifdef DEBUG
+# define DEBUG_LOG(args...) printf(args)
+#else
+# define DEBUG_LOG(...)
+#endif
+
+#endif /* SUDOKU_DEBUG_H */
diff --git a/display.h b/display.h
index b3b5a3d..e7cecc2 100644
--- a/display.h
+++ b/display.h
@@ -1 +1,6 @@
+#ifndef SUDOKU_DISPLAY_H
+#define SUDOKU_DISPLAY_H
+
void display(struct cell board[9][9]);
+
+#endif /* SUDOKU_DISPLAY_H */
diff --git a/solve.c b/solve.c
index 797837d..0a1cb69 100644
--- a/solve.c
+++ b/solve.c
@@ -1,59 +1,16 @@
#include <stdio.h>
#include <string.h>
+#include "debug.h"
+#include "update.h"
#include "cell.h"
#include "display.h"
-static const char row_letter_lookup[] = "ABCDEFGHI";
-static const char col_letter_lookup[] = "123456789";
-
-#define NAME_CELL(x,y) row_letter_lookup[x], col_letter_lookup[y]
-
-//#define DEBUG
-#ifdef DEBUG
-# define DEBUG_LOG(args...) printf(args)
-#else
-# define DEBUG_LOG(...)
-#endif
-
-
/*
- * FIXME rename
- * For each unsolved cell on the board, update its list of values that it
- * cannot be based on the solved cells in the same row or the same column
- * Does not attempt to solve cells
- */
-void update_not_row_col(struct cell (*b)[9][9])
-{
- int x = 0;
- int y = 0;
- int i = 0;
- int val = 0;
-
- for (y = 0; y < 9; y++)
- {
- for (x = 0; x < 9; x++)
- {
- val = (*b)[x][y].val;
- if (val != 0)
- {
- DEBUG_LOG("Update: (%d,%d) has value %d\n", x, y, val);
- for (i = 0; i < 9; i++)
- {
- (*b)[i][y].not[val - 1] = 1;
- (*b)[x][i].not[val - 1] = 1;
- }
- }
- }
- }
-}
-
-/*
- * FIXME rename
* For all unsolved cells on the board, solve them if they have been marked as
* impossible to be 8/9 values
*/
-int not_to_val_row_col(struct cell (*b)[9][9])
+int solve_row_col(struct cell (*b)[9][9])
{
int change_count = 0;
int x = 0;
@@ -242,11 +199,68 @@ int cells_fill_certainties(struct cell (*b)[9][9])
return change_count;
}
+/*
+ * Check if every cell on a board is filled.
+ * Returns -1 isf the board is not fully
+ * Returns 0 if the board is filled
+ */
+int board_is_filled(struct cell (*b)[9][9])
+{
+ int x = 0;
+ int y = 0;
+
+ for (x = 0; x < 9; x++) {
+ for (y = 0; y < 9; y++) {
+ if ((*b)[x][y].val == 0) {
+ return -1;
+ }
+ }
+ }
+ return 0;
+}
+
+int board_rows_are_solved(struct cell (*b)[9][9])
+{
+ return -1;
+}
+
+int board_cols_are_solved(struct cell (*b)[9][9])
+{
+ return -1;
+}
+
+int board_3s_are_solved(struct cell (*b)[9][9])
+{
+ return -1;
+}
+
+/*
+ * Check if a board is solved.
+ * Returns -1 isf the board is unsolved
+ * Returns 0 if the board is solved
+ */
+int board_is_solved(struct cell (*b)[9][9])
+{
+ int ret = 0;
+ ret = board_is_filled(b);
+ if (ret)
+ return ret;
+
+ ret = board_rows_are_solved(b);
+ if (ret)
+ return ret;
+
+ ret = board_cols_are_solved(b);
+ if (ret)
+ return ret;
+
+ ret = board_3s_are_solved(b);
+
+ return ret;
+}
int main(int argc, char **argv)
{
-// int x = 0;
-// int y = 0;
struct cell board[9][9];
memset(board, 0, sizeof(board));
@@ -351,13 +365,17 @@ int main(int argc, char **argv)
change_count = 0;
update_not_row_col(&board);
change_count += not_to_val_cell(&board);
- change_count += not_to_val_row_col(&board);
+ change_count += solve_row_col(&board);
change_count += cells_fill_certainties(&board);
total_changes += change_count;
// display(board);
}
- printf("Solution (%d changes)\n", total_changes);
+ if (board_is_solved(&board) < 0) {
+ printf("Could not solve the board! Here is the closest (%d changes)\n", total_changes);
+ } else {
+ printf("Solution (%d changes)\n", total_changes);
+ }
display(board);
}
diff --git a/update.c b/update.c
new file mode 100644
index 0000000..57c5dda
--- /dev/null
+++ b/update.c
@@ -0,0 +1,34 @@
+#include "cell.h"
+#include "debug.h"
+
+/*
+ * update_not_row_col
+ *
+ * For each unsolved cell on the board, update its list of values that it
+ * cannot be based on the solved cells in the same row or the same column
+ * Does not attempt to solve cells
+ */
+void update_not_row_col(struct cell (*b)[9][9])
+{
+ int x = 0;
+ int y = 0;
+ int i = 0;
+ int val = 0;
+
+ for (y = 0; y < 9; y++)
+ {
+ for (x = 0; x < 9; x++)
+ {
+ val = (*b)[x][y].val;
+ if (val != 0)
+ {
+ DEBUG_LOG("Update: (%d,%d) has value %d\n", x, y, val);
+ for (i = 0; i < 9; i++)
+ {
+ (*b)[i][y].not[val - 1] = 1;
+ (*b)[x][i].not[val - 1] = 1;
+ }
+ }
+ }
+ }
+}
diff --git a/update.h b/update.h
new file mode 100644
index 0000000..8bd67b6
--- /dev/null
+++ b/update.h
@@ -0,0 +1,8 @@
+#ifndef SUDOKU_UPDATE_H
+#define SUDOKU_UPDATE_H
+
+#include "cell.h"
+
+void update_not_row_col(struct cell (*)[9][9]);
+
+#endif /* SUDOKU_UPDATE_H */