@echo off
echo Welcome to 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 
nice but not supported in graphical interface so somewhat boring!!!!
ReplyDelete