Peg Solitaire ist ein beliebtes Spiel, das normalerweise alleine gespielt wird. Das Spiel besteht aus einer Reihe von Stiften und einem Brett, das in ein Gitter unterteilt ist - normalerweise ist das Brett nicht rechteckig, aber für diese Herausforderung werden wir dies annehmen.

Jeder gültige Zug ermöglicht es einem, einen einzelnen Stift zu entfernen, und das Ziel ist es, so zu spielen, dass nur ein einzelner Stift übrig bleibt. Jetzt muss eine gültige Bewegung in eine Richtung (Nord, Ost, Süd oder Ost) erfolgen und über einen Stift springen, der entfernt werden kann.

Beispiele

Lassen Sie .leere Felder auf dem Brett sein und Zahlen sind Stifte. Bei der folgenden Bewegung wird 1eines nach rechts verschoben und 2vom Brett entfernt:

.....     .....
.12..  -> ...1.
.....     .....

Eine Bewegung muss immer über einen einzelnen Stift springen, daher ist Folgendes nicht gültig:

......    ......
.123.. -> ....1.
......    ......

Hier sind einige gültige Konfigurationen nach jeweils einem Zug:

...1...        ...1...        ..71...        ..71...
.2.34.5  --->  .24...5  --->  .2....5  --->  ......5
.678...  (4W)  .678...  (7N)  .6.8...  (2S)  ...8...
.......        .......        .......        .2.....

Herausforderung

Bei einer anfänglichen Kartenkonfiguration und einer anderen Konfiguration wird ausgegeben, ob die andere Konfiguration durch sukzessives Bewegen der Stifte wie oben beschrieben erreicht werden kann.

Regeln

• Die Eingabe erfolgt durch eine Matrix / Liste von Listen / ... von Werten, die einen leeren Raum (z. B. Null oder Falsch) oder Stifte (z. B. Nicht-Null oder Wahr) angeben. $n \times m$
  • Sie können und annehmen$n \geq 3$$m \geq 3$
  • Sie können true / ungleich Null verwenden, um Leerzeichen anzugeben, und umgekehrt, wenn dies hilfreich ist
• Die Ausgabe besteht aus zwei unterschiedlichen Werten (einer der Werte kann abweichen), die angeben, ob die Endkonfiguration erreicht werden kann (z. B. falsch / wahr , []/ [list of moves]..).

Testfälle

initial  goal -> output
[[1,0,0],[1,1,0],[0,1,0]]  [[0,0,0],[0,1,0],[1,1,0]] -> True
[[1,0,0],[1,1,0],[0,1,0]]  [[0,0,1],[0,1,1],[0,0,0]] -> False
[[0,0,0],[1,0,0],[0,0,0]]  [[0,0,0],[0,0,1],[0,0,0]] -> False
[[0,0,0],[1,1,0],[0,0,0]]  [[0,0,0],[0,1,1],[0,0,0]] -> False
[[0,0,0,0],[1,1,1,0],[0,0,0,0]]  [[0,0,0,0],[0,0,0,1],[0,0,0,0]] -> False
[[1,0,0],[1,1,0],[1,1,1],[1,1,1]]  [[0,0,1],[0,1,0],[1,0,0],[0,0,1]] -> True
[[1,0,0],[1,1,0],[1,1,1],[1,1,1]]  [[1,0,0],[0,0,0],[0,0,0],[0,0,0]] -> False
[[1,0,1,1],[1,1,0,0],[1,1,1,0],[1,0,1,0]]  [[0,0,1,0],[1,0,0,0],[1,0,1,0],[1,0,0,1]] -> True
[[1,0,1,1],[1,1,0,0],[1,1,1,0],[1,0,1,0]]  [[0,0,0,0],[0,0,0,0],[0,0,1,0],[0,0,0,0]] -> False
[[1,0,0,0],[1,1,0,0],[1,1,1,0],[1,0,1,0]]  [[0,0,0,0],[0,0,0,0],[0,0,1,0],[0,0,0,0]] -> True
[[0,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,0]]  [[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]] -> False
[[0,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,0]]  [[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]] -> False
[[0,0,0,1,0,0,0],[0,1,0,1,1,0,1],[0,1,1,1,0,0,0],[0,0,0,0,0,0,0]]  [[0,0,0,1,0,0,0],[0,1,0,1,1,0,1],[0,1,1,1,0,0,0],[0,0,0,0,0,0,0]] -> True
[[0,0,0,1,0,0,0],[0,1,0,1,1,0,1],[0,1,1,1,0,0,0],[0,0,0,0,0,0,0]]  [[0,0,0,1,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0]] -> True
[[0,0,1,1,1,0,0],[0,0,1,1,1,0,0],[1,1,1,1,1,1,1],[1,1,1,0,1,1,1],[1,1,1,1,1,1,1],[0,0,1,1,1,0,0],[0,0,1,1,1,0,0]]  [[0,0,1,1,1,0,0],[0,0,1,1,1,0,0],[1,1,1,1,1,1,1],[1,1,1,1,0,0,1],[1,1,1,1,1,1,1],[0,0,1,1,1,0,0],[0,0,1,1,1,0,0]] -> True
[[0,0,1,1,1,0,0],[0,0,1,1,1,0,0],[1,1,1,1,1,1,1],[1,1,1,0,1,1,1],[1,1,1,1,1,1,1],[0,0,1,1,1,0,0],[0,0,1,1,1,0,0]]  [[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,1,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0]] -> True

JavaScript (ES6),  184 178  173 Bytes

(initial_board)(target_board)$0$$1$

a=>g=b=>a+''==b|a.some((r,y)=>r.some((v,x,A,X,R)=>[-1,0,1,2].some(h=>(A=a[y+(R=~-h%2)]||0)[X=x+(h%=2)]&v>(R=a[y+R*2]||0)[h+=x+h]&&g(b,A[X]=r[x]=R[h]++)&(A[X]=r[x]=R[h]--))))

Probieren Sie es online aus!

(Die letzten beiden Testfälle wurden entfernt, die für TIO zu lange dauern.)

Kommentiert

a =>                             // main function taking the initial board a[]
  g = b =>                       // g = recursive function taking the target board b[]
    a + '' == b |                // yield a truthy result if a[] is matching b[]
    a.some((r, y) =>             // for each row r[] at position y in a[]:
      r.some((v, x, A, X, R) =>  //   for each value v at position x in r[]:
        [-1, 0, 1, 2]            //     list of directions (West, North, East, South)
        .some(h =>               //     for each direction h:
          ( A =                  //       A = a[y + dy]
            a[y + (R = ~-h % 2)] //       R = dy
            || 0                 //       use a dummy row if we're out of the board
          )[X = x + (h %= 2)]    //       h = dx, X = x + dx
          &                      //       yield 1 if there's a peg on the skipped cell
          ( R =                  //       R = target row
            a[y + R * 2]         //         = a[y + 2 * dy]
            || 0                 //       use a dummy row if we're out of the board
          )[h += x + h]          //       h = x + 2 * dx = target column
          < v                    //       yield 1 if there's no peg on the target cell
          &&                     //       and there's a peg on the source cell (0 < 1)
          g(                     //       if the above result is true, do a recursive call:
            b,                   //         pass b[] unchanged
            A[X] = r[x] =        //         clear the source and skipped cells
            R[h]++               //         set the target cell
          ) & (                  //       and then restore the board to its initial state:
            A[X] = r[x] =        //         set the source and skipped cells
            R[h]--               //         clear the target cell
          )                      //
        )                        //     end of some() over directions
      )                          //   end of some() over columns
    )                            // end of some() over rows

Sauber , 232 Bytes

import StdEnv,Data.List
r=reverse
@[a:t=:[b,c:u]]=[[a:v]\\v<- @t]++take(a*b-c)[[0,0,1:u]];@l=[]

flip elem o\c=limit(iterate(nub o concatMap\l=[l]++[f(updateAt i p(f l))\\f<-[id,transpose],q<-f l&i<-[0..],p<- @q++(map r o@o r)q])[c])

Probieren Sie es online aus!

Dies ist eine der seltenen Situationen, in denen ich Komposition und Curry verwenden kann, während ich Bytes speichere.

Erklärt:

@ :: [Int] -> [[Int]]ist eine Hilfsfunktion, mit der die verschiedenen potenziellen neuen Zeilen / Spalten generiert werden , die sich aus einer Verschiebung ergeben können. Es vermeidet Spezialfall um [1,1,0:_]damit zu bemerken a*b-c>0nur , wenn [a,b,c]=[1,1,0]und so take(a*b-c)...gibt , []indem sie -1oder 0Elemente für alle Konfigurationen , die keine gültige unterwegs sind.

flip elem o...kehrt die Reihenfolge der Argumente um elem(macht "enthält x ein y" anstelle von "ist xa Mitglied von y") und wendet die anonyme Funktion auf cdas erste Argument an.

\c=limit(iterate(nub o concatMap ...)[c])generiert jedes potenzielle Board, das sich aus dem ergeben kann, cindem der aktuelle Board-Satz mit allen Bewegungen, die auf allen Boards auftreten können, verbunden und die Duplikate entfernt werden, bis sich das Ergebnis nicht mehr ändert.

\l=[l]++...Stellt die Karte der lListe aller potenziellen neuen Karten in einem Abstand von einer Bewegung voran , die durch Anwenden @auf die Reihen jeder Ausrichtung der Karte (0, 90, 180, 270-Grad-Drehung) und Ersetzen der entsprechenden geänderten Reihe durch die neue erzeugt wird Reihe.