Min sudoku lösare

sudoku.cpp

/*
Sodoku Solver and Checker v1.1.
By serverhiccups, 2019.
This file is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International
The license is available here: https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode
*/
#include<vector>
#include<iostream>
#include<set>
#include<utility>

using namespace std;

typedef vector<vector<set<int> > > Board;

bool isSolved(set<int> &square) { // A simple function to tell you whether a sqaure is solved or not.
    if(square.size() == 1 && !(*square.begin() == 0)){ // This second check is in here so that we can have unsolved squares that don't have a calculated value.
		return true;
    }
    return false;
}

void printBoard(Board &board) { // This function prints the first (or only) possibility for each square on the board.
	for(int i = 0; i < 19; i++) {
		cout << "-";
	}
	cout << endl;
	for(int i = 0; i < 9; i++) {
		for(int j = 0; j < 9; j++) {
			cout << "|" << *board[i][j].begin(); // This function will *work* on unsolved boards, but it will only show the first possibility.
		}
		cout << "|" << endl;
	}
	for(int i = 0; i < 19; i++) {
		cout << "-";
	}
}

bool checkIfSolved(Board &board) { // This function only looks at each square once, so it is very fast.
	int rows[9] = {0};		// |
	int columns[9] = {0};	// | Initalise all counting arrays to 0
	int boxes[9] = {0};		// |
	int value = 0;
	for(int i = 0; i < 9; i++) { // For every square on the board
		for(int j = 0; j < 9; j++) {
			set<int>& square = board[i][j]; // Get the square
			if(isSolved(square)) { // That is solved
				value = *(square.begin()); // Retrieve the value
				rows[i] += value;							// |
				columns[j] += value;						// | Add the value to the appropriate sumation array.
				boxes[((int)i/3)*3 + (int)j/3] += value;	// |
			} else { // If a square hasn't been calculated or doesn't have a definite value, then of course it isn't solved.
				return false;
			}
		}
	}
	for(int i = 0; i < 9; i++){ // Check that everything adds up to the right amount. The reason we use 45 is because that is 1+2+3...8+9. It is possible to create a board that works for the rows and columns, but not for all three conditions.
		if(rows[i] != 45) return false;
		if(columns[i] != 45) return false;
		if(boxes[i] != 45) return false;
	}
	return true;
}

vector<pair<int, int> > getAffectedSquares(int x, int y) { // Returns a list of coordinates that affect the one given.
    vector<pair<int, int> > affectedSquares;
    int i = 0;
    for(i = 0; i < x; i++) {								// |
        affectedSquares.push_back(pair<int, int>(i, y));	// |
    }														// |
    for(i = x + 1; i < 9; i++) {							// |
        affectedSquares.push_back(pair<int, int>(i, y)); 	// |
    }														// | Adds the squares in the cardinal directions.
    for(i = 0; i < y; i++) {								// |
        affectedSquares.push_back(pair<int, int>(x, i));	// |
    }														// |
    for(i = y + 1; i < 9; i++) {							// |
        affectedSquares.push_back(pair<int, int>(x, i));	// |
    }														// |
    for(i = 1; i < 4; i++) { // This addes the squares from the box that it's in
        for(int j = 1; j < 4; j++) {
			if(i == 2 && j == 2) { // Makes sure that we don't add the coordinates of the square that we provided.
				continue;
			}
            affectedSquares.push_back(pair<int, int>(((int)x/3)*3-1+i, ((int)y/3)*3-1+j));
        }
    }
    return affectedSquares;
}

set<int> getPossibilites(int x, int y, Board &board) { // This just finds the possibilites for one square, because recalculating the whole thing everything wouldn't work and would also be a waste.
	set<int> possibilites {1,2,3,4,5,6,7,8,9}; // Start off by assuming that all numbers are possible in this square.
	for(auto i: getAffectedSquares(x, y)) { // Find the coordinates of the squares that affect this one
		if(isSolved(board[i.first][i.second])) { // Only look at the ones that are solved (ie. the ones that affect the result).
			if(possibilites.find(*board[i.first][i.second].begin()) != possibilites.end()) { // If a number is already taken that is available
				possibilites.erase(possibilites.find(*board[i.first][i.second].begin())); // Then delete it
			}
		}
	}
	return possibilites;
}

void dumbSolve(Board &board) { // This could be considered a logic solver. It can not solve the board when the is no logical way of finding one solution for every square.
    for(int i = 0; i < 9; i++) { // For all the squares on the board
        for(int j = 0; j < 9; j++) {
            if(!isSolved(board[i][j])) { // that are not solved
				board[i][j] = getPossibilites(i, j, board); // Get the possible options for that sqaure
            }
        }
    }
}

bool solve(int position, Board &problem) {
    if(position < 81) {
		int x = (int)position / 9; // Turn the integer position into x and y so it is easier to use with our datastructure.
        int y = position % 9;
        if(isSolved(problem[x][y])) { // If the square is already solved, try and solve the next square. This essentially makes already solved squares invisible to the backtracking algorithm.
            return solve(position + 1, problem);
        }
        set<int> possibilites = getPossibilites(x, y, problem); // If the square isn't solved, find the possibilites for that square.
		bool solvable = false; // Start off by assuming that the current square isn't solvable
		for(auto i: possibilites) { // until we can prove it is.
			problem[x][y] = set<int> {i}; // Try the first possibility
			if(solve(position + 1, problem)) { // If we can solve the next square (and because this is recursive, all squares after that).
				solvable = true; // Say that it is solvable
				break; // And break out of the loop because we are done.
			}
		}
		if(solvable) { // Tell the level of recursion above us that we could solve this square and all the next ones.
			return true;
		} else { // If we couldn't solve this square.
			problem[x][y] = set<int> {0}; // We have to do this, otherwise future calculations will think that this square is solved.
			return false; // Tell the level above us that we could solve it. If this is the top level (ie. position = 1) then we are telling the caller the the problem wasn't solvable
		}
    } else { // If we are asked a square off the board is solvable it means that the square before it was solved are we are done so return true.
        return true;
    }
}

int main() {
    Board board(9, vector<set<int> >(9, set<int>{})); // Initialise the board
    int readin = 0;
    for(int i = 0; i < 9; i++) {
        for(int j = 0; j < 9; j++) {
            cin >> readin;
            if(readin != 0) { // If the square isn't empty
                board[i][j] = set<int> {readin}; // Set the square to a solved (i.e one item that isn't 0) set with the value in it.
            } else {
                board[i][j] = set<int> {0}; // Set any unsolved squares to uncalculated.
            }
        }
    }
	solve(0, board); // Passing in 0 essentially starts in the top left corner.