Project 2: Eight Numbers in a Cross Write a program which allocates the integers 1-8 to...

Transcribed Image Text:

Project 2: Eight Numbers in a Cross Write a program which allocates the integers 1-8 to the squares in the figure above, subject to the restrictions that no two adjacent squares contain consecutive integers. By adjacent we mean vertically, horizontally, or diagonally. Please provide both recursive solution and backtrack solution. Submission detail: Two independent cpp files should be submitted. 50 pt-Backtrack solution 50 pt - Recursive solution 8 number Eight Number in a Cross In the solution to this problem, use the backtracking scheme that we covered in class. Write a program which allocates the integers 1-8 to the squares in the figure above, subject to the restrictions that no two adjacent squares contain consecutive integers. By adjacent we mean vertically, horizontally, or diagonally. Eight Number in a Cross By-Hand Algorithm to. Obtain Adjacency Table 1) Label cross boxes arbitrarily from 0 through 7. 2) for each box i=0., 1.... 7: for each adjacent box k (such that k <i): add k to i's neighbor list add-1 to i's neighbor list 3) From the adjacency table obtained, create a look up in the form of a 2D array Cross: Box # 0 Box # 0 1 0 Neighbor List -1 Neighbor List -1 0,-1 3 o 5 6 A 2 3 2 3 7 5 6 5 6 7 7 Box # 0 1 2 Box # 0 1 2 3 Box # 0 1 2 3 4 Box # 0 1 2 3 4 S Neighbor List -1 0,-1 0, 1,-1 Neighbor List -1 0,-1 0,1,-1 0, 2, -1 Neighbor List -1 0,-1 0,1,-1 0,2,-1 1.2.-1 Neighbor List -1 0,-1 0,1,-1 0, 2, -1 1,2,-1 1,2,3,4,-1 O 0 0 1 2 3 2 3 2 3 1 2 3 S 5 6 5 6 6 5 6 7 7 7 7 Box # 0 1 2 3 4 S 6 Box # 0 1 2 3 4 S 6 7 Neighbor List -1 0.1.-1 0,2,-1 1,2,-1 1,2,3,4,-1 2, 3, 5, -1 Neighbor List -1 0,-1 0,1,-1 0,2,-1 1,2,-1 1,2,3,4,-1 2,3,5,-1 4, 5, 6,-1 {0, -1}, //box 1 {0, 1, -1}, //box 2 。 (0, 2,-1}, //box 3 {1, 2,-1}, //box 4 {1, 2, 3, 4, -1}, //box 5 {2, 3, 5, -1}, //box 6 {4, 5, 6, -1} //box 7 0 M 2 3 M 2 m 4 s 6 5 7 The Adjacency Table in C++ (Based on the Labeling Above) 115 columns because the largest neighbor list contains 5 numbers in our case int adj_table[8][5] = { //column size varies! {-1}, //box 0 7 Psuedo-Code for ok function bool okay(int cross[], int box) { static int adj_table[8][5] = {...}; do eight-queens style row-check here; if the test fails, return false //consecutive number check, notice that we only care to check the neighbors //of the current box, hence the need for the adjacency table i = 0; } neighbor_box = adj_table[box][i]; //this is the index of an adjacent box! while (neighbor_box != -1){ if (value at neighbor_box and cross[box] are consecutive) return false; move on to next neighbor box } return true; Project 2: Eight Numbers in a Cross Write a program which allocates the integers 1-8 to the squares in the figure above, subject to the restrictions that no two adjacent squares contain consecutive integers. By adjacent we mean vertically, horizontally, or diagonally. Please provide both recursive solution and backtrack solution. Submission detail: Two independent cpp files should be submitted. 50 pt-Backtrack solution 50 pt - Recursive solution 8 number Eight Number in a Cross In the solution to this problem, use the backtracking scheme that we covered in class. Write a program which allocates the integers 1-8 to the squares in the figure above, subject to the restrictions that no two adjacent squares contain consecutive integers. By adjacent we mean vertically, horizontally, or diagonally. Eight Number in a Cross By-Hand Algorithm to. Obtain Adjacency Table 1) Label cross boxes arbitrarily from 0 through 7. 2) for each box i=0., 1.... 7: for each adjacent box k (such that k <i): add k to i's neighbor list add-1 to i's neighbor list 3) From the adjacency table obtained, create a look up in the form of a 2D array Cross: Box # 0 Box # 0 1 0 Neighbor List -1 Neighbor List -1 0,-1 3 o 5 6 A 2 3 2 3 7 5 6 5 6 7 7 Box # 0 1 2 Box # 0 1 2 3 Box # 0 1 2 3 4 Box # 0 1 2 3 4 S Neighbor List -1 0,-1 0, 1,-1 Neighbor List -1 0,-1 0,1,-1 0, 2, -1 Neighbor List -1 0,-1 0,1,-1 0,2,-1 1.2.-1 Neighbor List -1 0,-1 0,1,-1 0, 2, -1 1,2,-1 1,2,3,4,-1 O 0 0 1 2 3 2 3 2 3 1 2 3 S 5 6 5 6 6 5 6 7 7 7 7 Box # 0 1 2 3 4 S 6 Box # 0 1 2 3 4 S 6 7 Neighbor List -1 0.1.-1 0,2,-1 1,2,-1 1,2,3,4,-1 2, 3, 5, -1 Neighbor List -1 0,-1 0,1,-1 0,2,-1 1,2,-1 1,2,3,4,-1 2,3,5,-1 4, 5, 6,-1 {0, -1}, //box 1 {0, 1, -1}, //box 2 。 (0, 2,-1}, //box 3 {1, 2,-1}, //box 4 {1, 2, 3, 4, -1}, //box 5 {2, 3, 5, -1}, //box 6 {4, 5, 6, -1} //box 7 0 M 2 3 M 2 m 4 s 6 5 7 The Adjacency Table in C++ (Based on the Labeling Above) 115 columns because the largest neighbor list contains 5 numbers in our case int adj_table[8][5] = { //column size varies! {-1}, //box 0 7 Psuedo-Code for ok function bool okay(int cross[], int box) { static int adj_table[8][5] = {...}; do eight-queens style row-check here; if the test fails, return false //consecutive number check, notice that we only care to check the neighbors //of the current box, hence the need for the adjacency table i = 0; } neighbor_box = adj_table[box][i]; //this is the index of an adjacent box! while (neighbor_box != -1){ if (value at neighbor_box and cross[box] are consecutive) return false; move on to next neighbor box } return true;