Slide Puzzle game in Batch

[Aacini]

At this SO post there is a question about "moving tiles" related to a sliding puzzle game. I posted a first version of the game and later completed it adding the test for "unsolvable puzzles" accordingly to the following description:

In particular, if the empty square is in the lower right corner (even anywhere in the last row) then the puzzle is solvable if and only if the number of inversions of the numbered pieces is even.

This is the Batch file of the slide puzzle game:

Code: Select all

@echo off
setlocal EnableDelayedExpansion

rem Slide Puzzle Game
rem Antonio Perez Ayala

set /A size=4, size2=size*size-1
for /L %%i in (0,1,%time:~-1%) do set /A !random!
set "empty=  "

:label-5 reset

rem Generate the numbers in random order
set "nums="
for /L %%i in (1,1,%size2%) do (
   set "num= %%i"
   set "nums=!nums!!num:~-2!"
)
set "solution=%nums%%empty%"
set "nums2= "
for /L %%n in (%size2%,-1,1) do (
   set /A num=!random! %% %%n * 2, numP2=num+2
   for /F "tokens=1,2" %%i in ("!num! !numP2!") do (
      set "nums2=!nums2!!nums:~%%i,2! "
      set "nums=!nums:~0,%%i!!nums:~%%j!"
   )
)

rem Check that it is a solvable puzzle
set "nums=%nums2%"
set "inversions=0"
for /L %%i in (1,1,%size2%) do (
   for /F %%a in ("!nums!") do (
      if %%a neq %%i (
         set "nums=!nums: %%i = %%a !"
         set /A inversions+=1
      )
   )
   for /F "tokens=1*" %%a in ("!nums!") do set "nums= %%b"
)
set /A mod2=inversions %% 2
if %mod2% equ 1 goto label-5 reset  Unsolvable puzzle

rem Populate the slides with the numbers
for /L %%j in (1,1,%size%) do (
   for /L %%i in (1,1,%size%) do (
      for /F "tokens=1*" %%a in ("!nums2!") do (
         set "num= %%a"
         set "slide[%%j][%%i]=!num:~-2!"
         set "nums2=%%b"
      )
   )
)
set "slide[%size%][%size%]=%empty%"
set /A i=j=size

:refresh
rem Show the puzzle
set "nums="
< NUL (
   cls
   for /L %%i in (1,1,%size%) do set /P "=.____"
   echo .
   for /L %%j in (1,1,%size%) do (
      for /L %%i in (1,1,%size%) do set /P "=|    "
      echo ^|
      for /L %%i in (1,1,%size%) do set /P "=| !slide[%%j][%%i]! " & set "nums=!nums!!slide[%%j][%%i]!"
      echo ^|
      for /L %%i in (1,1,%size%) do set /P "=|____"
      echo ^|
   )
)
if "%nums%" equ "%solution%" echo Completed^^^! & goto :EOF
echo Reset     W
echo          A D
set /P "=eXit      S    " < NUL

:getKey
rem Move the empty square
choice /C wasdrx /N
if errorlevel 5 goto label-%errorlevel%  Reset or eXit
set /A "mod2=%errorlevel% %% 2, newJ=j+(%errorlevel%-2)*mod2, newI=i+(%errorlevel%-3)*^!mod2"
if not defined slide[%newJ%][%newI%] goto getKey
for /F "tokens=1,2" %%i in ("%newI% %newJ%") do set "slide[%j%][%i%]=!slide[%%j][%%i]!" & set "slide[%%j][%%i]=%empty%"
set /A i=newI, j=newJ
goto refresh

:label-6 exit

Any comments about this program are welcomed...

Antonio

[CirothUngol]

Ok, that was fun. ^_^
Batch games! That's what originally brought me to DOStips... or actually it was Snake, but I stayed for the other goodies... like this! I haven't done one of these since I was a kid. I finally solved it, but it must have taken me 50+ moves. Maybe add a visible move counter, score by stroke like in golf?

Thanks for the fun little batch game, Mr.A!

[dbenham]

Nicely done. I think you have designed the interface the best way possible. But for some reason, my mind rebels against the concept of moving the hole.

I see that you test if the randomly generated grid is solvable, and if not, you loop back and randomly generate complete grids until you get one that is solvable. I'm pretty sure you can convert any unsolvable grid into a solvable one by simply swapping the last two tiles.


Dave Benham

[penpen]

I've seen different versions of this puzzle:
The missing tile may have the number "16" or "0".

It is always possible to transform the puzzle in one of the two states:

Code: Select all

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15

    1  2  3   
 4  5  6  7
 8  9 10 11
12 13 14 15

So i wouldn't call the second version unsolveable.
Maybe you could give a hint which tile is missing (although this is not really needed).


penpen

[dbenham]

@penpen - Ooh, very interesting observation. Though I have a problem with your choice of language.

Your first puzzle cannot be transformed to the second using legal slide moves. This should be obvious according to the solvability rules described at https://www.cs.bham.ac.uk/~mdr/teaching ... ility.html.

But if you consider both of those puzzles to be solved, then all random tile arrangements are indeed solvable

50% of all possible random arrangements solve as your first puzzle, and the remaining 50% solve as your second, and never the twain shall meet.

The same should be true for all square puzzles with even dimensions (2x2, 4x4, 6x6, etc.)

But this does not help puzzles with odd dimensions, like 3x3. I'm pretty sure 50% of all random arrangements are unsolvable for puzzles with odd dimensions.


Dave Benham

[pieh-ejdsch]

... But for some reason, my mind rebels against the concept of moving the hole.

you can use:

Code: Select all

choice /c sdwarx /n

Phil

[dbenham]

... But for some reason, my mind rebels against the concept of moving the hole.

you can use:

Code: Select all

choice /c sdwarx /n

Oh yes
Now my brain is much happier


Dave Benham

[Aacini]

Ok, that was fun. ^_^
Batch games! That's what originally brought me to DOStips... or actually it was Snake, but I stayed for the other goodies... like this! I haven't done one of these since I was a kid. I finally solved it, but it must have taken me 50+ moves. Maybe add a visible move counter, score by stroke like in golf?

Thanks for the fun little batch game, Mr.A!

Well, if you like Batch games I invite you to review my 2048.bat game (or the color version that don't require auxiliary .exe programs), or my pure Batch Tetris game, or the Tetris in color version...

Nicely done. I think you have designed the interface the best way possible. But for some reason, my mind rebels against the concept of moving the hole.

I see that you test if the randomly generated grid is solvable, and if not, you loop back and randomly generate complete grids until you get one that is solvable. I'm pretty sure you can convert any unsolvable grid into a solvable one by simply swapping the last two tiles.


Dave Benham

As I said before, the original concept was derived from the linked StackOverflow question, so I just completed the program and used the same "move the hole" approach. However, I fixed these two points in the new version below, and I added the capability of save/load unsolved puzzles...

Code: Select all

@echo off
setlocal EnableDelayedExpansion

rem Slide Puzzle Game
rem Antonio Perez Ayala
rem Version 2: Save/load unsolved puzzles

set /A size=4,  size2=size*size-1
for /L %%i in (0,1,%time:~-1%) do set /A !random!
set "empty=  "

rem Load a saved puzzle
if not exist SlidePuzzle.dat goto label-5 Reset
echo There are unsolved puzzles saved
choice /M "Do you want to load one"
if errorlevel 2 goto label-5 Reset
echo/
echo #- Timestamp            Pieces
set "n=0"
for /F "tokens=1-5*" %%a in (SlidePuzzle.dat) do (
   set /A n+=1
   echo !n!- %%a %%f
)
echo/
:getNum
set "i=0"
set /P "i=Enter desired puzzle: "
set /A "i=%i%" 2> NUL
if %i% lss 1 goto getNum
if %i% gtr %n% goto getNum
set "k=0"
(for /F "tokens=1-5*" %%a in (SlidePuzzle.dat) do (
   set /A k+=1
   if !k! equ %i% (
      set /A "size=%%b, size2=size*size-1, i=%%c, j=%%d, moves=%%e"
      set "nums2=%%f"
   ) else (
      echo %%a %%b %%c %%d %%e %%f
   )
)) > SlidePuzzle.tmp
move /Y SlidePuzzle.tmp SlidePuzzle.dat > NUL
if %n% equ 1 del SlidePuzzle.dat
for /L %%j in (1,1,%size%) do (
   for /L %%i in (1,1,%size%) do (
      for /F "tokens=1* delims=," %%a in ("!nums2!") do (
         set "slide[%%j][%%i]=%%a"
         set "nums2=%%b"
      )
   )
)
set "solution="
for /L %%i in (1,1,%size2%) do (
   set "num= %%i"
   set "solution=!solution!!num:~-2!"
)
set "solution=%solution%%empty%"
goto refresh

:label-5 Reset

rem Generate the numbers in random order
set "nums="
for /L %%i in (1,1,%size2%) do (
   set "num= %%i"
   set "nums=!nums!!num:~-2!"
)
set "solution=%nums%%empty%"
set "nums2= "
for /L %%n in (%size2%,-1,1) do (
   set /A num=!random! %% %%n * 2, numP2=num+2
   for /F "tokens=1,2" %%i in ("!num! !numP2!") do (
      set "nums2=!nums2!!nums:~%%i,2! "
      set "nums=!nums:~0,%%i!!nums:~%%j!"
   )
)

rem Fix an unsolvable puzzle
set "nums=%nums2%"
set "inversions=0"
for /L %%i in (1,1,%size2%) do (
   for /F %%a in ("!nums!") do (
      if %%a neq %%i (
         set "nums=!nums: %%i = %%a !"
         set /A inversions+=1
      )
   )
   for /F "tokens=1*" %%a in ("!nums!") do set "nums= %%b"
)
set /A mod2=inversions %% 2
if %mod2% equ 1 for /F "tokens=1,2*" %%a in ("%nums2%") do set "nums2=%%b %%a %%c"

rem Populate the slides with the numbers
for /L %%j in (1,1,%size%) do (
   for /L %%i in (1,1,%size%) do (
      for /F "tokens=1*" %%a in ("!nums2!") do (
         set "num= %%a"
         set "slide[%%j][%%i]=!num:~-2!"
         set "nums2=%%b"
      )
   )
)
set /A i=j=size, moves=0
set "slide[%j%][%i%]=%empty%"

:refresh
rem Show the puzzle
set "nums="
< NUL (
   cls
   echo/
   echo Moves: %moves%
   for /L %%i in (1,1,%size%) do set /P "=.____"
   echo .
   for /L %%j in (1,1,%size%) do (
      for /L %%i in (1,1,%size%) do set /P "=|    "
      echo ^|
      for /L %%i in (1,1,%size%) do set /P "=| !slide[%%j][%%i]! " & set "nums=!nums!!slide[%%j][%%i]!"
      echo ^|
      for /L %%i in (1,1,%size%) do set /P "=|____"
      echo ^|
   )
)
if "%nums%" equ "%solution%" echo Completed^^^! & goto :EOF
echo                   S
echo slide a piece     v
echo next to the    D-^> ^<-A
echo hole into it:     ^^
echo Reset or eXit     W

:getKey
choice /C sdwarx /N
if errorlevel 5 goto label-%errorlevel%  Reset or eXit

rem Move a piece
set /A "mod2=%errorlevel% %% 2, newJ=j+(%errorlevel%-2)*mod2, newI=i+(%errorlevel%-3)*^!mod2"
if not defined slide[%newJ%][%newI%] goto getKey
for /F "tokens=1,2" %%i in ("%newI% %newJ%") do set "slide[%j%][%i%]=!slide[%%j][%%i]!" & set "slide[%%j][%%i]=%empty%"
set /A i=newI, j=newJ, moves+=1
goto refresh

:label-6 eXit
rem Save this game
<NUL (
set /P "=%date%@%time:~0,-3% %size% %i% %j% %moves% "
for /L %%j in (1,1,%size%) do (
   for /L %%i in (1,1,%size%) do (
      set /P "=,!slide[%%j][%%i]!"
   )
)
echo/
) >> SlidePuzzle.dat
echo Unsolved puzzle saved...

Antonio

[penpen]

Your first puzzle cannot be transformed to the second using legal slide moves.

i wasn't aware, that one could misinterpret my above posting in such a way.

So, with "It is always possible to transform the puzzle in one of the two states" i meant, that you could transform any random tile arrangement (using legal moves only) into either the first given tile arrangement (state) or the second, but not into both:
Especially you cannot transform the first state into the second.

Any tile arrangement that could be transformed into the first state is one version of the game (== misisng tile has "16" on it).
Any tile arrangement that could be transformed into the second state is another version of the game (== missing tile has "0" on it).

And yes, the two states given above should be the "accepted solved states" for both versions of the game.

Code: Select all

But this does not help puzzles with odd dimensions, like 3x3. I'm pretty sure 50% of all random arrangements are unsolvable for puzzles with odd dimensions.

I didn't notice that you could just use any puzzle size (by changing the size to the wanted value).

So just for completeness - if i remember right, then you could transform the unsolvable tile arrangements (in uneven sized variations of this game) into a state in which the tile numbers are sorted clockwise helically with numbers increasing from any corner to the center; examples:

Code: Select all

Solved state for variation size=3:
    1  2
 7  8  3
 6  5  4

Solved state for variation size=5:
    1  2  3  4
15 16 17 18  5
14 23 24 19  6
13 22 21 20  7
12 11 10  9  8

penpen