Local Beam search demo:

Initial Board: [4, 4, 1, 6, 2, 2, 5, 7], score=4

Note: The following boards are stored as:
   [[score1, [board1]], [score2, [board2]],...]

To do this in Ruby:
  allboards=[]
    . . .
  allboards << [score, board]   assuming "board" is a list of positions

Get all boards generated from initial board, scores <= 4:
These boards are sorted by the score: 

Allboards=[[3, [4, 3, 1, 6, 2, 2, 5, 7]], [3, [4, 7, 1, 6, 2, 2, 5, 7]], 
           [4, [0, 4, 1, 6, 2, 2, 5, 7]], [4, [1, 4, 1, 6, 2, 2, 5, 7]], 
           [4, [4, 0, 1, 6, 2, 2, 5, 7]], [4, [4, 1, 1, 6, 2, 2, 5, 7]]]

Select the top 3 to use in "parallel" runs:
Top3=[[3, [4, 3, 1, 6, 2, 2, 5, 7]], [3, [4, 7, 1, 6, 2, 2, 5, 7]], 
      [4, [0, 4, 1, 6, 2, 2, 5, 7]]]

Generate all boards from 1st in top3, scores <= 3:
For i=0, j=0, 
   allboards=[[2, [4, 3, 1, 6, 2, 0, 5, 7]], [3, [0, 3, 1, 6, 2, 2, 5, 7]], 
              [3, [1, 3, 1, 6, 2, 2, 5, 7]], [3, [4, 3, 0, 6, 2, 2, 5, 7]], 
              [3, [4, 3, 3, 6, 2, 2, 5, 7]], [3, [4, 7, 1, 6, 2, 2, 5, 7]], 
              [3, [5, 3, 1, 6, 2, 2, 5, 7]]]

Generate all boards from second in top3, scores <= 3, add to list:
For i=0, j=1, 
   allboards=[[2, [4, 3, 1, 6, 2, 0, 5, 7]], [2, [4, 7, 1, 6, 2, 0, 5, 7]], 
              [2, [4, 7, 1, 6, 2, 2, 5, 3]], [2, [4, 7, 3, 6, 2, 2, 5, 7]], 
              [3, [0, 3, 1, 6, 2, 2, 5, 7]], [3, [1, 3, 1, 6, 2, 2, 5, 7]], 
              [3, [4, 3, 0, 6, 2, 2, 5, 7]], [3, [4, 3, 1, 6, 2, 2, 5, 7]], 
              [3, [4, 3, 3, 6, 2, 2, 5, 7]], [3, [4, 7, 0, 6, 2, 2, 5, 7]], 
              [3, [4, 7, 1, 6, 2, 2, 5, 7]], [3, [5, 3, 1, 6, 2, 2, 5, 7]]]

Generate all boards from third in top3, scores <= 4, add to list:
For i=0, j=2, 
   allboards=[[2, [4, 3, 1, 6, 2, 0, 5, 7]], [2, [4, 7, 1, 6, 2, 0, 5, 7]], 
              [2, [4, 7, 1, 6, 2, 2, 5, 3]], [2, [4, 7, 3, 6, 2, 2, 5, 7]], 
              [3, [0, 3, 1, 6, 2, 2, 5, 7]], [3, [0, 4, 1, 6, 2, 2, 5, 3]], 
              [3, [1, 3, 1, 6, 2, 2, 5, 7]], [3, [4, 3, 0, 6, 2, 2, 5, 7]], 
              [3, [4, 3, 1, 6, 2, 2, 5, 7]], [3, [4, 3, 3, 6, 2, 2, 5, 7]], 
              [3, [4, 7, 0, 6, 2, 2, 5, 7]], [3, [4, 7, 1, 6, 2, 2, 5, 7]], 
              [3, [5, 3, 1, 6, 2, 2, 5, 7]], [4, [1, 4, 1, 6, 2, 2, 5, 7]], 
              [4, [4, 4, 1, 6, 2, 2, 5, 7]]]

Select the top 3 boards from this combined list (all score 2):
Top 3= [[2, [4, 3, 1, 6, 2, 0, 5, 7]], [2, [4, 7, 1, 6, 2, 0, 5, 7]], 
        [2, [4, 7, 1, 6, 2, 2, 5, 3]]]

Generate all boards from 1st in top3, scores <= 2:
For i=1, j=0, 
   allboards=[[2, [1, 3, 1, 6, 2, 0, 5, 7]], [2, [4, 3, 1, 6, 2, 0, 2, 7]], 
              [2, [4, 3, 1, 6, 2, 0, 7, 7]], [2, [4, 6, 1, 6, 2, 0, 5, 7]], 
              [2, [4, 7, 1, 6, 2, 0, 5, 7]], [2, [7, 3, 1, 6, 2, 0, 5, 7]]]

Generate all boards from second in top3, scores <= 2, add to list:
For i=1, j=1, 
   allboards=[[1, [4, 7, 1, 6, 2, 0, 5, 3]], [2, [1, 3, 1, 6, 2, 0, 5, 7]], 
              [2, [4, 3, 1, 6, 2, 0, 2, 7]], [2, [4, 3, 1, 6, 2, 0, 5, 7]],   
              [2, [4, 3, 1, 6, 2, 0, 7, 7]], [2, [4, 6, 1, 6, 2, 0, 5, 7]], 
              [2, [4, 7, 1, 6, 2, 0, 3, 7]], [2, [4, 7, 1, 6, 2, 0, 5, 0]], 
              [2, [4, 7, 1, 6, 2, 0, 5, 7]], [2, [4, 7, 3, 6, 2, 0, 5, 7]], 
              [2, [7, 3, 1, 6, 2, 0, 5, 7]]]

Generate all boards from third in top3, scores <= 2, add to list:
For i=1, j=2, 
   allboards=[[1, [4, 7, 1, 6, 2, 0, 5, 3]], [2, [0, 7, 1, 6, 2, 2, 5, 3]], 
              [2, [1, 3, 1, 6, 2, 0, 5, 7]], [2, [4, 3, 1, 6, 2, 0, 2, 7]], 
              [2, [4, 3, 1, 6, 2, 0, 5, 7]], [2, [4, 3, 1, 6, 2, 0, 7, 7]], 
              [2, [4, 6, 1, 6, 2, 0, 5, 7]], [2, [4, 7, 0, 6, 2, 2, 5, 3]], 
              [2, [4, 7, 1, 6, 2, 0, 3, 7]], [2, [4, 7, 1, 6, 2, 0, 5, 0]], 
              [2, [4, 7, 1, 6, 2, 0, 5, 7]], [2, [4, 7, 3, 6, 2, 0, 5, 7]], 
              [2, [4, 7, 3, 6, 2, 2, 5, 3]], [2, [7, 3, 1, 6, 2, 0, 5, 7]]]

Select top 3, one score 1:
Top 3= [[1, [4, 7, 1, 6, 2, 0, 5, 3]], [2, [0, 7, 1, 6, 2, 2, 5, 3]], 
        [2, [1, 3, 1, 6, 2, 0, 5, 7]]]

Generate all boards from 1st in top3, scores <= 1:
For i=2, j=0, 
  allboards=[[1, [4, 7, 1, 6, 2, 0, 6, 3]], [1, [4, 7, 1, 6, 2, 0, 7, 3]]]

Generate all boards from second in top3, scores <= 2, add to list:
For i=2, j=1, 
  allboards=[[1, [4, 7, 1, 6, 2, 0, 6, 3]], [1, [4, 7, 1, 6, 2, 0, 7, 3]], 
             [2, [0, 7, 1, 6, 2, 0, 5, 3]], [2, [0, 7, 1, 6, 2, 2, 7, 3]], 
             [2, [0, 7, 1, 6, 2, 7, 5, 3]], [2, [0, 7, 3, 6, 2, 2, 5, 3]], 
             [2, [0, 7, 4, 6, 2, 2, 5, 3]], [2, [4, 7, 1, 6, 2, 2, 5, 3]]]

Generate all boards from third in top3, scores <= 3, add to list:
For i=2, j=2, 
  allboards=[[1, [1, 3, 6, 6, 2, 0, 5, 7]], [1, [4, 7, 1, 6, 2, 0, 6, 3]], 
             [1, [4, 7, 1, 6, 2, 0, 7, 3]], [2, [0, 7, 1, 6, 2, 0, 5, 3]], 
             [2, [0, 7, 1, 6, 2, 2, 7, 3]], [2, [0, 7, 1, 6, 2, 7, 5, 3]], 
             [2, [0, 7, 3, 6, 2, 2, 5, 3]], [2, [0, 7, 4, 6, 2, 2, 5, 3]], 
             [2, [1, 3, 0, 6, 2, 0, 5, 7]], [2, [1, 3, 4, 6, 2, 0, 5, 7]], 
             [2, [1, 3, 5, 6, 2, 0, 5, 7]], [2, [4, 3, 1, 6, 2, 0, 5, 7]], 
             [2, [4, 7, 1, 6, 2, 2, 5, 3]], [2, [7, 3, 1, 6, 2, 0, 5, 7]]]

Select top 3 from combined list:
Top 3= [[1, [1, 3, 6, 6, 2, 0, 5, 7]], [1, [4, 7, 1, 6, 2, 0, 6, 3]], 
        [1, [4, 7, 1, 6, 2, 0, 7, 3]]]

Generate all boards from 1st in top3, scores <= 1:
For i=3, j=0, 
  allboards=[[1, [1, 3, 6, 0, 2, 0, 5, 7]], [1, [1, 3, 6, 4, 2, 0, 5, 7]]]

Generate all boards from second in top3, scores <= 1, add to list:
For i=3, j=1, 
   allboards=[[1, [1, 3, 6, 0, 2, 0, 5, 7]], [1, [1, 3, 6, 4, 2, 0, 5, 7]], 
              [1, [4, 7, 1, 4, 2, 0, 6, 3]], [1, [4, 7, 1, 5, 2, 0, 6, 3]], 
              [1, [4, 7, 1, 6, 2, 0, 5, 3]], [1, [4, 7, 1, 6, 2, 0, 7, 3]]]

Generate all boards from third in top3, scores <= 1, add to list:
For i=3, j=2, 
  allboards=[[1, [1, 3, 6, 0, 2, 0, 5, 7]], [1, [1, 3, 6, 4, 2, 0, 5, 7]], 
             [1, [4, 1, 1, 6, 2, 0, 7, 3]], [1, [4, 6, 1, 6, 2, 0, 7, 3]], 
             [1, [4, 7, 1, 4, 2, 0, 6, 3]], [1, [4, 7, 1, 5, 2, 0, 6, 3]], 
             [1, [4, 7, 1, 6, 2, 0, 5, 3]], [1, [4, 7, 1, 6, 2, 0, 6, 3]], 
             [1, [4, 7, 1, 6, 2, 0, 7, 3]]]

Pick top 3:
Top 3= [[1, [1, 3, 6, 0, 2, 0, 5, 7]], [1, [1, 3, 6, 4, 2, 0, 5, 7]], 
        [1, [4, 1, 1, 6, 2, 0, 7, 3]]]

Generate all boards from first in top3, scores <= 1:
For i=4, j=0, 
  allboards=[[1, [1, 3, 6, 0, 2, 4, 5, 7]], [1, [1, 3, 6, 4, 2, 0, 5, 7]], 
             [1, [1, 3, 6, 6, 2, 0, 5, 7]]]

Generate all boards from second in top3, scores <= 1, add to list:
For i=4, j=1, 
  allboards=[[1, [1, 3, 6, 0, 2, 0, 5, 7]], [1, [1, 3, 6, 0, 2, 4, 5, 7]], 
             [1, [1, 3, 6, 4, 2, 0, 5, 7]], [1, [1, 3, 6, 6, 2, 0, 5, 7]], 
             [1, [3, 3, 6, 4, 2, 0, 5, 7]]]

Generate all boards from third in top3, scores <= 1, add to list:
For i=4, j=2, 
   allboards=[[1, [1, 3, 6, 0, 2, 0, 5, 7]], [1, [1, 3, 6, 0, 2, 4, 5, 7]], 
              [1, [1, 3, 6, 4, 2, 0, 5, 7]], [1, [1, 3, 6, 6, 2, 0, 5, 7]], 
              [1, [3, 3, 6, 4, 2, 0, 5, 7]], [1, [4, 1, 1, 5, 2, 0, 7, 3]], 
              [1, [4, 1, 5, 6, 2, 0, 7, 3]], [1, [4, 6, 1, 6, 2, 0, 7, 3]], 
              [1, [4, 7, 1, 6, 2, 0, 7, 3]]]

Pick top 3:
Top 3= [[1, [1, 3, 6, 0, 2, 0, 5, 7]], [1, [1, 3, 6, 0, 2, 4, 5, 7]], 
        [1, [1, 3, 6, 4, 2, 0, 5, 7]]]

Generate all boards from first in top3, scores <= 1:
For i=5, j=0, 
  allboards=[[1, [1, 3, 6, 0, 2, 4, 5, 7]], [1, [1, 3, 6, 4, 2, 0, 5, 7]], 
             [1, [1, 3, 6, 6, 2, 0, 5, 7]]]

Generate all boards from second in top3, scores <= 1, add to list:
For i=5, j=1, 
  allboards=[[1, [1, 3, 6, 0, 2, 0, 5, 7]], [1, [1, 3, 6, 0, 2, 4, 1, 7]], 
             [1, [1, 3, 6, 0, 2, 4, 5, 7]], [1, [1, 3, 6, 4, 2, 0, 5, 7]], 
             [1, [1, 3, 6, 6, 2, 0, 5, 7]]]

Generate all boards from third in top3, scores <= 1, add to list:
For i=5, j=2, 
  allboards=[[1, [1, 3, 6, 0, 2, 0, 5, 7]], [1, [1, 3, 6, 0, 2, 4, 1, 7]], 
             [1, [1, 3, 6, 0, 2, 4, 5, 7]], [1, [1, 3, 6, 4, 2, 0, 5, 7]], 
             [1, [1, 3, 6, 6, 2, 0, 5, 7]], [1, [3, 3, 6, 4, 2, 0, 5, 7]]]

Pick top 3:
Top 3= [[1, [1, 3, 6, 0, 2, 0, 5, 7]], [1, [1, 3, 6, 0, 2, 4, 1, 7]], 
        [1, [1, 3, 6, 0, 2, 4, 5, 7]]]

Generate all boards from first in top3, scores <= 1:
For i=6, j=0, 
  allboards=[[1, [1, 3, 6, 0, 2, 4, 5, 7]], [1, [1, 3, 6, 4, 2, 0, 5, 7]], 
             [1, [1, 3, 6, 6, 2, 0, 5, 7]]]

Generate all boards from second in top3, scores <= 1, add to list:
For i=6, j=1, 
  allboards=[[0, [5, 3, 6, 0, 2, 4, 1, 7]], [1, [1, 3, 6, 0, 2, 4, 5, 7]], 
             [1, [1, 3, 6, 4, 2, 0, 5, 7]], [1, [1, 3, 6, 6, 2, 0, 5, 7]]]

Generate all boards from third in top3, scores <= 1, add to list:
For i=6, j=2, 
  allboards=[[0, [5, 3, 6, 0, 2, 4, 1, 7]], [1, [1, 3, 6, 0, 2, 0, 5, 7]], 
             [1, [1, 3, 6, 0, 2, 4, 1, 7]], [1, [1, 3, 6, 0, 2, 4, 5, 7]], 
             [1, [1, 3, 6, 4, 2, 0, 5, 7]], [1, [1, 3, 6, 6, 2, 0, 5, 7]]]

Pick top 3, score 0 found:
Board found on i = 6, board = [5, 3, 6, 0, 2, 4, 1, 7], score=0

Top 3 = [[0, [5, 3, 6, 0, 2, 4, 1, 7]], [1, [1, 3, 6, 0, 2, 0, 5, 7]], 
         [1, [1, 3, 6, 0, 2, 4, 1, 7]]]