Brainvita Solution

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

Description of Game

Brainvita

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:

Brainvita2

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

Advertisements

About The Sunday Programmer

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. Pingback: Breadth First Search | The Sunday Programmer

  3. Pingback: No Raw Pointers | The Sunday Programmer

  4. 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s