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

Improve this question
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Can we replace . with something like 0 in the input? \$\endgroup\$ Commented Feb 17, 2022 at 8:27

7 Answers 7

Reset to default
3
\$\begingroup\$

Charcoal, 54 52 bytes

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

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:

≔⭆³Ｓθ

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

≔⭆83270561§θＩιθ

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

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

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 ..

Improve this answer
\$\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.

Improve this answer
\$\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.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ I think D56α‚ß can be 28α28α for the same byte count, but maybe you can deduplicate that somehow? \$\endgroup\$ Commented 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\$ Commented 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\$ Commented 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.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Does it really always work? For instance, [1,0,3,4,5,6,7,8,2] should return 1. \$\endgroup\$ Commented 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\$ Commented 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

Improve this answer
\$\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!

Improve this answer
\$\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.

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.