34
\$\begingroup\$

Create a program or function to unjumble a square of digits by flipping (reversing around the centre point) only rows and columns.

Input

Input will be a 9x9 grid of digits in the form of a 9 line string like the following:

986553229
264564891
759176443
643982153
567891234
526917874
685328912
891732537
117644378

This input format is non-negotiable - any solutions which are "creative" with the input format will be considered invalid.

Output

Output should be a list of flip moves which, when applied to the input in the given order, should recreate the target grid.

An example output (not a solution to the previous input example):

28IF5D3EAB9G3

This output format is also non-negotiable. There should be no newlines or spaces in the output, only the characters 1-9 and A-I (lower case characters are acceptable in place of upper case characters if you prefer).

The target grid (the state you need to recreate) is as follows:

123456789
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345678

The numbers 1-9 should be used as instructions to flip the rows, and the letters A-I should be used for the columns. This is shown below with the grid in its restored state.

     ABCDEFGHI
     |||||||||
     vvvvvvvvv
1 -> 123456789
2 -> 234567891
3 -> 345678912
4 -> 456789123
5 -> 567891234
6 -> 678912345
7 -> 789123456
8 -> 891234567
9 -> 912345678

So an 8 means flip the second row from the bottom, and an F means flip the sixth column.

In the case that no solution is possible, the program should end without outputting anything at all.

Examples

Input:

987654321
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345678

Output:

1

In this case only the top row needs flipping to return to the goal state.

Input:

123456788
234567897
345678916
456789125
567891234
678912343
789123452
891234561
912345679

Output:

I

In this case only the final column (column I) needs flipping to recreate the goal state.

Input:

123456788
798765432
345678916
456789125
567891234
678912343
789123452
891234561
912345679

Output:

2I

In this case we need to flip row 2 and then flip column I to return to the goal state.

Notes:

  • Please include an example usage in your answer.
  • The output given does not have to be the shortest sequence that will return the goal state - any sequence which returns the goal state will do as long as it works (i.e. as long as I can test it)
  • I'll endeavour to test each answer and upvote all those that work and have obviously had an attempt at golfing.
  • This is an open-ended competition - I'll accept the shortest answer sometime next week, but if a newer valid answer comes along which is shorter at any point in the future I'll change the accepted answer to reflect that.
  • The bounty has been set at 200 reputation for the shortest answer received by 23:59:59 (GMT) on 26/01/2014 The bounty was awarded to Howard for his 268 character GolfScript solution.

Testing

Please provide your program's output for the following three test grids with your answer:

986553229
264564891
759176443
643982153
567891234
526917874
685328912
891732537
117644378

927354389
194762537
319673942
351982676
567891234
523719844
755128486
268534198
812546671

813654789
738762162
344871987
341989324
567891234
576217856
619623552
194435598
926543271

I've created a small Python program to generate valid grids for testing purposes:

import random

def output(array):
  print '\n'.join([''.join(row) for row in array])

def fliprow(rownum, array):
  return [row[::1-2*(rownum==idx)] for idx,row in enumerate(array)]

def flipcol(colnum, array):
  return zip(*fliprow(colnum, zip(*array)))

def randomflip(array):
  op=random.randint(0,1)
  row=random.randint(0,9)
  if(op==1):
    return fliprow(row, array)
  else:
    return flipcol(row, array)

def jumble(array):
  arraycopy=array
  for i in range(10, 1000):
    arraycopy=randomflip(arraycopy)
  return arraycopy

startarray=[
['1','2','3','4','5','6','7','8','9'],
['2','3','4','5','6','7','8','9','1'],
['3','4','5','6','7','8','9','1','2'],
['4','5','6','7','8','9','1','2','3'],
['5','6','7','8','9','1','2','3','4'],
['6','7','8','9','1','2','3','4','5'],
['7','8','9','1','2','3','4','5','6'],
['8','9','1','2','3','4','5','6','7'],
['9','1','2','3','4','5','6','7','8']]

print output(jumble(startarray))
\$\endgroup\$
  • 8
    \$\begingroup\$ I just wrote a short solution that randomly flipped rows/columns until the sort was complete. After 500 million iterations it still had not solved the first puzzle you gave (where you only need to flip row 1). Randomness does not appear to be a usable solution to this problem! \$\endgroup\$ – Josh Jan 15 '14 at 15:20
  • 3
    \$\begingroup\$ @Josh Not surprising. This problem appears to be very similar to solving a rubik's cube. I think some kind of breadth-first search would be the best brute force. That being said, the random algorithm theoretically has to terminate eventually, and appears to fit the rules specified. \$\endgroup\$ – Cruncher Jan 15 '14 at 16:49
  • 4
    \$\begingroup\$ Brute force isn't needed. Consider the fact that each grid tile can only end up in one of four positions: its correct location, flipped X, flipped Y, or flipped XY. It may help you to mentally treat the grid as having (0,0) being the center-most tile. If you're solving tile (-2, 4), the only locations the target number could be is (-2, 4), (2, 4), (2, -4), or (-2, -4). \$\endgroup\$ – Mr. Llama Jan 15 '14 at 18:21
  • 2
    \$\begingroup\$ @Cruncher: Using whole row/column flips makes that impossible. For example, try to take the upperleftmost 1 (A1) and move it to B1. You can get a 1 to the position B1, but it'll be the tile from B9, not the tile from A1. Because we're only allowed whole row/column flips, the upperleftmost 1 will only ever be in one of the four outermost corners. If I've mistaken the rules, please let me know. \$\endgroup\$ – Mr. Llama Jan 15 '14 at 21:49
  • 7
    \$\begingroup\$ Congratulations, Gareth. This is a very well-designed problem. Also, quite challenging. \$\endgroup\$ – DavidC Jan 16 '14 at 2:45
7
+200
\$\begingroup\$

GolfScript, 300 279 268 characters

n%`{\5,{.9+}%{;.2/\2%},\;''{1${.9/7+7*+}%+:z;}:?~{{.9<77*{\zip\9-}>:Z~{1$!{-1%}*\(\}@%\Z;}/}:E~{:^;{:c;.`{[\E[.^=\8^-=]{.c=\8c-=}%[^c+^8c-+8^-c+16c-^-]{9%49+}%=}+[[]]:K[[8^- 17c-][^9c+]1$]{:s;{[[]s.+.2$+]{1$+}/}%.&}/\,K+0=z?E}5,/}5,/{{+9%)}+9,%''*}9,%={z:u;}*}+1024,/u

Note that this code is extremely slow (also due to heavy code-block manipulation) and might run several minutes. The code is very un-golfscript-ish with lots of variables and explicit loops.

I had written a more analytic solution which ran for less than a second. I completely broke that one during golfing. Unfortunately, I wasn't able to backtrack or repair the code in the last two days. Therefore, I produced this try-and-check version which is shorter anyways.

The answers for the puzzles given above:

1A2C4D9G9G9G9G1C1C1C1C9F9F9F9F1D1D1D1D2A2A2A2A8H8H8H8H2B2B2B2B2C2C8F8F2D2D2D2D3A3A7I7I3B3B7H7H7G7G7G7G3D3D7F7F6I6I6I6I4A4A4A4A6H6H6H6H6G6G4C4C4C4C6F6F4D4D

1AB39I9I1A1A9I9I1B1B9F9F8I8I8I8I2B2B8H8H8G8G8G8G2D2D2D2D3A3A3A3A7H7H7H7H3C3C3C3C3D3D7F7F6I6I4A4A6I6I4B4B4B4B6G6G4C4C4C4C6F6F6F6F4D4D

1A34D9I9I9I9I1A1A1A1A1B1B1B1B9G9G1C1C1C1C9F9F9F9F1D1D9F9F8I8I2A2A2A2A8H8H8H8H2C2C2C2C8F8F2D2D8F8F7I7I7I7I3A3A3B3B7G7G7G7G3C3C3C3C6I6I6I6I6H6H6H6H4B4B4B4B6G6G6G6G4C4C6G6G6F6F4D4D6F6F
\$\endgroup\$
  • \$\begingroup\$ Well, it's going to be pretty hard work beating this... \$\endgroup\$ – Gareth Jan 26 '14 at 20:22
  • \$\begingroup\$ Seems I was wrong... \$\endgroup\$ – Gareth Jan 26 '14 at 21:03
  • \$\begingroup\$ @Gareth I knew this is a challenge which would be hard with golfscript against e.g. mathematica. \$\endgroup\$ – Howard Jan 26 '14 at 21:10
  • 1
    \$\begingroup\$ @Howard - what approach did you use? What is 'try-and-check version' you mentioned? \$\endgroup\$ – SergeyS Jan 27 '14 at 10:28
24
\$\begingroup\$

Mathematica 582 575 503 464 282

To fight with golfscripters I have to use heavy artillery!

i = "986553229
264564891
759176443
643982153
567891234
526917874
685328912
891732537
117644378";

a=Array;h@M_:=Join@@a[9(M〚##〛/. 9->9⌈2Random[]⌉)+Abs[{##}-5]&,n={9,9}];
For[i_~t~j_:=i{#2,10-#2}+j#-9&~a~{9,4},!ListQ[e=GroupElementToWord[
PermutationGroup[Cycles/@Join[1~t~9,9~t~1]],
h[ToCharacterCode@StringSplit@i-48]~FindPermutation~h@a[Mod[8+##,9,1]&,n]]],];
e~IntegerString~36<>""

Output:

g69g69g8g8g7g7gd96d96d8d8d7d7dh6h64a6a46d6d4g4g6b6b7h7h7c7c2a8a27b7bd8db8b7f7fg8g82c2c94a4a3a3aigfdc91

Here PermutationGroup[...] sets up possible flips and GroupElementToWord[...] solves the problem (about 0.2 sec). The main problem is that it is difficult to identify the correspondence between the position of 9 in the initial and the final grid. For golfing I do it randomly (it takes several seconds). There are some warnings but one can ignore them.

Other to test grids:

g69g69g8g8g7g7gh89h89h7h7h6h6hf6f6g6g64f4f4h4hg7g73g3g2a8a28d8db8b83d3dg8g82c2c9a3a643a3a2g9f9d9c9ga
h89h89h7h7h6h6h6h6h6f6f6g6g6d6d3a7a37g7g7h7h3c3c2a8a27b7b8d8d2f2f8b8b3f3f2b2ba2a764a8aih9g9c9gb1i

It completely reproduces the examples:

1
i
2i

Previous solution (464)

without any clever built-in functions and with runtime 4 ms:

M=ToCharacterCode@StringSplit@i-48;
S="";s=Signature;H=(S=S<>{#,#2+9}~IntegerString~36)&;
A=(m=M〚##〛)-9Mod[m+##,2]&[s@{2#3,5}#,2#2#3~Mod~2-#2]&~Array~{4,4,4};
u=s/@Join@@A;
H@@({k,l}=#&@@@#~Position~1&/@{v=u〚13;;〛;{h=#2u〚2〛,-#u〚5〛,-#u〚9〛}&@@v,v〚4〛=u〚4〛h;v});
A〚k〛=A〚k,;;,{2,1,3,4}〛;A〚;;,l〛=A〚;;,l,{3,2,1,4}〛;
MapIndexed[4#≠#4&&H@@@If[#2<3,#0[#3,#,#2,#4];k,#0[#,#3,#4,#2];10-k]&@@
If[s@#<0,#〚{1,3,2,4}〛,#]&@Ordering[k={#2,#2};#]&,A,{2}];
M〚5,1〛<5&&5~H~{};M〚1,5〛<5&&{}~H~5;S

All new lines here are not necessary.

Output:

3b9i9i1a1a1a1a9i9i1a1a9h9h1b1b1b1b9h9h9g9g1c1c9g9g9f9f1d1d9f9f8h8h2b2b8f8f8f8f7i7i7h7h3b3b3b3b7h7h3b3b7h7h7g7g3c3c7g7g3c3c7f7f6i6i4a4a6h6h4b4b4b4b6g6g4c4c6g6g4c4c6f6f4d4d4d4d6f6f4d4d6f6f4d4d

Other two test grids:

13ab9i9i1a1a9i9i9h9h1b1b1b1b9h9h9f9f8i8i8i8i8h8h2b2b2b2b8h8h8h8h8g8g8g8g8f8f2d2d2d2d8f8f2d2d7i7i3a3a3a3a7i7i7h7h3b3b7h7h3b3b7g7g3c3c3c3c7g7g3c3c7f7f3d3d3d3d7f7f7f7f6i6i4a4a6i6i6h6h4b4b4b4b6h6h4b4b6g6g4c4c4c4c6f6f4d4d4d4d6f6f4d4d6f6f
2bc9i9i1a1a9i9i9g9g1c1c9g9g1c1c9f9f1d1d1d1d8i8i8i8i8h8h2b2b2b2b8f8f2d2d7i7i7h7h3b3b3b3b7h7h3b3b7g7g3c3c7f7f3d3d3d3d7f7f3d3d6i6i4a4a4a4a6h6h4b4b6g6g6g6g6f6f4d4d

Visualization:

anim = Reap[Fold[Function[{m, i}, 
 If[i > 9, (Sow@Grid[#, Background -> {i - 9 -> Pink, None}] & /@ {m, #}; #) &@
   Transpose@MapAt[Reverse, Transpose@m, i - 9], (Sow@Grid[#, 
         Background -> {None, i -> Pink}] & /@ {m, #}; #) &@
   MapAt[Reverse, m, i]]], M, IntegerDigits[FromDigits[S, 36], 36]]];

ListAnimate[Join[{#, #} &@Grid@M, anim[[2, 1]], {#, #} &@Grid@anim[[1]]], 5]

enter image description here

The input string i can be generated randomly by

M = Array[Mod[8 + ##, 9, 1] &, {9, 9}];
(M[[#]] = Reverse@M[[#]]; M[[All, #2]] = Reverse@M[[All, #2]];) & @@@
   RandomInteger[{1, 9}, {10000, 2}];
i = ToString /@ # <> "\n" & /@ M <> ""

Brief discussion

  • Flips can interchange only these elements ("quadruple"):

    enter image description here

  • It is possible to interchange these elements separately from other elements only if the initial and the final order has the same signature.

  • Flips of these four elements form the alternating group of degree 4 ( = group of rotations of the tetrahedral). Every element of this group is a composition of 2 generating elements. So if we know the initial and final position we can decompose the corresponding transformation as a combination of a simple flips.

Details

For sportsmanship I post details before the end of the bounty!

M=ToCharacterCode@StringSplit@i-48;

Convert the string i to the matrix M.

S="";s=Signature;H=(S=S<>{#,#2+9}~IntegerString~36)&;

We will append chars to S. Now it is the empty string. H[i,j] will add the character i (1,2,3,...,9) and the character j (a,b,c,...,i in base-36).

A=(m=M〚##〛)-9Mod[m+##,2]&[s@{2#3,5}#,2#2#3~Mod~2-#2]&~Array~{4,4,4};

I convert elements as

enter image description here

to obtain the target matrix in the following form

enter image description here

Then there are two main steps in my algorithm

  1. Find flips to obtain the signatures as in the target matrix (e.g. the signature of {-7,-1,1,7} is 1 and the signature of {-6,2,-2,6} is -1):

    u=s/@Join@@A;
    H@@({k,l}=#&@@@#~Position~1&/@{v=u〚13;;〛;{h=#2u〚2〛,-#u〚5〛,-#u〚9〛}&@@v,v〚4〛=u〚4〛h;v});
    A〚k〛=A〚k,;;,{2,1,3,4}〛;A〚;;,l〛=A〚;;,l,{3,2,1,4}〛;
    
  2. Rotate every "quadruple" to obtain the right order:

    MapIndexed[4#≠#4&&H@@@If[#2<3,#0[#3,#,#2,#4];k,#0[#,#3,#4,#2];10-k]&@@
    If[s@#<0,#〚{1,3,2,4}〛,#]&@Ordering[k={#2,#2};#]&,A,{2}];
    

    It is the most nontrivial part of the algorithm. For example, the transformation 1b1b will convert {-7,-1,1,7} to {-1,1,-7,7}. The transformation 9h9h will convert {-7,-1,1,7} to {-7,7,-1,1}. So we have two maps

    {1,2,3,4} -> {2,3,1,4}
    {1,2,3,4} -> {1,4,2,3}
    

    and we want to convert an arbitrary ordering {x,y,z,w} to {1,2,3,4}. The simple method is (except a random search)

    repeat   
    {x, y, z, w} -> If[z < 3, {y, z, x, w}, {x, w, y, z}]
    until {1,2,3,4}
    

    I can't proof it, but it works!

The last step is

M〚5,1〛<5&&5~H~{};M〚1,5〛<5&&{}~H~5;S

It performs trivial flips of the center row and the center column and return the result.

\$\endgroup\$
  • \$\begingroup\$ @Gareth Can I use small characters in the output? It saves me a number of characters. \$\endgroup\$ – ybeltukov Jan 18 '14 at 4:05
  • \$\begingroup\$ Yes, I'll accept lower-case characters in the output (I'll change the question to note this). I don't have Mathematica so could some other Mathematica user confirm that the code actually generates the output? I've validated the three test solutions and they are all correct, so +1. Nice job! \$\endgroup\$ – Gareth Jan 18 '14 at 14:26
  • \$\begingroup\$ Just curious - what is a performance of your approach? Did you test on inputs generated by thousands of flips? \$\endgroup\$ – SergeyS Jan 23 '14 at 5:50
  • \$\begingroup\$ @SergeyS Yes, it takes about 50 ms :) \$\endgroup\$ – ybeltukov Jan 25 '14 at 0:05
  • \$\begingroup\$ @Gareth I rewrite my program, could you check the results? My tests have shown that everything is correct. \$\endgroup\$ – ybeltukov Jan 25 '14 at 3:57
7
\$\begingroup\$

J 487 438

q=:3 :'(>:9|+/~i.9)=/&((,{;/(,.8&-)y){])g'
l=:2 :0
:
o=:o,(m+x){a.
x&(|.@{`[`]})&.v y
)
r=:49 l]
c=:97 l|:
w=:2 :'g=:4 v^:(4=(<m){g)g'
p=:_1=C.!.2@,@:I.@q
t=:2 :'for_i.>:i.3 do.g=:i v^:(p m*i)g end.'
z=:2 :0
'i j I J'=.y,8-y
g=:".'(',(,' ',.,(I.m{q y){,;._1 n),'])^:2 g'
)
d=:3 :0
g=:9 9$".,_ list,' ',.y
o=:''
0 4 w c
4 0 w r
0 1 t c
g=:0 c^:(-.(p 1 0)=p 1 2)g
1 0 t r
for_k.>,{;~i.4 do.0 z';;jcir;irjc;Irjc'k
3 z';;IrJc;JcIr;'k end.o
)

d is a verb which takes a grid string in the specified format and returns a solution string in the specified format.

Example use:

   d '987654321',LF,'234567891',LF,'345678912',LF,'456789123',LF,'567891234',LF,'678912345',LF,'789123456',LF,'891234567',LF,'912345678'
bcda2341a1a1b1b1c1c1d1da2a2b2b2c2c2d2d2a3a3b3b3c3c3d3d3a4a4b4b4c4c4d4d4

Now accepts either newline type.

Solutions to the test grids:

b3a1a11b1bc9c99g9gd9d99f9fb8b8f8f87i7i7h7hc3c3g7g77f7fa6a64b4bh6h6c4c4g6g6d6d6f6f6
cd24a9a91c1c1d1d9f9fa2a2i8i88h8hc2c2g8g82d2d3b3bh7h7d3d37f7fa6a64b4bg6g64d4d6f6f
bc2a9a99i9ic1c1g9g91d1df9f9i8i8b2b2h8h82c2cd8d87i7ib3b3c7c7d3d34a4ai6i6b6b6g6g6d6d6

I'm fairly new to J; this could probably be golfed even further.


Checking for invalid/unsolvable grids incurs a 123 character penalty. I don't think the other answers to date have such error checking.

To do so, change the first line of d to this:

if.-.+./89 90=#y do.0 return.end.if.-.*./(/:~y)=/:~(#y)$'123456789',LF do.0 return.end.g=:9 9$".,_ list,' ',.y

and the last line to this:

3 z';;IrJc;JcIr;'k end.if.*./,g=>:9|+/~i.9 do.o return.end.0

I've chosen to return 0 on such errors as returning an empty string would be indistinguishable from correctly solving a fully solved grid. Note that this assumes UNIX newlines (again).

\$\endgroup\$
  • \$\begingroup\$ Congratulations, you've just gone into the lead. :-) \$\endgroup\$ – Gareth Jan 25 '14 at 21:21
  • \$\begingroup\$ Looks like your input is not one string as required by rules, or I miss something? \$\endgroup\$ – SergeyS Jan 26 '14 at 9:35
  • \$\begingroup\$ @SergeyS: You might be confused. As far as I know, J has no way of placing escapes (such as newline) in string literals. The construction 'a',LF,'b' in J is similar to "a"+"\n"+"b" in languages where + works to append strings. \$\endgroup\$ – AlliedEnvy Jan 26 '14 at 9:38
  • \$\begingroup\$ Ok, it makes sense than, thanks. \$\endgroup\$ – SergeyS Jan 26 '14 at 9:43
  • \$\begingroup\$ I was just reading the section on files from the 1962 APL book, and I think @AlliedEnvy is correct. This is how the data will appear to the program if read from a file in the question's format. The LFs represent partitions of the sequential file. \$\endgroup\$ – luser droog Mar 9 '14 at 5:19
5
\$\begingroup\$

C# 540 399

Well, sacrificed performance (now it takes up to 30 seconds), introduced dynamic variables, slightly changed logic of solution. And yes, now it is expecting input as one string with line-breaks (as required in rules).

Of course C# do not have predefined math functions, so it would be hard to fight with Mathematica guys. Nevertheless, this was a great challenge, thanks to the author!

string S(string _){for(i=0,e=1>0;e;){
for(h=v=j=0;j<89;)m[j/10,j%10+9]=_[j++]-49;a="";
for(j=i++;j>0;v++,j/=2)if(j%2>0)F(v);
for(;h<9&(h<4|!e);h+=j/36,j%=36)if((e=m[h,g=j++%9+9]!=(t=(h+g)%9))|m[v=8-h,g]==t){F(v);F(g);F(v);F(g);}
}return a;}void F(int z){for(f=z<9;++l<9;)m[0,l]=m[f?z:l,f?9+l:z];for(;l-->0;)m[f?z:l,f?9+l:z]=m[0,8-l];a+=(char)(z+=f?49:56);}
dynamic h,v,i,j,e,t,l=-1,g,a,m=new int[9,19],f;

Test grids:

3B9A9A9B9B9C9C9D9D9F9F9G9G9H9H9I9I9B9B9C9C9D9D9F9F9G9G9H9H9C9C9D9D9C9C9D9D8B8B8F8F8H8H8B8B8F8F8B8B8H8H7B7B7C7C7F7F7H7H7I7I7H7H6A6A6B6B6C6C6D6D6F6F6H6H6A6A6B6B6D6D6F6F6D6D6D6D6F6F5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I

13AB9A9A9B9B9F9F9H9H9A9A9B9B9H9H9I9I8B8B8D8D8F8F8G8G8H8H8I8I8B8B8G8G8H8H8I8I8H8H7A7A7B7B7C7C7D7D7F7F7G7G7I7I7A7A7D7D7F7F7I7I7F7F6A6A6B6B6C6C6D6D6F6F6G6G6H6H6I6I6A6A6C6C6F6F6I6I6A6A6A6A5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I

2BC9A9A9C9C9D9D9F9F9A9A9D9D9I9I8B8B8D8D8H8H8I8I8B8B8D8D8I8I7B7B7C7C7D7D7F7F7G7G7H7H7I7I7C7C7C7C7G7G6A6A6B6B6D6D6F6F6G6G6I6I6A6A6B6B6D6D6G6G6D6D6F6F5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I

Old Solution (540)

Works in less than a second on any input (tested on thousands randomly generated grids). Maximum length of output string is 165 (initially any grid was solved in no more than 82 flips, but during golfing I sacrificed this).

string S(string[]_){for(i=0;i<1<<18;){
for(j=0;j<81;)m[j/9+49,j%9+65]=_[j/9][j++%9]-49;a="";char g,h='1',v='9',b,x=h,y;
for(j=i;j>0;x=x==v?'A':++x,j/=2)if(j%2>0)F(x);j=i+1;
for(i+=1<<19;h<58;h++,v--)for(g='A',b='I';g<74;g++,b--){
t=(h+g-6)%9;e=m[h,g];q=m[v,g];i=h>52&t!=e?j:i;
if(e!=t|q==t){x=q==t?v:g;y=q==t?g:v;
if(m[h,b]==t){x=b;y=h;}
F(x);F(y);F(x);F(y);}}}return a;}
void F(char z){var f=z<65;for(l=0;l<4;l++){n=m[d=f?z:49+l,s=f?65+l:z];m[d,s]=m[o=f?z:57-l,u=f?73-l:z];m[o,u]=n;}a+=z;}
int i,j,q,e,t,l,s,d,n,u,o;int[,]m=new int[99,99];string a;

Answer for example 1:

15A5A5B5B5C5C5D5DE5E55F5F5G5G5H5H5I5I

Answer for example 2:

19AI1I1H1H1G1G1F1F19F9F9G9G9H9H9I9I8A8AI8I87A7AI7I76A6AI6I65A5A5B5B5C5C5D
5DE5E55F5F5G5G5H5H5I5I

Answer for example 3:

129AI1I1H1H1G1G1F1F19F9F9G9G9H9H9I9I8A8AI8I87A7AI7I76A6AI6I65A5A5B5B5C5C5
D5DE5E55F5F5G5G5H5H5I5I

Answers for test squares:

346B9A9AH1H1C9C9D9D99F9F9G9GH9H99I9IB8B8F8F87B7B7C7C7F7FH7H77I7I6A6A6B6BC6C66D6DG6G6H6H66I6I5A5A5B5B5C5C5D5DE5E55F5F5G5G5H5H5I5I

1346ABA9A9H1H19F9FH9H99I9IH2H28D8D8F8FG8G8I8I8I3I37B7B7C7CF3F37G7GI7I7H4H4D6D66F6F5A5A5B5B5C5C5D5DE5E55F5F5G5G5H5H5I5I

2BCA9A99C9CF1F19F9F9I9IH2H2D8D88H8HI8I87B7BC7C77D7D7F7F7H7H7I7II4I4B6B6D6D6G6G66I6I5A5A5B5B5C5C5D5DE5E55F5F5G5G5H5H5I5I
\$\endgroup\$
  • \$\begingroup\$ I'm just downloading Mono for my Mac now so I can test the program itself, but I do already have a validator which runs a given solution on a given grid and tells me if the solution is a valid solution for that grid - and it's telling me that the three example solutions you've given me are not valid. I'm just investigating why now. \$\endgroup\$ – Gareth Jan 23 '14 at 7:39
  • \$\begingroup\$ Aha! I've figured out what's happened here! Your given answers seem to be answers to the 3 examples and not the three test grids (which are lower down in the question). They are indeed correct solutions to those grids, though they are quite a bit longer than 1, A, and 2I which are the simplest solutions - but that doesn't actually matter since I'm not judging on grid solution length :-) If you could edit and give the answers for the 3 test grids (I'm going to see if I can get this running on my Mac now) I can give you your +1. \$\endgroup\$ – Gareth Jan 23 '14 at 7:56
  • \$\begingroup\$ @Gareth - oops, I did missed answers for test squares, thanks for pointing that out. I have added them now to my answer. \$\endgroup\$ – SergeyS Jan 23 '14 at 8:10
  • \$\begingroup\$ Excellent, thanks for that. They've all validated fine. Xamarin wouldn't run on my Mac for some reason, so I'm going to have to test the program at work in a couple of hours. \$\endgroup\$ – Gareth Jan 23 '14 at 8:18
  • \$\begingroup\$ @Gareth - Actually there is nothing specific for C# in that code, one can probably convert it to Java or even C++ without much pain and... golf some characters out of it :) Also feel free to convert it to GolfScript or something more concise - this may appear twice or more shorter ;) \$\endgroup\$ – SergeyS Jan 23 '14 at 8:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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