In case you are looking for the actual solution, it is listed at the end

## Description of Game

Brainvita is a board game. It has set of pegs arranged as shown above. The aim of the game is to remove all pegs save one using valid moves only. A valid move consists of a peg jumping over its horizontal or vertical neighbour to a hole. In the process the peg that is jumped over is removed. Eg. the peg in the second column of the second row (jumper) can jump over the fourth peg of the third row (jumped) onto the hole in the fourth row. In the process jumped peg is removed with the following result:

## Solution

The solution, written in F#, is described below in two files consisting of the model and the search algorithm. The model is essentially an 7×7 matrix where the set of valid cells is the union of the middle three rows and middle three columns. The main helper functions are:

- IsValid – checks if the the given row and column index constitute a valid cell
- isMovableXY – checks if the a proposed move from source to destination is legal
- moveXY – changes the board configuration to reflect the suggested move.
- reverseXY – reverts a previous move.
- findMove – finds a valid move starting from a given location. Returns false if no move found

The algorithm to find the solution is a simple backtracking search and is listed as Program.fs below. It tries to make a move. If no valid move is found it reverts the last move and tries the next move. Notice that isMovable essentially takes a three-tuple as input. This tuple belongs to a linearly ordered set and hence it makes sense to increment the tuple. The algorithm continues to make moves until the count of moves is 31, at which point there should be only peg left and the list of valid moves is printed.

(For a C++ implementation checkout github)

Model.fs

// Mdel module JoeChakra.BrainVita open Microsoft.FSharp.Math open Microsoft.FSharp.Collections open System.Collections.Generic; let IsValid i j = (i>=2 && i<=4 && j>=0 && j<7) || (j>=2 && j<=4 && i>=0 && i<7) let board = Array2D.init 7 7 (fun i j -> (IsValid i j) && not (i=3 && j=3) ) let movableX i x y = board.[x,y] && board.[x+i,y] && not board.[x+2*i,y] let movableY j x y = board.[x,y] && board.[x,y+j] && not board.[x,y+2*j] let moveX i x y = board.[x,y] <- false board.[x+i,y] <- false board.[x+2*i,y] <- true true let moveXY i j x y = board.[x,y] <- false board.[x+i,y+j] <- false board.[x+2*i,y+2*j] <- true true let moveY j x y = board.[x,y] <- false board.[x,y+j] <- false board.[x,y+2*j] <- true true type Direction = | East | South | West | North let isMovable d x y = if IsValid x y then match d with | East -> (IsValid (x+2) y) && (movableX 1 x y) | West -> (IsValid (x-2) y) && (movableX -1 x y) | South -> (IsValid x (y+2)) && (movableY 1 x y) | North -> (IsValid x (y-2)) && (movableY -1 x y) else false let dirs = [East;South;West;North] let move mov = let (x,y,d) = mov match dirs.[d] with | East -> (moveX 1 x y) | West -> (moveX -1 x y) | South -> (moveY 1 x y) | North -> (moveY -1 x y) let reverseXY i j x y = board.[x,y] <- true board.[x+i,y+j] <- true board.[x+2*i,y+2*j] <- false true let reverseX i x y = board.[x,y] <- true board.[x+i,y] <- true board.[x+2*i,y] <- false true let reverseY i x y = board.[x,y] <- true board.[x,y+i] <- true board.[x,y+2*i] <- false true let reverse mov = let (x,y,d) = mov match dirs.[d] with | East -> reverseX 1 x y | West -> reverseX -1 x y | South -> reverseY 1 x y | North -> reverseY -1 x y let invalid = (-1, -1, -1) let zeroMove = 0,0,0 let incr mov = let (i,j,d) = mov if d<3 then i, j, (d+1) else if i<6 then (i+1), j, 0 else if j<7 then 0, (j+1), 0 else invalid let rec findNextMove mov = if mov = invalid then mov else let (i,j,d) = mov if isMovable (dirs.[d]) i j then mov else findNextMove (incr mov) let findFirstMove = findNextMove zeroMove

Program.fs

module JoeChakra.Main open Microsoft.FSharp.Math open Microsoft.FSharp.Collections type Move= { d:int x:int y:int } //let mutable dir=North let mutable count=32 let mutable totalMoves = 0; let printMove X = printfn "%d,%d %A" X.x X.y JoeChakra.BrainVita.dirs.[X.d] let rec BVMove mov0 (moves:seq<Move>) = let mov = JoeChakra.BrainVita.findNextMove mov0 if mov = JoeChakra.BrainVita.invalid then false else JoeChakra.BrainVita.move mov |> ignore totalMoves<-totalMoves+1 count<-count-1 let (i,j,d) = mov let move:Move = {d=d; x=i; y=j} if Solve (Seq.append moves [move]) then true else JoeChakra.BrainVita.reverse mov |> ignore count<-count+1 BVMove (JoeChakra.BrainVita.incr mov) moves and Solve (moves:seq<Move>) = if count=1 then moves |> Seq.iter printMove |>ignore printfn ";--------total moves %d----------" totalMoves true else BVMove JoeChakra.BrainVita.zeroMove moves // See the 'F# Tutorial' project for more help. [<EntryPoint>] let main argv = Solve Seq.empty |> ignore// Learn more about F# at http://fsharp.net 0 // return an integer exit code

On a personal note: I first wrote this program ages ago using Fortran on MicroVAX-II. It took hours to run. Now I am slowing it down using F# and the output is almost immediate.

The solution computed is:

3,1,South

1,2,East

2,0,South

4,0,West

3,2,West

0,2,East

4,2,North

6,2,West

2,3,North

2,0,South

0,3,East

2,3,North

4,3,West

6,3,West

4,3,North

4,0,South

2,4,North

2,1,South

0,4,East

3,4,West

4,5,North

6,4,West

2,6,North

2,3,South

4,6,West

2,6,North

1,4,East

3,4,East

4,2,South

5,4,West

3,5,North

Pingback: Interesting Algorithms | Joe's Blog

Pingback: Breadth First Search | The Sunday Programmer

Pingback: No Raw Pointers | The Sunday Programmer

Hmm it looks like your blog ate my first comment (it was extremely long) so I guess I’ll just sum it up

what I submitted and say, I’m thoroughly enjoying your blog.

I too am an aspiring blog blogger but I’m still new to everything.

Do you have any suggestions for newbie blog writers? I’d really appreciate

it.