Peg Solitaire - Stuck on creating a state array
<p>I need to modify a state array to use only four bits per state. As there is no native 4-bit type, you will need to use a larger type and bit manipulations to get and set the bits for each state. These four bits will be used for two purposes.</p>

<p>a. Two of the four bits will represent 4 values: Already seen, current depth, next depth, and
unseen. This will efficiently mark what states should be expanded in the current iteration
and future iterations.</p>

<p>b. The other bits will store the depth of each state modulo 4. This is sufficient information to extract the path from the board.</p>

<p>Yes, this is a HW question so I don't expect an answer, just guidance. I'm am unsure how to proceed with my determineStateInfo function. Here is my current code:</p>

<pre><code>    #include &lt;iostream&gt;
#include &lt;climits&gt;
#include &lt;vector&gt;
#include &lt;assert.h&gt;
#include &lt;stdio.h&gt;
enum state {NEXT_DEPTH = 2, UNSEEN = 3, CURRENT_DEPTH = 1, ALREADY_SEEN = 0};

bool valid[56] =
{
    false, false, false,  false, false, false, false,
    false,  true,  true,  true,  true,  true, false,
    false,  true,  true,  true,  true,  true, false,
    false,  true,  true,  true,  true,  true, false,
    false,  true,  true,  true,  true,  true, false,
    false,  true,  true,  true,  true,  true, false,
    false,  true,  true,  true,  true,  true, false,
    false, false, false,  false, false, false, false
};

struct PegState {
    bool board[56];
};

struct PegAction {
    int from, to, middle;
};

PegState GetStartState()
{
    PegState s;
    for (int x = 0; x &lt; 56; x++)
    {
        s.board[x] = true;
    }
    s.board[24] = 0;
    return s;
}

uint32_t GetHashFromState(PegState s)
{
    uint32_t hash = 0;
    for (int x = 0; x &lt; 56; x++)
    {
        if (valid[x])
            hash = (hash&lt;&lt;1)|(s.board[x]?1:0);
    }
    return hash;
}

PegState GetStateFromHash(uint32_t hash)
{
    PegState s;
    for (int x = 55; x &gt;= 0; x--)
    {
        if (valid[x])
        {
            s.board[x] = hash&amp;0x1;
            hash = hash&gt;&gt;1;
        }
    }
    return s;
}

uint32_t GetMaxHashValue()
{
    uint32_t vals = 0;
    for (int x = 0; x &lt; 55; x++)
    {
        if (valid[x])
            vals = (vals&lt;&lt;1)|1;
    }
    return vals;
//  return 0xFFFFFFFFul;
}

void Print(PegState s)
{
    for (int x = 0; x &lt; 7; x++)
    {
        for (int y = 0; y &lt; 8; y++)
        {
            if (valid[x+y*7])
            {
                printf("%c", s.board[x+y*7]?'o':'.');
            }
            else {
                printf(" ");
            }
        }
        printf("\n");
    }
    printf("\n");
    printf("\n");
}

std::vector&lt;PegAction&gt; GetLegalActions(PegState s)
{
    std::vector&lt;PegAction&gt; moves;
    for (int x = 0; x &lt; 5; x++)
    {
        for (int y = 1; y &lt; 7; y++)
        {
            if (valid[x+0+y*7] &amp;&amp; valid[x+1+y*7] &amp;&amp; valid[x+2+y*7])
            {
                // right
                if ((s.board[x+0+y*7] == true) &amp;&amp;
                    (s.board[x+1+y*7] == true) &amp;&amp;
                    (s.board[x+2+y*7] == false))
                {
                    PegAction a;
                    a.from = x+0+y*7;
                    a.middle = x+1+y*7;
                    a.to = x+2+y*7;
                    moves.push_back(a);
                }
                // left
                if ((s.board[x+0+y*7] == false) &amp;&amp;
                    (s.board[x+1+y*7] == true) &amp;&amp;
                    (s.board[x+2+y*7] == true))
                {
                    PegAction a;
                    a.from = x+2+y*7;
                    a.middle = x+1+y*7;
                    a.to = x+0+y*7;
                    moves.push_back(a);
                }
            }
        }
    }

    for (int x = 1; x &lt; 6; x++)
    {
        for (int y = 0; y &lt; 6; y++)
        {
            if (valid[x+(y+0)*7] &amp;&amp; valid[x+(y+1)*7] &amp;&amp; valid[x+(y+2)*7])
            {
                // down
                if ((s.board[x+(y+0)*7] == true) &amp;&amp;
                    (s.board[x+(y+1)*7] == true) &amp;&amp;
                    (s.board[x+(y+2)*7] == false))
                {
                    PegAction a;
                    a.from = x+(y+0)*7;
                    a.middle = x+(y+1)*7;
                    a.to = x+(y+2)*7;
                    moves.push_back(a);
                }
                // up
                if ((s.board[x+(y+0)*7] == false) &amp;&amp;
                    (s.board[x+(y+1)*7] == true) &amp;&amp;
                    (s.board[x+(y+2)*7] == true))
                {
                    PegAction a;
                    a.from = x+(y+2)*7;
                    a.middle = x+(y+1)*7;
                    a.to = x+(y+0)*7;
                    moves.push_back(a);
                }
            }
        }
    }
    return moves;
}

PegState ApplyAction(PegState s, PegAction a)
{
    assert(s.board[a.from] == true);
    s.board[a.from] = false;
    assert(s.board[a.middle] == true);
    s.board[a.middle] = false;
    assert(s.board[a.to] == false);
    s.board[a.to] = true;

    return s;
}

void undo()
{

}

void reverse()
{

}

void setBit(uint8_t *array, const uint32_t hash, const uint8_t new_info)
{
    assert(new_info == (new_info&amp;0xF));
    const uint8_t index ( hash/2 );
    if(hash%2 == 0) //even
    {
        array[index] &amp;= 0xF;  //00001111
        array[index] |= new_info &lt;&lt; 4;
    }
    else
    {
        array[index] &amp;= 0xF0;   //11110000
        array[index] |= new_info;
    }
}

uint8_t getStateInformation(const uint8_t *array, const uint32_t hash)
{
    const uint8_t index ( hash/2 );
    if(hash%2 == 0) //even
        return array[index] &amp; 0xF;
    else
        return array[index] &amp; 0xF0;
}

void savestate(PegState *temp)
{
    FILE *f;
    f = fopen("state.txt", "w+");

    for (int x = 0; x &lt; 55; x++) {}
        //fwrite(&amp;temp.board[x], sizeof(PegState), 1, f);
}

uint8_t determineStateInfo(uint8_t status, uint32_t depth)
{
    if(status == CURRENT_DEPTH)
    {

    }
    else if(status == ALREADY_SEEN)
    {

    }
    return 0;
}

bool compare(uint8_t stateInfo)
{
    if(stateInfo == 0xF)
        return true;
    else
        return false;
}

void BFS()
{
    // initialize memory, 1 byte per state, to store the depth of the state
    uint32_t maxVal = GetMaxHashValue();
    int8_t *dist = new int8_t[maxVal];

    // reset all memory to -1 (unseen)
    for (uint32_t x = 0; x &lt; maxVal; x++)
        dist[x] = -1;

    // Set the start state to depth 0
    PegState s = GetStartState();
    dist[GetHashFromState(s)] = 0;
    Print(s);

    printf("Ready to begin search\n");

    // Loop through all states; any at the current depth should:
    //   * Have their legal actions generated
    //   * Find all possible successor states
    //   * Write the depth of the successors
    // Repeat the loop until no states are updated in the loop
    int update = 0;
    int expand = 0;
    int currDepth = 0;
    do {
        expand = 0;
        update = 0;
        for (uint32_t x = 0; x &lt; maxVal; x++)
        {
            uint8_t i = getStateInformation(dist[x], maxVal);
//          if (0 == x%100000000)
//              printf("%ul\n", x);
            if (dist[x] == currDepth)
            {
                expand++;
                s = GetStateFromHash(x);
                std::vector&lt;PegAction&gt; m = GetLegalActions(s);
                for (unsigned int t = 0; t &lt; m.size(); t++)
                {
                    PegState res = ApplyAction(s, m[t]);
                    uint32_t rank = GetHashFromState(res);
                    if (dist[rank] == -1)
                    {
                        dist[rank] = currDepth+1;
                        update++;
                    }
                }
            }
        }
        printf("Depth %d; %d expanded; %d unique generated\n",currDepth, expand, update);
        currDepth++;
    } while (update &gt; 0);

    for (uint32_t x = 0; x &lt; maxVal; x++)
    {
        if (dist[x] == (currDepth-1) || dist[x] == 0)
        {
            s = GetStateFromHash(x);
            Print(s);
        }
    }
    // Print statistics about the search
}

int main(int argc, const char * argv[])
{
    BFS();
    return 0;
}
</code></pre>
