Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- @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
- Save As .cmd or .bat
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement