Project 2: Backtrack Project Eight Number 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: Fill the ok function for the template name p2_8n_ok.cpp Must use the template, and 0 will be given if template was not used. The Problem: You have n men and n woman, and their preference rankings of each other, and you need to match them up so that the total matching is "stable." The preference rankings: You are given 2nXn arrays, mp (men's preference) which gives the men's ranking of the women, and wp (women's preference) which gives the women's ranking of the men. So mp[i][j] gives man i's ranking of woman j and likewise for the women's ranking of the men in wp. For example in the following tables we have n=3 and the women and men are "named" 0,1 or 2 and the raking are in the range 0= highest, 1 second highest and 2 lowest. int mp[3][3]={0,2,1, 0,2,1, 1,2,0}; int wp[3][3]={2,1,0, 0,1,2, 2,0,1}; So man 1 assigns woman 2 the rank of 1 (i.e. second highest) and prefers woman 0 the best. What is a stable matching? A matching is stable if there are no "instabilities." Say the match assigns m1 to w1 and m2 to w2. An instability is the situation where there is a mutual greater preference for the other person's partner than for one's own. For example m1 would prefer w2 to w1 and likewise w2 prefers m1 to m2. The Problem: You have n men and n woman, and their preference rankings of each other, and you need to match them up so that the total matching is "stable." The preference rankings: You are given 2nXn arrays, mp (men's preference) which gives the men's ranking of the women, and wp (women's preference) which gives the women's ranking of the men. So mp[i][j] gives man i's ranking of woman j and likewise for the women's ranking of the men in wp. For example in the following tables we have n=3 and the women and men are "named" 0,1 or 2 and the raking are in the range 0= highest, 1 second highest and 2 lowest. intmp[3][3]={0,2,1,0,2,1,1,2,0};intwp[3][3]={2,1,0,0,1,2,2,0,1}; So man 1 assigns woman 2 the rank of 1 (i.e. second highest) and prefers woman 0 the best. What is a stable matching? A matching is stable if there are no "instabilities." Say the match assigns m1 to w1 and m2 to w2. An instability is the situation where there is a mutual greater preference for the other person's partner than for one's own. For example m1 would prefer w2 to w1 and likewise w2 prefers m1 to m2. Use the same approach that we used for the one dimensional eight queens problem. In the array q,q[i] is the woman assigned to man i. The main program stays the same, besides the limits on the loops. All that needs to change is the ok function. Is could look something like this: bool ok(int q[l, int col) col indicates the new man and q[col] the new woman proposed to be added to the match. We need to do 2 tests: 1. If the new woman has already been assigned to some man then return false 2. Check the new pair (new man, new woman) against each existing pair consisting of (current man, current woman) to see if the new pair would make the match unstable. So a. if the current man prefers the new woman to his partner and b. if the new woman prefers the current man to her partner i. this is unstable, so return false c. if the new man prefers the current woman to his partner and d. if the current woman prefers the new man to her partner i. This is unstable, so return false e. if there are no instabilities introduced with any of the existing (i.e. "current") couples, so we return true
