12
\$\begingroup\$

The knight is a chess piece that, when placed on the o-marked square, can move to any of the x-marked squares (as long as they are inside the board):

.x.x.
x...x
..o..
x...x
.x.x.

Eight knights, numbered from 1 to 8, have been placed on a 3×3 board, leaving one single square empty ..

They can neither attack each other, nor share the same square, nor leave the board: the only valid moves are jumps to the empty square.

Compute the minimum number of valid moves required to reach the following ordered configuration by any sequence of valid moves:

123
456
78.

Output -1 if it is not reachable.

Example detailed: Possible in 3 moves

128       12.       123       123
356  -->  356  -->  .56  -->  456
7.4       784       784       78.

Input & Output

  • You are given three lines of three characters (containing each of the characters 1-8 and . exactly once)
  • You are to output a single integer corresponding to the smallest number of moves needed to reach the ordered configuration, or -1 if it is not reachable.
  • You are allowed to take in the input as a matrix or array/list
  • You are allowed to use 0 or in the input instead of .

Test cases

128
356
7.4
->
3

674
.25
831
->
-1

.67
835
214
->
-1

417
.53
826
->
23

Scoring

This is code-golf, so shortest code wins!

Credits to this puzzle

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Can we replace . with something like 0 in the input? \$\endgroup\$
    – Aiden Chow
    Feb 17, 2022 at 8:27

7 Answers 7

3
\$\begingroup\$

Charcoal, 54 52 bytes

≔⭆³Sθ≔⭆83270561§θIιθI⌈⟦±¹⁻²⁸↔⁻²⁸⁺×⁸⌕”)″“◨_'↷χ”⁻θ.⌕θ.

Try it online! Link is to verbose version of code. Save 4 bytes if printing any negative number is acceptable for an unreachable configuration. Explanation:

≔⭆³Sθ

Input the grid and join the lines together into a single string.

≔⭆83270561§θIιθ

Reorder the digits from the string starting at the original bottom right corner and taking clockwise knight's moves.

I⌈⟦±¹⁻²⁸↔⁻²⁸

Output the difference from 28 of the absolute difference with 28 (or -1 if that is negative) of...

⁺×⁸⌕”)″“◨_'↷χ”⁻θ.⌕θ.

... finding the position of that string excluding the . in the compressed string 4381672438167, multiplying that by 8, and adding on the position of the ..

\$\endgroup\$
3
\$\begingroup\$

JavaScript (Node.js), 331 bytes

(n,F=(i,I)=>(I%3-i%3)**2+((I/3|0)-(i/3|0))**2==5)=>Math.min(...(X=[...Array(9)].flatMap((e,i,a)=>F(i,n.search`0`)?[eval('for(k=0,N=n,S=[];!(t=S.filter(Z=>Z==N)[1])&&N!="123456780";(N=[...m=N],N[h=m.search`0`]=N[(H=k?a.findIndex((E,P)=>P!=M&F(P,h)):i,M=m.search`0`,H)],N[H]="0",S.push(N=N.join``),k++));t?-1:k')]:[])).length?X:[-1])

Try it online!

Takes a 9-character string where the dot is replaced by a zero.

Explanation

As the trick is really fun to find, I've hidden it behind a spoiler.

There are only two spaces that are a knight's move away from the zero. Let us consider one of the pieces. If we move it to the zero, then we can decide to move it back to where it was. However, that wastes moves. Since there are only two spaces that are a knight's move away from any given space, this means that only one other piece can be moved to the new position of the zero, other than the one we just moved. As a result, we must move that piece. Using the same reasoning as above, this means that there is only one "path" originating from a given move, because we only have one choice at each stage. Eventually, we will end up at the ideal arrangement. Now, to account for the impossible cases, notice that there are only so many possible moves. Eventually, we will reach an arrangement that we have already seen. If we do, that means the case is impossible and we can break out of the loop and return -1.

A problem I have is that this is way too long, so I'll try to keep golfing it.

Fixed a bug that would create outputs of Infinity for certain inputs.

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 40 39 38 bytes

-1 byte porting @Neil's 54 bytes Charcoal approach:

•4Gв©Tв•8×I•55˜u•SèDðkUþJk8*X+D56α‚ß®M

Try it online or verify all test cases.

Original answer:

•þÜε•SDIðkk._Tиü2vÐ{QiND56α‚ßq}DyèyRǝ}®

Try it online or verify all test cases.

Both programs take a flattened list of digits as input with " " as empty square.

Explanation:

•4Gв©Tв•        # Push compressed integer 4381672438167
 8×             # Repeat it 8 times as string
   I            # Push the input-list
    •55˜u•      # Push compressed integer 83270561
     S          # Convert it to a list of digits
      è         # Index each into the input
       D        # Duplicate it
        ðk      # Get the index of the space " "
          U     # Pop and store this index in variable `X`
        þ       # Remove the space by only keeping digits
         J      # Join it together to a string
          k     # Get the first 0-based index of this in the large string
           8*   # Multiply this by 8
             X+ # Add index `X`
D               # Duplicate it
 56α            # Get the absolute difference with 56
    ‚           # Pair both together
     ß          # Pop and push the minimum
      ®         # Push -1
       M        # Push the largest number on the stack
                # (after which it is output implicitly as result)
•þÜε•           # Push compressed integer 16507238
 S              # Convert it to a list of digits
  D             # Duplicate it
   I            # Push the input-list
    ðk          # Get the index of the space " "
      k         # Use that to index into the duplicated list of digits
       ._       # Rotate the list of digits that many times towards the left
         Tи     # Repeat it 10 times as list
ü2              # Get all overlapping pairs of this list
  v             # Loop over each pair `y`:
   Ð            #  Triplicate the current list
                #  (which will be the implicit input in the first iteration)
    {           #  Sort the top copy
                #  (where the space will go to the end of the sorted digits)
     Qi         #  If the two lists are still the same
       N        #   Push the loop index
        D56α‚ß  #   Same as above
              q #   Stop the program
                #   (after which the result is output implicitly)
       }        #  Close the if-statement
        DyèyRǝ  #  Swap the values at indices `y`:
        D       #   Duplicate the list once more
         yè     #   Get the values at the `y` indices
           yR   #   Push the reversed pair `y`
             ǝ  #   Insert the values back into the list at those indices
}               # Close the loop
 ®              # Push -1
                # (which is output implicitly if we haven't encountered the `q`)

See this 05AB1E tip of mine (section How to compress large integers?) to understand why •4Gв©Tв• is 4381672438167; •55˜u• is 83270561; and •þÜε• is 16507238.

\$\endgroup\$
3
  • \$\begingroup\$ I think D56α‚ß can be 28α28α for the same byte count, but maybe you can deduplicate that somehow? \$\endgroup\$
    – Neil
    Feb 18, 2022 at 8:29
  • \$\begingroup\$ @Neil I'm afraid not. I could do it like 28©α®α or 2F28α}, but both would be the same byte-count. \$\endgroup\$ Feb 18, 2022 at 8:33
  • \$\begingroup\$ Oh well. It saved me two bytes in Charcoal, so I thought I'd mention it just in case. \$\endgroup\$
    – Neil
    Feb 18, 2022 at 8:41
2
\$\begingroup\$

Python 3, 126 bytes

def f(a,s=[*range(1,9),0],m=0,n=8):
 for o in(3,2,7,0,5,6,1,8)*7:m+=a!=s or m-55;s[n],s[o],n=s[o],0,o
 return min(56-m or-1,m)

Try it online!

-1 byte thanks to Jonathan Allan

-3 bytes thanks to Arnauld

There are 56 possible permutations. From the starting position, we can walk a circular path 7 times, until we reach the starting position again. If the input is found, we return the number of steps m required. If the path is shorter the other way around, we return 56-m.

\$\endgroup\$
2
  • \$\begingroup\$ Does it really always work? For instance, [1,0,3,4,5,6,7,8,2] should return 1. \$\endgroup\$
    – Arnauld
    Feb 17, 2022 at 13:00
  • \$\begingroup\$ def f(a,s=[*range(1,9),0],p=(3,2,7,0,5,6,1,8)*7,m=0): saves one. \$\endgroup\$ Feb 17, 2022 at 13:58
1
\$\begingroup\$

Excel, 158 bytes

=IFERROR(LET(a,MID(A1&A2&A3,{2;7;6;1;8;3;4;9},1)*1,b,CONCAT(FILTER(a,a)),d,"2761834",f,(FIND(2,b)*8+1-XMATCH(0,a))*(1-ISERROR(FIND(b,d&d)))-1,MIN(f,56-f)),-1)

Link to Spreadsheet

\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6),  110 108  105 bytes

This is very similar to Jitse's answer.

Expects a comma-separated string.

a=>(b=[..."123456780"],g=k=>i=b!=a&&k--?g(k,b[(s="83270561")[k+1&7]]=b[p=s[k&7]],b[p]=0):k)(56)>28?56-i:i

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Ruby, 101 98 bytes

->n{a=[*1..8,0];z=j=-29
("I`;-XAf#"*7).bytes{|i|j+=1;a==n&&z=j;a[i/9%9],a[i%9]=a[i%9],0}
28-z.abs}

Try it online!

Fairly straightforward. Cycle generates all 56 possible positions and compares with the input.

Saved some bytes off the orignal version by counting from the solved position at -28 through 0 to +27, and using 28-z.abs to decode the output.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.