For this assignment, you need to implement three functions to complete a Sudoku project, which is a logic-based puzzle game for number placement. The Classic Sudoku is a number placing puzzle based on a 9x9 grid with several given numbers. The object is to place the numbers 1 to 9 in the empty squares so that each row, each column and each 3x3 box contains the same number only once.

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

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

This function does the goal checking job to check whether the current variable assignment satisfies the constraints. If it satisfies the constraints, it returns true; otherwise, it returns false. This function is called by other functions such as backtrack, forwardChecking". So if you successfully define the goalCheck(), it enables different algorithms to work and terminate properly, such as back track, forward checking, and arc consistency checking. For this function, you just need to determine true or false as a return value, which means you do not need to do any update. The details of State structure will be described below.

(2) void CSP::updateDomain(const State state); - Attention: for this function, you need to modify a data member variables[9][9] in the CSP class.

This function is used to update the domain of each unassigned variable according to the current assignment state. This function is called by the forwardChecking() function. Just to make things easier, you do not need to know which variable was last assigned or what is the assignment sequence history. What you need to know is: which variables are assigned and which variables are not assigned yet (this information is provided by the input variable state). You task is: according to the assigned variable values, you need to update the domains of the remaining unassigned variables. In other words, the possible values in the domain of the unassigned variables, should not conflict with the assigned variables.

(3) void CSP::arcConsistency(const State state); - Attention: for this function, you need to modify a 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 of the variables[9][9] data member, according to the current state. As talked in the class, you can follow the pseducode to update the domains 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 user interface) framework is provided that is developed by C++ and OpenCV library. Below is the class structure highlight:

1. VisualDisplay class - This class deals with all the graphical or visual stuff, including pattern generation from an image, user mouse/keyboard interface, ... (You do not need to modify this class).

3. CSP class - This is the class deals with the variable assignment via different strategies. (You are required to implement the three functions inside this class).

3. main.cpp - This is just a simple file to start the project. (You do not need to modify it).

Also, to make the project run, you need to load the images inside the "imgs/" folder. For visual studio users, you can simply download the .rar file called "Sudoku_VisualStudio_Version.rar" and open the solution ".sln" file to run it directly. The project should be able to load these images in the default directory. For Mac users, you can download the one called "Sudoku_Source_Files_Only.rar". After unzip the files, make sure to copy 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 updated inside 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 is given to you as the input parameter of your function - const State state. 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 the sudoku table. For example, variable[0][5] is the cell in the first row and the 6th column. The structure Variable" definition is in the header file CSP.h. It has two data members: domain and assignment. domain is a vector representing the possible values can be assigned for this variable. So it has at most nigh numbers. assignment is an integer, which presents the current assignment for this cell. The value can be any integer between 1 and 9. If it is 0, it means the current variable has not been assigned yet. In your implemented functions, you should update the domains of these unassigned 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 a similar meaning as the assignment data member of the above variables[9][9]. For example, values[2][3] represents the assignment of the cell in the third row and the fourth column of the sudoku table. It can be any integer between 1 and 9. Again, if it 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

#include "CSP.h"

/************************************** Below are the three functions 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) {

}

/************************************************ End of Assignment ***********************************************/