Hill-Climbing Searching Algorith

8Puzzles Problem

#include<vector>
#include<iostream>
#include<utility>
#include<algorithm>


#define random(x) (rand()%x)
#define MaxSteps 100
int cost;
bool InRandomRestart = false;


using namespace std;

struct _8Puzzles {
    vector<vector<int>> State; // current state
    pair<int, int> BlankPos; // position of the blank.
    int ManhattanDis;
    vector<int> SuccessorsManhattan; // [0] - Manhattan after move up(if possible)
                                                        // [1] - Manhattan after move down(if possible)
                                                        // [2] - Manhattan after move left(if possible)
                                                        // [3] - Manhattan after move right(if possible)
    _8Puzzles() {
        ManhattanDis = 0;
        State.resize(3);
        for (int i = 0; i < 3; i++)
            State[i].resize(3);
        BlankPos = make_pair(0, 0);
        SuccessorsManhattan.resize(4);
    }

    int Manhattan() {  // Calculate and set Manhattan Distance
        int sum = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (State[i][j] == 0) continue;
                int row = State[i][j] / 3;
                int col = State[i][j] % 3;
                int distance = abs(row - i) + abs(col - j);
                sum += distance;
            }
        }
        ManhattanDis = sum;
        return sum;
    }

    void SetSuccessorsManhattan() {
        if (CanMoveUp()) {
            _8Puzzles Up = *this;
            Up.MoveUp();
            SuccessorsManhattan[0] = Up.Manhattan();
        }
        else SuccessorsManhattan[0] = 10000;

        if (CanMoveDown()) {
            _8Puzzles Down = *this;
            Down.MoveDown();
            SuccessorsManhattan[1] = Down.Manhattan();
        }
        else SuccessorsManhattan[1] = 10000;

        if (CanMoveLeft()) {
            _8Puzzles Left = *this;
            Left .MoveLeft();
            SuccessorsManhattan[2] = Left.Manhattan();
        }
        else SuccessorsManhattan[2] = 10000;

        if (CanMoveRight()) {
            _8Puzzles Right = *this;
            Right.MoveRight();
            SuccessorsManhattan[3] = Right.Manhattan();
        }
        else SuccessorsManhattan[3] = 10000;
    }
    
    bool CanMoveUp() {
        int row = BlankPos.first, col = BlankPos.second;
        if (row == 0) // on the first row, unable to move up
            return false;
        return true;
    }

    bool CanMoveDown() {
        int row = BlankPos.first, col = BlankPos.second;
        if (row == 2) // on the first row, unable to move up
            return false;
        return true;
    }

    bool CanMoveLeft() {
        int row = BlankPos.first, col = BlankPos.second;
        if (col == 0) // on the first row, unable to move up
            return false;
        return true;
    }

    bool CanMoveRight() {
        int row = BlankPos.first, col = BlankPos.second;
        if (col == 2) // on the first row, unable to move up
            return false;
        return true;
    }

    bool MoveUp() {
        int row = BlankPos.first, col = BlankPos.second;
        if (!CanMoveUp()) // on the first row, unable to move up
            return false;
        else {
            int temp = State[row - 1][col]; // the value that's on top of the blank
            State[row - 1][col] = 0; // blank moves up
            State[row][col] = temp; // value moves down
            BlankPos = make_pair(row - 1, col); // blank position updates
            return true;
        }
    }

    bool MoveDown() {
        int row = BlankPos.first, col = BlankPos.second;
        if (!CanMoveDown()) // on the first row, unable to move up
            return false;
        else {
            int temp = State[row + 1][col]; // the value that's on below of the blank
            State[row + 1][col] = 0; // blank moves below
            State[row][col] = temp; // value moves down
            BlankPos = make_pair(row + 1, col); // blank position updates
            return true;
        }
    }

    bool MoveLeft() {
        int row = BlankPos.first, col = BlankPos.second;
        if (!CanMoveLeft()) // on the first row, unable to move up
            return false;
        else {
            int temp = State[row][col-1]; // the value that's on left of the blank
            State[row][col-1] = 0; // blank moves left
            State[row][col] = temp; // value moves right
            BlankPos = make_pair(row, col-1); // blank position updates
            return true;
        }
    }

    bool MoveRight() {
        int row = BlankPos.first, col = BlankPos.second;
        if (!CanMoveRight()) // on the first row, unable to move up
            return false;
        else {
            int temp = State[row][col + 1]; // the value that's on right of the blank
            State[row][col + 1] = 0; // blank moves right
            State[row][col] = temp; // value moves left
            BlankPos = make_pair(row, col + 1); // blank position updates
            return true;
        }
    }
};

_8Puzzles Generator() {
    _8Puzzles ResultPuzzle;
    // init is the result state of 8Puzzles
    vector<vector<int>> init;
    init.resize(3);
    for (int i = 0; i < 3; i++)
        init[i].resize(3);
    for (int i = 0; i < 3; ++i) {  // 初始状态为目标状态
        for (int j = 0; j < 3; ++j) {
            init[i][j] = i * 3 + j;
        }
    }

    ResultPuzzle.State = init;
    ResultPuzzle.BlankPos = make_pair(0, 0);

    int MoveTimes = 1000;
    while (MoveTimes--) { // randomly moves 1000 times
        int Select = random(4);
        if (Select == 0)
            ResultPuzzle.MoveUp();
        else if (Select == 1)
            ResultPuzzle.MoveDown();
        else if (Select == 2)
            ResultPuzzle.MoveLeft();
        else if (Select == 3)
            ResultPuzzle.MoveRight();
    }
    ResultPuzzle.Manhattan();
    ResultPuzzle.SetSuccessorsManhattan();
    return ResultPuzzle;
}

bool SteepestAscent(_8Puzzles _8P) {
    _8Puzzles CopyPuzzle = _8P;
    int MinManhatton = 9999, MinManIndex;
    int chance = MaxSteps;
    chance = InRandomRestart ? cost + MaxSteps : MaxSteps;

    while (cost < chance) {
        MinManhatton = 9999;
        MinManIndex = -1;
        cost += 1;
        for (int i = 0; i < 4; i++) {
            if (CopyPuzzle.SuccessorsManhattan[i] < MinManhatton && CopyPuzzle.SuccessorsManhattan[i] < CopyPuzzle.ManhattanDis) {
                MinManhatton = CopyPuzzle.SuccessorsManhattan[i];
                MinManIndex = i;
            }
        }
        if (MinManIndex == -1) { // Can't find a smaller successor, reach Shoulder, no solution
            if (!InRandomRestart)
                cout << "Shoulder reaching ";
            return false;
        }
        if (MinManIndex == 0)
            CopyPuzzle.MoveUp();
        else if (MinManIndex == 1)
            CopyPuzzle.MoveDown();
        else if (MinManIndex == 2)
            CopyPuzzle.MoveLeft();
        else if (MinManIndex == 3)
            CopyPuzzle.MoveRight();

        CopyPuzzle.SetSuccessorsManhattan();
        CopyPuzzle.Manhattan();

        if (CopyPuzzle.ManhattanDis == 0) {
            return true;
        }
    }
    if (!InRandomRestart)
        cout << "Max steps exceeded ";
    return false;
}

bool FirstChoice(_8Puzzles _8P) {
    _8Puzzles CopyPuzzle = _8P;
    int MinManhatton = 9999, MinManIndex;

    while (cost < MaxSteps) {
        MinManhatton = 9999;
        MinManIndex = -1;
        cost += 1;
        for (int i = 0; i < 4; i++) {
            if (CopyPuzzle.SuccessorsManhattan[i] < MinManhatton && CopyPuzzle.SuccessorsManhattan[i] < CopyPuzzle.ManhattanDis) {
                MinManhatton = CopyPuzzle.SuccessorsManhattan[i];
                MinManIndex = i;
            }
        }
        if (MinManIndex == -1) { // Can't find a smaller successor, reach Shoulder, no solution
            if (!InRandomRestart)
                cout << "Shoulder reaching";
            return false;
        }
        if (MinManIndex == 0)
            CopyPuzzle.MoveUp();
        else if (MinManIndex == 1)
            CopyPuzzle.MoveDown();
        else if (MinManIndex == 2)
            CopyPuzzle.MoveLeft();
        else if (MinManIndex == 3)
            CopyPuzzle.MoveRight();

        CopyPuzzle.SetSuccessorsManhattan();
        CopyPuzzle.Manhattan();

        if (CopyPuzzle.ManhattanDis == 0)
            return true;
    }
    if (!InRandomRestart)
        cout << "Max steps exceeded ";
    return false;
}

bool SimulatedAnnealing(_8Puzzles _8P) {
    double temperature = 5;
    _8Puzzles CopyPuzzle = _8P;
    while (temperature > 0.00001) {
        cost += 1;
        bool better = false;
        int ran; // randomly choose a successor
        do {
            ran = random(4);
        } while (CopyPuzzle.SuccessorsManhattan[ran] == 10000); // make sure the successor is a valid one
        int nextState = CopyPuzzle.SuccessorsManhattan[ran];
        int curState = CopyPuzzle.ManhattanDis;
        // randomly decide whether use this position or not
        int E = nextState - curState;
        if (E < 0) {
            better = true;
        }
        else if (exp((-1)*E / temperature) >((double)(rand() % 1000) / 1000)) {
            better = true;
        }
        if (better) {
            if (ran == 0)
                CopyPuzzle.MoveUp();
            else if (ran == 1)
                CopyPuzzle.MoveDown();
            else if (ran == 2)
                CopyPuzzle.MoveLeft();
            else if (ran == 3)
                CopyPuzzle.MoveRight();
            CopyPuzzle.SetSuccessorsManhattan();
            CopyPuzzle.Manhattan();
            if (CopyPuzzle.ManhattanDis == 0) // not a result state, keep on climbing
                return true;
        }
        temperature *= 0.999;
    }
    return false;
}

bool RandomRestart(_8Puzzles _8P) {
    InRandomRestart = true;
    cost = 0;
    bool Found = SteepestAscent(Generator());
    while (!Found) {
        _8P = Generator();
        Found = SteepestAscent(_8P);
    }
    InRandomRestart = false;
    return true;
}

int main() {
    int TempTimes, TestTimes,SuccessCount,TotalCost;

    TempTimes = TestTimes = 1000;
    SuccessCount = 0;
    TotalCost = 0;
    while (TestTimes--) {
        cost = 0;
        cout << "Trail No." << TempTimes - TestTimes << ": ";
        if (SteepestAscent(Generator())) {
            cout << "Success! cost = " << cost << endl;
            SuccessCount++;
            TotalCost += cost;
        }
        else {
            cout << "Failure!" << endl;
        }
    }
    cout << "SteepestAscent statistics : " << endl;
    cout << "Success Rate = " << SuccessCount << "/1000" << endl;
    cout << "Average Cost = " << TotalCost / SuccessCount << endl << endl;

    TempTimes = TestTimes = 1000;
    SuccessCount = 0;
    TotalCost = 0;
    while (TestTimes--) {
        cost = 0;
        cout << "Trail No." << TempTimes - TestTimes << ": ";
        if (SimulatedAnnealing(Generator())) {
            cout << "Success! cost = " << cost << endl;
            SuccessCount++;
            TotalCost += cost;
        }
        else {
            cout << "Failure!" << endl;
        }
    }
    cout << "SimulatedAnnealing statistics : " << endl;
    cout << "Success Rate = " << SuccessCount << "/1000" << endl;
    cout << "Average Cost = " << TotalCost / SuccessCount << endl << endl;

    TempTimes = TestTimes = 100;
    SuccessCount = 0;
    TotalCost = 0;
    while (TestTimes--) {
        cout << "Trail No." << TempTimes - TestTimes << ": ";
        RandomRestart(Generator());
        cout << "Success! cost = " << cost << endl;
        SuccessCount++;
        TotalCost += cost;
    }
    cout << "Random Restart statistics : " << endl;
    cout << "Success Rate = " << SuccessCount << "/100" << endl;
    cout << "Average Cost = " << TotalCost / SuccessCount << endl << endl;


    return 0;
}

8Queens Problem

#include<iostream>
#include<vector>
#include<cstdlib>
#include<utility>

#define random(x) (rand()%x)
#define MaxStepsForClimbing 100
int cost = 0;
using namespace std;
int CalculateConflicts(vector<vector<int>> ChessBoard);

// A state of the 8-Queens problem
// Chess board representation of this state
// Number of conflicts of this state
// Number of conflicts there will be if a queen is moved to another row and the same column
struct _8Queen {
    vector < vector<int>> ChessBoard;
    int Conflicts;
    vector<vector<int>> ConflictsBoard;
    _8Queen() {
        ChessBoard.resize(8);
        for (int i = 0; i < 8; i++)
            ChessBoard[i].resize(8);
        ConflictsBoard.resize(8);
        for (int i = 0; i < 8; i++)
            ConflictsBoard[i].resize(8);
        Conflicts = 0;
    }
    
    // look for the least conflicts in the succeesors, so as to move to that state
    pair<int, int> FindLeastConflicts() {
        pair<int, int> ResultPosition;
        int Least = 29; // most conflicts in a 8queens state is 28;
        for (int row = 0; row < 8; row++) {
            for (int col = 0; col < 8; col++) {
                if (ConflictsBoard[row][col] < Least) {
                    Least = ConflictsBoard[row][col];
                    ResultPosition = make_pair(row, col);
                }
            }
        }
        return ResultPosition;
    }

    void ConfilctBoardConstruction() { // construct ConflictBorad
        // find a queen, move it to all rows of the same col to form 7 other states
        // for each state, calculate number of conflict, and set the values in ConflictsBoard
        for (int row = 0; row < 8; row++) {
            for (int col = 0; col < 8; col++) {
                if (ChessBoard[row][col] == 1) { // a queen is found
                    ConflictsBoard[row][col] = Conflicts;
                    vector<vector<int>> NewState = ChessBoard; // copy the chessboard of this state
                    NewState[row][col] = 0; // remove the queen and move her
                    for (int OtherRow = 0; OtherRow < 8; OtherRow++) { // move the queen to the other rows of the same column
                        if (OtherRow != row) { // not the same row
                            NewState[OtherRow][col] = 1; // place the queen
                            ConflictsBoard[OtherRow][col] = CalculateConflicts(NewState); // calculate the conflict of this state, and set it in ConflictsBoard
                        }
                        NewState[OtherRow][col] = 0; // remove the queen after calculation and ready to move her to another row
                    }
                }
            }
        }
    }

    bool CheckSuccess() { // wheather or not it has found a result
        return CalculateConflicts(ChessBoard) == 0;
    }
};



// randomly generates an 8-Queens problem where queens are placed in different column
_8Queen _8QueensGeneration() {
    _8Queen Result;
    for (int i = 0; i < 8; i++) {   // place an queen in a random row from col 0 to 7
        int ran = random(8);
        Result.ChessBoard[ran][i] = 1;
    }
    Result.Conflicts = CalculateConflicts(Result.ChessBoard); // calculate and set the conflicts of the problem
    Result.ConfilctBoardConstruction();


    return Result;
}

int CalculateConflicts(vector<vector<int>> ChessBoard) {
    int Result = 0; // Calculated number of conflicts

    for (int row = 0; row < 8; row++) {
        for (int col = 0; col < 8; col++) {
            if (ChessBoard[row][col] == 1) {
                for (int i = col + 1; i < 8; i++) { // Sum of queens on the right
                    if (ChessBoard[row][i] == 1)
                        Result++;
                }

                for (int i = row + 1; i < 8; i++) { // Sum of queens on below
                    if (ChessBoard[i][col] == 1)
                        Result++;
                }

                int temprow = row, tempcol = col;
                while (temprow + 1 < 8 && tempcol + 1 < 8) {
                    temprow += 1;
                    tempcol += 1;
                    if (ChessBoard[temprow][tempcol] == 1)
                        Result++;
                }

                temprow = row, tempcol = col;
                while (temprow + 1 < 8 && tempcol - 1 >= 0) {
                    temprow += 1;
                    tempcol -= 1;
                    if (ChessBoard[temprow][tempcol] == 1)
                        Result++;
                }

            }
        }
    }
    return Result;
}

bool InRandomRestart = false;
bool restart = false;
// select a position, whose state's conflict is the least of all
// move the queen that's in that column, to the selected row.
bool HillClimbing(_8Queen _8Q)  {
    pair<int, int> LeastPosition; // row and column of the least-conflict position;
    _8Queen QueenMove = _8Q; // the succesor state, the best neighbor
    restart = false;
    int chance = MaxStepsForClimbing;
    chance = InRandomRestart ? cost + MaxStepsForClimbing : MaxStepsForClimbing;
    while (cost < chance) {
        cost += 1;  
        LeastPosition = QueenMove.FindLeastConflicts();

        for (int row = 0; row < 8; row++) // find and remove the queen
            if (QueenMove.ChessBoard[row][LeastPosition.second] == 1)
                QueenMove.ChessBoard[row][LeastPosition.second] = 0;

        QueenMove.ChessBoard[LeastPosition.first][LeastPosition.second] = 1; // place the queen in the least confilcts position
        QueenMove.Conflicts = CalculateConflicts(QueenMove.ChessBoard);  // calculate new conflicts for the new state
        QueenMove.ConfilctBoardConstruction(); // construct the new conflict board for the new state
        if (QueenMove.CheckSuccess() == true) // not a result state, keep on climbing
            return true;
    }
    return false;
}

// randomly select a position, whose state's conflict would be smaller than the current one
// move the queen that's in that column, to the selected row.
int FirstChoice(_8Queen _8Q) {
    pair<int, int> BetterPosition; // row and column of a randomly selected better-conflict position;
    _8Queen QueenMove = _8Q; // the succesor state, the best neighbor
    int RandomRow, RandomCol;


    while (cost < MaxStepsForClimbing) {
        cost += 1;

        int generateCount = 0;
        bool betterFound = true;
        do { // keep generating new random value until the condition is fufiled.
            RandomRow = random(8);
            RandomCol = random(8);
            generateCount++;
            
            if (generateCount > 100) {
                betterFound = false;
                break;
            }
        } while (QueenMove.ConflictsBoard[RandomRow][RandomCol] >= QueenMove.Conflicts);

        if (betterFound == false)
            continue;
        
        BetterPosition = make_pair(RandomRow, RandomCol);

        for (int row = 0; row < 8; row++) // find and remove the queen
            if (QueenMove.ChessBoard[row][BetterPosition.second] == 1) {
                QueenMove.ChessBoard[row][BetterPosition.second] = 0;
                break;
            }

        QueenMove.ChessBoard[BetterPosition.first][BetterPosition.second] = 1; // place the queen in the least confilcts position
        QueenMove.Conflicts = CalculateConflicts(QueenMove.ChessBoard);  // calculate new conflicts for the new state
        QueenMove.ConfilctBoardConstruction(); // construct the new conflict board for the new state
        if (QueenMove.CheckSuccess() == true) // not a result state, keep on climbing
            break;
    }
    return cost;
}

bool RandomRestart(_8Queen _8Q) {
    InRandomRestart = true;
    cost = 0;
    bool Found = HillClimbing(_8Q);
    while (!Found) { // if 
        _8Q = _8QueensGeneration();
        Found = HillClimbing(_8Q);
    }
    InRandomRestart = false;
    return true;
}

bool SimulatedAnnealing(_8Queen _8Q) {
    double temperature = 5;
    _8Queen QueenMove = _8Q;
    while (temperature > 0.00001) {
        cost += 1;
        int RandomRow = random(8);
        int RandomCol = random(8); // randomly pick a position
        bool better = false;
        int nextState = QueenMove.ConflictsBoard[RandomRow][RandomCol];
        int curState = QueenMove.Conflicts;

        // randomly decide whether use this position or not
        int E = nextState - curState;
        if (E < 0) {
            better = true;
        }
        else if (exp((-1)*E / temperature) >((double)(rand() % 1000) / 1000)) {
            better = true;
        }

        if (better) {
            for (int row = 0; row < 8; row++) // find and remove the queen
                if (QueenMove.ChessBoard[row][RandomCol] == 1) {
                    QueenMove.ChessBoard[row][RandomCol] = 0;
                    break;
                }

            QueenMove.ChessBoard[RandomRow][RandomCol] = 1; // place the queen in the least confilcts position
            QueenMove.Conflicts = CalculateConflicts(QueenMove.ChessBoard);  // calculate new conflicts for the new state
            QueenMove.ConfilctBoardConstruction(); // construct the new conflict board for the new state
            if (QueenMove.CheckSuccess() == true) // not a result state, keep on climbing
                return true;
            temperature *= 0.99;
        }
    }
    return false;
}



int main() {
    int times = 1000;
    int SuccessCount = 0;
    int TotalCost = 0;

    // hillclimbing (steepest-ascent)
    /*while (times--) {
        cost = 0;
        cout << "Trail No." << 1000 - times << ": ";
        HillClimbing(_8QueensGeneration());
        if (cost >= MaxStepsForClimbing)
            cout << "Searched Failed." << endl;
        else {
            cout << "Success! cost = " << cost << endl;
            SuccessCount++;
            TotalCost += cost;
        }
    }
    cout << "HillClimbing(Steepest-Ascent) statistics : " << endl;
    cout << "Success Rate = " << SuccessCount << "/1000"  << endl;
    cout << "Average Cost = " << TotalCost / SuccessCount << endl << endl;

    times = 1000;
    SuccessCount = 0;
    TotalCost = 0;
    while (times--) {
        cost = 0;
        cout << "Trail No." << 1000 - times << ": ";
        cost = FirstChoice(_8QueensGeneration());
        if (cost >= MaxStepsForClimbing)
            cout << "Searched Failed." << endl;
        else {
            cout << "Success! cost = " << cost << endl;
            SuccessCount++;
            TotalCost += cost;
        }
    }
    cout << "HillClimbing(First Choice) statistics : " << endl;
    cout << "Success Rate = " << SuccessCount << "/1000" << endl;
    cout << "Average Cost = " << TotalCost / SuccessCount << endl << endl;*/

    times = 100;
    SuccessCount = 0;
    TotalCost = 0;
    while (times--) {
        cout << "Trail No." << 100 - times << ": ";
        RandomRestart(_8QueensGeneration());
        cout << "Success! cost = " << cost << endl;
        SuccessCount++;
        TotalCost += cost;
    }
    cout << "HillClimbing(Random Restart) statistics : " << endl;
    cout << "Success Rate = " << SuccessCount << "/100" << endl;
    cout << "Average Cost = " << TotalCost / SuccessCount << endl << endl;

    times = 100;
    SuccessCount = 0;
    TotalCost = 0;
    while (times--) {
        cost = 0;
        cout << "Trail No." << 100 - times << ": ";
        if (SimulatedAnnealing(_8QueensGeneration())) {
            cout << "Success! cost = " << cost << endl;
            SuccessCount++;
            TotalCost += cost;
        }
        else
            cout << "Searched Failed." << endl;
    }
    cout << "HillClimbing(Simulated Annealing) statistics : " << endl;
    cout << "Success Rate = " << SuccessCount << "/100" << endl;
    cout << "Average Cost = " << TotalCost / SuccessCount << endl << endl;

    return 0;
}