Sudoku Solver Class
Well the solution involves guessing and backtracking, so actually it will solve all possible (valid) boards. The idea is to get a solution that involves no searching for a candidate, since that always involves at least square complexity. The point for the two list, is a to keep a list of possible candidates for for the guessing. The solution will get about 3/4 of all possible sodoku boards. And I have never seen any boards where the guess took more than two candidates. But the heuristic behind the guess is that the best candidate for a guess is the one with the few possible candidates.
P.S. I am actually cheating... We had to solve the problem in a "computational intelligence" course
P.P.S I am the anonymous poster, had not noticed that I was not logged on.
P.P.P.S sorry about that double post...
P.S. I am actually cheating... We had to solve the problem in a "computational intelligence" course
P.P.S I am the anonymous poster, had not noticed that I was not logged on.
P.P.P.S sorry about that double post...
rioki, did you look at the code that was posted? I didn't see any backtracking in there. If I missed it, could someone point out where it is?
Using a char instead of an int is a really low level micro-optimization. You're not really saving any significant amount of memory, and unless you're profiling your code you really have no way of knowing if it makes the code run faster or slower. If it did make the code run faster, it would be by an extremely small amount. As long as you know it won't overflow, it can't hurt I guess. But you're not really gaining much.
Using a char instead of an int is a really low level micro-optimization. You're not really saving any significant amount of memory, and unless you're profiling your code you really have no way of knowing if it makes the code run faster or slower. If it did make the code run faster, it would be by an extremely small amount. As long as you know it won't overflow, it can't hurt I guess. But you're not really gaining much.
Quote:Original post by MVP
It would use less memory.
Really? What about alignment issues? Variables around your loop index may have to be placed on a 32-bit alignment (or something other than 8-bit alignment) anyway, leaving your loop variable with a number of bytes padding wasted memory. Nothing saved.
Besides, I can see you allocate arrays with several levels of pointers and allocations. Way more than all loop variables combined. Saving loop variables is nothing compared to that. Save where it matters, and loop variables is not that place.
[Edited by - Brother Bob on February 2, 2007 6:11:32 AM]
Quote:Original post by MVP
It would use less memory.
You should be aware that anything smaller than an int is very likely to be optimized to int.
In the IA-32 architecture, if the data on the stack is not 4 byte aligned then you incur an extra IO cycle when popping and pushing from the stack. Sure, in this example it's an irrelevance, but it's worthwhile being aware of it.
Author
Small update, I just cleaned it up a little bit, still need to add guessing functionality.
Link to the Code Blocks Project File: Sudoku Solver
Main.cpp
Sudoku.h
Sudoku.cpp
MiscFunctions.h
Link to the Code Blocks Project File: Sudoku Solver
Main.cpp
#include <iostream>using namespace std;#include "Sudoku.h"#include <windows.h>double GetMicroTime(){ LARGE_INTEGER ticks, ticksPerSecond; QueryPerformanceFrequency(&ticksPerSecond); QueryPerformanceCounter(&ticks); return ( double(ticks.QuadPart) / double(ticksPerSecond.QuadPart) );}void PrintSudoku(Sudoku *sud){ for(int y = 0; y < sud->GetSize(); y++) { for(int x = 0; x < sud->GetSize(); x++) { if( sud->GetMatrixElement(x, y) < 10) cout << " "; cout << sud->GetMatrixElement(x, y) << " "; } cout << endl; }}int main(){ double time1 = 0.0, time2 = 0.0; Sudoku sud; char fileName[64]; cout << "Open File: "; cin >> fileName; time1 = GetMicroTime(); if( sud.ReadFile(fileName) ) { time2 = GetMicroTime(); cout << "ReadFile: " << (time2 - time1)*1000.0 << " ms" << endl << endl; PrintSudoku(&sud); cout << endl; time1 = GetMicroTime(); // START TIMING sud.Solve(); // END TIMING time2 = GetMicroTime(); PrintSudoku(&sud); cout << endl << "Solve: " << (time2 - time1)*1000.0 << " ms" << endl << endl; } else cout << "Failed to read file." << endl; system("PAUSE"); return 0;}Sudoku.h
#ifndef SUDOKU_H#define SUDOKU_H#include <fstream>using namespace std;class Sudoku {public: Sudoku(); ~Sudoku(); // Methods of sudoku matrix inputs int ReadFile(const char* filePath); // Scans all cells for numbers and marks that number // in all cells of the same row, column, and 3x3 as not // possible because it is already used. int MarkNotPossible(); // Scans all cells and if there is only 1 possiblility // then simply set that value to the corresponding // matrix value. int CheckForSinglePossibility(); // Fill in the blanks as much as possible without guessing int Solve(); // Check if the sudoku has been solved bool IsSolved(); // Take 1 step toward solving void Step(); // Accessor functions int GetSize() { return size; } int GetMatrixElement(int x, int y) { return matrix[x][y]; }private: int **matrix; int size; bool ***possible; bool readSuccessful; void CreateMatrixAndPossibilityArray(int size); void DeleteMatrixAndPossibilityArray(); bool MarkNotPossible_Row(int x, int y); bool MarkNotPossible_Column(int x, int y); bool MarkNotPossible_MiniSquare(int x, int y); void SetSize( ifstream *file );};#endifSudoku.cpp
#include "Sudoku.h"#include "MiscFunctions.h"#include <iostream>using namespace std;Sudoku::Sudoku(){ size = 1; readSuccessful = false;}Sudoku::~Sudoku(){ DeleteMatrixAndPossibilityArray();}int Sudoku::ReadFile(const char* filePath){ bool bSuccess = true; // Open File ifstream file(filePath); // If path given doesnt link to a file if(!file.good()) return false; SetSize(&file); CreateMatrixAndPossibilityArray(size); int maxLength = IntLen(size); // Get File Length file.seekg (0, ios::end); int fileLen = file.tellg(); file.seekg (0, ios::beg); // Create array to store the file contents in char *fileArray = new char[fileLen]; for(int i = 0; i < fileLen; i++) { file.get( fileArray); } // File inside of array now so close the file file.close(); // Parse the fileArray for number sections and place them int the matrix array char *curNumAsStr = new char[maxLength]; int curNumAsStrIndex = 0; int matrixIndex = 0; for(int i = 0; i < fileLen; i++) { if(fileArray >= '0' && fileArray <= '9') { curNumAsStr[curNumAsStrIndex] = fileArray; curNumAsStrIndex++; } else if(curNumAsStrIndex && (fileArray == ' ' || fileArray == '\n'|| i == fileLen-1)) { matrix[matrixIndex%size][matrixIndex/size] = StringToInt(curNumAsStr); matrixIndex++; curNumAsStrIndex = 0; // Unset curNumAsStr for(int j = 0; j < maxLength; j++) curNumAsStr[j] = '\0'; } } delete [] curNumAsStr; delete [] fileArray; readSuccessful = bSuccess; return bSuccess;}int Sudoku::MarkNotPossible(){ bool bChanged = false; for(int y = 0; y < size; y++) { for(int x = 0; x < size; x++) { if( matrix[x][y] > 0) { // MarkNotPossible functions return true if // they changed the possibility array if( MarkNotPossible_Row(x, y) || MarkNotPossible_Column(x, y) || MarkNotPossible_MiniSquare(x, y) ) { bChanged = true; } } } } return bChanged;}int Sudoku::CheckForSinglePossibility(){ int possibleVal = 0; int possibilities = 0; bool bChanged = false; // Find a cell with only 1 possibility and adjust matrix value for(int y = 0; y < size; y++) { for(int x = 0; x < size; x++) { if(matrix[x][y] == 0) { for(int z = 0; z < size; z++) { if( possible[x][y][z] == true ) { possibleVal = z; possibilities++; } } if(possibilities == 1) { bChanged = true; matrix[x][y] = possibleVal + 1; } } possibilities = 0; } } return bChanged;}int Sudoku::Solve(){ // Loop while one of these are making progress while( MarkNotPossible() || CheckForSinglePossibility() ) {} return IsSolved();}bool Sudoku::IsSolved(){ // If any cell is 0 then fail for(int y = 0; y < size; y++) { for(int x = 0; x < size; x++) { if( matrix[x][y] == 0) { return false; } } } return true;}void Sudoku::Step(){ MarkNotPossible(); CheckForSinglePossibility();}void Sudoku::CreateMatrixAndPossibilityArray(int size){ // Create the matrix array matrix = new int*[size]; for(int i = 0; i < size; i++) { matrix = new int[size]; for(int j = 0; j < size; j++) { matrix[j] = 0; } } // Create the possible array possible = new bool**[size]; for(int i = 0; i < size; i++) { possible = new bool*[size]; for(int j = 0; j < size; j++) { possible[j] = new bool[size]; for(int k = 0; k < size; k++) { possible[j][k] = 1; } } }}void Sudoku::DeleteMatrixAndPossibilityArray(){ if( readSuccessful ) { // Cleanup matrix for(int i = 0; i < size; i++) { delete [] matrix; } delete [] matrix; // Cleanup Possible array for(int i = 0; i < size; i++) { for(int j = 0; j < size; j++) { delete [] possible[j]; } delete [] possible; } delete [] possible; }}bool Sudoku::MarkNotPossible_Row(int x, int y){ bool bChanged = false; // Mark not possible for ROW (x) for( int z = 0; z < size; z++ ) { if( possible[z][y][matrix[x][y]-1] ) { possible[z][y][matrix[x][y]-1] = false; bChanged = true; } } return bChanged;}bool Sudoku::MarkNotPossible_Column(int x, int y){ bool bChanged = false; // Mark not possible for COLUMN (y) for( int z = 0; z < size; z++ ) { if( possible[x][z][matrix[x][y]-1] ) { possible[x][z][matrix[x][y]-1] = false; bChanged = true; } } return bChanged;}bool Sudoku::MarkNotPossible_MiniSquare(int x, int y){ bool bChanged = false; // Mark not possible for minisquare int miniSize = int(sqrt(size)); int ymin = y - (y % miniSize); int ymax = y + (miniSize - (y % miniSize)); int xmin = x - (x % miniSize); int xmax = x + (miniSize - (x % miniSize)); for(int Y = ymin; Y < ymax; Y++) { for(int X = xmin; X < xmax; X++) { if( possible[X][Y][matrix[x][y]-1] ) { possible[X][Y][matrix[x][y]-1] = false; bChanged = true; } } } return bChanged;}// Set the size of the sudoku matrix stored in the filevoid Sudoku::SetSize( ifstream *file ){ char c; while( file->get(c) && c != '\n' ) { if(c == ' ') size++; }}MiscFunctions.h
#ifndef MISCFUNCTIONS_H#define MISCFUNCTIONS_H#include <math.h>#include <iostream>using namespace std;int Power(int x, int y){ int ret = 1; for(int i = 0; i < y; i++) { ret *= x; } return ret;}int CharToInt(char c){ if( c < '0' || c > '9' ) return -1; else return c - '0';}int StringToInt(char *str){ int number = 0; int power = strlen(str) - 1; for(int i = 0; i <= power; i++) { number += CharToInt(str) * Power(10, power - i); } return number;}int IntLen(int num){ return static_cast<int>( ceil( log10( static_cast<float>( num ) ) ) );}#endif
You moved the function implementations in Soduku.h to Soduku.cpp. That's excellent, but you also need to do that for the functions in MiscFunctions.h
Honestly, saving 3 bytes of memory on a machine with over a billion bytes of memory* is not worth the millisecond you spent considering it. That is an example of micro-optimization at its worst. Avoid optimizing your code for now, it will only lead to hard-to-solve problems.
* Actually, in this case the compiler is likely to keep the variable in a register regardless of the size, so you have saved no memory at all.
Quote:Original post by MVP
It would use less memory.
Honestly, saving 3 bytes of memory on a machine with over a billion bytes of memory* is not worth the millisecond you spent considering it. That is an example of micro-optimization at its worst. Avoid optimizing your code for now, it will only lead to hard-to-solve problems.
* Actually, in this case the compiler is likely to keep the variable in a register regardless of the size, so you have saved no memory at all.
Author
Thanks. :) I split MiscFunctions.h up. Im going to be looking into algorithms now, I haven't done any complex ones before so Im not sure where to start for the guessing stuff. If you know of any awesome resources for this one I would love a link so I can take a gander. :)
Thanks again. :)
Thanks again. :)
Oh boy.
Sorry to say, this is still pretty awful. I haven't had a chance to test anything, cut it up properly into files or write out my explanations of what's wrong coherently, yet; but for now you can go over my notes:
I pretty much had to rewrite the file parsing from scratch, because the current approach is a dead end. You'll notice the misc functions are *completely gone*. I won't even bother to go into detail about how the power() algorithm can be made faster for large powers, or how it's wasteful to exponentiate each digit instead of just iteratively "multiplying and accumulating"; because it's not important - manually converting integers to strings is, in a desktop environment, a fool's task.
Sorry to say, this is still pretty awful. I haven't had a chance to test anything, cut it up properly into files or write out my explanations of what's wrong coherently, yet; but for now you can go over my notes:
- bizarre file parsing: requires whitespace to separate numbers even though it calculates a "max length" for them - can only generate overflows. No null terminator anyway!- Hungarian notation on booleans. Also, return bool FFS!- But never mind that, because the correct approach is to read the data in in the constructor, and throw an exception on failure. Also, storing 'readSuccessful' internally is no use because it isn't checked except to clean up (hint: deleting a null pointer is fine).- Use the standard library.- You don't need to comment things like "open the file"; see the other thread.- Data layout. There should be a separate class to represent individual cells. Having done that, we can organize the algorithm properly, and also see that the 'value' property of a cell is redundant and can be calculated from the possibilities array.- fstream include goes in Sudoku.cpp, not .h. And never 'using namespace std' in a header!!!- PrintSudoku is Sudoku class functionality. Also the formatting is not very general.- Public interface of Sudoku should only have the solve and print functionality.- Time conversion is the wrong way around.- endl abuse.- Don't artificially pause programs at the end!!!Keep scrolling for improved-source-in-progress...#include <iostream>using namespace std;#include "Sudoku.h"#include <windows.h>double GetMicroTime() { LARGE_INTEGER ticks, ticksPerSecond; QueryPerformanceFrequency(&ticksPerSecond); QueryPerformanceCounter(&ticks); return ( double(ticks.QuadPart) / double(ticksPerSecond.QuadPart) );}int main() { std::string fileName; cout << "Open File: "; cin >> fileName; try { double time = GetMicroTime(); Sudoku s(fileName); cout << "ReadFile: " << (GetMicroTime() - time1) / 1000.0 << " ms\n\n" << s << endl; time = GetMicroTime(); s.solve(); time = GetMicroTime() - time; cout << s << "\nSolve: " << time / 1000.0 << " ms\n" << endl; } catch (std::exception& ex) { cout << "Oops, something went wrong: " << ex.what() << endl; }}#ifndef SUDOKU_H#define SUDOKU_Hconst int UNKNOWN_CELL = 0;const int IMPOSSIBLE_CELL = -1; // a logical contradiction was found.class Cell { public: Cell(int value, int max) : possibilities(new bool[max]) { for (int i = 0; i < max; ++i) { possibilities = (i + 1 == value) || (value == UNKNOWN_CELL); } } ~Cell() { delete[] possibilities; } bool removePossibility(int value) { if (possibilities[value - 1]) { possibilities[value - 1] = false; return true; } return false; } bool known() { int v = value(); return v != IMPOSSIBLE_CELL && v != UNKNOWN_CELL; } int value() { int result = IMPOSSIBLE_CELL; for (int i = 0; i < max; ++i) { if (possibilities) { result = (result == IMPOSSIBLE_CELL) ? (i + 1) : UNKNOWN_CELL; } } return result; } private: bool* possibilities; Cell(const Cell&); Cell& operator=(const Cell&);};class Sudoku { public: Sudoku(); // Fill in the blanks as much as possible without guessing bool solve(); // Check if the sudoku has been solved bool isSolved(); // Take 1 step toward solving void reduce(); friend ostream& operator<<(ostream& os, const Sudoku& s); private: vector<Cell> matrix; int size; int mini_size; Cell& at(int x, int y) { return matrix[y * size + x]; } bool reduce_row(int x, int y, int value); bool reduce_column(int x, int y, int value); bool reduce_minisquare(int x, int y, int value);};#endif#include "Sudoku.h"#include <iostream>#include <fstream>using namespace std;ostream& operator<<(ostream& os, const Sudoku& s) { // Figure out how wide the numbers may be. stringstream ss; ss << s.size; int width = ss.str().size(); for (int y = 0; y < s.size; y++) { for (int x = 0; x < s.size; x++) { os << setwidth(width); int value = s.at(x, y).value(); switch(value) { case UNKNOWN_CELL: os << "?"; break; case IMPOSSIBLE_CELL: os << "X"; break; default: os << value; } } os << '\n'; } return os;}void Sudoku::appendFileLineToData(const std::string& line, std::vector<int>& data) { std::stringstream parser(line); int value; while (parser >> value) { data.push_back(value); }}Sudoku::Sudoku(const std::string& filePath) { ifstream file(filePath.c_str()); // Since we're going to throw an exception for any unexpected file failure, // we can just let the file object do that for us: file.exceptions(); vector<int> data; // Read the first line and deduce the sudoku size. std::string line; std::getline(file, line); appendFileLineToData(line, data); size = data.size(); // Make sure this is a valid size mini_size = sqrt(size); if (size != mini_size * mini_size) { stringstream error_message(""); error_message << size << " is not a valid sudoku size (must be a square number)\n"; throw std::runtime_error(error_message); } // Now read all the rest of the lines. data.reserve(size * size); // This is an unusual way of numbering the lines, but it's convenient here. for (int i = 2; i <= size; ++i) { std::getline(file, line); appendFileLineToData(line, data); if (data.size() != size * i) { stringstream error_message(""); error_message << "Incorrect number of elements on line " << i << "(expected " << size << ", got " << data.size() - size * (i - 1) << ")\n"; throw std::runtime_error(error_message); } } // Finally we can convert the numbers into Cell objects. matrix.reserve(size * size); for (int i = 0; i < size * size; ++i) { matrix = Cell(data, size); }}int Sudoku::reduce() { bool changed = false; for (int y = 0; y < size; y++) { for (int x = 0; x < size; x++) { if (at(x, y).known()) { int value = at(x, y).value(); if (reduce_row(x, y, value) || reduce_column(x, y, value) || reduce_minisquare(x, y, value)) { changed = true; } } } } return changed;}bool Sudoku::solve() { while (reduce()); return IsSolved();}bool Sudoku::isSolved() { for (int y = 0; y < size; y++) { for (int x = 0; x < size; x++) { if (!at(x, y).known()) { return false; } } } return true;}bool Sudoku::reduce_row(int x, int y, int value) { bool changed = false; for (int z = 0; z < size; z++) { if (at(z, y).removePossibility(value)) { changed = true; } } return changed;}bool Sudoku::reduce_column(int x, int y, int value) { bool changed = false; for (int z = 0; z < size; z++) { if (at(x, z).removePossibility(value)) { changed = true; } } return changed;}bool Sudoku::reduce_minisquare(int x, int y, int value) { bool changed = false; int ymin = (y / mini_size) * mini_size; int xmin = (x / mini_size) * mini_size; for (int j = ymin; j < ymin + mini_size; ++j) { for (int i = xmin; i < xmin + mini_size; ++i) { if (at(i, j).removePossibility(value)) { changed = true; } } } return changed;}I pretty much had to rewrite the file parsing from scratch, because the current approach is a dead end. You'll notice the misc functions are *completely gone*. I won't even bother to go into detail about how the power() algorithm can be made faster for large powers, or how it's wasteful to exponentiate each digit instead of just iteratively "multiplying and accumulating"; because it's not important - manually converting integers to strings is, in a desktop environment, a fool's task.
Author
Oh wow, some great ideas. I am definetly going to be going through that later. Thanks a lot. Rating++ :)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
