Sudoku Solver

@echo off

::Entering invalid puzzles will make the program act strangely or crash.
::It's better to get puzzles from the internet than to try to make them up.

::Sets the title, and enables delayed expansion.

SetLocal EnableDelayedExpansion
Title Sudoku Solver

echo Welcome to ScrewTheLotOfYou's Batch Sudoku Solver.
echo.
echo.
echo.
echo Loading...


::Glossary:

::    Space: Each place that number can be placed. 81 of these on a sudoku puzzle.
::    Box: Each 3x3 grid. There are 9 of these.
::    Row: From left to right. 9 squares in each row. 9 rows alogether.
::    Column: From top to bottom. 9 squares in each column. 9 columns altogether.

::    X: X is the column number of a given space. Numbers 1-9 from left to right.
::    Y: Y is the row number of a given space. Numbers 1-9 from top to bottom.

::    Puzzle (grid): The grid of numbers that have been entered by the user or worked out by the program. These numbers are the final positions of each number.
::    Solution (grid): The grid of numbers that the program has worked out that COULD go in each space with the current Puzzle grid.
::    R (grid): This stands for Row Grid. Contains the possible locations that each number from 1-9 could reside.
::    C (grid): This stands for Column Grid. Contains the possible locations that each number from 1-9 could reside.
::    B (grid): This stands for Box Grid. Contains the possible locations that each number from 1-9 could reside.

::    Variables that are part of the Puzzle grid are in the format: PX-Y=Value
::    Variables that are part of the Solution grid are in the format: SX-Y=Possible solutions
::    Variables that are part of the R grid are in the format: RY-Value=Possible X values
::    Variables that are part of the C grid are in the format: CX-Value=Possible Y values
::    Variables that are part of the B grid are in the format: BBoxNumber-Value=Possible XY values
::    The R, C and S variables are a list of single digit numbers, not separated. The B variables are a list of two digit numbers, each separated by a space.




::Sets up the Puzzle Row Grid, a 9x9 square.
::Sets up the Puzzle Columns, a 9x9 square.
::Sets up the Column and Row grids.

for /L %%I in (1,1,9) do (

    for /L %%J in (1,1,9) do (
        set PuzzleRow%%I=!PuzzleRow%%I!#P%%J-%%I#
        set PuzzleColumn%%I=!PuzzleColumn%%I!#P%%I-%%J#

        for /L %%K in (1,1,9) do (
            set R%%I-%%J=!R%%I-%%J!%%K
            set C%%I-%%J=!C%%I-%%J!%%K
        )
    )
    set PuzzleDisplayRow%%I=!PuzzleRow%%I:~0,21!][!PuzzleRow%%I:~21,21!][!PuzzleRow%%I:~42,21!
    set PuzzleDisplayRow%%I=!PuzzleDisplayRow%%I: =!

)






::Sets up all 9 3x3 Puzzle boxes and all 9 3x3 solution boxes.

::Boxes are more complicated because they don't follow a simple rule, e.g. column 2 x=2.
::This is why I'm setting up solution list boxes.

set BoxNumber=0



for /l %%I in (0,1,2) do (
    for /l %%J in (0,1,2) do (
        set /a StartY=%%I * 3 + 1
        set /a EndY=%%I * 3 + 3
        set /a StartX=%%J * 3 + 1
        set /a EndX=%%J * 3 + 3
        call :SetUpBoxes !StartY! !EndY! !StartX! !EndX!
    )
)


goto SetUpAllSolutionSpaces






:SetUpBoxes

::%1=StartY %2=EndY %3=StartX %4=EndX

::SpaceCount is set to 1 each time so each solution box can have the format SolutionBox(BoxNumber)-SpaceCount
::This allows me to cycle through each space in a box as quickly as a row or column.

set SpaceCount=1

set /a BoxNumber+=1

for /l %%I in (%1,1,%2) do (
    for /l %%J in (%3,1,%4) do (
        set PuzzleBox%BoxNumber%=!PuzzleBox%BoxNumber%!#P%%J-%%I#
        set SolutionBox%BoxNumber%-!SpaceCount!=S%%J-%%I
       
        for /L %%K in (1,1,9) do (
            set B%BoxNumber%-%%K=!B%BoxNumber%-%%K!%%J%%I
        )

        set /a SpaceCount=!SpaceCount!+1
    )
)
exit /b



               



:SetUpAllSolutionSpaces

::Sets up all the solution spaces, so each one starts off as 1-9.

for /l %%I in (1,1,9) do (
    for /l %%J in (1,1,9) do (
        set S%%I-%%J=123456789
        set P%%I-%%J=
    )
)



::goto SetupSolutionGrid




set P1-1=

:BeginEntering

set InputCount=0

cls




::Asks the user to input each space. Calls :InputEachSpace for the user to input. Calls to display the grid so far. Clears the screen. It does all this 9x9 times.
::The function RefreshPuzzleDisplay is further down, as it is used now and later.

for /L %%I in (1,1,9) do for /L %%J in (1,1,9) do echo Enter the puzzle below.& echo Just press enter if the space is blank.& echo.& set P%%J-%%I=&& Call :RefreshPuzzleDisplay& Call :InputEachSpace %%J %%I& cls
echo.
echo.
echo Processing puzzle...
goto SetUpSolutionGrid






:: This function is called as the user inputs each part of the grid.

:InputEachSpace
::Recieves arguments %1=X and %2=Y
echo.
echo Column:%1 Row:%2
echo.
::The format is Px-y (P stands for Puzzle. As these variables are part of the puzzle grid, not the solutions grid).
set /p P%1-%2=
set P%1-%2=!P%1-%2:~0,1!
if NOT !P%1-%2! leq 9 set P%1-%2=
if NOT !P%1-%2! geq 1 set P%1-%2=

if NOT "!P%1-%2!"==" "  set /a InputCount+=1&& set DefinedSpaces!InputCount!=P%1-%2=!P%1-%2!

exit /b








:SetUpSolutionGrid

:: Adjusts the solutions for each row, column and box containing a space defined by the user.
:: Works out which box the space is in using the formula: BoxNumber= ( (x+2)/3) ) + ( ((y-1)/3)*3 )
:: This works because set /a does not use decimals when dividing, so only the number of whole divisions is returned.
:: For example, set /a 2 / 3 returns 0. set /a 8 / 3 returns 2.


:: Set FoundSolutions to a single space, as trying to use envirnoment variable substition on a non existent variable causes trouble.

set FoundSolutions=

::Sorry about it all being on one line, but the FOR command crashes if I try and put it in brackets on serparate lines. Think it's something to do with the brackets in the set /a command.
::The function AdjustSolutionGrid is quite far down, as it's used now and later.

for /l %%I in (1,1,%InputCount%) do set /a BoxNumber= ( ( (!DefinedSpaces%%I:~1,1! + 2 ) / 3) + ( ( ( !DefinedSpaces%%I:~3,1! - 1 ) / 3 ) * 3 ) )&& call :AdjustSolutionGrid !DefinedSpaces%%I:~1,1! !DefinedSpaces%%I:~3,1! !DefinedSpaces%%I:~5,1! !BoxNumber!





:BeginSolving
cls
echo Ready to solve puzzle.
echo.
echo.
echo After each number is found the program will pause.
echo Press enter to begin.
Pause>nul
cls
call :RefreshPuzzleDisplay


















:ProcessFoundSolutions
::This is where the FoundSolutions variable is processed.
::If it is empty, other algorithms are tried.



if "%FoundSolutions: =%"=="" goto CheckForLineBoxRules

for /f %%I in ("%FoundSolutions%") do (
    set SolutionTemp=%%I
    set FoundSolutions=!FoundSolutions:%%I=!
)

set /a BoxNumber= ( ( (!SolutionTemp:~0,1! + 2 ) / 3) + ( ( ( !SolutionTemp:~1,1! - 1 ) / 3 ) * 3 ) )

call :AdjustSolutionGrid %SolutionTemp:~0,1% %SolutionTemp:~1,1% %SolutionTemp:~2,1% %BoxNumber%

set /a InputCount+=1

set P%SolutionTemp:~0,1%-%SolutionTemp:~1,1%=%SolutionTemp:~2,1%
cls
call :RefreshPuzzleDisplay
echo.
echo.
echo A %SolutionTemp:~2,1% has been added at (%SolutionTemp:~0,1%,%SolutionTemp:~1,1%)
echo.
pause
goto ProcessFoundSolutions








::This is the function that displays the puzzle on screen. No arguments are recieved.

:RefreshPuzzleDisplay
echo. ^|^|%PuzzleDisplayRow1:#=!%^|^|
echo. ^|^|%PuzzleDisplayRow2:#=!%^|^|
echo. ^|^|%PuzzleDisplayRow3:#=!%^|^|
echo  ^|^|-------------^|^|
echo. ^|^|%PuzzleDisplayRow4:#=!%^|^|
echo. ^|^|%PuzzleDisplayRow5:#=!%^|^|
echo. ^|^|%PuzzleDisplayRow6:#=!%^|^|
echo  ^|^|-------------^|^|
echo. ^|^|%PuzzleDisplayRow7:#=!%^|^|
echo. ^|^|%PuzzleDisplayRow8:#=!%^|^|
echo. ^|^|%PuzzleDisplayRow9:#=!%^|^|
exit /b










:AdjustSolutionGrid



::Recieves arguments %1=X, %2=Y, %3=Value and %4=Box Number.

::This Function adjusts the solution grid by removing solutions from the row, column and box.
::It also takes out possible locations of values in affected boxes and the row, column and box in which the value resides.
::If this function finds a space that has just one solution, or a number that has just one possible location, it sets FoundSolutions to include its co-ordinates and value, for processing later.

set S%1-%2=
set R%2-%3=
set C%1-%3=
set B%4-%3=

::I know a few of the commands here are incredibly complicated and hard to follow. Can't be helped.
::Once again the box calculation algorithm had to go on the line because of the bracket disagreement.

::No commentary can be typed inside a FOR loop. Sorry.

for /l %%I in (1,1,9) do set /a AffectedBox1= ( ( (%1 + 2 ) / 3) + ( ( ( %%I - 1 ) / 3 ) * 3 ) )&& set /a AffectedBox2= ( ( (%%I + 2 ) / 3) + ( ( ( %2 - 1 ) / 3 ) * 3 ) )&& (


    set B%4-%%I=!B%4-%%I:%1%2 =!
    set C%1-%%I=!C%1-%%I:%2=!
    set R%2-%%I=!R%2-%%I:%1=!

    call set B!AffectedBox1!-%3=%%B!AffectedBox1!-%3:%1%%I =%%
    call set B!AffectedBox2!-%3=%%B!AffectedBox2!-%3:%%I%2 =%%
   

    set C%%I-%3=!C%%I-%3:%2=!
    set R%%I-%3=!R%%I-%3:%1=!
    set S%1-%%I=!S%1-%%I:%3=!
    set S%%I-%2=!S%%I-%2:%3=!

   
    call set !SolutionBox%4-%%I!=%%!SolutionBox%4-%%I!:%3=%%

    call set C!SolutionBox%4-%%I:~1,1!-%3=%%C!SolutionBox%4-%%I:~1,1!-%3:!SolutionBox%4-%%I:~3,1!=%%
    call set R!SolutionBox%4-%%I:~3,1!-%3=%%R!SolutionBox%4-%%I:~3,1!-%3:!SolutionBox%4-%%I:~1,1!=%%


    for /f %%J in ("!R%%I-%3!") do (
        if "!R%%I-%3:~1!"=="" (
            set FoundSolutions=!FoundSolutions:%%J%%I%3=! %%J%%I%3
        )
    )

    for /f %%J in ("!C%%I-%3!") do (
        if "!C%%I-%3:~1!"=="" (
            set FoundSolutions=!FoundSolutions:%%I%%J%3=! %%I%%J%3
        )
    )

    for /f %%J in ("!S%1-%%I!") do (
        if "!S%1-%%I:~1!"=="" (
            set FoundSolutions=!FoundSolutions:%1%%I%%J=! %1%%I%%J
        )
    )

    for /f %%J in ("!S%%I-%2!") do (
        if "!S%%I-%2:~1!"=="" (
            set FoundSolutions=!FoundSolutions:%%I%2%%J=! %%I%2%%J
        )
    )   

    call set Temp=%%B!AffectedBox1!-%3: =%%

    if NOT "!Temp!"=="" if "!Temp:~2!"=="" (
        call set FoundSolutions=%%FoundSolutions:!Temp!%3=%% !Temp!%3
    )
   

    call set Temp=%%B!AffectedBox2!-%3: =%%

    if NOT "!Temp!"=="" if "!Temp:~2!"=="" (
        call set FoundSolutions=%%FoundSolutions:!Temp!%3=%% !Temp!%3
    )

)

exit /b




:CheckForLineBoxRules

::This is an alternate algorithm to just checking for single solutions and algorithms.

::It is based on the idea that if all solutions for one number of one row/column lie in one box, then only solutions on that row/column are possible in that box.
::The opposite is true, that if all solutions for a certain number in a box line up horisontally or vertically (So they lie on one column/row), only solutions in that box are possible for that row/column.


for /l %%I in (1,1,9) do (
    for /l %%J in (1,1,9) do (
        if NOT "!B%%I-%%J: =!"=="" (
            if "!B%%I-%%J:~9!"=="" (
                if "!B%%I-%%J:~0,1!" equ "!B%%I-%%J:~3,1!" (
                    if "!B%%I-%%J:~6,1!"=="" (
                        call :RemoveColumnSolutions %%I !B%%I-%%J:~0,1! %%J
                    ) else (
                        if "!B%%I-%%J:~0,1!" equ "!B%%I-%%J:~6,1!" (
                            call :RemoveColumnSolutions %%I !B%%I-%%J:~0,1! %%J
                        )
                    )
                ) else (
                    if "!B%%I-%%J:~1,1!" equ "!B%%I-%%J:~4,1!" (
                        if "!B%%I-%%J:~7,1!"=="" (
                            call :RemoveRowSolutions %%I !B%%I-%%J:~1,1! %%J
                        ) else (
                            if "!B%%I-%%J:~1,1!" equ "!B%%I-%%J:~7,1!" (
                                call :RemoveRowSolutions %%I !B%%I-%%J:~1,1! %%J
                            )
                        )
                    )
                )
            )
        )


        if NOT "!C%%I-%%J: =!"=="" (
            if "!C%%I-%%J:~3!"=="" (
                call :CheckSameBoxCOLUMN %%J %%I !C%%I-%%J:~0,1! !C%%I-%%J:~1,1! !C%%I-%%J:~2,1!
            )
        )

        if NOT "!R%%I-%%J: =!"=="" (
            if "!R%%I-%%J:~3!"=="" (
                call :CheckSameBoxROW %%J %%I !R%%I-%%J:~0,1! !R%%I-%%J:~1,1! !R%%I-%%J:~2,1!
            )
        )

    )
)


goto ReprocessSolutions



:CheckSameBoxCOLUMN
::Recieves %1=Value %2=X %3=Y1 %4=Y2 %5=Y3

if "%4"=="" exit /b

set /a AffectedBox1= ( ( (%2 + 2 ) / 3) + ( ( ( %3 - 1 ) / 3 ) * 3 ) )
set /a AffectedBox2= ( ( (%2 + 2 ) / 3) + ( ( ( %4 - 1 ) / 3 ) * 3 ) )
set /a AffectedBox3= ( ( (%2 + 2 ) / 3) + ( ( ( %5 - 1 ) / 3 ) * 3 ) )

if NOT "%AffectedBox1%"=="%AffectedBox2%" exit /b

if NOT "%5"=="" (
    if NOT "%AffectedBox1%"=="%AffectedBox3%" exit /b
)

for /l %%I in (1,1,9) do (
    if NOT "!SolutionBox%AffectedBox1%-%%I:~1,1!"=="%2" (
        call set !SolutionBox%AffectedBox1%-%%I!=%%!SolutionBox%AffectedBox1%-%%I!:%1=%%
    )
)

set Temp=

for /l %%I in (0,3,27) do (

    if "!B%AffectedBox1%-%1:~%%I,1!"=="" (
        set B%AffectedBox1%-%1=!Temp!
        exit /b
    )

    if "!B%AffectedBox1%-%1:~%%I,1!"=="%2" (
    set Temp=!Temp!!B%AffectedBox1%-%1:~%%I,3!
    )
)
exit /b   







:CheckSameBoxROW
::Recieves %1=Value %2=Y %3=X1 %4=X2 %5=X3

if "%4"=="" exit /b

set /a AffectedBox1= ( ( (%3 + 2 ) / 3) + ( ( ( %2 - 1 ) / 3 ) * 3 ) )
set /a AffectedBox2= ( ( (%4 + 2 ) / 3) + ( ( ( %2 - 1 ) / 3 ) * 3 ) )
set /a AffectedBox3= ( ( (%5 + 2 ) / 3) + ( ( ( %2 - 1 ) / 3 ) * 3 ) )

if NOT "%AffectedBox1%"=="%AffectedBox2%" exit /b

if NOT "%5"=="" (
    if NOT "%AffectedBox1%"=="%AffectedBox3%" exit /b
)

for /l %%I in (1,1,9) do (
    if NOT "!SolutionBox%AffectedBox1%-%%I:~3,1!"=="%2" (
        call set !SolutionBox%AffectedBox1%-%%I!=%%!SolutionBox%AffectedBox1%-%%I!:%1=%%
    )
)

set Temp=

for /l %%I in (0,3,27) do (

    if "!B%AffectedBox1%-%1:~%%I,1!"=="" (
        set B%AffectedBox1%-%1=!Temp!
        exit /b
    )

    if "!B%AffectedBox1%-%1:~%%I,2!"=="!B%AffectedBox1%-%1:~%%I,1!%2" (
    set Temp=!Temp!!B%AffectedBox1%-%1:~%%I,3!
    )
)
exit /b   






:RemoveColumnSolutions
::Recieves %1=Box Number %2=X %3=Value

for /l %%I in (1,1,9) do set /a AffectedBox= ( ( (%2 + 2 ) / 3) + ( ( ( %%I - 1 ) / 3 ) * 3 ) )&& (
    if NOT !AffectedBox!==%1 (
        set C%2-%3=!C%2-%3:%%I=!
        call set B!AffectedBox!-%3=%%B!AffectedBox!-%3:%2%%I =%%
        set S%2-%%I=!S%2-%%I:%3=!
    )
)
exit /b


:RemoveRowSolutions
::Recieves %1=Box Number %2=Y %3=Value

for /l %%I in (1,1,9) do set /a AffectedBox= ( ( (%%I + 2 ) / 3) + ( ( ( %2 - 1 ) / 3 ) * 3 ) )&& (
    if NOT !AffectedBox!==%1 (
        set R%2-%3=!R%2-%3:%%I=!
        call set B!AffectedBox!-%3=%%B!AffectedBox!-%3:%%I%2 =%%
        set S%%I-%2=!S%%I-%2:%3=!
    )
)
exit /b



:ReprocessSolutions

::Here, all the solutions, boxes, rows and columns are checked for single solutions/locations. This is because the Line-Box rule may have created single solutions.


for /l %%I in (1,1,9) do (
    for /l %%J in (1,1,9) do (
   
        for /f %%K in ("!R%%I-%%J!") do (
            if "!R%%I-%%J:~1!"=="" set FoundSolutions=!FoundSolutions:%%K%%I%%J=! %%K%%I%%J
        )


        for /f %%K in ("!B%%I-%%J!") do (
            if "!B%%I-%%J:~3!"=="" set FoundSolutions=!FoundSolutions:%%K%%J=! %%K%%J
        )


        for /f %%K in ("!C%%I-%%J!") do (
            if "!C%%I-%%J:~1!"=="" set FoundSolutions=!FoundSolutions:%%I%%K%%J=! %%I%%K%%J
        )


        for /f %%K in ("!S%%J-%%I!") do (
            if "!S%%J-%%I:~1!"=="" set FoundSolutions=!FoundSolutions:%%J%%I%%K=! %%J%%I%%K
        )


    )
)


if NOT "%FoundSolutions: =%"=="" goto ProcessFoundSolutions



:EndSolving

::The code only reaches this point if the code cannot solve the puzzle.


::If all 81 numbers are filled then the puzzle has been solved.

if %InputCount%==81 (
echo Puzzle Solved^!
) ELSE (
echo Sorry, your puzzle could not be solved.
echo It may have been entered incorrectly, or it is too difficult for this program.
)



:RequestStartAgain

::Asks if the user wants to enter another puzzle.

echo Would you like to start again? [Y/N]

set /p Response=
if /i "%Response:~0,1%"=="Y" goto ClearPreviousPuzzle
if /i "%Response:~0,1%"=="N" exit /b
goto RequestStartAgain



:ClearPreviousPuzzle

::Clears all variables that may interfere with the next puzzle entered.

for /l %%I in (1,1,9) do (
    for /l %%J in (1,1,9) do (
        set S%%J-%%I=
        set P%%J-%%I=
        set R%%J-%%I=123456789
        set C%%J-%%I=123456789
        set B%%J-%%I=123456789
        set InputCount=0
    )
)


goto SetUpAllSolutionSpaces