For this assignment, you need to implement three functions tocomplete a “Sudoku” project, which is a logic-based puzzle game fornumber placement. The Classic **Sudoku** is a numberplacing puzzle based on a 9×9 grid with several given numbers. Theobject is to place the numbers 1 to 9 in the empty squares so thateach row, each column and each 3×3 box contains the same numberonly once.

According to the constraint satisfaction problem (CSP), thedefinitions of these three functions are as follows:

**(1) bool CSP::goalCheck(const State state);**

This function does the goal checking job to check whether thecurrent variable assignment satisfies the constraints. If itsatisfies the constraints, it returns true; otherwise, it returnsfalse. This function is called by other functions such as“backtrack”, “forwardChecking”. So if you successfully define thegoalCheck(), it enables different algorithms to work and terminateproperly, such as back track, forward checking, and arc consistencychecking. For this function, you just need to determine true orfalse as a return value, which means you do not need to do anyupdate. The details of “State” structure will be describedbelow.

(2) **void CSP::updateDomain(const Statestate);** – Attention: for thisfunction, you need to modify a data member “variables[9][9]” in theCSP class.

This function is used to update the domain of each unassignedvariable according to the current assignment state. This functionis called by the “forwardChecking()” function. Just to make thingseasier, you do not need to know which variable was last assigned orwhat is the assignment sequence history. What you need to know is:which variables are assigned and which variables are not assignedyet (this information is provided by the input variable state). Youtask is: according to the assigned variable values, you need toupdate the domains of the remaining unassigned variables. In otherwords, the possible values in the domain of the unassignedvariables, should not conflict with the assigned variables.

(3) **void CSP::arcConsistency(const Statestate);** – Attention: for this function, you need to modifya data member “variables[9][9]” in the CSP class.

This function has a stronger constraint than the“udpateDomain()” function. Again, you need to update the domains ofthe “variables[9][9]” data member, according to the current state.As talked in the class, you can follow the pseducode to update thedomains of the unassigned variables based on the “tail” and “head”principle of an arrow.

**Project Documentation:**

Similar to your first/second projects, the GUI (graphical userinterface) framework is provided that is developed by C++ andOpenCV library. Below is the class structure highlight:

1. **VisualDisplay class** – This class deals withall the graphical or visual stuff, including pattern generationfrom an image, user mouse/keyboard interface, … (**You donot need to modify this class**).

3. **CSP class** – This is the class deals with thevariable assignment via different strategies. (**You arerequired to implement the three functions inside thisclass**).

3. **main.cpp** – This is just a simple file tostart the project. (**You do not need to modifyit**).

Also, to make the project run, you need to load the imagesinside the “imgs/” folder. For visual studio users, you can simplydownload the .rar file called “Sudoku_VisualStudio_Version.rar” andopen the solution “.sln” file to run it directly. The projectshould be able to load these images in the default directory. ForMac users, you can download the one called”Sudoku_Source_Files_Only.rar”. After unzip the files, make sure tocopy the “imgs/” folder to the directory where the “sudoku.exe”file locates.

**Two important variables: **

Variable variables[9][9];

State cur_state;

Both of the two variables are the data members of the CSP class.But only the first variable (variables[9][9]) needs to be updatedinside your implemented functions. For the second variable(cur_state), you do not need to update its value but just read it.Actually you do not need to read this variable directly, as it isgiven to you as the input parameter of your function – “const Statestate”. So you just need to read the information from “state”variable. They are the same.

(1) variable[9][9] – each variable represents a cell of thesudoku table. For example, variable[0][5] is the cell in the firstrow and the 6th column. The structure “Variable” definition is inthe header file “CSP.h”. It has two data members: domain andassignment. “domain” is a vector representing the possible valuescan be assigned for this variable. So it has at most nigh numbers.“assignment” is an integer, which presents the current assignmentfor this cell. The value can be any integer between 1 and 9. If itis 0, it means the current variable has not been assigned yet. Inyour implemented functions, you should update the domains of theseunassigned variables.

(2) cur_state – its structure is also defined in the “CSP.h”file. It only has one data member “values[9][9]” which has asimilar meaning as the assignment data member of the above“variables[9][9]”. For example, values[2][3] represents theassignment of the cell in the third row and the fourth column ofthe sudoku table. It can be any integer between 1 and 9. Again, ifit is 0, it means the cell has not been assigned yet.

(Hint: if you want to check whether a cell (ith row, jth column)has been assigned yet, you can use any of the three ways:cur_state.value[i-1][j-1] == 0, or variables[i-1][j-1].assignment== 0, or the function input parameter state.value[i -1][j-1] ==0)

**Requirements:**

(1) Successful goalCheck() to terminate the search (30%)

(2) Successful updateDomain() to support the forward checking(30%)

(3) Successful arcConsistency() to support the arc checking.(40%)

CSP.cpp

#include <stdio.h>

#include “CSP.h”

/************************************** Below are the threefunctions you need to implement***************************************/

/*Check whether current state satisfy the constraints*/

bool CSP::goalCheck(const State state)

{

return false;

}

/*Update Domain for the forward checking*/

void CSP::updateDomain(const State state)

{

}

/*Arc consistency use*/

void CSP::arcConsistency(const State state)

{

}

/************************************************ Endof Assignment ***********************************************/

## Expert Answer

Answer to For this assignment, you need to implement three functions to complete a “Sudoku” project, which is a logic-based pu…