Peg solitaire is a popular game usually played alone. The game consists of some number of pegs and a board which is divided into a grid - usually the board is not rectangular but for this challenge we will assume so.

Each valid move allows one to remove a single peg and the goal is to play in a way, such that there is a single peg left. Now, a valid move has to be in a single direction (north, east, south or east) and jump over one peg which can be removed.

Examples

Let . be empty spaces on the board and numbers are pegs, the following move will move 1 one to the right and remove 2 from the board:

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

A move will always have to jump over a single peg, so the following is not valid:

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

Here are some valid configurations after one move each:

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

Challenge

Given an initial board configuration and some other configuration, output whether the other configuration can be reached by successively moving pegs around as described above.

Rules

  • Input will be a \$n \times m\$ matrix/list of lists/... of values indicating an empty space (eg. zero or false) or pegs (eg. non-zero or true)
    • you may assume \$n \geq 3\$ and \$m \geq 3\$
    • you may use true/non-zero to indicate empty spaces and vice-versa if it helps
  • Output will be two distinct (one of the values might differ) values indicating whether the end-configuration can be reached (eg. falsy/truthy, []/[list of moves] ..)

Test cases

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
  • 1
    What happened to peg 7 in your example? Why does it vanish after 2 moves south? – Οurous Nov 29 at 0:46
  • @Ourous: That was just a typo, fixed it. – BMO Nov 29 at 10:40

JavaScript (ES6),  184 178  173 bytes

Takes input as (initial_board)(target_board). Returns \$0\$ or \$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]--))))

Try it online!

(removed the last two test cases that take too much time for TIO)

Commented

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

Clean, 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])

Try it online!

This is one of the rare occasions in which I can utilize composition and currying while saving bytes.

Explained:

@ :: [Int] -> [[Int]] is a helper function used to generate the different potential new rows/columns that could result from a move being made. It avoids needing to special-case [1,1,0:_] by noticing that a*b-c>0 only when [a,b,c]=[1,1,0], and so take(a*b-c)... gives [] by taking -1 or 0 elements for all configurations that aren't a valid move.

flip elem o... reverses the order of arguments to elem (making it "does x contain a y" instead of "is x a member of y") and applies the anonymous function on c to the first argument.

\c=limit(iterate(nub o concatMap ...)[c]) generates every potential board that can result from the c by joining the current set of boards with all the moves that can happen on all of the boards and removing the duplicates, until the result stops changing.

\l=[l]++... prepends the board l to the list of all potential new boards one-move distance away, generated by applying @ to the rows of each orientation of the board (0, 90, 180, 270-degree rotations) and replacing the corresponding changed row with the new row.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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