Flippin 'Squares

34

Utwórz program lub funkcję, aby odłączyć kwadrat cyfr, odwracając (odwracając punkt środkowy) tylko wiersze i kolumny.

Wkład

Dane wejściowe będą siatką cyfr 9 x 9 w postaci ciągu 9 wierszy, jak poniżej:

986553229
264564891
759176443
643982153
567891234
526917874
685328912
891732537
117644378

Ten format wejściowy nie podlega negocjacji - wszelkie rozwiązania, które są „kreatywne” z formatem wejściowym, zostaną uznane za nieprawidłowe.

Wydajność

Wyjściem powinna być lista ruchów odwracających, które zastosowane do danych wejściowych w podanej kolejności powinny odtworzyć siatkę docelową.

Przykładowe dane wyjściowe (nie rozwiązanie poprzedniego przykładu wprowadzania):

28IF5D3EAB9G3

Ten format wyjściowy również nie podlega negocjacji. Wyjście nie powinno zawierać znaków nowej linii ani spacji, a jedynie znaki 1- 9i A- I(małe litery są dopuszczalne zamiast wielkich liter, jeśli wolisz).

Siatka docelowa (stan, który należy odtworzyć) jest następująca:

123456789
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345678

Liczby 1- 9powinny być używane jako instrukcje do odwracania wierszy, a litery A- Ipowinny być używane dla kolumn. Jest to pokazane poniżej z przywróconą siatką.

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

Tak więc 8środek przewraca drugi rząd od dołu, a Fśrodek przewraca szóstą kolumnę.

W przypadku, gdy żadne rozwiązanie nie jest możliwe, program powinien zakończyć się bez wypisywania niczego.

Przykłady

Wkład:

987654321
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345678

Wydajność:

1

W takim przypadku tylko górny wiersz wymaga przewrócenia, aby powrócić do stanu docelowego.

Wkład:

123456788
234567897
345678916
456789125
567891234
678912343
789123452
891234561
912345679

Wydajność:

I

W takim przypadku tylko ostatnia kolumna (kolumna I) wymaga odwrócenia, aby odtworzyć stan celu.

Wkład:

123456788
798765432
345678916
456789125
567891234
678912343
789123452
891234561
912345679

Wydajność:

2I

W takim przypadku musimy odwrócić wiersz, 2a następnie odwrócić kolumnę, Iaby powrócić do stanu docelowego.

Uwagi:

  • W odpowiedzi podaj przykład użycia.
  • Podane dane wyjściowe nie muszą być najkrótszą sekwencją, która zwróci stan celu - każda sekwencja, która zwróci stan celu, będzie działać tak długo, jak to działa (tj. Tak długo, jak mogę to przetestować)
  • Postaram się przetestować każdą odpowiedź i głosować za tymi wszystkimi, którzy działają i oczywiście próbowali grać w golfa.
  • To są zawody otwarte - zaakceptuję najkrótszą odpowiedź w przyszłym tygodniu, ale jeśli pojawi się nowa, ważniejsza odpowiedź, która będzie krótsza w dowolnym momencie w przyszłości, zmienię zaakceptowaną odpowiedź, aby to odzwierciedlić .
  • Nagroda została ustalona na 200 reputacji za najkrótszą odpowiedź otrzymaną do 23:59:59 (GMT) w dniu 26.01.2014. Nagroda została przyznana Howardowi za jego 268-znakowe rozwiązanie GolfScript .

Testowanie

Podaj odpowiedź swojego programu dla następujących trzech siatek testowych:

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

Stworzyłem mały program w języku Python do generowania prawidłowych siatek do celów testowych:

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))
Gareth
źródło
8
Właśnie napisałem krótkie rozwiązanie, które losowo przewracało wiersze / kolumny aż do zakończenia sortowania. Po 500 milionach iteracji wciąż nie rozwiązał pierwszej podanej układanki (w której wystarczy przerzucić wiersz 1). Losowość nie wydaje się użytecznym rozwiązaniem tego problemu!
Josh
3
@Josh Nic dziwnego. Ten problem wydaje się bardzo podobny do rozwiązania kostki rubika. Uważam, że jakaś brutalna siła byłaby najlepszym przeszukiwaniem w pierwszej kolejności. To powiedziawszy, losowy algorytm teoretycznie musi się ostatecznie skończyć i wydaje się pasować do określonych reguł.
Cruncher
4
Brutalna siła nie jest potrzebna. Weź pod uwagę fakt, że każdy kafelek siatki może skończyć się tylko w jednej z czterech pozycji: w prawidłowej lokalizacji, odwrócony X, odwrócony Y lub odwrócony XY. Pomoże ci to potraktować w myślach kratkę jako (0,0) będącą środkową płytką. Jeśli rozwiązywania płytki (-2, 4), jedyne lokalizacje numer docelowy może być to (-2, 4), (2, 4), (2, -4), lub (-2, -4).
Pan Llama,
2
@Cruncher: Użycie całych wierszy / kolumn powoduje, że jest to niemożliwe. Na przykład spróbuj wziąć najwyższą lewą 1 ( A1) i przesuń ją do B1. Możesz dostać 1pozycję B1, ale będzie to płytka z B9, a nie płytka z A1. Ponieważ wolno nam przewracać tylko cały wiersz / kolumnę, najwyższy lewy 1 będzie zawsze w jednym z czterech najbardziej zewnętrznych narożników. Jeśli popełniłem błąd, daj mi znać.
Pan Llama,
7
Gratulacje, Gareth. To bardzo dobrze zaprojektowany problem. Także dość trudne.
DavidC

Odpowiedzi:

7

GolfScript, 300 279 268 znaków

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

Zauważ, że ten kod jest bardzo wolny (również z powodu ciężkich manipulacji blokami kodu) i może działać kilka minut. Kod jest bardzo nieskryptowy z dużą ilością zmiennych i wyraźnych pętli.

Napisałem bardziej analityczne rozwiązanie, które działało krócej niż sekundę. Zepsułem to całkowicie podczas gry w golfa. Niestety nie byłem w stanie przywrócić ani naprawić kodu w ciągu ostatnich dwóch dni. Dlatego stworzyłem tę wersję próbną, która i tak jest krótsza.

Odpowiedzi na puzzle podane powyżej:

1A2C4D9G9G9G9G1C1C1C1C9F9F9F9F1D1D1D1D2A2A2A2A8H8H8H8H2B2B2B2B2C2C8F8F2D2D2D2D3A3A7I7I3B3B7H7H7G7G7G7G3D3D7F7F6I6I6I6I4A4A4A4A6H6H6H6H6G6G4C4C4C4C6F6F4D4D

1AB39I9I1A1A9I9I1B1B9F9F8I8I8I8I2B2B8H8H8G8G8G8G2D2D2D2D3A3A3A3A7H7H7H7H3C3C3C3C3D3D7F7F6I6I4A4A6I6I4B4B4B4B6G6G4C4C4C4C6F6F6F6F4D4D

1A34D9I9I9I9I1A1A1A1A1B1B1B1B9G9G1C1C1C1C9F9F9F9F1D1D9F9F8I8I2A2A2A2A8H8H8H8H2C2C2C2C8F8F2D2D8F8F7I7I7I7I3A3A3B3B7G7G7G7G3C3C3C3C6I6I6I6I6H6H6H6H4B4B4B4B6G6G6G6G4C4C6G6G6F6F4D4D6F6F
Howard
źródło
Cóż, pokonanie tego będzie ciężką pracą ...
Gareth
Wygląda na to, że się myliłem ...
Gareth
@Gareth Wiedziałem, że jest to wyzwanie, które byłoby trudne przy golfa przeciwko np. Matematyce.
Howard
1
@Howard - jakie podejście zastosowałeś? Czym jest „wersja próbna”, o której wspominałeś?
SergeyS
24

Mathematica 582 575 503 464 282

Do walki z golfistami muszę używać ciężkiej artylerii!

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

Wydajność:

g69g69g8g8g7g7gd96d96d8d8d7d7dh6h64a6a46d6d4g4g6b6b7h7h7c7c2a8a27b7bd8db8b7f7fg8g82c2c94a4a3a3aigfdc91

Tutaj PermutationGroup[...]ustawia możliwe odwroty i GroupElementToWord[...]rozwiązuje problem (około 0.2sekundy). Głównym problemem jest to, że trudno jest ustalić zgodność między pozycją 9w początkowej i końcowej siatce. Do gry w golfa robię to losowo (zajmuje to kilka sekund). Istnieją pewne ostrzeżenia, ale można je zignorować.

Inne do testowania siatek:

g69g69g8g8g7g7gh89h89h7h7h6h6hf6f6g6g64f4f4h4hg7g73g3g2a8a28d8db8b83d3dg8g82c2c9a3a643a3a2g9f9d9c9ga
h89h89h7h7h6h6h6h6h6f6f6g6g6d6d3a7a37g7g7h7h3c3c2a8a27b7b8d8d2f2f8b8b3f3f2b2ba2a764a8aih9g9c9gb1i

Całkowicie odtwarza przykłady:

1
i
2i

Poprzednie rozwiązanie (464)

bez sprytnych wbudowanych funkcji i przy czasie działania 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

Wszystkie nowe linie tutaj nie są konieczne.

Wydajność:

3b9i9i1a1a1a1a9i9i1a1a9h9h1b1b1b1b9h9h9g9g1c1c9g9g9f9f1d1d9f9f8h8h2b2b8f8f8f8f7i7i7h7h3b3b3b3b7h7h3b3b7h7h7g7g3c3c7g7g3c3c7f7f6i6i4a4a6h6h4b4b4b4b6g6g4c4c6g6g4c4c6f6f4d4d4d4d6f6f4d4d6f6f4d4d

Pozostałe dwie siatki testowe:

13ab9i9i1a1a9i9i9h9h1b1b1b1b9h9h9f9f8i8i8i8i8h8h2b2b2b2b8h8h8h8h8g8g8g8g8f8f2d2d2d2d8f8f2d2d7i7i3a3a3a3a7i7i7h7h3b3b7h7h3b3b7g7g3c3c3c3c7g7g3c3c7f7f3d3d3d3d7f7f7f7f6i6i4a4a6i6i6h6h4b4b4b4b6h6h4b4b6g6g4c4c4c4c6f6f4d4d4d4d6f6f4d4d6f6f
2bc9i9i1a1a9i9i9g9g1c1c9g9g1c1c9f9f1d1d1d1d8i8i8i8i8h8h2b2b2b2b8f8f2d2d7i7i7h7h3b3b3b3b7h7h3b3b7g7g3c3c7f7f3d3d3d3d7f7f3d3d6i6i4a4a4a4a6h6h4b4b6g6g6g6g6f6f4d4d

Wyobrażanie sobie:

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]

wprowadź opis zdjęcia tutaj

Ciąg wejściowy imoże być generowany losowo przez

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

Krótka dyskusja

  • Przerzuty mogą zamieniać tylko te elementy („poczwórne”):

    wprowadź opis zdjęcia tutaj

  • Możliwe jest wymienianie tych elementów oddzielnie od innych elementów tylko wtedy, gdy zamówienie początkowe i końcowe ma ten sam podpis.

  • Odwrócenie tych czterech elementów tworzy naprzemienną grupę stopnia 4 (= grupa obrotów czworościennych). Każdy element z tej grupy składa się z 2 elementów generujących. Więc jeśli znamy pozycję początkową i końcową, możemy dekomponować odpowiednią transformację jako kombinację prostych przerzutów.

Detale

Dla sportowców zamieszczam szczegóły przed końcem nagrody!

M=ToCharacterCode@StringSplit@i-48;

Konwertuj ciąg ina macierz M.

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

Dodamy znaki do S. Teraz jest to pusty ciąg. H[i,j]doda znak i( 1,2,3,...,9) i znak j( a,b,c,...,iw bazie 36).

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

Konwertuję elementy jako

wprowadź opis zdjęcia tutaj

aby uzyskać macierz docelową w następującej formie

wprowadź opis zdjęcia tutaj

W moim algorytmie są dwa główne etapy

  1. Znajdź flipy, aby uzyskać podpisy jak w macierzy docelowej (np. Podpis {-7,-1,1,7}is 1i podpis {-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. Obracaj każdy „poczwórny”, aby uzyskać odpowiednią kolejność:

    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}];
    

    Jest to najbardziej nietrywialna część algorytmu. Na przykład transformacja 1b1bzostanie przekonwertowana {-7,-1,1,7}na {-1,1,-7,7}. Transformacja 9h9hzostanie przekonwertowana {-7,-1,1,7}na {-7,7,-1,1}. Mamy więc dwie mapy

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

    i chcemy przekształcić dowolną kolejność {x,y,z,w}do {1,2,3,4}. Prostą metodą jest (z wyjątkiem wyszukiwania losowego)

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

    Nie mogę tego udowodnić, ale działa!

Ostatnim krokiem jest

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

Wykonuje trywialne odwrócenie środkowego rzędu i środkowej kolumny i zwraca wynik.

Ybeltukov
źródło
@Gareth Czy mogę używać małych znaków na wyjściu? Oszczędza mi to wielu znaków.
ybeltukov
Tak, zaakceptuję małe litery w danych wyjściowych (zmienię pytanie, aby to zauważyć). Nie mam Mathematica, więc czy inny użytkownik Mathematica może potwierdzić, że kod faktycznie generuje dane wyjściowe? Zweryfikowałem trzy testowe rozwiązania i wszystkie są poprawne, więc daj +1. Dobra robota!
Gareth
Ciekawe - jakie jest twoje podejście? Czy testowałeś dane wejściowe generowane przez tysiące przerzutów?
SergeyS
@SergeyS Tak, zajmuje to około 50 ms :)
ybeltukov
@Gareth Przepisuję mój program, czy możesz sprawdzić wyniki? Moje testy wykazały, że wszystko jest w porządku.
ybeltukov
7

jot 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 jest czasownikiem, który pobiera ciąg siatki w określonym formacie i zwraca ciąg rozwiązania w określonym formacie.

Przykładowe zastosowanie:

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

Teraz akceptuje albo nowy typ linii.

Rozwiązania do siatek testowych:

b3a1a11b1bc9c99g9gd9d99f9fb8b8f8f87i7i7h7hc3c3g7g77f7fa6a64b4bh6h6c4c4g6g6d6d6f6f6
cd24a9a91c1c1d1d9f9fa2a2i8i88h8hc2c2g8g82d2d3b3bh7h7d3d37f7fa6a64b4bg6g64d4d6f6f
bc2a9a99i9ic1c1g9g91d1df9f9i8i8b2b2h8h82c2cd8d87i7ib3b3c7c7d3d34a4ai6i6b6b6g6g6d6d6

Jestem dość nowy w J; to może być jeszcze bardziej golfa.


Sprawdzanie, czy siatki są nieprawidłowe / nierozwiązywalne, podlega karze 123 znaków. Nie sądzę, aby inne dotychczasowe odpowiedzi zawierały takie sprawdzanie błędów.

Aby to zrobić, zmień pierwszy wiersz dna:

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

i ostatnia linia do tego:

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

Zdecydowałem się powrócić 0po takich błędach, że zwrócenie pustego łańcucha byłoby nie do odróżnienia od poprawnego rozwiązania w pełni rozwiązanej siatki. Zauważ, że zakłada to nowe wiersze UNIX (ponownie).

AlliedEnvy
źródło
Gratulacje, właśnie wyszedłeś na prowadzenie. :-)
Gareth,
Wygląda na to, że Twój wpis nie jest jednym ciągiem, jak wymagają tego reguły, czy coś mi umknęło?
SergeyS
@SergeyS: Możesz się mylić. O ile mi wiadomo, J nie ma możliwości umieszczania znaków ucieczki (takich jak nowa linia) w literałach łańcuchowych. Konstrukcja „a”, LF, „b” w J jest podobna do „a” + „\ n” + „b” w językach, w których + działa, aby dodać ciągi znaków.
AlliedEnvy
Ok, to ma sens niż dzięki.
SergeyS
Właśnie czytałem sekcję dotyczącą plików z książki APL z 1962 roku i myślę, że @AlliedEnvy ma rację. W ten sposób dane pojawią się w programie, jeśli zostaną odczytane z pliku w formacie pytania. Do LFs reprezentują partycje pliku sekwencyjnego.
luser droog
5

DO# 540 399

Cóż, poświęcona wydajność (teraz zajmuje to do 30 sekund), wprowadzono zmienne dynamiczne, nieznacznie zmieniono logikę rozwiązania. I tak, teraz oczekuje danych wejściowych jako jednego ciągu z podziałem wierszy (zgodnie z wymaganiami reguł).

Oczywiście C # nie ma predefiniowanych funkcji matematycznych, więc ciężko byłoby walczyć z chłopakami Mathematica. Niemniej jednak było to wielkie wyzwanie, dzięki autorowi!

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;

Siatki testowe:

3B9A9A9B9B9C9C9D9D9F9F9G9G9H9H9I9I9B9B9C9C9D9D9F9F9G9G9H9H9C9C9D9D9C9C9D9D8B8B8F8F8H8H8B8B8F8F8B8B8H8H7B7B7C7C7F7F7H7H7I7I7H7H6A6A6B6B6C6C6D6D6F6F6H6H6A6A6B6B6D6D6F6F6D6D6D6D6F6F5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I

13AB9A9A9B9B9F9F9H9H9A9A9B9B9H9H9I9I8B8B8D8D8F8F8G8G8H8H8I8I8B8B8G8G8H8H8I8I8H8H7A7A7B7B7C7C7D7D7F7F7G7G7I7I7A7A7D7D7F7F7I7I7F7F6A6A6B6B6C6C6D6D6F6F6G6G6H6H6I6I6A6A6C6C6F6F6I6I6A6A6A6A5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I

2BC9A9A9C9C9D9D9F9F9A9A9D9D9I9I8B8B8D8D8H8H8I8I8B8B8D8D8I8I7B7B7C7C7D7D7F7F7G7G7H7H7I7I7C7C7C7C7G7G6A6A6B6B6D6D6F6F6G6G6I6I6A6A6B6B6D6D6G6G6D6D6F6F5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I

Stare rozwiązanie (540)

Działa w mniej niż sekundę na dowolnym wejściu (testowane na tysiącach losowo generowanych siatek). Maksymalna długość łańcucha wyjściowego to 165 (początkowo każda siatka została rozwiązana w nie więcej niż 82 rzutach, ale podczas gry w golfa poświęciłem to).

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;

Odpowiedz na przykład 1:

15A5A5B5B5C5C5D5DE5E55F5F5G5G5H5H5I5I

Odpowiedz na przykład 2:

19AI1I1H1H1G1G1F1F19F9F9G9G9H9H9I9I8A8AI8I87A7AI7I76A6AI6I65A5A5B5B5C5C5D
5DE5E55F5F5G5G5H5H5I5I

Odpowiedz na przykład 3:

129AI1I1H1H1G1G1F1F19F9F9G9G9H9H9I9I8A8AI8I87A7AI7I76A6AI6I65A5A5B5B5C5C5
D5DE5E55F5F5G5G5H5H5I5I

Odpowiedzi na kwadraty testowe:

346B9A9AH1H1C9C9D9D99F9F9G9GH9H99I9IB8B8F8F87B7B7C7C7F7FH7H77I7I6A6A6B6BC6C66D6DG6G6H6H66I6I5A5A5B5B5C5C5D5DE5E55F5F5G5G5H5H5I5I

1346ABA9A9H1H19F9FH9H99I9IH2H28D8D8F8FG8G8I8I8I3I37B7B7C7CF3F37G7GI7I7H4H4D6D66F6F5A5A5B5B5C5C5D5DE5E55F5F5G5G5H5H5I5I

2BCA9A99C9CF1F19F9F9I9IH2H2D8D88H8HI8I87B7BC7C77D7D7F7F7H7H7I7II4I4B6B6D6D6G6G66I6I5A5A5B5B5C5C5D5DE5E55F5F5G5G5H5H5I5I
SergeyS
źródło
Właśnie pobieram teraz Mono na komputer Mac, aby móc przetestować sam program, ale mam już moduł sprawdzania poprawności, który uruchamia dane rozwiązanie na danej siatce i mówi mi, czy rozwiązanie jest prawidłowe dla tej siatki - i jest to mówiąc mi, że trzy przykładowe rozwiązania, które mi podałeś, są nieprawidłowe. Właśnie badam, dlaczego teraz.
Gareth
Aha! Zrozumiałem, co się tutaj wydarzyło! Podane odpowiedzi wydają się być odpowiedziami na 3 przykłady, a nie na trzy siatki testowe (które znajdują się niżej w pytaniu). Rzeczywiście są one poprawnymi rozwiązaniami dla tych siatek, choć są one nieco dłuższe niż 1, Ai 2Iktóre są najprostszymi rozwiązaniami - ale to nie ma znaczenia, ponieważ nie oceniam długości rozwiązania siatki :-) Jeśli mógłbyś edytować i udzielę odpowiedzi na 3 siatki testowe (zobaczę, czy mogę to teraz uruchomić na moim komputerze Mac). Mogę dać ci +1.
Gareth
@Gareth - Ups, przegapiłem odpowiedzi na kwadraty testowe, dziękuję za zwrócenie na to uwagi. Dodałem je teraz do mojej odpowiedzi.
SergeyS
Doskonale, dzięki za to. Wszyscy dobrze się sprawdzili. Xamarin z jakiegoś powodu nie działałby na moim Macu, więc za kilka godzin będę musiał przetestować program w pracy.
Gareth
@Gareth - Właściwie nie ma nic specyficznego dla C # w tym kodzie, prawdopodobnie można go przekonwertować na Javę, a nawet C ++ bez większego bólu i ... golfować niektóre znaki z niego :) Również możesz przekonwertować go na GolfScript lub coś więcej zwięzłe - może pojawić się dwa lub więcej razy;)
SergeyS