## Brainvita Solution

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&gt;=2 && i&lt;=4 && j&gt;=0 && j&lt;7) ||
(j&gt;=2 && j&lt;=4 && i&gt;=0 && i&lt;7)

let board = Array2D.init 7 7 (fun i j -&gt;
(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] &lt;- false
board.[x+i,y] &lt;- false
board.[x+2*i,y] &lt;- true
true

let moveXY i j x y =
board.[x,y] &lt;- false
board.[x+i,y+j] &lt;- false
board.[x+2*i,y+2*j] &lt;- true
true

let moveY j x y =
board.[x,y] &lt;- false
board.[x,y+j] &lt;- false
board.[x,y+2*j] &lt;- true
true

type Direction =
| East
| South
| West
| North
let isMovable d x y =
if IsValid x y then
match d with
| East -&gt; (IsValid (x+2) y) && (movableX 1 x y)
| West -&gt; (IsValid (x-2) y) && (movableX -1 x y)
| South -&gt; (IsValid x (y+2)) && (movableY 1 x y)
| North -&gt; (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 -&gt;  (moveX 1 x y)
| West -&gt;  (moveX -1 x y)
| South -&gt; (moveY 1 x y)
| North -&gt; (moveY -1 x y)

let reverseXY i j x y =
board.[x,y] &lt;- true
board.[x+i,y+j] &lt;- true
board.[x+2*i,y+2*j] &lt;- false
true

let reverseX i x y =
board.[x,y] &lt;- true
board.[x+i,y] &lt;- true
board.[x+2*i,y] &lt;- false
true

let reverseY i x y =
board.[x,y] &lt;- true
board.[x,y+i] &lt;- true
board.[x,y+2*i] &lt;- false
true

let reverse mov =
let (x,y,d) = mov
match dirs.[d] with
| East -&gt; reverseX 1 x y
| West -&gt; reverseX -1 x y
| South -&gt; reverseY 1 x y
| North -&gt; reverseY -1 x y

let invalid = (-1, -1, -1)
let zeroMove = 0,0,0

let incr mov =
let (i,j,d) = mov
if d&lt;3 then
i, j, (d+1)
else if i&lt;6 then
(i+1), j, 0
else if j&lt;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&lt;Move&gt;) =
let mov = JoeChakra.BrainVita.findNextMove mov0
if mov = JoeChakra.BrainVita.invalid then
false
else
JoeChakra.BrainVita.move mov |&gt; ignore
totalMoves&lt;-totalMoves+1
count&lt;-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 |&gt; ignore
count&lt;-count+1
BVMove (JoeChakra.BrainVita.incr mov) moves
and Solve  (moves:seq&lt;Move&gt;) =
if count=1 then
moves |&gt; Seq.iter printMove |&gt;ignore
printfn ";--------total moves %d----------" totalMoves
true
else
BVMove JoeChakra.BrainVita.zeroMove moves

// See the 'F# Tutorial' project for more help.

[&lt;EntryPoint&gt;]
let main argv =
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 ``` Joe is an experienced C++/C# developer on Windows. Currently looking out for an opening in C/C++ on Windows or Linux.
This entry was posted in .NET, Software Puzzle. Bookmark the permalink.

### 4 Responses to Brainvita Solution

1. Pingback: Interesting Algorithms | Joe's Blog

2. Irs Tax Attorneys says:

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.