From 16a2da0f217aa4f2da4b084014e4da731740e0df Mon Sep 17 00:00:00 2001 From: David Phillips Date: Sat, 16 Mar 2019 20:33:08 +1300 Subject: Add simple solver testing framework --- Makefile | 14 +++++++-- run_tests.sh | 33 ++++++++++++++++++++ solve.c | 50 ----------------------------- solve.h | 63 +++++++++++++++++++++++++++++++++++++ solver.c | 65 ++++++++++++++++++++++++++++++++++++++ test-solver.c | 78 ++++++++++++++++++++++++++++++++++++++++++++++ test/001-easy/expected.sku | 9 ++++++ test/001-easy/in.sku | 10 ++++++ test/xfails | 0 9 files changed, 269 insertions(+), 53 deletions(-) create mode 100755 run_tests.sh create mode 100644 solve.h create mode 100644 solver.c create mode 100644 test-solver.c create mode 100644 test/001-easy/expected.sku create mode 100644 test/001-easy/in.sku create mode 100644 test/xfails 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 +#include + +#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 +#include + +#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 -- cgit v1.1