Implement the function solve$()$ that attempts to solve the puzzle using the strategy described below.

solve$()$

$$Compute$$the$$set$$of$$valid$$values$$V$[($r$,$c$)]$for$$every$$cell$($r$,$c$).$

$$known$=$set$()$

$$For$$every$$cell$$whose$$set$$of$$valid$$values$$has$$length$1,$add$($val$,$r$,$c$)$to$$the$$known$$set$,$where$$val$$is$$the$($only$)$element$$of$$set$$V$[($r$,$c$)].$

$$while$$known$$set$$is$$not$$empty:

$($val$,$r$,$c$)=$known$.$pop$()$#$$Remove$$an$$element$$from$$known$$set

$$S$[$r$,$c$]=$val$$#$$Set$$value$$in$$puzzle$$

$$V$[($r$,$c$)]=$set$()$#$$Make$$the$$candidate$$set$$for$$cell$($r$,$c$)$empty$,$since$$it$$has$$already$$been$$filled$.$

$$update$$sets$$#$$Remove$$val$$from$$all$$sets$$that$$are$$in$$the$$same$$row$,$column$$or$$region$$as$$cell$($r$,$c$).$Add$$to$$known$$set$$all$$sets$$whose$$length$$is$$reduced$$to$1$by$$this$$update$.$

$$If$$the$$puzzle$$has$$been$$solved$($that$$is$,$all$$cells$$in$$S$$are$$filled$),$return$1$

$$If$$there$$is$$a$$cell$($r$,$c$)$that$$has$$not$$been$$filled$$but$$whose$$set$$of$$valid$$values$$is$$empty$,$return$-1$

$$Return$0-$the$$puzzle$$has$$not$$been$$solved$,$but$$it$$still$$may$$have$$a$$solution