A Sudoku solver..Fun stuff..
So here is a c++ version that is intended to handle sudokus of various sizes(4x4,9x9,16x16...)
It was intended to be a short program, but it was a little trickier and longer than I thought. However it seems to be working for a couple of test puzzles.
#include <tchar.h>
#include <math.h>
#include <set>
#include <map>
#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>
#include <ostream>
#include <boost/smart_ptr.hpp>
//forward declarations
class Cell;
struct RowColumnBox;
class VectorMap;
class Grid;
class SolutionPoint;
// Convenient typedefs
typedef std::set<int> OptionsSet;
typedef std::map<int, Cell> GridMap;
typedef std::vector<int> GroupVector;
typedef std::map<int, GroupVector> GroupVectorCollection;
typedef std::map<int, RowColumnBox> CellLocationMap;
typedef std::pair<int,int> CellValuePair;
typedef std::queue<CellValuePair> SolvedQueue;
typedef boost::shared_ptr<VectorMap> VectorMapPtr;
typedef boost::shared_ptr<SolutionPoint> SolutionPointPtr;
typedef boost::shared_ptr<Grid> GridPtr;
// helper functions for determining important dimensions of the grid
inline int CellCount( int size ) { return static_cast<int>(pow( (double)size, 4)); }
inline int GridLength( int size ) { return size * size;}
// Just generates a sequence of numbers for filling in sequences into vectors etc
class SequenceGenerator {
int increment, current;
public:
SequenceGenerator(int inc, int start) : increment(inc), current(start - inc) {;}
int operator()() {
current += increment;
return current;
}
};
// Class holds all the available options for a cell
class Options {
OptionsSet options;
public:
Options(int size) {
std::generate_n( std::inserter(options, options.begin()), GridLength(size), SequenceGenerator(1, 1) );
}
Options(const Options& obj) : options(obj.options){
}
Options& operator=(const Options& obj ) {
options = obj.options;
//std::copy( obj.options.begin(), obj.options.end(), std::inserter( options, options.begin() ) );
}
// returns the value if there is only one possibility left else 0
int RemoveOption( int removeOption ) {
options.erase( removeOption );
return (options.size() == 1) ? *options.begin() : 0;
}
// returns a count of the available options for a cell
int GetCount() const { return static_cast<int>(options.size()); }
int GetGuessValue( int guessNumber ) const {
OptionsSet::const_iterator it = options.begin();
for( int i = 0; i < guessNumber; ++i, ++it );
return *it;
}
};
// One cell from the grid
class Cell {
int value;
Options options;
Cell& operator=(const Cell&); // at the moment don't need =
public:
Cell(int size) : options(size), value(0) {
}
Cell(const Cell& cell ) : value(cell.value), options(cell.options) {
}
// returns true if removing an option has solved the cell else false
int RemoveOption(int option) {
// if we have a value we no longer care about what we removing options
// but if it is already solved don't return the value
if( !value ) {
value = options.RemoveOption(option);
return value;
}
return 0;
}
// get/set for the value of the cell
void SetValue( int val ) { value = val; }
int GetValue() const { return value; }
// checks if the cell is solved
bool IsSolved() const { return (value != 0); }
//returns a count of the availble options for a cell
int GetOptionCount() const { return value ? 0 : options.GetCount(); }
// applies the guess number and returns the value guessed ( not equal to guessNumber )
int ApplyGuess( int guessNumber ) {
value = options.GetGuessValue( guessNumber );
return value;
}
};
// stores the row,column and box values for a cell
// 0 based so -1 means not set.
struct RowColumnBox {
int row;
int column;
int box;
RowColumnBox() : row(-1), column(-1), box(-1) {;}
};
// returns an iterator pointing to the location of the given cell
// if it cannot return a valid iterator an exception is thrown
CellLocationMap::iterator GetCellMapLocation( int cell, CellLocationMap& map ) {
CellLocationMap::iterator it = map.find( cell );
if( it == map.end() ) {
std::pair<CellLocationMap::iterator, bool> location
= map.insert( std::make_pair( cell, RowColumnBox() ) );
_ASSERT( location.second );
it = location.first;
}
return it;
}
// helper class for setting the row value
struct AddRowValueToCell{
AddRowValueToCell( CellLocationMap::iterator& it, int row ) {
it->second.row = row;
}
};
// helper class for setting the column value
struct AddColumnValueToCell{
AddColumnValueToCell( CellLocationMap::iterator& it, int column ) {
it->second.column = column;
}
};
// helper class for setting the box value
struct AddBoxValueToCell{
AddBoxValueToCell( CellLocationMap::iterator& it, int box ) {
it->second.box = box;
}
};
// adds all the items in the groupvector to the appropriate cell location map
// use one of the helper structs above for the template
template <typename T>
class AddCellToCellMap {
const int item;
CellLocationMap& map;
public:
AddCellToCellMap(int i, CellLocationMap& m) : item(i), map(m) {;}
void operator() ( const GroupVector::value_type& value ) {
CellLocationMap::iterator it = GetCellMapLocation( value, map );
T( it, item );
}
};
// add a vector of cells(either row/column/box) to the cell location map
// use one of the helper classes above for the template
template <typename T>
class AddCellsToMap {
CellLocationMap& map;
public:
AddCellsToMap( CellLocationMap& m ) : map(m) {;}
void operator() ( const GroupVectorCollection::value_type& val ) {
std::for_each( val.second.begin(), val.second.end(), AddCellToCellMap<T>( val.first, map ) );
}
};
// Contains maps for calculating row/column/box numbers from a given cell number
// and vice-versa
class VectorMap {
GroupVectorCollection rows;
GroupVectorCollection columns;
GroupVectorCollection boxes;
CellLocationMap cells;
static const int RowInc(int) { return 1; }
static const int ColumnInc( int size) { return GridLength( size ); }
// used for filling in the sequences for the rows/columns maps
void FillSequenceVector( GroupVectorCollection& col, int item, int inc, int start, int gridLength ) {
std::pair< GroupVectorCollection::iterator, bool>
insertPair = col.insert( std::make_pair( item, GroupVector() ));
std::generate_n( std::back_inserter( insertPair.first->second ),
gridLength, SequenceGenerator( inc, start ) );
}
// initialises the rows/columns/boxes maps
void InitCollectionMaps(int size) {
const int gridLength = GridLength(size);
for( int item = 0; item < gridLength; ++item ) {
int boxRow = item / size; int boxCol = item % size;
int box = boxCol + boxRow * size;
int boxStart = boxRow * GridLength(size) * size + boxCol * size;
int rowStart = item * GridLength(size); int colStart = item;
FillSequenceVector( rows, item, RowInc(size), rowStart, gridLength );
FillSequenceVector( columns, item, ColumnInc(size), colStart, gridLength );
// the box is a little more tricky so can't just call FillVector
std::pair< GroupVectorCollection::iterator, bool>
insertPair = boxes.insert( std::make_pair( item, GroupVector() ));
for( int i = 0; i < size; ++i ) {
std::generate_n( std::back_inserter(insertPair.first->second), size,
SequenceGenerator(RowInc(size), i * GridLength(size) + boxStart) );
}
}
}
// loops through the rows/columns/boxes and fills in the cell location map
void InitCellLocationMap(int size) {
std::for_each(rows.begin(), rows.end(), AddCellsToMap<AddRowValueToCell>(cells));
std::for_each(columns.begin(), columns.end(), AddCellsToMap<AddColumnValueToCell>(cells));
std::for_each(boxes.begin(), boxes.end(), AddCellsToMap<AddBoxValueToCell>(cells));
}
VectorMap(const VectorMap&);
VectorMap& operator=(const VectorMap&);
public:
VectorMap(int size)
{
InitCollectionMaps( size );
InitCellLocationMap(size );
}
// returns the row number for a given cell number
int GetRow( int cell ) const {
CellLocationMap::const_iterator it = cells.find(cell);
return it == cells.end() ? -1 : it->second.row;
}
// returns the column number for a given cell number
int GetColumn( int cell ) const {
CellLocationMap::const_iterator it = cells.find(cell);
return it == cells.end() ? -1 : it->second.column;
}
// returns the box number for a given cell number
int GetBox( int cell ) const {
CellLocationMap::const_iterator it = cells.find(cell);
return it == cells.end() ? -1 : it->second.box;
}
// need better error checking on these three accessors
const GroupVector& GetRowVector( int row ) const {
return rows.find( row )->second;
}
const GroupVector& GetColumnVector( int column ) const {
return columns.find( column )->second;
}
const GroupVector& GetBoxVector( int box ) const {
return boxes.find( box )->second;
}
};
// predicate for searching for cells with the right number of possibilities
struct CheckOptionCount
: public std::binary_function<GridMap::value_type, int, bool> {
bool operator()(const GridMap::value_type& value, const int& desiredOptionCount) const {
return (value.second.GetOptionCount() == desiredOptionCount);
}
};
class Grid {
const int gridSize;
int solvedCount;
GridMap grid;
VectorMapPtr map;
SolvedQueue solved;
Grid& operator=(const Grid&);
public:
// The initial grid is just 1d since we don't want to hard code in the 2d dimensions
Grid( int size, const int initialGrid[] ) : gridSize(size), map( new VectorMap(size)),
solvedCount(CellCount(size)) {
// generate a blank grid
std::generate_n( std::inserter( grid, grid.begin()), CellCount(size), CellInit(grid, gridSize));
//set the initial variables
const int gridLength = GridLength(size);
for(int row = 0; row < gridLength; ++ row ) {
for(int col = 0; col < gridLength; ++ col){
const int cell = row * gridLength + col;
if( initialGrid[cell] ) { // most cells are 0 at the start(ie. blank)
SetCellValue( cell, initialGrid[cell] );
}
}
}
SetSolvedQSolved();//start off solution
}
Grid( const Grid& obj ) : //copy constructor
gridSize(obj.gridSize),
map(obj.map),
solvedCount(obj.solvedCount),
solved(obj.solved),
grid(obj.grid){
}
// returns true if the grid is solved
bool IsGridSolved() const { return solvedCount == 0; }
int GetCellsToSolveCount() const { return solvedCount; }
VectorMapPtr GetMapPtr() const { return map; }
// returns true if there are items in the solved queue that need to be dealt to
bool IsSolvedQEmpty() const { return solved.empty(); }
// If we need to guess then returns the square with the least possible options
// i.e. searches first for cells that have only 2 possible values and then
// for cells with 3. (we want to find the cell with the best possible chance
// of picking the right cell
int GetBestGuessSquare() const {
if( IsGridSolved() ) {
return -1;
}
int result = -1;
const int maxCount = GridLength( gridSize ) + 1;
for(int desiredCount = 2; desiredCount < maxCount; ++ desiredCount ) {
GridMap::const_iterator it = std::find_if( grid.begin(), grid.end(), std::bind2nd( CheckOptionCount(), desiredCount ));
if( it != grid.end() ) {
result = it->first;
break;
}
}
return result;
}
void Guess(int cell, int guessNumber ) {
int value = grid.find(cell)->second.ApplyGuess( guessNumber );
_ASSERT( value );
AddCellToSolvedQueue( cell, value );
SetSolvedQSolved();
}
//check to see if the grid is in an invalid state ( useful after applying guesses )
bool IsGridValid() const {
GridMap::const_iterator it = std::find_if( grid.begin(), grid.end(), CheckGridValid(*this));
return it == grid.end();
}
// returns the current value of a given cell
int GetCellValue(int cell) const {
return grid.find(cell)->second.GetValue();
}
// returns a count of the available options
int GetOptionCount(int cell) const {
return grid.find(cell)->second.GetOptionCount();
}
// draws a grid to the ostream source -- the _T macro reduces readibility
void DisplayGrid( std::ostream& os ) const{
os << "\r\n";
const int gridLength = GridLength( gridSize );
for(int row = 0; row < gridLength; ++row ) {
for(int col = 0; col < gridLength; ++ col ) {
int cell = col + row * gridLength;
os << grid.find(cell)->second.GetValue() << " ";
}
os << "\r\n"; // new line
}
os << "\r\n";
}
private:
// helper class for initialising the blank grid
class CellInit {
int current;
const int size;
GridMap& map;
public:
CellInit(GridMap& m, int gridSize) : current(0), map(m),size(gridSize) {;}
GridMap::value_type operator()() {
return std::make_pair( current++, Cell(size));
}
};
// helper class for removing a value from a cell
class RemoveCellValue {
const int value;
Grid* grid;
public:
RemoveCellValue( int v , Grid* g ) :value(v), grid(g) {;}
void operator()( const GroupVector::value_type& cell ) {
// if there is notification of a forced select then add it to the
int solvedValue = grid->RemoveValue( cell, value );
if( solvedValue ) {
grid->AddCellToSolvedQueue( cell, solvedValue );
}
}
};
// searches to find if the grid is invalid - ie. true if invalid ( false if valid )
class CheckGridValid : public std::binary_function<GridMap::value_type, Grid, bool>
{
const Grid& grid;
public:
CheckGridValid(const Grid& g) : grid(g) {;}
bool operator()( const GridMap::value_type& value ) const {
const VectorMapPtr ptr = grid.GetMapPtr();
if(CheckVector( ptr->GetColumnVector( ptr->GetColumn( value.first )), value, grid ))
return true;
if(CheckVector( ptr->GetRowVector( ptr->GetRow( value.first )), value, grid ))
return true;
if(CheckVector( ptr->GetBoxVector( ptr->GetBox( value.first )), value, grid ))
return true;
return false;
}
private:
bool CheckVector( const GroupVector& vec, const GridMap::value_type& value, const Grid& grid ) const{
GroupVector::const_iterator it = std::find_if( vec.begin(), vec.end(), std::bind2nd( CheckCellValueExists(grid), value ) );
return it != vec.end();
}
};
// check that a cell matches the
class CheckCellValueExists : public std::binary_function<GroupVector::value_type, GridMap::value_type, bool>
{
const Grid& grid;
public:
CheckCellValueExists( const Grid& g ) : grid(g) {;}
bool operator()( const GroupVector::value_type& value, const GridMap::value_type& testValue ) const {
bool result = false;
if( testValue.second.GetValue() && value != testValue.first ) { //don't want to be comparing itself or checking zeros
result = ( grid.GetCellValue( value ) == testValue.second.GetValue() );
}
return result;
}
};
// sets a solved value
void SetCellValue( int cell, int value ) {
grid.find(cell)->second.SetValue( value );
RemoveSolvedValue( cell, value );
--solvedCount;
}
// removes a solved value from the other rows/columns/boxes
void RemoveSolvedValue( int cell, int value ) {
RemoveRowCellValue( map->GetRow( cell ), value );
RemoveColumnCellValue( map->GetColumn( cell ), value );
RemoveBoxCellValue( map->GetBox( cell ), value );
}
// removes a value from all the squares in a row
void RemoveRowCellValue( int row, int value ) {
std::for_each(map->GetRowVector(row).begin(), map->GetRowVector(row).end(), RemoveCellValue(value, this));
}
// removes a value from all the squares in a column
void RemoveColumnCellValue( int column, int value ) {
std::for_each(map->GetColumnVector(column).begin(), map->GetColumnVector(column).end(), RemoveCellValue(value, this));
}
// removes a value from all the squares in a box
void RemoveBoxCellValue( int box, int value ) {
std::for_each(map->GetBoxVector(box).begin(), map->GetBoxVector(box).end(), RemoveCellValue(value, this));
}
// removes a value from a cell
int RemoveValue( int cell, int value ) {
return grid.find(cell)->second.RemoveOption( value );
}
// adds a cell to the solved queue
void AddCellToSolvedQueue( int cell, int value ) {
solved.push( std::make_pair( cell, value) );
}
// loops throught the solved queue and removes the value from the rows/colums/boxes
void SetSolvedQSolved() {
while( !solved.empty() && solvedCount ) {
const CellValuePair pair = solved.front();
solved.pop();
RemoveSolvedValue( pair.first, pair.second );
--solvedCount;
}
}
};
// Stores a copy of the grid and the status of the guesses at a given point
class SolutionPoint {
GridPtr grid; // the grid before the guess
int guessCell; // the cell we are guessing
int guessNumber; // the guess number that we are going to try next(NOT THE VALUE OF THE GUESS )
int guessCount; // the number of possible guesses for that cell
public:
SolutionPoint( const Grid& g, int cell ) : grid( new Grid(g) ),
guessNumber(0), guessCell(cell) {
guessCount = g.GetOptionCount(cell);
}
bool TriedAllGuesses() const { return guessNumber == guessCount; }
// applies the next guess to a copy of the stored grid
// returns a pointer the the grid once it is solved
GridPtr ApplyNextGuess() {
_ASSERT( !TriedAllGuesses() );
GridPtr ptr = GridPtr( new Grid( *grid ) );
ptr->Guess( guessCell, guessNumber++ );
return ptr;
}
};
// Class that performs the solving of the grid
class GridSolver {
GridPtr mainGrid; // the grid on which all the working is performed
bool solved; // is the current mainGrid solved
GridSolver(const GridSolver&);
GridSolver& operator=(const GridSolver&);
public:
GridSolver( int size, const int initialGrid[] ) :
mainGrid( new Grid( size, initialGrid)) {
solved = mainGrid->IsGridSolved();
_ASSERT( mainGrid->IsGridValid()); // this will pick up bad initial grids ( at least in debug )
}
// call this to solve the grid
bool Solve() {
if( !solved )
RecursiveGuessLoop( CreateGuessPoint() );
_ASSERT( !solved || mainGrid->IsGridValid() );
return solved;
}
void DisplayGrid( std::ostream& os ) const {
mainGrid->DisplayGrid( os );
}
private:
// recursive function for applying guesses until we find a solution
// ( or run out of guesses )
void RecursiveGuessLoop( const SolutionPointPtr& ptr ) {
while(!solved && !ptr->TriedAllGuesses() ) {
mainGrid = ptr->ApplyNextGuess();
if( !mainGrid->IsGridSolved() ) {
RecursiveGuessLoop( CreateGuessPoint() ); // recursion
} else if( mainGrid->IsGridValid() ) {
solved = true;
break;
}
}
}
// just a convient function to help me type a long line -> I'm too lazy
inline SolutionPointPtr CreateGuessPoint() const{
return SolutionPointPtr( new SolutionPoint( *mainGrid, mainGrid->GetBestGuessSquare() ));
}
};
const int puzzle2[] = {
1,0,0,2,
0,2,0,0,
0,0,4,0,
0,3,0,0 };
const int puzzleTest[] = {
0,6,0,1,0,4,0,5,0,
0,0,8,3,0,5,6,0,0,
2,0,0,0,0,0,0,0,1,
8,0,0,4,0,7,0,0,6,
0,0,6,0,0,0,3,0,0,
7,0,0,9,0,1,0,0,4,
5,0,0,0,0,0,0,0,2,
0,0,7,2,0,6,9,0,0,
0,4,0,5,0,8,0,7,0 };
const int puzzlePress1[] = {
7,0,0,4,0,0,3,0,0,
0,0,0,0,0,1,7,0,0,
0,2,0,0,0,0,9,0,1,
0,0,1,0,4,0,2,0,0,
0,6,0,8,9,7,0,3,0,
0,0,8,0,2,0,5,0,0,
3,0,9,0,0,0,0,1,0,
0,0,7,9,0,0,0,0,0,
0,0,2,0,0,5,0,0,3 };
const int puzzleHard1[] = {
6,0,0,0,0,0,0,4,0,
0,0,5,0,0,2,0,0,7,
7,2,9,0,0,0,0,0,3,
0,9,0,0,4,0,0,0,1,
0,0,0,0,6,0,0,0,0,
4,0,0,0,8,0,0,7,0,
3,0,0,0,0,0,1,6,5,
2,0,0,4,0,0,8,0,0,
0,5,0,0,0,0,0,0,4 };
const int puzzleHard2[] = {
0,0,9,0,8,0,0,0,4,
0,6,0,0,0,0,0,0,8,
5,2,8,0,6,0,1,7,0,
2,0,0,7,0,0,0,0,5,
0,0,0,4,0,6,0,0,0,
9,0,0,0,0,1,0,0,6,
0,9,7,0,3,0,4,6,1,
6,0,0,0,0,0,0,3,0,
3,0,0,0,4,0,9,0,0 };
int _tmain(int argc, _TCHAR* argv[])
{
GridSolver solver(3, puzzleTest);
std::cout << "Solved = " << solver.Solve() << std::endl;
solver.DisplayGrid(std::cout);
GridSolver solver2(2, puzzle2);
std::cout << "Solved = " << solver2.Solve() << std::endl;
solver2.DisplayGrid(std::cout);
GridSolver solver3(3, puzzlePress1);
std::cout << "Solved = " << solver3.Solve() << std::endl;
solver3.DisplayGrid(std::cout);
GridSolver solver4(3, puzzleHard2);
std::cout << "Solved = " << solver4.Solve() << std::endl;
solver4.DisplayGrid(std::cout);
GridSolver solver5(3, puzzleHard1);
std::cout << "Solved = " << solver5.Solve() << std::endl;
solver5.DisplayGrid(std::cout);
return 0;
}
By some miracle it is looking pretty good - ( I managed to correct a bug in my recursive function which was causing some grief )
Here is a brief explanation of what I think I did ( any resemblance to actual code is purely coincidental )
Notes:
1) There are quite a few classes just used as predicates for stl algorithms
2) The grid dimensions are given as 2 for a 4x4, 3 for a 9x9, 4 for a 16x16 etc and the solver should be able to solve any of these...(the 2x2 test works well
3) The main classes:
Options holds a list of the possible values for a cell basically just a vector that starts of with all the possible numbers (1...9) and erases them as they are no longer a possibilty
Cell A representation of a sudoku cell. Stores a value for the cell (0 if unassigned ) and a list of possible options for the cell.
Grid Contains a map of all the cells in the sudoku grid. Cells are number from 0 at the top left corner the the 1,2,3 moving along the row and finally 81 in the bottom right hand corner.
VectorMap Basically maps a cell number to a row number, column number, and box number. Also contains lists of all the cells each row/column/box.
SolutionPoint Keeps track of the current guess we are making.
GridSolver Implements the recursive solving mechanism.
All the other class/struct are just helpers for the stl functions i.e. std::find_if, std::for_each, etc
How it works:
1) In the grid constructor:
a) Creates a blank grid with each cell having all options available.
b) Starts adding the given numbers. This involves setting the value in the cell and removing that value as an option from the other cells in the same row/column/box.
note: as options are removed from a cell, that cell may reach the point where there is only one remaining value and hence is solved. In this case the cell is added to the solved queue.
c) Iterates through the solved queue and removes value of the solved cell from the option list in the same row/column/box
For easy/medium puzzles step c is usually self sustaining and when it is completed the puzzle is solved.
If this is not the case then we need some more advanced logic, or for the lazy, guessing. I went with guessing.
2) In the GridSolver.Solve Function
- check that the grid was not solved as described above. Then guess
a) find the first cell with the minimum of options ( so there is a good chance of guessing correctly ) ie. search for cells with 2 possibilties then 3..4..5 etc
b) Choose the next guess ( storing a copy of the current grid /which guess etc )
c) Iterates through the solved queue and removes value of the solved cell from the option list in the same row/column/box
d) Check if there is a solution -> (no) goto step a (yes)continue
e) Check if the solution is valid -> (no) retreat to the last guess point and goto step b (yes) solved!!!!111!!!!one1!!!11eleven!!!!
steps a-d are implemented as a recursive function.
The solver should work