Advertisement
Guest User

Untitled

a guest
May 21st, 2019
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 11.96 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement