Brute Force Marble Solitaire Solver

Image result for french solitaire

My grandfather gave me a marble solitaire set about 15 years ago that my father always puts out for us/him to play during the holiday visit. This xmas he¬†challenged me to beat his best score of two marbles left on the board with no moves left. After playing it a couple times I decided it would be pretty easy to write a little MATLAB program to find the winning moves using a “brute force” search approach. The program starts with a “winnable” initial empty spot and then runs through legal moves at random until eventually a solution is found (hopefully). If the program does find a solution in which there is only a single “marble” left on the board the recorded moves will be saved as a *.mat variable that can be used to determine the sequential steps that will provide a solution to the game. The program code below will just carry out the computation and print the current iteration and best score to the command window. For more information on the probability of finding a solution/number of solutions for any given starting board layout you can read more here (http://www.durangobill.com/Peg37.html). The best score I’ve been able to find thus far is 2 final pieces, but maybe you’ll have better luck (the search process is random). If you would like to download the command window output or GUI version script files they can be found on my GitHub repository here:

(Screen capture of MATLAB GUI)


function ballGameV3
     
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    % ballGameV3.m
    % 
    %     AUTHOR: Miles Vincent Barnhart
    %       DATE: 01 Jan. 2018
    %        VER: 3.0
    %
    %     INFO: A MATLAB program that tries to solve the marble solitaire
    %           game (sometimes referred to as 'Venecian solitaire') using
    %           a brute force guess approach.
    %
    %           Can be run using a parallel pool and calling from the
    %           command line as:
    %
    %                          >> parpool(N); % N = Number of cores
    %
    %                          >> parfor i = 1:N
    %                          >> ballGameV3;
    %                          >> end
    %
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    iter = 1;
    disp(' Iteration    Best yet     Current Iter.');
    disp(' ---------    --------     -------------');

    xbest = 100; % Dummy initial best score value
    flags = getFlags(); % Assign possible moves to cell array
    emptySpots = initEmpty(); % Obtain possible empty initial locations
    tic; % Start timer
    
    % for testtime = 1:5000 % USE TO TEST SPEED
    while xbest > 1
        
        [x, moves] = genMoves(flags, emptySpots);

        xi = sum(sum(x)); % If sum(x) == 1, game has been solved
        
        if xi < xbest % Update best game score
            
            xbest = xi;
            
        end

        fprintf('\t%0.0f\t\t\t\t%0.0f\t\t\t%0.0f\n', iter, xbest, xi);
        
        iter = iter + 1;

    end
    
    disp(['Time elapsed = ', sprintf('%f ',toc), ' seconds']);
    randNum =  sprintf('%d', randi([1,10000], 1)); % Save winning moves
    save(['winningMoves',randNum, '.mat'], 'moves');
    save(['winningBoard',randNum, '.mat'], 'x');
    disp(moves);
    disp('Solution found!');
    
    function [x, realmoves] = genMoves(flags, emptySpots)
        
        rand_row = 1:7;
        rand_row = randperm(length(rand_row));
        rand_col = randperm(length(rand_row));
        c = 1;
        mc = 1;                       

        x = genMat(emptySpots); % Generate initial board                                     
                      % with random empty spot
        while 1

            xold = x;

            for i = rand_row % Stepping over rows

                for j = rand_col % Stepping over columbs

                    [x, moves.(['m',sprintf('%d', c)])] = cellEdit(x, i, j, flags);
                    
                    if isequaln(moves.(['m',sprintf('%d', c)]).move, 0) == 0

                        realmoves.(['m',sprintf('%d', mc)]) = moves.(['m',sprintf('%d', c)]).move;
                        mc = mc + 1;
                        
                    end
                    
                    c = c + 1;
                    
                end
                
            x(x == 2) = 0; % Set boundary values to zero

            end

            if x == xold % Check if the board layout has changed

                break

            end

        end
        
        
    function [x, step] = cellEdit(x, row, col, flags)
        
        step.move = 0;
        
        flCk = flags{row, col};
        shuffledFL = flCk(randperm(length(flCk))); % Shuffle moves
        
        start = randi([1, randi([1, length(flCk)])], 1); % Random starting move
        len = randi([1, length(shuffledFL)],1); % Random end move
        
        if len > start
            
            d = 1; % Left-to-right
            
        else 
            
            d = -1; % Right-to-left
            
        end
        
        for i = start:d:len
            
            if isequaln(shuffledFL{i}, '')
                
                break
                
            elseif isequaln(shuffledFL{i}, 'vu') % Upward jump
                    
                if x(row, col) == 0 && ... % Check if empty spot and populated spots are available
                   x(row - 1, col) == 1 && ...
                   x(row - 2, col) == 1
                       
                   x(row, col) = 1; % Update board after jump
                   x(row - 1, col) = 0;
                   x(row - 2, col) = 0;
                   step.move = {row, col, 'vu'};
                    
                end
                    
            elseif isequaln(shuffledFL{i}, 'vd') % Downward jump
                    
                if x(row, col) == 0 && ... % Check if empty spot and populated spots are available
                   x(row + 1, col) == 1 && ...
                   x(row + 2, col) == 1
                       
                   x(row, col) = 1; % Update board after jump
                   x(row + 1, col) = 0;
                   x(row + 2, col) = 0;
                    
                   step.move = {row, col, 'vd'};
                        
                end
                    
            elseif isequaln(shuffledFL{i}, 'hl') % Horizontal-left jump
                    
                if x(row, col) == 0 && ... % Check if empty spot and populated spots are available
                   x(row, col - 1) == 1 && ...
                   x(row, col - 2) == 1
                       
                   x(row, col) = 1; % Update board after jump
                   x(row, col - 1) = 0;
                   x(row, col - 2) = 0;
                   step.move = {row, col, 'hl'};
                   
                end
                    
            elseif isequaln(shuffledFL{i}, 'hr') % Horizontal-right jump
                    
                if x(row, col) == 0 && ... % Check if empty spot and populated spots are available
                   x(row, col + 1) == 1 && ...
                   x(row, col + 2) == 1
                       
                   x(row, col) = 1; % Update board after jump
                   x(row, col + 1) = 0;
                   x(row, col + 2) = 0;
                   step.move = {row, col, 'hr'};
                   
                end
                
            end
            
            if isempty(step.move)

                step.move = 0;

            end
            
        end     

    function [x] = genMat(pickAspot)
                 
        x = ones(7);          % Initial board layout w/ 2's denoting
                              % boundary positions (not included)            
        x(2, 1) = 2;          % 2  2  1  1  1  2  2 
        x(1, 1:2) = 2;        % 2  1  1  1  1  1  2
        x(1,6:7) = 2;         % 1  1  1  1  1  1  1
        x(2, end) = 2;        % 1  1  1  1  1  1  1 
        x(end - 1, 1) = 2;    % 2  1  1  1  1  1  2
        x(end, 1:2) = 2;      % 2  2  1  1  1  2  2
        x(end, 6:7) = 2;
        x(end-1, end) = 2;
        x(pickAspot(randi([1,16],1),:)) = 0; % Initial empty spot

    function flags = getFlags()
            
        flags = cell(7);   % Assign possible moves for each cell
        flags(:) = {{''}}; % (this section needs to be optimized)
        flags{1, 3} = {'vd', 'hr'};
        flags{1, 4} = {'vd'};
        flags{1, 5} = {'vd', 'hl'};
        
        flags{2, 2} = {'vd', 'hr'};
        flags{2, 3} = {'vd', 'hr'};
        flags{2, 4} = {'vd','hl','hr'};
        flags{2, 5} = {'vd', 'hl'};
        flags{2, 6} = {'vd', 'hl'};
        
        flags{3, 1} = {'vd', 'hr'};
        flags{3, 2} = {'vd', 'hr'};        
        flags{3, 3} = {'vu', 'vd', 'hl', 'hr'};
        flags{3, 4} = {'vu', 'vd', 'hl', 'hr'};
        flags{3, 5} = {'vu', 'vd', 'hl', 'hr'};
        flags{3, 6} = {'vd', 'hl'};
        flags{3, 7} = {'vd', 'hl'};
        
        flags{4, 1} = {'hr'};
        flags{4, 2} = {'vu','vd','hr'};
        flags{4, 3} = {'vu', 'vd', 'hl', 'hr'};
        flags{4, 4} = {'vu', 'vd', 'hl', 'hr'};
        flags{4, 5} = {'vu', 'vd', 'hl', 'hr'};
        flags{4, 6} = {'vu','vd','hl'};
        flags{4, 7} = {'hl'};
        
        flags{5, 1} = {'vu', 'hr'};
        flags{5, 2} = {'vu', 'hr'};
        flags{5, 3} = {'vu', 'vd', 'hl', 'hr'};
        flags{5, 4} = {'vu', 'vd', 'hl', 'hr'};
        flags{5, 5} = {'vu', 'vd', 'hl', 'hr'};
        flags{5, 6} = {'vu', 'hl'};
        flags{5, 7} = {'vu', 'hl'};
        
        flags{6, 2} = {'vu', 'hr'};
        flags{6, 3} = {'vu', 'hr'};
        flags{6, 4} = {'vu','hl','hr'};
        flags{6, 5} = {'vu', 'hl'};
        flags{6, 6} = {'vu', 'hl'};
        
        flags{7, 3} = {'vu', 'hr'};
        flags{7, 4} = {'vu'};
        flags{7, 5} = {'vu', 'hl'};
        
        
    function pickAspot = initEmpty()
            
        pickAspot = [1, 3;    % Empty spots with possible 
                     1, 5;    % winning solutions
                     2, 4;    %
                     3, 1;    %          W   L   W
                     3, 4;    %      L   L   W   L   L
                     3, 7;    %  W   L   L   W   L   L   W
                     4, 2;    %  L   W   W   L   W   W   L
                     4, 3;    %  W   L   L   W   L   L   W
                     4, 5;    %      L   L   W   L   L
                     4, 6;    %          W   L   W
                     5, 1;
                     5, 4;
                     5, 7;
                     6, 4;
                     7, 3;
                     7, 5];

(c) Miles V. Barnhart