So.. After creating this, I no longer find sudoku as fun as it used to be =(
It solves 39 puzzles out of 50 from Project Euler and the daily newspaper.
I never got the stupid HiddenPairs algorithm working but then again I never put much effort into it. It reads:
http://projecteuler.net/project/sudoku.txt
And solves almost all of them. Zipped Source: SudokuSolver.zip
Enjoy.
Screenies (At random that shows solved and un-solved puzzles):

View-able Source:
PuzzleInfo.hpp:
C++ Code:
#ifndef PUZZLEINFO_HPP_INCLUDED
#define PUZZLEINFO_HPP_INCLUDED
#include <windows.h>
#include <iostream>
#include <vector>
#include <fstream>
#include "Manipulation.hpp"
void Move(short X, short Y);
void FormatPuzzle(std::string FilePath, std::string CurrentDelimiter, std::string PuzzleDelimiter);
void CreatePuzzles(std::string ProjectEulerFile, std::string PuzzleFolder);
void ReadPuzzle(const std::string &FilePath, std::string Delimiter, int Matrix[9][9]);
bool PuzzleSolved(int PuzzleMatrix[9][9]);
void ReadRowLine(int Index, int PuzzleMatrix[9][9], int LineMatrix[9]);
void ReadColumnLine(int Index, int PuzzleMatrix[9][9], int LineMatrix[9]);
void ReadRow(int Index, int PuzzleMatrix[9][9], int RowMatrix[3][9]);
void ReadColumn(int Index, int PuzzleMatrix[9][9], int ColumnMatrix[9][3]);
void ReadBox(int RowIndex, int ColumnIndex, int PuzzleMatrix[9][9], int Box[3][3]);
void PrintPuzzle(int Matrix[9][9], char BlankCharacter = '.');
void PrintRowLine(int RowLine[9], char BlankCharacter = '.');
void PrintColumnLine(int ColumnLine[9], char BlankCharacter = '.');
void PrintRowMatrix(int RowMatrix[3][9], char BlankCharacter = '.');
void PrintColumnMatrix(int ColumnMatrix[9][3], char BlankCharacter = '.');
void PrintBoxMatrix(int BoxMatrix[3][3], char BlankCharacter = '.');
#endif // PUZZLEINFO_HPP_INCLUDED
PuzzleInfo.cpp:
C++ Code:
#include "PuzzleInfo.hpp"
void Move(short X, short Y)
{
SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), COORD{X, Y});
}
void FormatPuzzle(std::string FilePath, std::string CurrentDelimiter, std::string PuzzleDelimiter)
{
std::string Line = std::string();
std::vector<std::string> Lines;
std::fstream File(FilePath.c_str(), std::ios::in);
while(std::getline(File, Line))
{
if (Line.find(", ") == std::string::npos)
{
Lines.push_back(JoinStrings(SplitString(Line, CurrentDelimiter), PuzzleDelimiter) + "\n");
}
}
File.close();
if (!Lines.empty())
{
File.open(FilePath.c_str(), std::ios::out);
for (auto it = Lines.begin(); it != Lines.end(); ++it)
{
File.write(it->c_str(), it->size());
}
File.close();
}
}
void CreatePuzzles(std::string ProjectEulerFile, std::string PuzzleFolder)
{
std::fstream File(ProjectEulerFile.c_str(), std::ios::in);
if (File.is_open())
{
int I = 0, J = 10;
std::string Line;
std::vector<std::string> Lines;
while (std::getline(File, Line))
{
if (--J == 0)
{
Lines.push_back(Line);
std::fstream Output(PuzzleFolder + "/" + ToString(++I) + ".hpp", std::ios::out);
if (Output.is_open())
{
for (auto it = Lines.begin(); it != Lines.end(); ++it)
Output.write(it->c_str(), it->size());
Output.close();
}
Lines.clear();
J = 10;
}
else if (J != 9)
Lines.push_back(Line + "\n");
}
File.close();
}
}
void ReadPuzzle(const std::string &FilePath, std::string Delimiter, int Matrix[9][9])
{
std::string Line = std::string();
std::vector<std::vector<std::string>> Lines;
std::fstream File(FilePath.c_str(), std::ios::in);
while(std::getline(File, Line))
{
Lines.push_back(SplitString(Line, Delimiter));
}
File.close();
for (int I = 0; I < 9; ++I)
{
for (int J = 0; J < 9; ++J)
{
Matrix[J][I] = ToNumber<int>(Lines[I][J]);
}
}
}
bool PuzzleSolved(int PuzzleMatrix[9][9])
{
for (int I = 0; I < 9; ++I)
{
for (int J = 0; J < 9; ++J)
{
if (PuzzleMatrix[J][I] == 0)
return false;
}
}
return true;
}
void ReadRowLine(int Index, int PuzzleMatrix[9][9], int LineMatrix[9])
{
for (int I = 0; I < 9; ++I)
{
LineMatrix[I] = PuzzleMatrix[I][Index];
}
}
void ReadColumnLine(int Index, int PuzzleMatrix[9][9], int LineMatrix[9])
{
for (int I = 0; I < 9; ++I)
{
LineMatrix[I] = PuzzleMatrix[Index][I];
}
}
void ReadRow(int Index, int PuzzleMatrix[9][9], int RowMatrix[3][9])
{
Index *= 3;
for (int I = Index; I < Index + 3; ++I)
{
for (int J = 0; J < 9; ++J)
{
RowMatrix[J][I] = PuzzleMatrix[J][I];
}
}
}
void ReadColumn(int Index, int PuzzleMatrix[9][9], int ColumnMatrix[9][3])
{
Index *= 3;
for (int I = 0; I < 9; ++I)
{
for (int J = Index; J < Index + 3; ++J)
{
ColumnMatrix[J][I] = PuzzleMatrix[J][I];
}
}
}
void ReadBox(int RowIndex, int ColumnIndex, int PuzzleMatrix[9][9], int Box[3][3])
{
RowIndex *= 3;
ColumnIndex *= 3;
for (int C = 0, I = ColumnIndex; I < ColumnIndex + 3; ++C, ++I)
{
for (int R = 0, J = RowIndex; J < RowIndex + 3; ++R, ++J)
{
Box[R][C] = PuzzleMatrix[J][I];
}
}
}
void PrintPuzzle(int Matrix[9][9], char BlankCharacter)
{
for (int I = 0; I < 9; ++I)
{
for (int J = 0; J < 9; ++J)
{
if (J == 3 || J == 6)
{
std::cout<<"| ";
}
if (Matrix[J][I] == 0)
std::cout<<BlankCharacter<<" ";
else
std::cout<<Matrix[J][I]<<" ";
}
std::cout<<std::endl;
if (I != 8)
{
std::cout<<"\t |\t |\n";
}
if (I == 2 || I == 5)
{
std::cout<<"--------- ----------- ---------";
std::cout<<std::endl;
std::cout<<"\t |\t |\n";
}
}
}
void PrintRowLine(int RowLine[9], char BlankCharacter)
{
for (int I = 0; I < 9; ++I)
{
if (RowLine[I] == 0)
std::cout<<BlankCharacter<<' ';
else
std::cout<<RowLine[I]<<' ';
}
}
void PrintColumnLine(int ColumnLine[9], char BlankCharacter)
{
for (int I = 0; I < 9; ++I)
{
if (ColumnLine[I] == 0)
std::cout<<BlankCharacter<<std::endl;
else
std::cout<<ColumnLine[I]<<std::endl;
}
}
void PrintRowMatrix(int RowMatrix[3][9], char BlankCharacter)
{
for (int I = 0; I < 3; ++I)
{
for (int J = 0; J < 9; ++J)
{
if (RowMatrix[J][I] == 0)
std::cout<<BlankCharacter<<" ";
else
std::cout<<RowMatrix[J][I]<<" ";
}
std::cout<<std::endl;
}
}
void PrintColumnMatrix(int ColumnMatrix[9][3], char BlankCharacter)
{
for (int I = 0; I < 9; ++I)
{
for (int J = 0; J < 3; ++J)
{
if (ColumnMatrix[J][I] == 0)
std::cout<<BlankCharacter<<' ';
else
std::cout<<ColumnMatrix[J][I]<<' ';
}
std::cout<<std::endl;
}
}
void PrintBoxMatrix(int BoxMatrix[3][3], char BlankCharacter)
{
for (int I = 0; I < 3; ++I)
{
for (int J = 0; J < 3; ++J)
{
if (BoxMatrix[J][I] == 0)
std::cout<<BlankCharacter<<' ';
else
std::cout<<BoxMatrix[J][I]<<' ';
}
std::cout<<std::endl;
}
}
PuzzleAlgorithms.hpp:
C++ Code:
#ifndef PUZZLEALGORITHMS_HPP_INCLUDED
#define PUZZLEALGORITHMS_HPP_INCLUDED
#include <vector>
#include <algorithm>
#include "PuzzleInfo.hpp"
template<typename T>
inline bool InRange(T LowerBound, T UpperBound, T Value) {return ((LowerBound < Value) && (Value < UpperBound));}
void GetBoxIndex(int RowX, int RowY, int &BoxXIndex, int &BoxYIndex);
void GetCellPossibilities(int X, int Y, int PuzzleMatrix[9][9], std::vector<int> &CellInfo);
void FillUniqueCells(int PuzzleMatrix[9][9]);
void FillHiddenSingles(int Index, int PuzzleMatrix[9][9], bool Rows);
#endif // PUZZLEALGORITHMS_HPP_INCLUDED
PuzzleAlgorithms.cpp:
C++ Code:
#include "PuzzleAlgorithms.hpp"
void GetBoxIndex(int RowX, int RowY, int &BoxXIndex, int &BoxYIndex)
{
if (RowX < 3) {BoxXIndex = 0;}
else if (InRange(2, 6, RowX)) {BoxXIndex = 1;}
else if (InRange(5, 9, RowX)) {BoxXIndex = 2;}
if (RowY < 3) {BoxYIndex = 0;}
else if (InRange(2, 6, RowY)) {BoxYIndex = 1;}
else if (InRange(5, 9, RowY)) {BoxYIndex = 2;}
}
void GetCellPossibilities(int X, int Y, int PuzzleMatrix[9][9], std::vector<int> &CellInfo)
{
if (PuzzleMatrix[X][Y] != 0) return;
std::vector<int> Data;
int BoxMatrix[3][3] = {{0}};
int RowLineMatrix[9] = {0};
int ColumnLineMatrix[9] = {0};
int RowBoxIndex = 0, ColumnBoxIndex = 0;
GetBoxIndex(X, Y, RowBoxIndex, ColumnBoxIndex);
ReadRowLine(Y, PuzzleMatrix, RowLineMatrix);
ReadColumnLine(X, PuzzleMatrix, ColumnLineMatrix);
ReadBox(RowBoxIndex, ColumnBoxIndex, PuzzleMatrix, BoxMatrix);
for (int I = 0; I < 9; ++I)
{
if (BoxMatrix[I / 3][I % 3] != 0) Data.push_back(BoxMatrix[I / 3][I % 3]);
if (RowLineMatrix[I] != 0) Data.push_back(RowLineMatrix[I]);
if (ColumnLineMatrix[I] != 0) Data.push_back(ColumnLineMatrix[I]);
}
std::sort(Data.begin(), Data.end());
Data.erase(std::unique(Data.begin(), Data.end()), Data.end());
for (int I = 1, J = 0; I < 10; ++I, ++J)
{
if (std::find(Data.begin(), Data.end(), I) == Data.end())
{
CellInfo.push_back(I);
}
}
}
void FillUniqueCells(int PuzzleMatrix[9][9])
{
for (int I = 0; I < 9; ++I)
{
for (int J = 0; J < 9; ++J)
{
std::vector<int> CellInfo;
GetCellPossibilities(J, I, PuzzleMatrix, CellInfo);
if (CellInfo.size() == 1)
{
PuzzleMatrix[J][I] = CellInfo[0];
}
}
}
}
void FillHiddenSingles(int Index, int PuzzleMatrix[9][9], bool Rows)
{
std::vector<int> Data;
std::vector<std::vector<int>> Possibilities;
for (int I = 0; I < 9; ++I)
{
Possibilities.push_back(std::vector<int>());
if (Rows)
{
GetCellPossibilities(I, Index, PuzzleMatrix, Possibilities.back());
}
else
{
GetCellPossibilities(Index, I, PuzzleMatrix, Possibilities.back());
}
Data.insert(Data.end(), Possibilities.back().begin(), Possibilities.back().end());
}
for (auto it = Data.begin(); it != Data.end(); ++it)
{
if (std::count(Data.begin(), Data.end(), *it) == 1)
{
int I = 0;
for (auto jt = Possibilities.begin(); jt != Possibilities.end(); ++jt, ++I)
{
if (std::find(jt->begin(), jt->end(), *it) != jt->end())
{
if (Rows)
{
PuzzleMatrix[I][Index] = *it;
}
else
{
PuzzleMatrix[Index][I] = *it;
}
}
}
}
}
}
Manipulation.hpp:
C++ Code:
#ifndef MANIPULATION_HPP_INCLUDED
#define MANIPULATION_HPP_INCLUDED
#include <vector>
#include <sstream>
template <typename T>
T ToNumber(const std::string &Text) {std::istringstream SS(Text); T Result; return (SS >> Result ? Result : 0);}
template<typename T>
inline std::string ToString(T Type){std::stringstream SS; SS<<Type; return SS.str();}
template<typename T>
std::ostream& operator << (std::ostream& Stream, const std::vector<T>& VectorToPrint)
{
if (VectorToPrint.size() > 1)
{
for (std::size_t I = 0; I < VectorToPrint.size() - 1; ++I)
{
Stream<<VectorToPrint[I]<<", ";
}
}
if (!VectorToPrint.empty())
{
Stream<<VectorToPrint.back();
}
return Stream;
}
std::string JoinStrings(std::vector<std::string> StringsToJoin, std::string Delimiter);
std::vector<std::string> SplitString(std::string StringToSplit, std::string Delimiter);
#endif // MANIPULATION_HPP_INCLUDED
Manipulation.cpp
C++ Code:
#include "Manipulation.hpp"
std::string JoinStrings(std::vector<std::string> StringsToJoin, std::string Delimiter)
{
std::string Result;
for (std::size_t I = 0; I < StringsToJoin.size() - 1; ++I)
Result += StringsToJoin[I] + Delimiter;
Result += StringsToJoin[StringsToJoin.size() - 1];
return Result;
}
std::vector<std::string> SplitString(std::string StringToSplit, std::string Delimiter)
{
std::vector<std::string> Result;
if (Delimiter == std::string())
{
for (std::string::iterator it = StringToSplit.begin(); it != StringToSplit.end(); ++it)
{
std::string Character = std::string();
Character += *it;
Result.push_back(Character);
}
}
else
{
std::size_t Pos = StringToSplit.find_first_of(Delimiter);
while(Pos != std::string::npos)
{
if(Pos > 0)
{
Result.push_back(StringToSplit.substr(0, Pos));
}
StringToSplit = StringToSplit.substr(Pos + 1);
Pos = StringToSplit.find_first_of(Delimiter);
}
if(StringToSplit.length() > 0)
{
Result.push_back(StringToSplit);
}
}
return Result;
}
main.cpp:
C++ Code:
#include <windows.h>
#include <iostream>
#include "PuzzleInfo.hpp"
#include "PuzzleAlgorithms.hpp"
using namespace std;
int Matrix[9][9];
void Solve(int PuzzleMatrix[9][9])
{
FillUniqueCells(PuzzleMatrix);
for (int I = 0; I < 9; ++I)
{
FillHiddenSingles(I, PuzzleMatrix, true);
}
for (int I = 0; I < 9; ++I)
{
FillHiddenSingles(I, PuzzleMatrix, false);
}
}
void SolveAllPuzzles(std::string PuzzlePath)
{
int Count = 0;
std::vector<int> Puzzles;
for (int I = 1; I < 51; ++I)
{
std::cout<<"\n\nPuzzle: "<<I<<"\n\n";
ReadPuzzle(PuzzlePath + ToString(I) + ".hpp", ", ", Matrix);
for (int I = 0; I < 10; ++I)
Solve(Matrix);
PrintPuzzle(Matrix);
if (PuzzleSolved(Matrix)) ++Count;
else Puzzles.push_back(I);
}
std::cout<<"Failed: "<<Puzzles<<std::endl;
std::cout<<"Solved: "<<Count<<" Puzzles!"<<std::endl;
}
int main()
{
CreatePuzzles("C:/Users/Brandon/Desktop/SudokuSolver/Sudoku.txt", "C:/Users/Brandon/Desktop/SudokuSolver/Puzzles/");
SolveAllPuzzles("C:/Users/Brandon/Desktop/SudokuSolver/Puzzles/");
return 0;
/*ReadPuzzle("C:/Users/Brandon/Desktop/SudokuSolver/Puzzles/6.hpp", ", ", Matrix);
for (int I = 0; I < 10 && !PuzzleSolved(Matrix); ++I)
{
Solve(Matrix);
}
PrintPuzzle(Matrix);
//Move(0, 21);
return 0;*/
}