SudokuPuzzle.h
#ifndef SudokuPuzzle_Header
#define SudokuPuzzle_Header
#include <vector>
using namespace std;
class SudokuPuzzle
{
public:
//Default constructor.
SudokuPuzzle();
//Returns a list of candidate values for a spot at (x, y).
void getPossibleValuesAt(int possibleSolutions[], int x, int y);
//Returns the number of possible candidates at (x, y).
int getNumberOfPossibleValuesAt(int x, int y);
//Attempts to add a number to (x, y). As long as the number
//is a valid candidate, the method returns true.
bool addNumberAt(int addNumber, int x, int y);
//Removes a number at (x, y)
void removeNumberAt(int x, int y);
//Resets the puzzle grid and solution list.
void newPuzzle();
//Prints the puzzle.
void printPuzzle();
//Returns a vector container of all the possible solutions
//found for the current puzzle.
void solvePuzzle();
//Determines whether or not the current puzzle is solved.
bool isSolved();
//Copies the puzzle into newPuzzle with a deep copy of the
//grid.
void copyPuzzle(SudokuPuzzle &newPuzzle);
//Shows a solution in the list of solutions at the
//specified index.
void showSolution(int index);
//Returns a solution in the list of solutions at the
//specified index.
SudokuPuzzle getSolution(int index);
//Returns the number of solutions in the list of solutions.
int getNumberOfSolutionsFound();
private:
//Two-dimensional grid to store the puzzle.
int myGrid[9][9];
//Dynamically expanding vector to store all possible solutions
//to the puzzle. Most puzzles only have 1 solution, but poorly
//designed puzzles may have many.
vector<SudokuPuzzle> possibleSolutions;
};
#endif
SudokuPuzzle.cpp
#include <iostream>
#include <cmath>
#include <vector>
#include "SudokuPuzzle.h"
using namespace std;
SudokuPuzzle::SudokuPuzzle()
{
//Default constructor. This constructor creates an empty Sudoku grid.
for (int x = 0; x < 9; x++)
{
for (int y = 0; y < 9; y++)
{
myGrid[x][y] = 0;
}
}
}
void SudokuPuzzle::getPossibleValuesAt(int possibleSolutions[], int x, int y)
{
//This function will use the array possibleSolutions as a hash table to
//determine the value of all candidates for the Sudoku grid at (x, y).
//The hash table is then used by the calling method to determine which
//candidates are allowed for that spot.
for (int index = 0; index < 9; index++)
{
possibleSolutions[index] = 1;
}
for (int xPos = 0; xPos < 9; xPos++)
{
if (xPos != x && myGrid[xPos][y] > 0) possibleSolutions[myGrid[xPos][y] - 1] = 0;
}
for (int yPos = 0; yPos < 9; yPos++)
{
if (yPos != y && myGrid[x][yPos] > 0) possibleSolutions[myGrid[x][yPos] - 1] = 0;
}
int xGroup = floor((double)(x / 3));
int yGroup = floor((double)(y / 3));
for (int xPos = 0 + (3 * xGroup); xPos < 3 + (3 * xGroup); xPos++)
{
for (int yPos = 0 + (3 * yGroup); yPos < 3 + (3 * yGroup); yPos++)
{
if (yPos != y && xPos != x && myGrid[xPos][yPos] > 0) possibleSolutions[myGrid[xPos][yPos] - 1] = 0;
}
}
return;
}
int SudokuPuzzle::getNumberOfPossibleValuesAt(int x, int y)
{
//This function will return the number of candidates available
//for the Sudoku grid at (x, y).
if (myGrid[x][y] != 0) return 0;
int possibleSolutions[9];
getPossibleValuesAt(possibleSolutions, x, y);
int candidateCount = 0;
for (int x = 0; x < 9; x++)
{
if (possibleSolutions[x] == 1) candidateCount++;
}
return candidateCount;
}
bool SudokuPuzzle::addNumberAt(int addNumber, int x, int y)
{
//This function will put in addNumber in the grid at (x, y) as long
//as addNumber is a valid candidate for that spot. A boolean is returned
//so the caller knows whether or not the number was successfully added.
if (addNumber == 0) return true;
if (myGrid[x][y] != 0)
{
cout << "The spot at (" << x << "," << y << ") is currently occupied.\n\n";
system("PAUSE");
return false;
}
int possibleSolutions[9];
getPossibleValuesAt(possibleSolutions, x, y);
if (possibleSolutions[addNumber - 1] == 0)
{
cout << addNumber << " is not a valid candidate for (" << x << "," << y << ").\n\n";
system("PAUSE");
return false;
}
myGrid[x][y] = addNumber;
return true;
}
void SudokuPuzzle::removeNumberAt(int x, int y)
{
//Remove one number.
myGrid[x][y] = 0;
}
void SudokuPuzzle::newPuzzle()
{
//Clears the grid.
for (int x = 0; x < 9; x++)
{
for (int y = 0; y < 9; y++)
{
myGrid[x][y] = 0;
}
}
}
void SudokuPuzzle::printPuzzle()
{
//Display the puzzle for implementation
//in a command-line environment.
cout << "\t0 1 2 3 4 5 6 7 8\n\n";
for (int y = 0; y < 9; y++)
{
cout << y << "\t";
for (int x = 0; x < 9; x++)
{
cout << myGrid[x][y] << " ";
if (x == 2 || x == 5) cout << " ";
}
if (y == 2 || y == 5 || y == 8) cout << "\n\n";
else cout << "\n";
}
}
bool SudokuPuzzle::isSolved()
{
//Determine if all spots are filled with valid candidates.
for (int x = 0; x < 9; x++)
{
for (int y = 0; y < 9; y++)
{
if (myGrid[x][y] == 0) return false;
}
}
return true;
}
void SudokuPuzzle::solvePuzzle()
{
//The puzzle solving algorithm. The algorithm scans each spot
//and starts with the spot that has the lowest number of
//possible candidates. Each candidate is tried one at a time
//and the rest of the spots are filled in the same manner.
//If a spot is found that is not yet filled, but there are no
//valid candidates, then the puzzle is unsolvable and a new
//candidate is tried in a previous spot.
int candidateX, candidateY, candidateNumber = 100, tempCandidate;
int candidateList[9];
for (int x = 0; x < 9; x++)
{
for (int y = 0; y < 9; y++)
{
if (myGrid[x][y] == 0)
{
tempCandidate = getNumberOfPossibleValuesAt(x, y);
if (tempCandidate < candidateNumber)
{
candidateNumber = tempCandidate;
candidateX = x;
candidateY = y;
getPossibleValuesAt(candidateList, x, y);
}
}
}
}
//All candidates have been determine for (candidateX, candidateY) where
//that spot has the least amount of candidates. Loop through those candidates
//and attempt to solve the next resulting puzzle.
for (int index = 0; index < 9; index++)
{
if (candidateList[index] == 1)
{
addNumberAt(index + 1, candidateX, candidateY);
if (isSolved())
{
SudokuPuzzle tempPuzzle;
copyPuzzle(tempPuzzle);
possibleSolutions.push_back(tempPuzzle);
}
else solvePuzzle();
removeNumberAt(candidateX, candidateY);
}
}
}
void SudokuPuzzle::copyPuzzle(SudokuPuzzle &newPuzzle)
{
//Deep copy the grid into newPuzzle.
for (int x = 0; x < 9; x++)
{
for (int y = 0; y < 9; y++)
{
newPuzzle.addNumberAt(myGrid[x][y], x, y);
}
}
}
void SudokuPuzzle::showSolution(int index)
{
//Show the solution in possibleSolutions at the specified index.
if (index < 0 || index >= possibleSolutions.size()) return;
possibleSolutions[index].printPuzzle();
}
SudokuPuzzle SudokuPuzzle::getSolution(int index)
{
//Return the solution in possibleSolutions at the specified index.
if (index < 0 || index >= possibleSolutions.size())
{
SudokuPuzzle newPuzzle;
return newPuzzle;
}
return possibleSolutions[index];
}
int SudokuPuzzle::getNumberOfSolutionsFound()
{
//Return the number of solutions in possibleSolutions.
return possibleSolutions.size();
}
