Write a program that solves Sudoku puzzles. The input to Sudoku is a $9$x$9$ board that is subdivided

into $3$x$3$ squares. Each cell is either blank or contains an integer from $1$ to $9.$

A solution to a puzzle is the same board with every blank cell filled in with a digit from $1$ to $9$ such

that every digit appears exactly once in every row, column, and square.

The input to the program is a text file containing a collection of Sudoku boards, with one board

per line. For example:

$....\mathrm{.}2......\mathrm{.}7..\mathrm{.}17.\mathrm{.}3..\mathrm{.}9\mathrm{.}8.\mathrm{.}7.....\mathrm{.}2\mathrm{.}89\mathrm{.}6..\mathrm{.}13.\mathrm{.}6...\mathrm{.}9.\mathrm{.}5\mathrm{.}824....\mathrm{.}891..........$

$3..\mathrm{.}8......\mathrm{.}7...\mathrm{.}51.............\mathrm{.}36..\mathrm{.}2.\mathrm{.}4...\mathrm{.}7..........\mathrm{.}6\mathrm{.}13.\mathrm{.}452..........\mathrm{.}8..$Z

For each board that is read, the output is a printout of the board correctly filled in$.$

Part a

Some of the declarations and definitions for the board class are given to you. $($Optional$.$

You can choose to write your own codes.$)$ Add functions to the class that:

$1.$ initialize the board, and update conflicts,

$2.$ print the board and the conflicts to the screen,

$3.$ add a value to a cell, and update conflicts,

$4.$ clear a cell, and update conflicts, and

$5.$ check to see if the board has been solved $($return true or false, and print the result to

the screen$)$

For each row i and digit j$,$ keep track of whether each digit j has been placed in row i$.$ Do

the same for each column and each square. We will use this information in part b of the

project to write the Sudoku solver.

The code you submit should read each Sudoku board from the file one$-$by$-$one, print the

board and conflicts to the screen, and check to see if the board has been solved $($all boards

will not be solved at this point$).$

board.cpp:

#include

#include

#include $"$d$\_$matrix.h$"$

#include $"$d$\_$except.h$"$

#include

#include

using namespace std;

typedef int ValueType; $//$ The type of the value in a cell

const int Blank $=-1$; $//$ Indicates that a cell is blank

const int SquareSize $=3$; $//$ The number of cells in a small square

$//($usually $3).$ The board has

$//$ SquareSize$^2$ rows and SquareSize$^2$

$//$ columns.

const int BoardSize $=$ SquareSize $*$ SquareSize;

const int MinValue $=1$;

const int MaxValue $=9$;

int numSolutions $=0$;

class board

$//$ Stores the entire Sudoku board

$\{$

public:

board$($int$)$;

void clear$()$;

void initialize$($ifstream &fin$)$;

void print$()$;

bool isBlank$($int$,$ int$)$;

ValueType getCell$($int$,$ int$)$;

private:

$//$ The following matrices go from $1$ to BoardSize in each

$//$ dimension, i$.$e$.,$ they are each $($BoardSize$+1)*($BoardSize$+1)$

matrix value;

$\}$;

board::board$($int sqSize$)$

: value$($BoardSize$+1,$BoardSize$+1)$

$//$ Board constructor

$\{$

clear$()$;

$\}$

void board::clear$()$

$//$ Mark all possible values as legal for each board entry

$\{$

for $($int i $=1$; i $<=$ BoardSize; i$++)$

for $($int j $=1$; j $<=$ BoardSize; j$++)$

$\{$

value$[$i$][$j$]=$ Blank;

$\}$

$\}$

void board::initialize$($ifstream &fin$)$

$//$ Read a Sudoku board from the input file.

$\{$

char ch;

clear$()$;

for $($int i $=1$; i $<=$ BoardSize; i$++)$

for $($int j $=1$; j $<=$ BoardSize; j$++)$

$\{$

fin $>>$ ch;

$//$ If the read char is not Blank

if $($ch $!=\text{'}.\text{'})$

setCell$($i$,$j$,$ch$-\text{'}0\text{'})$; $//$ Convert char to int

$\}$

$\}$

int squareNumber$($int i$,$ int j$)$

$//$ Return the square number of cell i$,$j $($counting from left to right,

$//$ top to bottom. Note that i and j each go from $1$ to BoardSize

$\{$

$//$ Note that $($int$)$ i$/$SquareSize and $($int$)$ j$/$SquareSize are the x$-$y

$//$ coordinates of the square that i$,$j is in$.$

return SquareSize $*(($i$-1)/$SquareSize$)+($j$-1)/$SquareSize $+1$;

$\}$

ostream &operator$<<($ostream &ostr, vector &v$)$

$//$ Overloaded output operator for vector class.

$\{$

for $($int i $=0$; i $<$ v$.$size$()$; i$++)$

ostr $<<$ v$[$i$]<<""$;

cout $<<$ endl;

$\}$

ValueType board::getCell$($int i$,$ int j$)$

$//$ Returns the value stored in a cell. Throws an exception

$//$ if bad values are passed.

$\{$

if $($i $>=1$ && i $<=$ BoardSize && j $>=1$ && j $<=$ BoardSize$)$

return value$[$i$][$j$]$;

else

throw rangeError$("$bad value in getCell"$)$;

$\}$

bool board::isBlank$($int i$,$ int j$)$

$//$ Returns true if cell i$,$j is blank, and false otherwise.

$\{$

if $($i $<1||$ i $>$ BoardSize $||$ j $<1||$ j $>$ BoardSize$)$

throw rangeError$("$bad value in setCell"$)$;

return $($getCell$($i$,$j$)==$ Blank$)$;

$\}$

void board::print$()$

$//$ Prints the current board.

$\{$

for $($int i $=1$; i $<=$ BoardSize; i$++)$

$\{$

if $(($i$-1)\%$ SquareSize $==0)$

$\{$

cout $<<"-"$;

for $($int j $=1$; j $<=$ BoardSize; j$++)$

cout $<<"---"$;

cout $<<"-"$;

cout $<<$ endl;

$\}$

for $($int j $=1$; j $<=$ BoardSize; j$++)$

$\{$

if $(($j$-1)\%$ SquareSize $==0)$

cout $<<"|"$;

if $(!$isBlank$($i$,$j$))$

cout $<<""<<$ getCell$($i$,$j$)<<""$;

else

cout $<<""$;

$\}$

cout $<<"|"$;

cout $<<$ endl;

$\}$

cout $<<"-"$;

for $($int j $=1$; j $<=$ BoardSize; j$++)$

cout $<<"---"$;

cout $<<"-"$;

cout $<<$ endl;

$\}$

int main$()$

$\{$

ifstream fin;

$//$ Read the sample grid from the file.

string fileName $=$ "sudoku.txt$"$;

fin.open$($fileName$.$c$\_$str$())$;

if $(!$fin$)$

$\{$

cerr $<<$ "Cannot open $"<<$ fileName $<<$ endl;

exit$(1)$;

$\}$

try

$\{$

board b$1($SquareSize$)$;

while $($fin && fin.peek$()!=\text{'}$Z$\text{'})$

$\{$

b$1.$initialize$($fin$)$;

b$1.$print$()$;

b$1.$printConflicts$()$;

$\}$

$\}$