Write a C$++$program that solves Sudoku puzzles. The input to Sudoku is a $9$x$9$ board that is subdivided into $3$x$3$ squares.

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$.$

Complete your program that solves Sudoku puzzles. Your algorithm should be based on recursion. Your algorithm should read each board from the text file, solve it$,$ print the solution, and print the number of recursive iterations needed to solve that board. After all boards have

been solved, print the average number of recursive calls needed to solve all the boards. Your algorithm should minimize the average number of recursive calls needed to solve all the boards. Print the total number of your recursive calls

Board.cpp:

#include

#include

#include

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

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

using namespace std;

typedef int ValueType;

const int Blank $=-1$;

const int SquareSize $=3$;

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

const int MinValue $=1$;

const int MaxValue $=9$;

class board $\{$

public:

board$($int sqSize$)$;

void clear$()$;

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

void print$()$;

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

bool isSolved$()$;

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

void setCell$($int$,$ int, ValueType$)$;

void clearCell$($int$,$ int$)$;

void printConflicts$()$;

private:

matrix value;

matrix rowConflicts, colConflicts, squareConflicts;

int squareNumber$($int$,$ int$)$;

void updateConflicts$($int$,$ int, ValueType, bool$)$;

$\}$;

board::board$($int sqSize$)$ : value$($BoardSize $+1,$ BoardSize $+1),$

rowConflicts$($BoardSize $+1,$ vector$($MaxValue $+1,$ false$)),$

colConflicts$($BoardSize $+1,$ vector$($MaxValue $+1,$ false$)),$

squareConflicts$($BoardSize $+1,$ vector$($MaxValue $+1,$ false$))\{$

clear$()$;

$\}$

void board::clear$()\{$

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

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

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

$\}$

$\}$

$\}$

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

char ch;

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

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

fin $>>$ ch;

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

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

else

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

$\}$

$\}$

$\}$

void board::print$()\{$

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

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

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 $<<"|"<<$ endl;

$\}$

cout $<<"-------------------------"<<$ endl;

$\}$

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

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

$\}$

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

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

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

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

$\}$

void board::setCell$($int i$,$ int j$,$ ValueType val$)\{$

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

updateConflicts$($i$,$ j$,$ val, true$)$;

$\}$

void board::clearCell$($int i$,$ int j$)\{$

updateConflicts$($i$,$ j$,$ getCell$($i$,$ j$),$ false$)$;

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

$\}$

void board::updateConflicts$($int i$,$ int j$,$ ValueType val, bool add$)\{$

int sqNum $=$ squareNumber$($i$,$ j$)$;

rowConflicts$[$i$][$val$]=$ add;

colConflicts$[$j$][$val$]=$ add;

squareConflicts$[$sqNum$][$val$]=$ add;

$\}$

int board::squareNumber$($int i$,$ int j$)\{$

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

$\}$

bool board::isSolved$()\{$

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

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

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

return false;

$\}$

$\}$

return true;

$\}$

void board::printConflicts$()\{$

cout $<<$ "Conflicts for rows, columns, and squares:" $<<$ endl;

$\}$

int main$()\{$

const vector fileNames $=\{$ "sudoku$1-3.$txt$"\}$;

for $($const string& fileName : fileNames$)\{$

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

if $(!$fin$)\{$

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

continue;

$\}$

cout $<<$ "Processing file: $"<<$ fileName $<<$ endl;

board b$1($SquareSize$)$;

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

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

b$1.$print$()$;

cout $<<$ "Solved: $"<<($b$1.$isSolved$()?$ "Yes" : $"$No$")<<$ endl;

b$1.$printConflicts$()$;

$\}$

fin.close$()$;

cout $<<$ endl;

$\}$

return $0$;

$\}$