Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // AIProject2.cpp : This file contains the 'main' function. Program execution begins and ends there.
- //
- #include "pch.h"
- #include <iostream>
- #include <fstream>
- #include <string>
- #include <queue>
- #include <vector>
- using namespace std;
- struct Tile {
- Tile () {}
- int data;
- //Degree Heuristic
- int degreeHeuristic = 0;
- //MRV Heuristic
- int amountLegal = 9;
- vector<bool> legalValues = { true, true, true, true, true, true, true, true, true };
- };
- struct stateData {
- //For rows and columns
- stateData() {}
- int amountFilled = 0;
- vector<vector<Tile>> tilesState;
- };
- void amountFilledFunc(stateData& initial) {
- int amountFilledEval = 0;
- for (int i = 0; i < 9; i++) {
- for (int j = 0; j < 9; j++) {
- if (initial.tilesState[i][j].data != 0) {
- amountFilledEval++;
- }
- }
- }
- initial.amountFilled = amountFilledEval;
- }
- vector<Tile*> minimumRemainingValueHeuristics(stateData& initial) {
- int miniHeur = INT_MAX;
- Tile* miniHeurTile = &initial.tilesState[0][0];
- //Run this initial check trying to find the minimum remaining values heurstic for each tile, returning the min tile
- for (int i = 0; i < 9; i++) {
- for (int j = 0; j < 9; j++) {
- if (initial.tilesState[i][j].data != 0) {
- continue;
- }
- if (initial.tilesState[i][j].amountLegal < miniHeur) {
- miniHeurTile = &initial.tilesState[i][j];
- miniHeur = initial.tilesState[i][j].amountLegal;
- }
- }
- }
- vector<Tile*> miniHeurTileVector;
- miniHeurTileVector.push_back(miniHeurTile);
- //Want to run this check a second time to see if there are any tiles with same MRV value!!
- for (int i = 0; i < 9; i++) {
- for (int j = 0; j < 9; j++) {
- if (initial.tilesState[i][j].data != 0) {
- continue;
- }
- if (initial.tilesState[i][j].amountLegal == miniHeur) {
- //The fact we are here means we need to run Heuristic 2
- miniHeurTile = &initial.tilesState[i][j];
- miniHeurTileVector.push_back(miniHeurTile);
- }
- }
- }
- return miniHeurTileVector;
- }
- //Highest Number of unassigned neighbors!
- Tile* degreeHeuristic(vector<Tile*>& tileToConsider) {
- int miniHeur = INT_MAX;
- Tile* miniHeurTile =tileToConsider[0];
- //Run this initial check trying to find the minimum degree heuristics for each tile, returning the min tile
- //This list is obtained from the tiles we got in our first heuristic!! The ties!
- for (size_t i = 0; i < tileToConsider.size(); i++) {
- if (tileToConsider[i]->data != 0) {
- continue;
- }
- if (tileToConsider[i]->degreeHeuristic < miniHeur) {
- miniHeur = tileToConsider[i]->degreeHeuristic;
- miniHeurTile = tileToConsider[i];
- }
- }
- return miniHeurTile;
- }
- bool forwardChecking(stateData& initial) {
- //Needed for later
- bool reDo = false;
- for (int i = 0; i < 9; i++) {
- for (int j = 0; j < 9; j++) {
- int amountLegalTemp = 9;
- int amountDegreeTemp = 0;
- int evalValue = initial.tilesState[i][j].data;
- if (evalValue != 0) {
- continue;
- }
- //Col evaluation
- for (int col = 0; col < 9; col++) {
- //Find out column discrepencies for filled tiles
- int colEvalLegal = initial.tilesState[i][col].data;
- if (colEvalLegal != 0 && (initial.tilesState[i][j].legalValues[colEvalLegal - 1])) {
- initial.tilesState[i][j].legalValues[colEvalLegal - 1] = false;
- //Just to state, this will be our MRV evaluation
- amountLegalTemp -= 1;
- }
- else if (colEvalLegal == 0) {
- //This will be our degree Heurstic Evaluation
- amountDegreeTemp++;
- }
- }
- //Row Evaluation
- for (int row = 0; row < 9; row++) {
- //Find out row discrepencies for filled tiles
- int rowEvalLegal = initial.tilesState[row][j].data;
- if (rowEvalLegal != 0 && (initial.tilesState[i][j].legalValues[rowEvalLegal - 1])) {
- initial.tilesState[i][j].legalValues[rowEvalLegal - 1] = false;
- amountLegalTemp -= 1;
- }
- else if (rowEvalLegal == 0) {
- amountDegreeTemp++;
- }
- }
- //Block Evaluation
- //Find the block row and column
- int blockRow = i / 3;
- int blockCol = j / 3;
- //Evaluate all 9 blocks, from 1st to 9nth
- if (blockRow == 0 && blockCol == 0) {
- for (int row = 0; row < 3; row++) {
- for (int col = 0; col < 3; col++) {
- //Find out block discrepencies for filled tiles
- int blockEvalLegal = initial.tilesState[row][col].data;
- if (blockEvalLegal != 0 && (initial.tilesState[i][j].legalValues[blockEvalLegal - 1])) {
- initial.tilesState[i][j].legalValues[blockEvalLegal - 1] = false;
- amountLegalTemp -= 1;
- }
- else if (blockEvalLegal == 0) {
- amountDegreeTemp++;
- }
- }
- }
- }
- else if (blockRow == 0 && blockCol == 1) {
- for (int row = 0; row < 3; row++) {
- for (int col = 3; col < 6; col++) {
- int blockEvalLegal = initial.tilesState[row][col].data;
- if (blockEvalLegal != 0 && (initial.tilesState[i][j].legalValues[blockEvalLegal - 1])) {
- initial.tilesState[i][j].legalValues[blockEvalLegal - 1] = false;
- amountLegalTemp -= 1;
- }
- else if (blockEvalLegal == 0) {
- amountDegreeTemp++;
- }
- }
- }
- }
- else if (blockRow == 0 && blockCol == 2) {
- for (int row = 0; row < 3; row++) {
- for (int col = 6; col < 9; col++) {
- int blockEvalLegal = initial.tilesState[row][col].data;
- if (blockEvalLegal != 0 && (initial.tilesState[i][j].legalValues[blockEvalLegal - 1])) {
- initial.tilesState[i][j].legalValues[blockEvalLegal - 1] = false;
- amountLegalTemp -= 1;
- }
- else if (blockEvalLegal == 0) {
- amountDegreeTemp++;
- }
- }
- }
- }
- else if (blockRow == 1 && blockCol == 0) {
- for (int row = 3; row < 6; row++) {
- for (int col = 0; col < 3; col++) {
- int blockEvalLegal = initial.tilesState[row][col].data;
- if (blockEvalLegal != 0 && (initial.tilesState[i][j].legalValues[blockEvalLegal - 1])) {
- initial.tilesState[i][j].legalValues[blockEvalLegal - 1] = false;
- amountLegalTemp -= 1;
- }
- else if (blockEvalLegal == 0) {
- amountDegreeTemp++;
- }
- }
- }
- }
- else if (blockRow == 1 && blockCol == 1) {
- for (int row = 3; row < 6; row++) {
- for (int col = 3; col < 6; col++) {
- int blockEvalLegal = initial.tilesState[row][col].data;
- if (blockEvalLegal != 0 && (initial.tilesState[i][j].legalValues[blockEvalLegal - 1])) {
- initial.tilesState[i][j].legalValues[blockEvalLegal - 1] = false;
- amountLegalTemp -= 1;
- }
- else if (blockEvalLegal == 0) {
- amountDegreeTemp++;
- }
- }
- }
- }
- else if (blockRow == 1 && blockCol == 2) {
- for (int row = 3; row < 6; row++) {
- for (int col = 6; col < 9; col++) {
- int blockEvalLegal = initial.tilesState[row][col].data;
- if (blockEvalLegal != 0 && (initial.tilesState[i][j].legalValues[blockEvalLegal - 1])) {
- initial.tilesState[i][j].legalValues[blockEvalLegal - 1] = false;
- amountLegalTemp -= 1;
- }
- else if (blockEvalLegal == 0) {
- amountDegreeTemp++;
- }
- }
- }
- }
- else if (blockRow == 2 && blockCol == 0) {
- for (int row = 6; row < 9; row++) {
- for (int col = 0; col < 3; col++) {
- int blockEvalLegal = initial.tilesState[row][col].data;
- if (blockEvalLegal != 0 && (initial.tilesState[i][j].legalValues[blockEvalLegal - 1])) {
- initial.tilesState[i][j].legalValues[blockEvalLegal - 1] = false;
- amountLegalTemp -= 1;
- }
- else if (blockEvalLegal == 0) {
- amountDegreeTemp++;
- }
- }
- }
- }
- else if (blockRow == 2 && blockCol == 1) {
- for (int row = 6; row < 9; row++) {
- for (int col = 3; col < 6; col++) {
- int blockEvalLegal = initial.tilesState[row][col].data;
- if (blockEvalLegal != 0 && (initial.tilesState[i][j].legalValues[blockEvalLegal - 1])) {
- initial.tilesState[i][j].legalValues[blockEvalLegal - 1] = false;
- amountLegalTemp -= 1;
- }
- else if (blockEvalLegal == 0) {
- amountDegreeTemp++;
- }
- }
- }
- }
- else if (blockRow == 2 && blockCol == 2) {
- for (int row = 6; row < 9; row++) {
- for (int col = 6; col < 9; col++) {
- int blockEvalLegal = initial.tilesState[row][col].data;
- if (blockEvalLegal != 0 && (initial.tilesState[i][j].legalValues[blockEvalLegal - 1])) {
- initial.tilesState[i][j].legalValues[blockEvalLegal - 1] = false;
- amountLegalTemp -= 1;
- }
- else if (blockEvalLegal == 0) {
- amountDegreeTemp++;
- }
- }
- }
- }
- //THE ABOVE ARE REPEATS!! PLEASE REFER TO FIRST FEW COMMENTS
- //Check if one more legal values!!! If not we need to assign the value and then REDO forward checking
- if (amountLegalTemp == 1) {
- //Find out which one is true!
- for (int newValLegal = 0; newValLegal < 9; newValLegal++) {
- if (initial.tilesState[i][j].legalValues[newValLegal] == true) {
- initial.tilesState[i][j].data = newValLegal + 1;
- break;
- }
- }
- reDo = true;
- }
- //If no legal values, we want to RETURN FALSE
- if (amountLegalTemp <= 0) {
- return false;
- }
- initial.tilesState[i][j].amountLegal = amountLegalTemp;
- initial.tilesState[i][j].degreeHeuristic = amountDegreeTemp;
- }
- }
- if (reDo) {
- forwardChecking(initial);
- }
- //Done forward checking with no hassles!
- return true;
- }
- void inFile(vector<vector<Tile>>& tileStateVec, string documentName) {
- ifstream myfile;
- myfile.open(documentName);
- if (!myfile) {
- cerr << "Unable to open file datafile.txt";
- exit(1); // call system to stop
- }
- //Copy all our values into our 2D array of Tiles!
- int value = 0;
- for (int i = 0; i < 9; i++) {
- for (int j = 0; j < 9; j++) {
- myfile >> value;
- tileStateVec[i][j].data = value;
- }
- }
- myfile.close();
- }
- //FORWARD CHECKING LAST!
- bool backTracking(stateData& initial) { //Will either return a solution or a failure
- //Base case, don't continue if our entire board is filled up!
- amountFilledFunc(initial);
- if (initial.amountFilled == 81) {
- return true;
- }
- //Select an unassigned Tile and from there we want to test a value
- //Run minimumRemaininValueHeuristics to pick unassigned Tile
- vector<Tile*> checkVec = minimumRemainingValueHeuristics(initial);
- Tile* check = &initial.tilesState[0][0];
- if (checkVec.size() > 1) {
- //Run degreeHeuristics to pick unassigned Tile since first one failed
- check = degreeHeuristic(checkVec);
- }
- else if(checkVec.size() == 1) {
- check = checkVec[0];
- }
- //We picked an unassigned tile!!! We want to assign it a value!
- bool finalForwardCheck = false;
- bool finalBackTrackCheck = false;
- for (int valuetoAdd = 0; valuetoAdd < 9; valuetoAdd++) {
- //Check for consistency! If inconsistent, go to next value!
- if (check->legalValues[valuetoAdd] == false) {
- continue;
- }
- //ASSIGN AND DO A FORWARD CHECK WITH THAT VALUE
- check->data = valuetoAdd + 1;
- finalForwardCheck = forwardChecking(initial);
- if (finalForwardCheck == false) {
- continue; //Try with next value
- }
- finalBackTrackCheck = backTracking(initial);
- if (finalBackTrackCheck == true) {
- return true;
- }
- }
- return false;
- }
- int main()
- {
- //Empty Initial State Vector
- vector<vector<Tile>> tileStateVec(9, vector<Tile>(9));
- string documentName;
- //string destinationName;
- //String inputs are pretty explanatory
- cout << "Enter a file name with .txt extension: " << endl;
- cin >> documentName;
- /*
- cout << "Create a destination name with .txt extension:" << endl;
- cin >> destinationName;
- */
- //Read and put new values into our 9x9 2D vector
- inFile(tileStateVec, documentName);
- //Create our struct
- stateData initial;
- initial.tilesState = tileStateVec;
- //Find out the amount of filled tiles!
- amountFilledFunc(initial);
- //Forward Checking Here (initially)
- //THIS WILL ALSO UPDATE OUR HEURISTIC VALUES!!!!!!!!
- bool solvable = forwardChecking(initial);
- if (!solvable) {
- cout << "We can't solve this Sudoku board, please input a new one!" << endl;
- }
- //BACKTRACKING ALGORITHM
- solvable = backTracking(initial);
- if (!solvable) {
- cout << "We can't solve this Sudoku board, please input a new one!" << endl;
- }
- //PRINTING SOLUTION TO CONSOLE
- for (int i = 0; i < 9; i++) {
- for (int j = 0; j < 9; j++) {
- cout << initial.tilesState[i][j].data << " ";
- }
- cout << endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement