SHARE
TWEET

Untitled

a guest May 21st, 2019 72 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // AIProject2.cpp : This file contains the 'main' function. Program execution begins and ends there.
  2. //
  3.  
  4. #include "pch.h"
  5. #include <iostream>
  6. #include <fstream>
  7. #include <string>
  8. #include <queue>
  9. #include <vector>
  10.  
  11. using namespace std;
  12.  
  13. struct Tile {
  14.     Tile () {}
  15.     int data;
  16.     //Degree Heuristic
  17.     int degreeHeuristic = 0;
  18.     //MRV Heuristic
  19.     int amountLegal = 9;
  20.     vector<bool> legalValues = { true, true, true, true, true, true, true, true, true };
  21. };
  22.  
  23.  
  24. struct stateData {
  25.     //For rows and columns
  26.     stateData() {}
  27.     int amountFilled = 0;
  28.     vector<vector<Tile>> tilesState;
  29.    
  30. };
  31.  
  32.  
  33.  
  34.  
  35. void amountFilledFunc(stateData& initial) {
  36.     int amountFilledEval = 0;
  37.     for (int i = 0; i < 9; i++) {
  38.         for (int j = 0; j < 9; j++) {
  39.             if (initial.tilesState[i][j].data != 0) {
  40.                 amountFilledEval++;
  41.             }
  42.         }
  43.     }
  44.  
  45.     initial.amountFilled = amountFilledEval;
  46. }
  47.  
  48.  
  49.  
  50. vector<Tile*> minimumRemainingValueHeuristics(stateData& initial) {
  51.    
  52.     int miniHeur = INT_MAX;
  53.     Tile* miniHeurTile = &initial.tilesState[0][0];
  54.  
  55.  
  56.     //Run this initial check trying to find the minimum remaining values heurstic for each tile, returning the min tile
  57.     for (int i = 0; i < 9; i++) {
  58.         for (int j = 0; j < 9; j++) {
  59.  
  60.             if (initial.tilesState[i][j].data != 0) {
  61.                 continue;
  62.             }
  63.  
  64.             if (initial.tilesState[i][j].amountLegal < miniHeur) {
  65.                 miniHeurTile = &initial.tilesState[i][j];
  66.                 miniHeur = initial.tilesState[i][j].amountLegal;
  67.             }
  68.  
  69.  
  70.         }
  71.     }
  72.  
  73.     vector<Tile*> miniHeurTileVector;
  74.     miniHeurTileVector.push_back(miniHeurTile);
  75.  
  76.     //Want to run this check a second time to see if there are any tiles with same MRV value!!
  77.     for (int i = 0; i < 9; i++) {
  78.         for (int j = 0; j < 9; j++) {
  79.             if (initial.tilesState[i][j].data != 0) {
  80.                 continue;
  81.             }
  82.  
  83.             if (initial.tilesState[i][j].amountLegal == miniHeur) {
  84.                 //The fact we are here means we need to run Heuristic 2
  85.                 miniHeurTile = &initial.tilesState[i][j];
  86.                 miniHeurTileVector.push_back(miniHeurTile);
  87.             }
  88.         }
  89.     }
  90.  
  91.  
  92.     return miniHeurTileVector;
  93.  
  94.  
  95. }
  96.  
  97.  
  98. //Highest Number of unassigned neighbors!
  99. Tile* degreeHeuristic(vector<Tile*>& tileToConsider) {
  100.     int miniHeur = INT_MAX;
  101.     Tile* miniHeurTile =tileToConsider[0];
  102.  
  103.  
  104.     //Run this initial check trying to find the minimum degree heuristics for each tile, returning the min tile
  105.     //This list is obtained from the tiles we got in our first heuristic!! The ties!
  106.  
  107.     for (size_t i = 0; i < tileToConsider.size(); i++) {
  108.         if (tileToConsider[i]->data != 0) {
  109.             continue;
  110.         }
  111.  
  112.         if (tileToConsider[i]->degreeHeuristic < miniHeur) {
  113.             miniHeur = tileToConsider[i]->degreeHeuristic;
  114.             miniHeurTile = tileToConsider[i];
  115.         }
  116.     }
  117.  
  118.     return miniHeurTile;
  119. }
  120.  
  121. bool forwardChecking(stateData& initial) {
  122.  
  123.     //Needed for later
  124.     bool reDo = false;
  125.  
  126.     for (int i = 0; i < 9; i++) {
  127.         for (int j = 0; j < 9; j++) {
  128.  
  129.             int amountLegalTemp = 9;
  130.             int amountDegreeTemp = 0;
  131.  
  132.             int evalValue = initial.tilesState[i][j].data;
  133.             if (evalValue != 0) {
  134.                 continue;
  135.             }
  136.            
  137.  
  138.             //Col evaluation
  139.             for (int col = 0; col < 9; col++) {
  140.                 //Find out column discrepencies for filled tiles
  141.                 int colEvalLegal = initial.tilesState[i][col].data;
  142.                 if (colEvalLegal  != 0 && (initial.tilesState[i][j].legalValues[colEvalLegal - 1])) {
  143.                     initial.tilesState[i][j].legalValues[colEvalLegal - 1] = false;
  144.                     //Just to state, this will be our MRV evaluation
  145.                     amountLegalTemp -= 1;
  146.                 }
  147.                 else if (colEvalLegal == 0) {
  148.                     //This will be our degree Heurstic Evaluation
  149.                     amountDegreeTemp++;
  150.                 }
  151.             }
  152.  
  153.             //Row Evaluation
  154.             for (int row = 0; row < 9; row++) {
  155.                 //Find out row discrepencies for filled tiles
  156.                 int rowEvalLegal = initial.tilesState[row][j].data;
  157.                 if (rowEvalLegal != 0 && (initial.tilesState[i][j].legalValues[rowEvalLegal - 1])) {
  158.                     initial.tilesState[i][j].legalValues[rowEvalLegal - 1] = false;
  159.                     amountLegalTemp -= 1;
  160.                 }
  161.                 else if (rowEvalLegal == 0) {
  162.                     amountDegreeTemp++;
  163.                 }
  164.             }
  165.  
  166.             //Block Evaluation
  167.            
  168.             //Find the block row and column
  169.             int blockRow = i / 3;
  170.             int blockCol = j / 3;
  171.  
  172.             //Evaluate all 9 blocks, from 1st to 9nth
  173.             if (blockRow == 0 && blockCol == 0) {
  174.                 for (int row = 0; row < 3; row++) {
  175.                     for (int col = 0; col < 3; col++) {
  176.                         //Find out block discrepencies for filled tiles
  177.                         int blockEvalLegal = initial.tilesState[row][col].data;
  178.                         if (blockEvalLegal != 0 && (initial.tilesState[i][j].legalValues[blockEvalLegal - 1])) {
  179.                             initial.tilesState[i][j].legalValues[blockEvalLegal - 1] = false;
  180.                             amountLegalTemp -= 1;
  181.                         }
  182.                         else if (blockEvalLegal == 0) {
  183.                             amountDegreeTemp++;
  184.                         }
  185.                     }
  186.                 }
  187.             }
  188.             else if (blockRow == 0 && blockCol == 1) {
  189.                 for (int row = 0; row < 3; row++) {
  190.                     for (int col = 3; col < 6; col++) {
  191.                         int blockEvalLegal = initial.tilesState[row][col].data;
  192.                         if (blockEvalLegal != 0 && (initial.tilesState[i][j].legalValues[blockEvalLegal - 1])) {
  193.                             initial.tilesState[i][j].legalValues[blockEvalLegal - 1] = false;
  194.                             amountLegalTemp -= 1;
  195.                         }
  196.                         else if (blockEvalLegal == 0) {
  197.                             amountDegreeTemp++;
  198.                         }
  199.                     }
  200.                 }
  201.             }
  202.             else if (blockRow == 0 && blockCol == 2) {
  203.                 for (int row = 0; row < 3; row++) {
  204.                     for (int col = 6; col < 9; col++) {
  205.                         int blockEvalLegal = initial.tilesState[row][col].data;
  206.                         if (blockEvalLegal != 0 && (initial.tilesState[i][j].legalValues[blockEvalLegal - 1])) {
  207.                             initial.tilesState[i][j].legalValues[blockEvalLegal - 1] = false;
  208.                             amountLegalTemp -= 1;
  209.                         }
  210.                         else if (blockEvalLegal == 0) {
  211.                             amountDegreeTemp++;
  212.                         }
  213.                     }
  214.                 }
  215.             }
  216.             else if (blockRow == 1 && blockCol == 0) {
  217.                 for (int row = 3; row < 6; row++) {
  218.                     for (int col = 0; col < 3; col++) {
  219.                         int blockEvalLegal = initial.tilesState[row][col].data;
  220.                         if (blockEvalLegal != 0 && (initial.tilesState[i][j].legalValues[blockEvalLegal - 1])) {
  221.                             initial.tilesState[i][j].legalValues[blockEvalLegal - 1] = false;
  222.                             amountLegalTemp -= 1;
  223.                         }
  224.                         else if (blockEvalLegal == 0) {
  225.                             amountDegreeTemp++;
  226.                         }
  227.                     }
  228.                 }
  229.             }
  230.             else if (blockRow == 1 && blockCol == 1) {
  231.                 for (int row = 3; row < 6; row++) {
  232.                     for (int col = 3; col < 6; col++) {
  233.                         int blockEvalLegal = initial.tilesState[row][col].data;
  234.                         if (blockEvalLegal != 0 && (initial.tilesState[i][j].legalValues[blockEvalLegal - 1])) {
  235.                             initial.tilesState[i][j].legalValues[blockEvalLegal - 1] = false;
  236.                             amountLegalTemp -= 1;
  237.                         }
  238.                         else if (blockEvalLegal == 0) {
  239.                             amountDegreeTemp++;
  240.                         }
  241.                     }
  242.                 }
  243.             }
  244.             else if (blockRow == 1 && blockCol == 2) {
  245.                 for (int row = 3; row < 6; row++) {
  246.                     for (int col = 6; col < 9; col++) {
  247.                         int blockEvalLegal = initial.tilesState[row][col].data;
  248.                         if (blockEvalLegal != 0 && (initial.tilesState[i][j].legalValues[blockEvalLegal - 1])) {
  249.                             initial.tilesState[i][j].legalValues[blockEvalLegal - 1] = false;
  250.                             amountLegalTemp -= 1;
  251.                         }
  252.                         else if (blockEvalLegal == 0) {
  253.                             amountDegreeTemp++;
  254.                         }
  255.                     }
  256.                 }
  257.             }
  258.             else if (blockRow == 2 && blockCol == 0) {
  259.                 for (int row = 6; row < 9; row++) {
  260.                     for (int col = 0; col < 3; col++) {
  261.                         int blockEvalLegal = initial.tilesState[row][col].data;
  262.                         if (blockEvalLegal != 0 && (initial.tilesState[i][j].legalValues[blockEvalLegal - 1])) {
  263.                             initial.tilesState[i][j].legalValues[blockEvalLegal - 1] = false;
  264.                             amountLegalTemp -= 1;
  265.                         }
  266.                         else if (blockEvalLegal == 0) {
  267.                             amountDegreeTemp++;
  268.                         }
  269.                     }
  270.                 }
  271.             }
  272.             else if (blockRow == 2 && blockCol == 1) {
  273.                 for (int row = 6; row < 9; row++) {
  274.                     for (int col = 3; col < 6; col++) {
  275.                         int blockEvalLegal = initial.tilesState[row][col].data;
  276.                         if (blockEvalLegal != 0 && (initial.tilesState[i][j].legalValues[blockEvalLegal - 1])) {
  277.                             initial.tilesState[i][j].legalValues[blockEvalLegal - 1] = false;
  278.                             amountLegalTemp -= 1;
  279.                         }
  280.                         else if (blockEvalLegal == 0) {
  281.                             amountDegreeTemp++;
  282.                         }
  283.                     }
  284.                 }
  285.             }
  286.             else if (blockRow == 2 && blockCol == 2) {
  287.                 for (int row = 6; row < 9; row++) {
  288.                     for (int col = 6; col < 9; col++) {
  289.                         int blockEvalLegal = initial.tilesState[row][col].data;
  290.                         if (blockEvalLegal != 0 && (initial.tilesState[i][j].legalValues[blockEvalLegal - 1])) {
  291.                             initial.tilesState[i][j].legalValues[blockEvalLegal - 1] = false;
  292.                             amountLegalTemp -= 1;
  293.                         }
  294.                         else if (blockEvalLegal == 0) {
  295.                             amountDegreeTemp++;
  296.                         }
  297.                     }
  298.                 }
  299.             }
  300.            
  301.             //THE ABOVE ARE REPEATS!! PLEASE REFER TO FIRST FEW COMMENTS
  302.  
  303.             //Check if one more legal values!!! If not we need to assign the value and then REDO forward checking
  304.             if (amountLegalTemp == 1) {
  305.                 //Find out which one is true!
  306.                 for (int newValLegal = 0; newValLegal < 9; newValLegal++) {
  307.                     if (initial.tilesState[i][j].legalValues[newValLegal] == true) {
  308.                         initial.tilesState[i][j].data = newValLegal + 1;
  309.                         break;
  310.                     }
  311.                 }
  312.                
  313.                 reDo = true;
  314.             }
  315.  
  316.  
  317.             //If no legal values, we want to RETURN FALSE
  318.             if (amountLegalTemp <= 0) {
  319.                 return false;
  320.             }
  321.  
  322.             initial.tilesState[i][j].amountLegal = amountLegalTemp;
  323.             initial.tilesState[i][j].degreeHeuristic = amountDegreeTemp;
  324.  
  325.  
  326.         }
  327.     }
  328.  
  329.     if (reDo) {
  330.         forwardChecking(initial);
  331.     }
  332.  
  333.     //Done forward checking with no hassles!
  334.     return true;
  335.  
  336. }
  337.  
  338. void inFile(vector<vector<Tile>>& tileStateVec, string documentName) {
  339.     ifstream myfile;
  340.     myfile.open(documentName);
  341.  
  342.     if (!myfile) {
  343.         cerr << "Unable to open file datafile.txt";
  344.         exit(1);   // call system to stop
  345.     }
  346.  
  347.     //Copy all our values into our 2D array of Tiles!
  348.     int value = 0;
  349.     for (int i = 0; i < 9; i++) {
  350.         for (int j = 0; j < 9; j++) {
  351.             myfile >> value;
  352.             tileStateVec[i][j].data = value;
  353.            
  354.         }
  355.     }
  356.  
  357.  
  358.     myfile.close();
  359. }
  360.  
  361. //FORWARD CHECKING LAST!
  362. bool backTracking(stateData& initial) { //Will either return a solution or a failure
  363.  
  364.     //Base case, don't continue if our entire board is filled up!
  365.     amountFilledFunc(initial);
  366.     if (initial.amountFilled == 81) {
  367.         return true;
  368.     }
  369.  
  370.     //Select an unassigned Tile and from there we want to test a value
  371.    
  372.     //Run minimumRemaininValueHeuristics to pick unassigned Tile
  373.     vector<Tile*> checkVec = minimumRemainingValueHeuristics(initial);
  374.     Tile* check = &initial.tilesState[0][0];
  375.     if (checkVec.size() > 1) {
  376.         //Run degreeHeuristics to pick unassigned Tile since first one failed
  377.         check = degreeHeuristic(checkVec);
  378.     }
  379.     else if(checkVec.size() == 1) {
  380.         check = checkVec[0];
  381.     }
  382.  
  383.  
  384.  
  385.     //We picked an unassigned tile!!! We want to assign it a value!
  386.     bool finalForwardCheck = false;
  387.     bool finalBackTrackCheck = false;
  388.  
  389.     for (int valuetoAdd = 0; valuetoAdd < 9; valuetoAdd++) {
  390.         //Check for consistency! If inconsistent, go to next value!
  391.         if (check->legalValues[valuetoAdd] == false) {
  392.             continue;
  393.         }
  394.  
  395.         //ASSIGN AND DO A FORWARD CHECK WITH THAT VALUE
  396.         check->data = valuetoAdd + 1;
  397.         finalForwardCheck = forwardChecking(initial);
  398.         if (finalForwardCheck == false) {
  399.             continue; //Try with next value
  400.         }
  401.        
  402.         finalBackTrackCheck = backTracking(initial);
  403.         if (finalBackTrackCheck == true) {
  404.             return true;
  405.         }
  406.  
  407.  
  408.     }
  409.  
  410.     return false;
  411. }
  412. int main()
  413. {
  414.     //Empty Initial State Vector
  415.     vector<vector<Tile>> tileStateVec(9, vector<Tile>(9));
  416.  
  417.     string documentName;
  418.     //string destinationName;
  419.  
  420.     //String inputs are pretty explanatory
  421.     cout << "Enter a file name with .txt extension: " << endl;
  422.     cin >> documentName;
  423.    
  424.     /*
  425.     cout << "Create a destination name with .txt extension:" << endl;
  426.     cin >> destinationName;
  427.     */
  428.  
  429.     //Read and put new values into our 9x9 2D vector
  430.     inFile(tileStateVec, documentName);
  431.  
  432.     //Create our struct
  433.     stateData initial;
  434.     initial.tilesState = tileStateVec;
  435.  
  436.     //Find out the amount of filled tiles!
  437.     amountFilledFunc(initial);
  438.  
  439.     //Forward Checking Here (initially)
  440.     //THIS WILL ALSO UPDATE OUR HEURISTIC VALUES!!!!!!!!
  441.     bool solvable = forwardChecking(initial);
  442.     if (!solvable) {
  443.         cout << "We can't solve this Sudoku board, please input a new one!" << endl;
  444.     }
  445.  
  446.     //BACKTRACKING ALGORITHM
  447.     solvable = backTracking(initial);
  448.     if (!solvable) {
  449.         cout << "We can't solve this Sudoku board, please input a new one!" << endl;
  450.     }
  451.  
  452.  
  453.     //PRINTING SOLUTION TO CONSOLE
  454.     for (int i = 0; i < 9; i++) {
  455.         for (int j = 0; j < 9; j++) {
  456.             cout << initial.tilesState[i][j].data << " ";
  457.         }
  458.         cout << endl;
  459.     }
  460. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top