Initial commit

diff --git a/.gitignore b/.gitignore
new file mode 100644 (file)
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 (file)
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 (file)
index 0000000..b737a25
--- /dev/null
+++ b/debug.h
@@ -0,0 +1,8 @@
+#ifndef DEBUG_H
+#define DEBUG_H
+
+#include <iostream>
+
+#define DPRINT std::cout << __FILE__ << ":" << __LINE__ << " "
+
+#endif

diff --git a/main.cpp b/main.cpp
new file mode 100644 (file)
index 0000000..ac9a8da
--- /dev/null
+++ b/main.cpp
@@ -0,0 +1,48 @@
+#include <iostream>
+
+#include "sudoku.h"
+#include "debug.h"
+
+int main(int argc, char *argv[])
+{
+       int row, i;
+       std::string line;
+       sudoku sudo;
+       std::vector<sudoku> 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 (file)
index 0000000..a1777e5
--- /dev/null
+++ b/sudoku.cpp
@@ -0,0 +1,473 @@
+#include <iostream>
+#include <string>
+
+#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> sudoku::solve_all()
+{
+       int x, y, i, j, ret;
+       std::string str;
+       std::vector<sudoku> 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<sudoku> 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 (file)
index 0000000..986d63a
--- /dev/null
+++ b/sudoku.h
@@ -0,0 +1,39 @@
+#ifndef SUDOKU_H
+#define SUDOKU_H
+
+#include <vector>
+
+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<sudoku> 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