Interesting 16x16 grid sum
<p>EDIT: Path, not line --- it can wind around and stuff. The path connects adjacent squares. You cannot go diagonally.</p>

<p>Also, my proposed solution was an attempt to take every possible string of 50-digit numbers base 4 - so that, you start at each square, and move left, right, up or down --- in every possible combination 4^50</p>

<p>This problem asks you to find the greatest sum of 50 numbers that can be connected by a path, without going diagonally, in this 16x16 grid:</p>

<pre><code>                         {{50,54,46,55,45,56,44,53,47,59,41,60,40,59,41,59},
                          {47,57,46,49,52,46,53,47,53,41,59,40,60,41,59,41},
                          {56,42,54,51,48,54,47,53,53,57,48,54,49,57,46,59},
                          {48,50,52,54,56,58,57,47,48,49,48,47,46,53,52,51},
                          {50,56,50,48,49,50,51,59,42,60,39,62,38,63,38,50},
                          {60,40,50,50,50,50,60,40,55,45,55,45,56,44,56,44},
                          {60,45,46,37,56,50,43,39,50,53,56,39,50,58,39,49},
                          {26,56,54,38,48,50,67,64,32,54,50,49,48,47,46,45},
                          {28,45,35,57,54,34,34,32,64,57,58,74,24,64,34,50},
                          {40,50,60,54,45,56,46,47,35,36,39,27,38,50,51,52},
                          {29,38,47,58,48,37,50,58,37,46,50,50,50,50,50,50},
                          {47,48,49,50,52,65,64,52,49,47,43,47,58,46,30,32},
                          {59,47,47,56,65,34,45,56,75,24,35,45,56,65,50,54},
                          {53,46,35,45,29,46,46,50,23,32,40,46,64,64,64,20},
                          {53,54,56,58,60,43,43,34,34,35,64,30,50,40,49,59},
</code></pre>

<p>This algorithm tries <strong>random</strong> paths and turns after each of the 50 steps - up, right, down, left - without crossing over itself. It gets me to about 2750, but I need at least 2800 to complete the assignment.
//lol</p>

<pre><code>import java.util.ArrayList;

public class lol
{
private int[][] square = {{50,54,46,55,45,56,44,53,47,59,41,60,40,59,41,59},
                          {47,57,46,49,52,46,53,47,53,41,59,40,60,41,59,41},
                          {56,42,54,51,48,54,47,53,53,57,48,54,49,57,46,59},
                          {48,50,52,54,56,58,57,47,48,49,48,47,46,53,52,51},
                          {50,56,50,48,49,50,51,59,42,60,39,62,38,63,38,50},
                          {60,40,50,50,50,50,60,40,55,45,55,45,56,44,56,44},
                          {60,45,46,37,56,50,43,39,50,53,56,39,50,58,39,49},
                          {26,56,54,38,48,50,67,64,32,54,50,49,48,47,46,45},
                          {28,45,35,57,54,34,34,32,64,57,58,74,24,64,34,50},
                          {40,50,60,54,45,56,46,47,35,36,39,27,38,50,51,52},
                          {29,38,47,58,48,37,50,58,37,46,50,50,50,50,50,50},
                          {47,48,49,50,52,65,64,52,49,47,43,47,58,46,30,32},
                          {59,47,47,56,65,34,45,56,75,24,35,45,56,65,50,54},
                          {53,46,35,45,29,46,46,50,23,32,40,46,64,64,64,20},
                          {53,54,56,58,60,43,43,34,34,35,64,30,50,40,49,59},
                          {52,12,17,50,63,62,62,64,50,51,52,57,43,44,42,69}};                         ;

    public static void main(String [] args)
{
    lol lol1 = new lol();
}
public lol()
{
    ArrayList&lt;Integer&gt; record = new ArrayList&lt;Integer&gt;();
    int max =0;
    for(int count = 0; count&lt;10000; count++)
    {
        for(int startx=0; startx&lt;16; startx++)
        {
            for(int starty =0; starty&lt;16; starty++)
            {
                int[] pos = new int[2];
                pos[0] = starty;
                pos[1] = startx;
                ArrayList&lt;Integer&gt; past = new ArrayList&lt;Integer&gt;();
                int total = 0;

                for(int i=0; i&lt;50; i++)
                {
                    int random = (int)(Math.random()*4);
                    int switchcount = 0;
                    past.add(100*pos[0] + pos[1]);
                    total+= square[pos[0]][pos[1]];

                    if(random == 0)
                    {
                        if(pos[0] == 0 || checkexists((pos[0]-1)*100+pos[1],past))
                        {
                            random++;
                            switchcount++;
                        }
                        else
                        {
                            pos[0]--;

                        }
                    }
                    if(random == 1)
                    {
                        if(pos[0] == 15 || checkexists((pos[0]+1)*100+pos[1],past))
                        {
                            random++;
                            switchcount++;
                        }
                        else
                        {
                            pos[0]++;

                        }
                    }
                    if(random == 2)
                    {
                        if(pos[1] == 0 || checkexists((pos[0])*100+pos[1]-1,past))
                        {
                            random++;
                            switchcount++;
                        }
                        else
                        {
                            pos[1]--;

                        }
                    }
                    if(random == 3)
                    {
                        if(pos[1] == 15 || checkexists((pos[0])*100+pos[1]+1,past))
                        {
                            if(switchcount &gt;= 3)
                            {
                                break;
                            }
                            else
                            {
                                random = 0;
                                if(pos[0] == 0 || checkexists((pos[0]-1)*100+pos[1],past))
                                {
                                    random++;
                                    switchcount++;
                                }
                                else
                                {
                                    pos[0]--;

                                }
                                if(random == 1)
                                {
                                    if(pos[0] == 15 || checkexists((pos[0]+1)*100+pos[1],past))
                                    {
                                        random++;
                                        switchcount++;
                                    }
                                    else
                                    {
                                        pos[0]++;

                                    }
                                }

                                if(random == 2)
                                {
                                    if(pos[1] == 0 || checkexists((pos[0])*100+pos[1]-1,past))
                                    {
                                        break;
                                    }
                                    else
                                    {
                                        pos[1]--;

                                    }
                                }
                            }
                        }
                        else
                        {
                            pos[1]++;
                        }
                    }
                }
                if (total&gt;max)
                {
                    max = total;
                    record = past;
                }







            }
        }
    }
    for(int p = 0; p&lt;record.size(); p++)
    {
        System.out.println(record.get(p));
    }
    System.out.println("\n\n" + max);

}
public boolean checkexists(int pos, ArrayList&lt;Integer&gt; past)
{
    for(int i=0; i&lt;past.size(); i++)
    {
        if(past.get(i) == pos)
        {
            //System.out.println("TRUE");
            return true;
        }
    }
    return false;
}
}
</code></pre>

<p>This is my attempt at a full solution - it attempt to take every possible string of 50-digit numbers base 4 - so that, you start at each square, and move left, right, up or down --- in every possible combination 4^50</p>

<pre><code>import java.util.ArrayList;

    public class lol2
     {
     private int[][] square =      {{50,54,46,55,45,56,44,53,47,59,41,60,40,59,41,59},
                              {47,57,46,49,52,46,53,47,53,41,59,40,60,41,59,41},
                          {56,42,54,51,48,54,47,53,53,57,48,54,49,57,46,59},
                          {48,50,52,54,56,58,57,47,48,49,48,47,46,53,52,51},
                          {50,56,50,48,49,50,51,59,42,60,39,62,38,63,38,50},
                          {60,40,50,50,50,50,60,40,55,45,55,45,56,44,56,44},
                          {60,45,46,37,56,50,43,39,50,53,56,39,50,58,39,49},
                          {26,56,54,38,48,50,67,64,32,54,50,49,48,47,46,45},
                          {28,45,35,57,54,34,34,32,64,57,58,74,24,64,34,50},
                          {40,50,60,54,45,56,46,47,35,36,39,27,38,50,51,52},
                          {29,38,47,58,48,37,50,58,37,46,50,50,50,50,50,50},
                          {47,48,49,50,52,65,64,52,49,47,43,47,58,46,30,32},
                          {59,47,47,56,65,34,45,56,75,24,35,45,56,65,50,54},
                          {53,46,35,45,29,46,46,50,23,32,40,46,64,64,64,20},
                          {53,54,56,58,60,43,43,34,34,35,64,30,50,40,49,59},
                               {52,12,17,50,63,62,62,64,50,51,52,57,43,44,42,69}};

public static void main(String [] args)
{
    lol2 lol1 = new lol2();
}
public lol2()
{
    ArrayList&lt;Integer&gt; record = new ArrayList&lt;Integer&gt;();
    int max =0;
    for(int count = 0; count&lt;10000; count++)
    {
        for(int startx=0; startx&lt;16; startx++)
        {
            for(int starty =0; starty&lt;16; starty++)
            {
                for(int a1 = 0; a1 &lt;4; a1++) {
                    for(int a2 = 0; a2 &lt;4; a2++) {
                        for(int a3 = 0; a3 &lt;4; a3++) {
                            for(int a4 = 0; a4 &lt;4; a4++) {
                                for(int a5 = 0; a5 &lt;4; a5++) {
                                    for(int a6 = 0; a6 &lt;4; a6++) {
                                        for(int a7 = 0; a7 &lt;4; a7++) {
                                            for(int a8 = 0; a8 &lt;4; a8++) {
                                                for(int a9 = 0; a9 &lt;4; a9++) {
                                                    for(int a10 = 0; a10 &lt;4; a10++) {
                                                        for(int a11 = 0; a11 &lt;4; a11++) {
                                                            for(int a12 = 0; a12 &lt;4; a12++) {
                                                                for(int a13 = 0; a13 &lt;4; a13++) {
                                                                    for(int a14 = 0; a14 &lt;4; a14++) {
                                                                        for(int a15 = 0; a15 &lt;4; a15++) {
                                                                            for(int a16 = 0; a16 &lt;4; a16++) {
                                                                                for(int a17 = 0; a17 &lt;4; a17++) {
                                                                                    for(int a18 = 0; a18 &lt;4; a18++) {
                                                                                        for(int a19 = 0; a19 &lt;4; a19++) {
                                                                                            for(int a20 = 0; a20 &lt;4; a20++) {
                                                                                                for(int a21 = 0; a21 &lt;4; a21++) {
                                                                                                    for(int a22 = 0; a22 &lt;4; a22++) {
                                                                                                        for(int a23 = 0; a23 &lt;4; a23++) {
                                                                                                            for(int a24 = 0; a24 &lt;4; a24++) {
                                                                                                                for(int a25 = 0; a25 &lt;4; a25++) {
                                                                                                                    for(int a26 = 0; a26 &lt;4; a26++) {
                                                                                                                        for(int a27 = 0; a27 &lt;4; a27++) {
                                                                                                                            for(int a28 = 0; a28 &lt;4; a28++) {
                                                                                                                                for(int a29 = 0; a29 &lt;4; a29++) {
                                                                                                                                    for(int a30 = 0; a30 &lt;4; a30++) {
                                                                                                                                        for(int a31 = 0; a31 &lt;4; a31++) {
                                                                                                                                            for(int a32 = 0; a32 &lt;4; a32++) {
                                                                                                                                                for(int a33 = 0; a33 &lt;4; a33++) {
                                                                                                                                                    for(int a34 = 0; a34 &lt;4; a34++) {
                                                                                                                                                        for(int a35 = 0; a35 &lt;4; a35++) {
                                                                                                                                                            for(int a36 = 0; a36 &lt;4; a36++) {
                                                                                                                                                                for(int a37 = 0; a37 &lt;4; a37++) {
                                                                                                                                                                    for(int a38 = 0; a38 &lt;4; a38++) {
                                                                                                                                                                        for(int a39 = 0; a39 &lt;4; a39++) {
                                                                                                                                                                            System.out.println("SPAM");
                                                                                                                                                                            for(int a40 = 0; a40 &lt;4; a40++) {
                                                                                                                                                                                for(int a41 = 0; a41 &lt;4; a41++) {
                                                                                                                                                                                    for(int a42 = 0; a42 &lt; 4; a42++){
                                                                                                                                                                                        for(int a43=0; a43&lt;4; a43++){
                                                                                                                                                                                            for(int a44 =0; a44&lt;4; a44++){
                                                                                                                                                                                                for(int a45=0; a45&lt;4; a45++){
                                                                                                                                                                                                    for(int a46=0; a46&lt;4; a46++){
                                                                                                                                                                                                        for(int a47=0; a47&lt;4; a47++){
                                                                                                                                                                                                            for(int a48=0; a48&lt;4; a48++){
                                                                                                                                                                                                                for(int a49=0; a49&lt;4; a49++){
                                                                                                                                                                                                                    for(int a50=0; a50&lt;4; a50++){
                                                                                                                                                                                                                        int[] pos = new int[2];
                                                                                                                                                                                                                        pos[0] = starty;
                                                                                                                                                                                                                        pos[1] = startx;
                                                                                                                                                                                                                        ArrayList&lt;Integer&gt; past = new ArrayList&lt;Integer&gt;();
                                                                                                                                                                                                                        int total = 0;
                                                                                                                                                                                                                        String path = "" + a1 + a2+a3+a4+a5+a6+a7+a8+a9+a10+a11+a12+a13+a14+a15+a16+a17+a18+a19+a20+a21+a22+a23+a24+a25+a26+a27+a28+a29+a30+a31+a32+a33+a34+a35+a36+a37+a38+a39+a40+a41+a42+a43+a44+a45+a46+a47+a48+a49+a50;
                                                                                                                                                                                                                        for(int i =0; i&lt;50; i++)
                                                                                                                                                                                                                                {

                                                                                                                                                                                                                                    int random = Integer.parseInt(path.substring(i,i+1));
                                                                                                                                                                                                                                    int switchcount = 0;

                                                                                                                                                                                                                                    past.add(100*pos[0] + pos[1]);
                                                                                                                                                                                                                                                        total+= square[pos[0]][pos[1]];

                                                                                                                                                                                                                                                        if(random == 0)
                                                                                                                                                                                                                                                        {
                                                                                                                                                                                                                                                            if(pos[0] == 0 || checkexists((pos[0]-1)*100+pos[1],past))
                                                                                                                                                                                                                                                            {
                                                                                                                                                                                                                                                                random++;
                                                                                                                                                                                                                                                                switchcount++;
                                                                                                                                                                                                                                                            }
                                                                                                                                                                                                                                                            else
                                                                                                                                                                                                                                                            {
                                                                                                                                                                                                                                                                pos[0]--;

                                                                                                                                                                                                                                                            }
                                                                                                                                                                                                                                                        }
                                                                                                                                                                                                                                                        if(random == 1)
                                                                                                                                                                                                                                                        {
                                                                                                                                                                                                                                                            if(pos[0] == 15 || checkexists((pos[0]+1)*100+pos[1],past))
                                                                                                                                                                                                                                                            {
                                                                                                                                                                                                                                                                random++;
                                                                                                                                                                                                                                                                switchcount++;
                                                                                                                                                                                                                                                            }
                                                                                                                                                                                                                                                            else
                                                                                                                                                                                                                                                            {
                                                                                                                                                                                                                                                                pos[0]++;

                                                                                                                                                                                                                                                            }
                                                                                                                                                                                                                                                        }
                                                                                                                                                                                                                                                        if(random == 2)
                                                                                                                                                                                                                                                        {
                                                                                                                                                                                                                                                            if(pos[1] == 0 || checkexists((pos[0])*100+pos[1]-1,past))
                                                                                                                                                                                                                                                            {
                                                                                                                                                                                                                                                                random++;
                                                                                                                                                                                                                                                                switchcount++;
                                                                                                                                                                                                                                                            }
                                                                                                                                                                                                                                                            else
                                                                                                                                                                                                                                                            {
                                                                                                                                                                                                                                                                pos[1]--;

                                                                                                                                                                                                                                                            }
                                                                                                                                                                                                                                                        }
                                                                                                                                                                                                                                                        if(random == 3)
                                                                                                                                                                                                                                                        {
                                                                                                                                                                                                                                                            if(pos[1] == 15 || checkexists((pos[0])*100+pos[1]+1,past))
                                                                                                                                                                                                                                                            {
                                                                                                                                                                                                                                                                if(switchcount &gt;= 3)
                                                                                                                                                                                                                                                                {
                                                                                                                                                                                                                                                                    break;
                                                                                                                                                                                                                                                                }
                                                                                                                                                                                                                                                                else
                                                                                                                                                                                                                                                                {
                                                                                                                                                                                                                                                                    random = 0;
                                                                                                                                                                                                                                                                    if(pos[0] == 0 || checkexists((pos[0]-1)*100+pos[1],past))
                                                                                                                                                                                                                                                                    {
                                                                                                                                                                                                                                                                        random++;
                                                                                                                                                                                                                                                                        switchcount++;
                                                                                                                                                                                                                                                                    }
                                                                                                                                                                                                                                                                    else
                                                                                                                                                                                                                                                                    {
                                                                                                                                                                                                                                                                        pos[0]--;

                                                                                                                                                                                                                                                                    }
                                                                                                                                                                                                                                                                    if(random == 1)
                                                                                                                                                                                                                                                                    {
                                                                                                                                                                                                                                                                        if(pos[0] == 15 || checkexists((pos[0]+1)*100+pos[1],past))
                                                                                                                                                                                                                                                                        {
                                                                                                                                                                                                                                                                            random++;
                                                                                                                                                                                                                                                                            switchcount++;
                                                                                                                                                                                                                                                                        }
                                                                                                                                                                                                                                                                        else
                                                                                                                                                                                                                                                                        {
                                                                                                                                                                                                                                                                            pos[0]++;

                                                                                                                                                                                                                                                                        }
                                                                                                                                                                                                                                                                    }

                                                                                                                                                                                                                                                                    if(random == 2)
                                                                                                                                                                                                                                                                    {
                                                                                                                                                                                                                                                                        if(pos[1] == 0 || checkexists((pos[0])*100+pos[1]-1,past))
                                                                                                                                                                                                                                                                        {
                                                                                                                                                                                                                                                                            break;
                                                                                                                                                                                                                                                                        }
                                                                                                                                                                                                                                                                        else
                                                                                                                                                                                                                                                                        {
                                                                                                                                                                                                                                                                            pos[1]--;

                                                                                                                                                                                                                                                                        }
                                                                                                                                                                                                                                                                    }
                                                                                                                                                                                                                                                                }
                                                                                                                                                                                                                                                            }
                                                                                                                                                                                                                                                            else
                                                                                                                                                                                                                                                            {
                                                                                                                                                                                                                                                                pos[1]++;
                                                                                                                                                                                                                                                            }
                                                                                                                                                                                                                                                        }
                                                                                                                                                                                                                                            }
                                                                                                                                                                                                                        if (total&gt;max) max = total;f
                                                                                                                                                                                                                    }
                                                                                                                                                                                                                }
                                                                                                                                                                                                            }
                                                                                                                                                                                                        }
                                                                                                                                                                                                    }
                                                                                                                                                                                                }
                                                                                                                                                                                            }
                                                                                                                                                                                        }
                                                                                                                                                                                    }
                                                                                                                                                                                }
                                                                                                                                                                            }
                                                                                                                                                                        }

                                                                                                                                                                    }
                                                                                                                                                                }
                                                                                                                                                            }
                                                                                                                                                        }
                                                                                                                                                    }
                                                                                                                                                }
                                                                                                                                            }
                                                                                                                                        }
                                                                                                                                    }
                                                                                                                                }
                                                                                                                            }
                                                                                                                        }
                                                                                                                    }
                                                                                                                }
                                                                                                            }
                                                                                                        }
                                                                                                    }
                                                                                                }
                                                                                            }
                                                                                        }
                                                                                    }
                                                                                }
                                                                            }
                                                                        }
                                                                    }
                                                                }
                                                            }
                                                        }
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    for(int p = 0; p&lt;record.size(); p++)
    {
        System.out.println(record.get(p));
    }
    System.out.println("\n\n" + max);

}
public boolean checkexists(int pos, ArrayList&lt;Integer&gt; past)
{
    for(int i=0; i&lt;past.size(); i++)
    {
        if(past.get(i) == pos)
        {
            //System.out.println("TRUE");
            return true;
        }
    }
    return false;
}
/*public ArrayList&lt;String&gt; setint()
{
    ArrayList&lt;String&gt; bob = new ArrayList&lt;String&gt;();
    for(BigInteger i =1267650600228229401496703205376; ; i&lt;2535301200456458802993406410752; i++)
    {
        String number = i + "";
        bob.add(BigInteger.toString(BigInteger.parseInt(number, 10), 4));
    }
    return bob;
}
*/
</code></pre>

<p>}</p>