import csv

import itertools

class Board$()$:

##########################################

# Constructor

##########################################

def $\_\_$init$\_\_($self$,$ filename$)$:

self.n$2=0$

self.n $=0$

self.spaces $=0$

self.board $=$ None

self.valsInRows $=$ None

self.valsInCols $=$ None

self.valsInBoxes $=$ None

self.unsolvedSpaces $=$ None

self.loadSudoku$($filename$)$

def loadSudoku$($self$,$ filename$)$:

with open$($filename$)$ as csvFile:

self.n $=-1$

reader $=$ csv$.$reader$($csvFile$)$

for row in reader:

if self.n $==-1$:

self.n $=$ int$($len$($row$)**(1/2))$

if not self.n $**2==$ len$($row$)$:

raise Exception$(\text{'}$Each row must have n$^2$ values! $($See row $0)\text{'})$

else:

self.n$2=$ len$($row$)$

self.spaces $=$ self.n $**4$

self.board $=\{\}$

self.valsInRows $=[$set$()$ for $\_$ in range$($self$.$n$2)]$

self.valsInCols $=[$set$()$ for $\_$ in range$($self$.$n$2)]$

self.valsInBoxes $=[$set$()$ for $\_$ in range$($self$.$n$2)]$

self.unsolvedSpaces $=$ set$($itertools$.$product$($range$($self$.$n$2),$ range$($self$.$n$2)))$

else:

if len$($row$)!=$ self.n$2$:

raise Exception$(\text{'}$Each row must have the same number of values. $($See row $\text{'}+$ str$($reader$.$line$\_$num $-1)+\text{'})\text{'})$

for index, item in enumerate$($row$)$:

if not item $==\text{'}\text{'}$:

self.board$[($reader$.$line$\_$num$-1,$ index$)]=$ int$($item$)$

self.valsInRows$[$reader$.$line$\_$num$-1].$add$($int$($item$))$

self.valsInCols$[$index$].$add$($int$($item$))$

self.valsInBoxes$[$self$.$spaceToBox$($reader$.$line$\_$num$-1,$ index$)].$add$($int$($item$))$

self.unsolvedSpaces.remove$(($reader$.$line$\_$num$-1,$ index$))$

##########################################

# Utility Functions

##########################################

def spaceToBox$($self$,$ row, col$)$:

return self.n $*($row $//$ self.n$)+$ col $//$ self.n

def print$($self$)$:

for r in range$($self$.$n$2)$:

if r $\%$ self.n $==0$ and not r $==0$:

if self.n$2>9$:

print$(""+"----"*$ self.n$2)$

else:

print$(""+"---"*$ self.n$2)$

row $=""$

for c in range$($self$.$n$2)$:

if $($r$,$c$)$ in self.board:

val $=$ self.board$[($r$,$c$)]$

else:

val $=$ None

if c $\%$ self.n $==0$ and not c $==0$:

row $+="|"$

else:

row $+=""$

if self.n$2>9$:

if val is None: row $+="\_\_"$

else: row $+="\%2$i$"\%$ val

else:

if val is None: row $+="\_"$

else: row $+=$ str$($val$)$

print$($row$)$

##########################################

# Move Functions $-$ YOUR IMPLEMENTATIONS GO HERE

##########################################

# makes a move, records it in its row, col, and box, and removes the space from unsolvedSpaces

def makeMove$($self$,$ space, value$)$:

raise NotImplementedError

# removes the move, its record in its row, col, and box, and adds the space back to unsolvedSpaces

def undoMove$($self$,$ space, value$)$:

raise NotImplementedError

# returns True if the space is empty and on the board,

# and assigning value to it if not blocked by any constraints

def isValidMove$($self$,$ space, value$)$:

raise NotImplementedError

# optional helper function for use by getMostConstrainedUnsolvedSpace

def evaluateSpace$($self$,$ space$)$:

raise NotImplementedError

# gets the unsolved space with the most current constraints

# returns None if unsolvedSpaces is empty

def getMostConstrainedUnsolvedSpace$($self$)$:

raise NotImplementedError

class Solver:

##########################################

#### Constructor

##########################################

def $\_\_$init$\_\_($self$)$:

pass

####################################