rendered paste body#include <vector>
#include <stdlib.h>
#include <iostream>
#include <stdio.h>
using namespace std;
enum CellType {
RULECELL,
NUMBERCELL
};
class Rule;
class Cell {
public:
Cell() : colRule(NULL), rowRule(NULL), painted(false) {}
Cell(Rule *cr, Rule *rr) : colRule(cr), rowRule(rr), painted(false) {
}
virtual CellType type() = 0;
Rule* getRowRule() {
return rowRule;
}
Rule* getColRule() {
return colRule;
}
bool painted;
protected:
Rule* colRule;
Rule* rowRule;
};
class NumberCell : public Cell {
public:
NumberCell(Rule *cr, Rule *rr);
int getNumber() {
return number;
}
bool canPutNumber(int number);
void setNumber(int number);
virtual CellType type() {
return NUMBERCELL;
}
private:
int number;
};
class Rule {
public:
Rule(int thesum) : sum(thesum), currentSum(0), numberOfOccupiedCells(0){ }
bool isValid() {
return cells.size() > 1;
}
bool CanPutNumber(int number)
{
// Check that the number is unique
for (unsigned int i = 0; i < cells.size(); i++)
{
if (cells[i]->getNumber() == number)
{
return false;
}
}
// Make sure we don't overflow
if (number + currentSum > sum ||
(number + currentSum == sum && numberOfOccupiedCells < (int)cells.size() - 1))
{
return false;
}
// And that if we are the last one, it has to sum up
if (numberOfOccupiedCells == (int)cells.size() - 1 &&
number + currentSum != sum)
{
return false;
}
return true;
}
void addNumberCell(NumberCell *cell) {
cells.push_back(cell);
}
int sum;
vector<NumberCell*> cells;
int currentSum;
int numberOfOccupiedCells;
private:
};
NumberCell::NumberCell(Rule *cr, Rule *rr) : Cell(cr, rr), number(0) {
rr->addNumberCell(this);
cr->addNumberCell(this);
}
bool NumberCell::canPutNumber(int number)
{
return (rowRule->CanPutNumber(number) && colRule->CanPutNumber(number));
}
void NumberCell::setNumber(int number)
{
// If we had a previous number, remove from the rules current sums
if (this->number != 0)
{
rowRule->currentSum -= this->number;
rowRule->numberOfOccupiedCells--;
colRule->currentSum -= this->number;
colRule->numberOfOccupiedCells--;
}
this->number = number;
if (number != 0)
{
rowRule->currentSum += this->number;
rowRule->numberOfOccupiedCells++;
colRule->currentSum += this->number;
colRule->numberOfOccupiedCells++;
}
}
std::vector<Rule *> rules;
class RuleCell : public Cell {
public:
RuleCell(int colN, int rowN) {
if (colN != -1) {
colRule = new Rule(colN);
rules.push_back(colRule);
}
if (rowN != -1) {
rowRule = new Rule(rowN);
rules.push_back(rowRule);
}
}
virtual CellType type(){
return RULECELL;
}
};
Cell* leftOf(Cell *board[10][10], int x, int y) {
if (x <= 0) {
return NULL;
}
return board[y][x-1];
}
Cell* topOf(Cell *board[10][10], int x, int y) {
if (y <= 0) {
return NULL;
}
return board[y-1][x];
}
bool check_rules(int N) {
for (unsigned int j = 0; j < rules.size(); j++) {
if (!rules[j]->isValid()) {
return false;
}
}
return true;
}
vector<NumberCell*> numberCells;
// Returns the size of the board if succeed. Fails if a number cell is missing a rule. Returns -1 on failure;
int read_input(Cell *board[10][10]) {
int N;
cin >> N;
for (int j = 0; j < N; j++) {
for (int i = 0; i < N; i++) {
int colN, rowN;
cin >> colN >> rowN;
// If it is a number cell
if (colN == 0 && rowN == 0) {
// Check if we have a rule and col rule
Cell *left = leftOf(board, i, j);
Cell *top = topOf(board, i, j);
if (!left || !top) {
goto fred;
}
Rule *rowRule = left->getRowRule();
Rule *colRule = top->getColRule();
if (!rowRule || !colRule) {
goto fred;
}
// Looks good
NumberCell *cell = new NumberCell(colRule, rowRule);
numberCells.push_back(cell);
board[j][i] = cell;
} else {
board[j][i] = new RuleCell(colN, rowN);
}
}
}
return N;
fred:
return -1;
}
void MultipleSolution()
{
cout << "No Unique Solution";
exit(0);
}
bool solutionFound = false;
void CheckSolutions(vector<NumberCell*>& cells, int index)
{
if (index == (int)cells.size())
{
if (solutionFound == true)
{
MultipleSolution();
}
else
{
solutionFound = true;
}
return;
}
for (int i = 1; i <= 9; i++)
{
if(cells[index]->canPutNumber(i))
{
cells[index]->setNumber(i);
CheckSolutions(cells, index + 1);
cells[index]->setNumber(0);
}
}
// Before backtracking, better set the number back to 0
cells[index]->setNumber(0);
return;
}
void CheckForSolutions(vector<NumberCell*>& cells)
{
CheckSolutions(cells, 0);
if (solutionFound == false)
{
cout << "No Solution";
}
else
{
cout << "Valid Puzzle";
}
exit(0);
}
void paint(Cell *board[10][10], int N, int x, int y) {
if (x < 0 || x >= N) {
return;
}
if (y < 0 || y >= N) {
return;
}
if (board[y][x]->type() == NUMBERCELL && !board[y][x]->painted) {
board[y][x]->painted = true;
paint(board, N, x + 1, y);
paint(board, N, x - 1, y);
paint(board, N, x, y - 1);
paint(board, N, x, y + 1);
}
}
bool MSPaint(Cell *board[10][10], int N)
{
// Find the first numberCell
for(int j = 0; j < N; j++)
{
for(int i = 0; i < N; i++)
{
if (board[j][i]->type() == NUMBERCELL) {
paint(board, N, i, j);
goto out;
}
}
}
out:
for(int j = 0; j < N; j++)
{
for(int i = 0; i < N; i++)
{
if (board[j][i]->type() == NUMBERCELL && !board[j][i]->painted) {
return false;
}
}
}
return true;
}
int main() {
Cell *board[10][10];
int N = read_input(board);
if (N == -1) {
printf("Invalid Puzzle Structure");
return 0;
}
if (rules.size() == 0)
{
printf("Invalid Puzzle Structure");
return 0;
}
if (!check_rules(N)) {
printf("Invalid Puzzle Structure");
return 0;
}
if (!MSPaint(board, N)) {
printf("Invalid Puzzle Structure");
return 0;
}
CheckForSolutions(numberCells);
return 0;
}