Add simple solver testing framework

9 files changed, 269 insertions, 53 deletions

diff --git a/Makefile b/Makefile
index d5483ab..f8dc3da 100644
--- a/Makefile
+++ b/Makefile
@@ -1,12 +1,20 @@
 CFLAGS += -Werror -Wall
 
-all: solve
+all: solver
 
-solve: display.o update.o load.o cell.h load.h
+solver: solver.o load.o update.o display.o solve.o load.h
+
+test-solver: test-solver.o load.o update.o solve.o load.h
+
+solve.o: solve.c update.h cell.h
 
 display.o: display.c cell.h display.h
 
 update.o: update.c cell.h display.h
 
+.PHONY: test
+test: test-solver
+	- ./run_tests.sh
+
 clean:
-	rm -f *.o solve 
+	rm -f *.o solver test-solver
diff --git a/run_tests.sh b/run_tests.sh
new file mode 100755
index 0000000..2cff423
--- /dev/null
+++ b/run_tests.sh
@@ -0,0 +1,33 @@
+#!/bin/bash -e
+
+exit_code=0
+
+[ -z "$SOLVER" ] && SOLVER="$PWD/test-solver"
+XFAILS="$PWD/test/xfails"
+
+test_fail() {
+	t="$(basename $1)"
+	if grep -q "$t" "$XFAILS" ; then
+		echo -e "$t: "'[\e[34;1mXFAIL\e[0m]'
+	else
+		echo -e "$t: "'[\e[31;1mFAIL\e[0m]'
+	fi
+}
+
+test_pass() {
+	t="$(basename $1)"
+	echo -e "$t: "'[\e[32;1mPASS\e[0m]'
+}
+
+for t in test/*-* ; do
+	pushd "$t" >/dev/null
+	if ! "$SOLVER" >/dev/null ; then
+		test_fail "$t"
+		exit_code=1
+	else
+		test_pass "$t"
+	fi
+	popd >/dev/null
+done
+
+exit "$exit_code"
diff --git a/solve.c b/solve.c
index ff82351..7aae707 100644
--- a/solve.c
+++ b/solve.c
@@ -341,53 +341,3 @@ int board_is_solved(struct cell (*b)[9][9])
 
 	return ret;
 }
-
-int main(int argc, char **argv)
-{
-	struct cell board[9][9];
-	FILE *f = NULL;
-
-	memset(board, 0, sizeof(board));
-
-	if (argc != 2) {
-		printf("Syntax: %s puzzle_file\n", argv[0]);
-		return 1;
-	}
-
-	f = fopen(argv[1], "r");
-	if (!f) {
-		perror("fopen");
-		return 1;
-	}
-
-	if (load(f, &board) < 0) {
-		fclose(f);
-		return 1;
-	}
-
-	fclose(f);
-
-	display(board);
-
-	int i = 0;
-	int total_changes = 0;
-	int change_count = -1;
-	/* 9*9 is worst case */
-	for (i = 0; i < 9*9 && change_count; i++) {
-		change_count = 0;
-		update_not_row_col(&board);
-		change_count += not_to_val_cell(&board);
-		change_count += solve_row_col(&board);
-		change_count += cells_fill_certainties(&board);
-		total_changes += change_count;
-//		display(board);
-	}
-
-	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/solve.h b/solve.h
new file mode 100644
index 0000000..ea1d1ca
--- /dev/null
+++ b/solve.h
@@ -0,0 +1,63 @@
+#ifndef SUDOKU_SOLVE_H
+#define SUDOKU_SOLVE_H
+
+#include "cell.h"
+
+/*
+ * For all unsolved cells on the board, solve them if they have been marked as
+ * impossible to be 8/9 values
+ */
+int solve_row_col(struct cell (*b)[9][9]);
+
+/*
+ * FIXME rename - cell != cell
+ * For all unsolved cells on the board, solve them if they are the only place
+ * left in their local 3x3 (box) that a value missing from that box could fit
+ */
+int not_to_val_cell(struct cell (*b)[9][9]);
+
+
+/* For the numbers 1-9 not filled into a cell, fill in those which have only
+ * one place they can go */
+int cell_fill_certainties(struct cell (*b)[9][9], int bx, int by);
+
+int cells_fill_certainties(struct cell (*b)[9][9]);
+
+/*
+ * 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]);
+
+/*
+ * Check if all of the rows on are correctly solved on a board
+ * Returns 0 for all rows correctly solved
+ */
+int board_rows_are_solved(struct cell (*b)[9][9]);
+
+/*
+ * Check if all of the columns on are correctly solved on a board
+ * Returns 0 for all columns correctly solved
+ */
+int board_cols_are_solved(struct cell (*b)[9][9]);
+
+/*
+ * Check if one of the nine 3x3 boxes is correctly solved on a board
+ * Returns 0 for a correctly solved 3x3
+ */
+int board_box_is_solved(struct cell (*b)[9][9], int bx, int by);
+
+/*
+ * Check if all of the nine 3x3 boxes are correctly solved on a board
+ * Returns 0 for correctly solved boxes
+ */
+int board_boxes_are_solved(struct cell (*b)[9][9]);
+
+/*
+ * Check if a board is solved.
+ * Returns 0 if the board is solved correctly
+ */
+int board_is_solved(struct cell (*b)[9][9]);
+
+#endif /* SUDOKU_SOLVE_H */
diff --git a/solver.c b/solver.c
new file mode 100644
index 0000000..b6de45e
--- /dev/null
+++ b/solver.c
@@ -0,0 +1,65 @@
+#include <stdio.h>
+#include <string.h>
+
+#include "debug.h"
+#include "update.h"
+#include "cell.h"
+#include "solve.h"
+#include "display.h"
+#include "load.h"
+
+int solve(struct cell (*board)[9][9])
+{
+	int i = 0;
+	int total_changes = 0;
+	int change_count = -1;
+	/* 9*9 is worst case */
+	for (i = 0; i < 9*9 && change_count; i++) {
+		change_count = 0;
+		update_not_row_col(board);
+		change_count += not_to_val_cell(board);
+		change_count += solve_row_col(board);
+		change_count += cells_fill_certainties(board);
+		total_changes += change_count;
+//		display(board);
+	}
+	return total_changes;
+}
+
+int main(int argc, char **argv)
+{
+	int total_changes = 0;
+	struct cell board[9][9];
+	FILE *f = NULL;
+
+	memset(board, 0, sizeof(board));
+
+	if (argc != 2) {
+		printf("Syntax: %s puzzle_file\n", argv[0]);
+		return 1;
+	}
+
+	f = fopen(argv[1], "r");
+	if (!f) {
+		perror("fopen");
+		return 1;
+	}
+
+	if (load(f, &board) < 0) {
+		fclose(f);
+		return 1;
+	}
+
+	fclose(f);
+
+	display(board);
+	total_changes = solve(&board);
+
+	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/test-solver.c b/test-solver.c
new file mode 100644
index 0000000..4ea14a0
--- /dev/null
+++ b/test-solver.c
@@ -0,0 +1,78 @@
+#include <stdio.h>
+#include <string.h>
+
+#include "debug.h"
+#include "update.h"
+#include "cell.h"
+#include "solve.h"
+#include "display.h"
+#include "load.h"
+
+/* FIXME move to another TU */
+int boards_match(struct cell (*lb)[9][9], struct cell (*rb)[9][9])
+{
+	int x = 0;
+	int y = 0;
+
+	for (y = 0; y < 9; y++)
+		for (x = 0; x < 9; x++)
+			if ((*lb)[x][y].val != (*rb)[x][y].val)
+				return -1;
+
+	return 0;
+}
+
+/* FIXME move to another TU, dedup with solver.c */
+int solve(struct cell (*board)[9][9])
+{
+	int i = 0;
+	int total_changes = 0;
+	int change_count = -1;
+	/* 9*9 is worst case */
+	for (i = 0; i < 9*9 && change_count; i++) {
+		change_count = 0;
+		update_not_row_col(board);
+		change_count += not_to_val_cell(board);
+		change_count += solve_row_col(board);
+		change_count += cells_fill_certainties(board);
+		total_changes += change_count;
+	}
+	return total_changes;
+}
+
+int main(int argc, char **argv)
+{
+	struct cell working_board[9][9];
+	struct cell correct_board[9][9];
+	FILE *f = NULL;
+
+	memset(working_board, 0, sizeof(working_board));
+
+	if (!(f = fopen("./in.sku", "r"))) {
+		perror("fopen");
+		return 1;
+	}
+
+	if (load(f, &working_board) < 0) {
+		fclose(f);
+		return 1;
+	}
+
+	fclose(f);
+
+	solve(&working_board);
+
+	if (!(f = fopen("./expected.sku", "r"))) {
+		perror("fopen");
+		return 1;
+	}
+
+	if (load(f, &correct_board) < 0) {
+		fclose(f);
+		return 1;
+	}
+
+	fclose(f);
+
+	return boards_match(&working_board, &correct_board);
+}
diff --git a/test/001-easy/expected.sku b/test/001-easy/expected.sku
new file mode 100644
index 0000000..a193127
--- /dev/null
+++ b/test/001-easy/expected.sku
@@ -0,0 +1,9 @@
+8 6 1 |5 2 7 |3 4 9
+2 7 5 |4 9 3 |6 8 1
+9 4 3 |6 1 8 |5 7 2
+4 1 7 |2 3 6 |9 5 8
+3 5 9 |1 8 4 |2 6 7
+6 2 8 |9 7 5 |4 1 3
+7 8 6 |3 4 9 |1 2 5
+1 3 4 |7 5 2 |8 9 6
+5 9 2 |8 6 1 |7 3 4
diff --git a/test/001-easy/in.sku b/test/001-easy/in.sku
new file mode 100644
index 0000000..2145237
--- /dev/null
+++ b/test/001-easy/in.sku
@@ -0,0 +1,10 @@
+? 6 1 |5 ? ? |? ? 9
+? 7 5 |4 9 3 |6 ? ?
+9 ? ? |6 ? ? |? 7 ?
+4 ? ? |2 ? 6 |? ? ?
+3 ? 9 |? ? ? |2 ? 7
+? ? ? |9 ? 5 |? ? 3
+? 8 ? |? ? 9 |? ? 5
+? ? 4 |7 5 2 |8 9 ?
+5 ? ? |? ? 1 |7 3 ?
+
diff --git a/test/xfails b/test/xfails
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/xfails