Project Description: Implement the Backtracking Algorithm in Figure $3$ below to solve the Kropki Sudoku puzzle. The rules of the game are:

$-$ The game board consists of $\backslash (9\backslash$times $9\backslash )$ cells divided into $\backslash (3\backslash$times $3\backslash )$ non$-$overlapping blocks as shown below. Some of the cells already have digits $(1$ to $9)$ assigned to them initially.

$-$ The goal is to find assignments $(1$ to $9)$ for the empty cells so that every row, every column, and every $\backslash (3\backslash$times $3\backslash )$ block contains the digits from $1$ to $9$ exactly once.

$-$ A white dot between two adjacent cells requires that the value in one cell is exactly $1$ greater than the value of the other cell. This could be satisfied in either direction; e$.$g$.,"3\backslash (\backslash$& $4\backslash )"$ or $"\backslash (4\backslash$& $3\backslash )"$ will both satisfy the requirement. A black dot between two adjacent cells requires that the value in one cell is exactly double the value of the other cell. This also could be satisfied in either direction; e$.$g$.,"\backslash (3\backslash$& $6\backslash )"$ or $"\backslash (6\backslash$& $3\backslash )."$ If there is no dot between two adjacent cells, then neither condition needs to be fulfilled between the two cells.

Figure $2$ shows the solution for the puzzle in Figure $1.$

Figure $1.$ Initial game board

Figure $2.$ Solution

In the Backtracking Algorithm, use the minimum remaining value and degree heuristics to implement the SELECT$-$UNASSIGNED$-$VARIABLE function. For the ORDER$-$DOMAINVALUES function, simply order the domain values in increasing order from $1$ to $9$ instead of using heuristics. You can skip the INFERENCE function inside the Backtracking Algorithm in your implementation. $($Reminder: when implementing the minimum remaining value and degree heuristics, two or more variables are neighbors if they share one or more common constraints.$)$

Extra Credits $(20$ points$)$: This part is optional. Implement the INFERENCE function with Forward Checking in your implementation of the Backtracking Algorithm. If you do the extra credits part, indicate this in your PDF report. n n n n n n n n

n n n n n n n n

n nnnnnnn

nnnnnnnn

nnnnnnnn

nnnnnnnn

n n n n n n n n

n n n n n n n n

n n n n n n n n

dddddddd

dddddddd

dddddddd

d d d d d d d

dddddddd

dddddddd

dddddddd

dddddddd

d d d d d d d

dddddddd

ddddddddd

ddddddddd

ddddddddd

ddddddddd

ddddddddd

ddddddddd

d d d d d d d

Figure $4.$ Input file format: $\backslash (\backslash$boldsymbol$\{$n$\}\backslash )$ is an integer between $0$ and $\backslash (9,\backslash$boldsymbol$\{$d$\}\backslash )$ is an integer between $0$ and $2.$ The digits are separated by blanks.

n n n n n n n n

n n n n n n n n

nnnnnnnn

n n n n n n n n

n nnnnnnn

nnnnnnnn

nnnnnnnn

n nnnnnnn

n n n n n n n n

Figure $5.$ Output file format: $\backslash (\backslash$boldsymbol$\{$n$\}\backslash )$ is an integer between $1$ and $9.$ The digits are separated by blanks.

Figure $3.$ The Backtracking Algorithm for CSPs$.$ Input and output files: Your program will read in the initial game board values from an input text file and then produce an output text file that contains the solution. The format of the input file is as shown in Figure $4$ below. The first $9$ rows contain the initial cell values of the game board, separated by blanks. The cell values range from $0$ to $9,$ with $0$ indicating a blank cell. This is followed by a blank line. The next $9$ rows contain the locations of dots between horizontally$-$adjacent cells. Row $\backslash$#$1$ contains the locations of dots for horizontally$-$adjacent cells in row $\backslash$#$1$ of the game board, and similarly for the other rows. A value of $0$ means there is no dot between two adjacent cells, a value of $1$ means there is a white dot between two adjacent cells, and a value of $2$ means there is a black dot between two adjacent cells. This is then followed by another blank line. The next $8$ rows contain the locations of dots between vertically$-$adjacent cells. Row $\backslash$#$1$ contains the locations of dots between vertically$-$adjacent cells in the first and second rows of the game board, and similarly for the other rows. Again, a value of $0$ means there is no dot between two adjacent cells, a value of $1$ means there is a white dot between two adjacent cells, and a value of $2$ means there is a black dot between two adjacent cells. The format of the output file is as shown in Figure $5$ below. The output file contains $9$ rows of integers ranging from $1$ to $9,$ separated by blanks.