From bee8748e469dbead45acb61fef24c3efcf56a6bb Mon Sep 17 00:00:00 2001 From: Timo Kokkonen Date: Sun, 24 Aug 2008 15:54:36 +0300 Subject: [PATCH] Initial commit --- .gitignore | 5 + Makefile | 20 +++ debug.h | 8 + main.cpp | 48 ++++++ sudoku.cpp | 473 +++++++++++++++++++++++++++++++++++++++++++++++++++++ sudoku.h | 39 +++++ 6 files changed, 593 insertions(+) create mode 100644 .gitignore create mode 100644 Makefile create mode 100644 debug.h create mode 100644 main.cpp create mode 100644 sudoku.cpp create mode 100644 sudoku.h diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..c0e1426 --- /dev/null +++ b/.gitignore @@ -0,0 +1,5 @@ +*.o +*.txt +.*.o.d +*~ +sudokusolver diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..81dbd2a --- /dev/null +++ b/Makefile @@ -0,0 +1,20 @@ +CC=g++ +LD=ld +CFLAGS=-Wall -O2 -g + +SUDOKUSOLVER_OBJS= main.o sudoku.o + +all: sudokusolver + +sudokusolver: $(SUDOKUSOLVER_OBJS) + $(CC) $(SUDOKUSOLVER_OBJS) -o sudokusolver + +.cpp.o: + $(CC) -MMD -MF .$@.d $(CFLAGS) -c $< -o $@ + +clean: + rm -rfv *~ *.o *.d sudokusolver + +.PHONY: all clean + +-include .*.d diff --git a/debug.h b/debug.h new file mode 100644 index 0000000..b737a25 --- /dev/null +++ b/debug.h @@ -0,0 +1,8 @@ +#ifndef DEBUG_H +#define DEBUG_H + +#include + +#define DPRINT std::cout << __FILE__ << ":" << __LINE__ << " " + +#endif diff --git a/main.cpp b/main.cpp new file mode 100644 index 0000000..ac9a8da --- /dev/null +++ b/main.cpp @@ -0,0 +1,48 @@ +#include + +#include "sudoku.h" +#include "debug.h" + +int main(int argc, char *argv[]) +{ + int row, i; + std::string line; + sudoku sudo; + std::vector results; + + if (argc > 1) { + if ((std::string)argv[1] == "-q") + verbose = 0; + } + + for (row = 0; row < 9; row++) { + std::getline(std::cin, line, '\n'); + + if(sudo.str_to_row(row, line)) { + std::cout << "Error reading line " << row << std::endl; + return 1; + } + } + + std::cout << "Done parsing.\n"; + +// int solved; +// sudo = sudo.solve(solved); + sudo.print(); + std::cout << "Solving this sudoku.\n\n"; + + results = sudo.solve_all(); + + std::cout << "Found " << results.size() << " solutions\n"; + + for (i = 0; i < (int)results.size(); i++) { + + std::cout << "\nSolution " << i + 1 << ", iteration depth: " + << results.at(i).recursion_depth << std::endl; + results.at(i).print(); + } + std::cout << "Had to guess " << guesses + << " times while solving this sudoku\n"; + + return 0; +} diff --git a/sudoku.cpp b/sudoku.cpp new file mode 100644 index 0000000..a1777e5 --- /dev/null +++ b/sudoku.cpp @@ -0,0 +1,473 @@ +#include +#include + +#include "sudoku.h" +#include "debug.h" + +#define EMPTY ' ' + +int guesses = 0; +int verbose = 1; + +sudoku::sudoku() +{ + int x,y; + + for (y = 0; y < 9; y++) + for (x = 0; x < 9; x++) + table[x][y] = EMPTY; + + recursion_depth = 0; +} + +sudoku::~sudoku() +{ +} + +static int check_validity(const int col, const int row) +{ + if (col < 0 || col >= 9) { + DPRINT << "Invalid column: " << col << std::endl; + return 0; + } + + if (row < 0 || row >= 9) { + DPRINT << "Invalid row: " << row << std::endl; + return 0; + } + return 1; +} + +char sudoku::get(const int col, const int row) +{ + if (!check_validity(row, col)) { + DPRINT << "over here\n"; + return 0; + } + + return table[col][row]; +} + +int sudoku::set(const int col, const int row, const char val) +{ + std::string str; + + if (!check_validity(col, row)) { + DPRINT << "over here\n"; + return -1; + } + + if (table[col][row] != EMPTY) { + DPRINT << "Assigning value to a non-empty slot\n"; + return -1; + } + + str = get_col_contents(col); + if (str.find(val, 0) != std::string::npos) { + DPRINT << "Illegal assignment " << col << "." << row << ": " + << val << std::endl; + return -1; + } + + str = get_row_contents(row); + if (str.find(val, 0) != std::string::npos) { + DPRINT << "Illegal assignment " << col << "." << row << ": " + << val << std::endl; + return -1; + } + + str = get_block_contents(col, row); + if (str.find(val, 0) != std::string::npos) { + DPRINT << "Illegal assignment " << col << "." << row << ": " + << val << std::endl; + return -1; + } + + + table[col][row] = val; + + return 0; +} + +int sudoku::str_to_row(const int row, const std::string &str) +{ + unsigned int i, col = 0; + char chr; + + if (row < 0 || row >= 9) { + DPRINT << "Illegal row " << row << std::endl; + return -1; + } + + for (i = 0; i < str.length(); i++) { + chr = str.at(i); + + if ((chr == '?') || + (chr == '_') || + (chr == '.')){ + col++; + continue; + } + + /* Ignore non-numbers */ + if (chr < '1' || chr > '9') + continue; + + set(col++, row, chr); + if (col >= 9) + break; + } + return 0; +} + +void sudoku::print(void) +{ + int x,y; + + printf("+-------+------+--------+\n"); + for (y = 0; y < 9; y++) { + printf("| "); + for (x = 0; x < 9; x++) { + printf("%c ", table[x][y]); + if (!((x + 1)% 3)) + printf("| "); + } + printf("\n"); + if (!((y + 1) % 3)) + printf("+-------+-------+-------+\n"); + } +} + +void sudoku::clone_to(sudoku &to) +{ + sudoku clone; + int x, y; + + for (x = 0; x < 9; x++) + for (y = 0; y < 9; y++) + to.table[x][y] = table[x][y]; +} + +std::string sudoku::get_row_contents(int row) +{ + std::string s; + int col; + + for (col = 0; col < 9; col++) { + if (table[col][row] != EMPTY) + s += table[col][row]; + } + + return s; +} + +std::string sudoku::get_col_contents(int col) +{ + std::string s; + int row; + + for (row = 0; row < 9; row++) { + if (table[col][row] != EMPTY) + s += table[col][row]; + } + + return s; +} + +std::string sudoku::get_block_contents(int col, int row) +{ + std::string s; + int x, y; + char c; + + if (col < 0 || col >= 9) + DPRINT "Aiee " << col << std::endl; + if (row < 0 || row >= 9) + DPRINT "Aiee " << row << std::endl; + + col = (col /= 3) * 3; + row = (row /= 3) * 3; + + for (y = 0; y < 3; y++) + for (x = 0; x < 3; x++) { + c = get(x + col, y + row); + if (c != EMPTY) + s += c; + } + + return s; +} + + + +static std::string exclude_common(std::string s1, std::string s2) +{ + std::string::iterator a, b; + +restart: + for (a = s1.begin(); a != s1.end(); a++) { + for (b = s2.begin(); b != s2.end(); b++) { + if (*a == *b) { + a = s1.erase(a); + b = s2.erase(b); + goto restart; + } + } + } + return s1; +} + +std::string sudoku::get_legal_numbers(int col, int row) +{ + char val; + std::string a, b, c, ret; + + if (!check_validity(col, row)) { + DPRINT << "over here\n"; + return NULL; + } + + val = get(col, row); + if (val != EMPTY) { + return "0"; + } + +// std::cout << "[" << col << "." << row << "] "; + + a = get_col_contents(col); +// std::cout << " col " << a; + + b = get_row_contents(row); +// std::cout << " row " << b; + + c = get_block_contents(col, row); +// std::cout << " block " << c; + + ret = exclude_common("123456789", a); + ret = exclude_common(ret, b); + ret = exclude_common(ret, c); + +// std::cout << " legal " << ret << std::endl; + return ret; +} + +int sudoku::fill_missing() +{ + int x, y, solved = 0; + std::string num; + + for (y = 0; y < 9; y++) + for (x = 0; x < 9; x++) { + num = get_legal_numbers(x, y); + if ((num != "0") && (num.length() == 1)) { + set(x, y, num[0]); + solved++; + } + } + if (verbose) { + std::cout << "Solved " << solved << " numbers\n"; + } + + return solved; +} + +int sudoku::get_best_guess(int &col, int &row) +{ + int x, y; + int min = 0, filled = 0, illegals = 0; + std::string numbers; + + /* + * Initialize row and col with illegal values to spot possible + * misuse + */ + col = -1; + row = -1; + + for (y = 0; (y < 9) && !illegals; y++) + for (x = 0; x < 9; x++) { + numbers = get_legal_numbers(x, y); + + if (numbers == "0") { + filled++; + continue; + } + + if (numbers.length() == 0) { + illegals++; + break; + } + + if (!min) { + min = numbers.length(); + col = x; + row = y; + continue; + } + + if ((int)numbers.length() < min) { + min = numbers.length(); + col = x; + row = y; + if (min == 1) + return min; + } +// std::cout << x << "." << y << ": " << " min " +// << numbers << col << "." << row << std::endl; + } + + if ((!min && !filled) || illegals) { +// DPRINT << "Is this sudoku has no solutions?\n"; + return -1; + } + + if (!min && (filled == 99)) { + DPRINT << "This sudoku is solved\n"; + return 0; + } + + return min; +} + +sudoku sudoku::solve(int &solvable) +{ + int x, y, i, ret; + std::string str; + sudoku empty; + + // Fill in as much as possible + do { + if (verbose) { + std::cout << std::endl; + print(); + } + } while (fill_missing() != 0); + + ret = get_best_guess(x, y); + + // Did we solve it yet? + switch (ret) { + case -1: + // Unsolvable + solvable = 0; + if (verbose) { + std::cout << "This is unsolvable, recursion: " + << recursion_depth << std::endl; + } + return empty; + case 0: + // Solved + solvable = 1; + if (verbose) { + std::cout << "Solution found , recursion: " + << recursion_depth << std::endl; + } + return *this; + } + + if (verbose) { + std::cout << "Not solved yet, guessing at depth " + << recursion_depth << std::endl; + } + + // Try guessim something + str = get_legal_numbers(x, y); + for (i = 0; i < (int)str.length(); i++) { + + sudoku guess = *this; + guess.set(x, y, str[i]); + + if (verbose) { + std::cout << "Guessing number " << str[i] << " to " + << x << "." << y << std::endl; + } + + guess.recursion_depth = recursion_depth + 1; + + int can_solve; + guess = guess.solve(can_solve); + + //Did it solve? + if (can_solve) + return guess; + } + + // It didn't solve + solvable = 0; + return empty; +} + +std::vector sudoku::solve_all() +{ + int x, y, i, j, ret; + std::string str; + std::vector sudokus; + + // Fill in as much as possible + do { + if (verbose) { + std::cout << std::endl; + print(); + } + } while (fill_missing() != 0); + + ret = get_best_guess(x, y); + + // Did we solve it yet? + switch (ret) { + case -1: + // Unsolvable + if (verbose) { + std::cout << "This is unsolvable, recursion: " + << recursion_depth << std::endl; + } + return sudokus; + case 0: + // Solved + if (verbose) { + std::cout << "Solution found , recursion: " + << recursion_depth << std::endl; + } + sudokus.push_back(*this); + print(); + return sudokus; + } + + if (verbose) { + std::cout << "Not solved yet, guessing at depth " + << recursion_depth << std::endl; + } + + // Try guessim something + str = get_legal_numbers(x, y); + for (i = 0; i < (int)str.length(); i++) { + std::vector results; + + sudoku guess = *this; + guesses++; + + if (verbose) { + std::cout << "Guessing number " << str[i] << " to " + << x << "." << y << std::endl; + } + + guess.set(x, y, str[i]); + guess.recursion_depth = recursion_depth + 1; + + results = guess.solve_all(); + + //Did it solve? + if (!results.empty()) { +/* printf("Got %d solutions, guessed %d: %s\n", + (int)results.size(), (int)str.size(), + str.c_str());*/ + + for(j = 0;j < (int)results.size(); j++) + sudokus.push_back(results.at(j)); + } + } + + // Return what was solved + return sudokus; +} + diff --git a/sudoku.h b/sudoku.h new file mode 100644 index 0000000..986d63a --- /dev/null +++ b/sudoku.h @@ -0,0 +1,39 @@ +#ifndef SUDOKU_H +#define SUDOKU_H + +#include + +extern int guesses; +extern int verbose; + +class sudoku { +public: + sudoku(); + ~sudoku(); + + void print(void); + + int set(const int col, const int row, const char num); + char get(const int col, const int row); + + // convert a string of numbers to a sudoku row + int str_to_row(const int row, const std::string &str); + + std::string get_legal_numbers(const int col, const int row); + sudoku solve(int &solvable); + std::vector solve_all(); + + int recursion_depth; +private: + + std::string get_row_contents(const int row); + std::string get_col_contents(const int col); + std::string get_block_contents(const int col, const int row); + int fill_missing(); + void clone_to(sudoku &to); + int get_best_guess(int &col, int &row); + + char table[9][9]; +}; + +#endif -- 2.44.0