In this blog, I will be introducing you to the first heuristic algorithm Simple Hill Climbing.
It is relatively simple to implement, making it a popular first choice. Although more advanced
algorithms may give better results, in some situations hill climbing works well.
The algorithm is as follows :
Step 1: Evaluate the initial state. It is also a goal state, then return it and quit.
Otherwise continue with the initial state as the current state.
Step 2: Loop until a solution is found or until there are no new operators left to be
applied in the current state :
(a) Select an operator that has not yet been applied to the current state and
apply it to produce a new state.
(b) Evaluate the new state.
(i) If it is a goal state, then return it and quit .
(ii) If it is not a goal state, but it is better than the
current state, then make it the current state.
(iii) If it is not better than the current state, then continue
in the loop.
Here "evaluate" denotes the heuristic function. It measures the heuristic value of the
node.
This algorithm does not evaluate all the successive nodes at once. The first node that
has the higher heuristic value than the current node is set as the current node.
This picture will clear your doubts.
But, there is a big disadvantage of this algorithm. It cannot traverse back to its
parent and gets stuck at an intermediate node. This intermediate node is known as Local
Maximum.
There are three types of situation which prevents the algorithm to reach the Global
Maximum :
Local Maximum : A local maximum is a state that is better than all its neighbours but
is not better than some other states farther away.
Plateau: A Plateau is a flat area of the search space in which a whole set of
neighbouring states have the same value.
Ridge : A ridge is a special kind of local maximum. It is an area of the search space
that is higher than surrounding areas and that itself has a slope.
To get a clear understanding, I have implemented Simple Hill Climbing algorithm
in the Four Queens Problem. The Four Queens Problem is a problem where four
queens are to be placed in such a way that no queens attack each other in
the 4 x 4 chessboard.
Here is the C# code :
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Windows.UI;
using Windows.UI.Xaml.Controls;
using Windows.UI.Xaml.Media;
using Windows.UI.Xaml.Media.Imaging;
using Windows.UI.Xaml.Shapes;
namespace Win81AppSimpleHillClimbing4Queens
{
public class FourQueensProblem
{
private int NumberOfQueensPlaced;
private bool IsAttacked, IsPlaced;
private Rectangle[,] Queens, Rects;
private string Result;
public FourQueensProblem(Rectangle[,] Queens, Rectangle[,] Rects)
{
this.Queens = Queens;
this.Rects = Rects;
}
private void SetIndicatorYellow(int i, int j)
{
Rects[i, j].Stroke = new SolidColorBrush(Color.FromArgb(255, 255, 255, 0));
}
private void SetIndicatorGreen(int i, int j)
{
Rects[i, j].Stroke = new SolidColorBrush(Color.FromArgb(255, 0, 255, 0));
}
private void SetIndicatorRed(int i, int j)
{
Rects[i, j].Stroke = new SolidColorBrush(Color.FromArgb(255, 255, 0, 0));
}
private void SetIndicatorNormal(int i, int j)
{
Rects[i, j].Stroke = new SolidColorBrush(Color.FromArgb(255, 9, 93, 240));
}
private bool CheckUpperLeftDiagonalCells(int i, int j)
{
bool culdc = false;
int t;
if (i == j)
t = i;
else if (i < j)
t = i;
else
t = j;
for (int x = 0; x < t; x++)
{
--i;
--j;
if (IsQueenPresent(i, j) == true)
{
culdc = true;
break;
}
else
culdc = false;
}
return culdc;
}
private bool CheckUpperRightDiagonalCells(int i, int j)
{
bool curdc = false;
for (int x = 0; x < 3; x++)
{
--i;
++j;
if (i >= 0 && j < 4)
{
if (IsQueenPresent(i, j) == true)
{
curdc = true;
break;
}
else
curdc = false;
}
else
{
break;
}
}
return curdc;
}
private bool CheckUpperTopCells(int i, int j)
{
bool cutc = false;
int t = i;
for (int x = 0; x < t; x++)
{
--i;
if (IsQueenPresent(i, j) == true)
{
cutc = true;
break;
}
else
cutc = false;
}
return cutc;
}
//Simple Hill Climbing
public async Task Solve(int a, int b)
{
NumberOfQueensPlaced = 0;
IsPlaced = true;
for (int i = 0; i < 4; i++)
{
if(IsPlaced == true)
{
for (int j = 0; j < 4; j++)
{
if (i == a && j < b)
continue;
else
{
SetIndicatorYellow(i, j);
await Task.Delay(TimeSpan.FromSeconds(1));
if (IsQueenAttacked(i, j) == false) //Evaluate
{
SetIndicatorGreen(i, j);
SetQueen(i, j); //set as current state
await Task.Delay(TimeSpan.FromSeconds(1));
IsPlaced = true;
++NumberOfQueensPlaced;
break;
}
else
{
SetIndicatorRed(i, j);
await Task.Delay(TimeSpan.FromSeconds(1));
SetIndicatorNormal(i, j);
IsPlaced = false;
}
}
}
}
else
{
break;
}
}
if (NumberOfQueensPlaced == 4)
Result = "Success";
else
Result = "Failure";
}
public string GetResult()
{
return Result;
}
//heuristic function
private bool IsQueenAttacked(int i, int j)
{
IsAttacked = false;
if (i == 0)
IsAttacked = false;
else if (CheckUpperLeftDiagonalCells(i, j) == true)
IsAttacked = true;
else if (CheckUpperTopCells(i, j) == true)
IsAttacked = true;
else if(CheckUpperRightDiagonalCells(i, j) == true)
IsAttacked = true;
else
IsAttacked = false;
return IsAttacked;
}
private void SetQueen(int i, int j)
{
ImageBrush ib = new ImageBrush();
ib.ImageSource = new BitmapImage(new Uri("ms-appx:///Assets/chess_piece_queen2.png"));
Queens[i, j].Fill = ib;
Queens[i, j].IsTapEnabled = false;
}
private bool IsQueenPresent(int i, int j)
{
bool IsPresent = false;
if (Queens[i, j].IsTapEnabled == false)
IsPresent = true;
else
IsPresent = false;
return IsPresent;
}
public void ResetQueens()
{
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
SetIndicatorNormal(i, j);
Queens[i, j].Fill = null;
Queens[i, j].IsTapEnabled = true;
}
}
}
}
}
Here is the video of how it works :
That's the end of this blog. I hope you find it useful. Keep coding.
It is relatively simple to implement, making it a popular first choice. Although more advanced
algorithms may give better results, in some situations hill climbing works well.
The algorithm is as follows :
Step 1: Evaluate the initial state. It is also a goal state, then return it and quit.
Otherwise continue with the initial state as the current state.
Step 2: Loop until a solution is found or until there are no new operators left to be
applied in the current state :
(a) Select an operator that has not yet been applied to the current state and
apply it to produce a new state.
(b) Evaluate the new state.
(i) If it is a goal state, then return it and quit .
(ii) If it is not a goal state, but it is better than the
current state, then make it the current state.
(iii) If it is not better than the current state, then continue
in the loop.
Here "evaluate" denotes the heuristic function. It measures the heuristic value of the
node.
This algorithm does not evaluate all the successive nodes at once. The first node that
has the higher heuristic value than the current node is set as the current node.
This picture will clear your doubts.
But, there is a big disadvantage of this algorithm. It cannot traverse back to its
parent and gets stuck at an intermediate node. This intermediate node is known as Local
Maximum.
There are three types of situation which prevents the algorithm to reach the Global
Maximum :
Local Maximum : A local maximum is a state that is better than all its neighbours but
is not better than some other states farther away.
Plateau: A Plateau is a flat area of the search space in which a whole set of
neighbouring states have the same value.
Ridge : A ridge is a special kind of local maximum. It is an area of the search space
that is higher than surrounding areas and that itself has a slope.
To get a clear understanding, I have implemented Simple Hill Climbing algorithm
in the Four Queens Problem. The Four Queens Problem is a problem where four
queens are to be placed in such a way that no queens attack each other in
the 4 x 4 chessboard.
Here is the C# code :
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Windows.UI;
using Windows.UI.Xaml.Controls;
using Windows.UI.Xaml.Media;
using Windows.UI.Xaml.Media.Imaging;
using Windows.UI.Xaml.Shapes;
namespace Win81AppSimpleHillClimbing4Queens
{
public class FourQueensProblem
{
private int NumberOfQueensPlaced;
private bool IsAttacked, IsPlaced;
private Rectangle[,] Queens, Rects;
private string Result;
public FourQueensProblem(Rectangle[,] Queens, Rectangle[,] Rects)
{
this.Queens = Queens;
this.Rects = Rects;
}
private void SetIndicatorYellow(int i, int j)
{
Rects[i, j].Stroke = new SolidColorBrush(Color.FromArgb(255, 255, 255, 0));
}
private void SetIndicatorGreen(int i, int j)
{
Rects[i, j].Stroke = new SolidColorBrush(Color.FromArgb(255, 0, 255, 0));
}
private void SetIndicatorRed(int i, int j)
{
Rects[i, j].Stroke = new SolidColorBrush(Color.FromArgb(255, 255, 0, 0));
}
private void SetIndicatorNormal(int i, int j)
{
Rects[i, j].Stroke = new SolidColorBrush(Color.FromArgb(255, 9, 93, 240));
}
private bool CheckUpperLeftDiagonalCells(int i, int j)
{
bool culdc = false;
int t;
if (i == j)
t = i;
else if (i < j)
t = i;
else
t = j;
for (int x = 0; x < t; x++)
{
--i;
--j;
if (IsQueenPresent(i, j) == true)
{
culdc = true;
break;
}
else
culdc = false;
}
return culdc;
}
private bool CheckUpperRightDiagonalCells(int i, int j)
{
bool curdc = false;
for (int x = 0; x < 3; x++)
{
--i;
++j;
if (i >= 0 && j < 4)
{
if (IsQueenPresent(i, j) == true)
{
curdc = true;
break;
}
else
curdc = false;
}
else
{
break;
}
}
return curdc;
}
private bool CheckUpperTopCells(int i, int j)
{
bool cutc = false;
int t = i;
for (int x = 0; x < t; x++)
{
--i;
if (IsQueenPresent(i, j) == true)
{
cutc = true;
break;
}
else
cutc = false;
}
return cutc;
}
//Simple Hill Climbing
public async Task Solve(int a, int b)
{
NumberOfQueensPlaced = 0;
IsPlaced = true;
for (int i = 0; i < 4; i++)
{
if(IsPlaced == true)
{
for (int j = 0; j < 4; j++)
{
if (i == a && j < b)
continue;
else
{
SetIndicatorYellow(i, j);
await Task.Delay(TimeSpan.FromSeconds(1));
if (IsQueenAttacked(i, j) == false) //Evaluate
{
SetIndicatorGreen(i, j);
SetQueen(i, j); //set as current state
await Task.Delay(TimeSpan.FromSeconds(1));
IsPlaced = true;
++NumberOfQueensPlaced;
break;
}
else
{
SetIndicatorRed(i, j);
await Task.Delay(TimeSpan.FromSeconds(1));
SetIndicatorNormal(i, j);
IsPlaced = false;
}
}
}
}
else
{
break;
}
}
if (NumberOfQueensPlaced == 4)
Result = "Success";
else
Result = "Failure";
}
public string GetResult()
{
return Result;
}
//heuristic function
private bool IsQueenAttacked(int i, int j)
{
IsAttacked = false;
if (i == 0)
IsAttacked = false;
else if (CheckUpperLeftDiagonalCells(i, j) == true)
IsAttacked = true;
else if (CheckUpperTopCells(i, j) == true)
IsAttacked = true;
else if(CheckUpperRightDiagonalCells(i, j) == true)
IsAttacked = true;
else
IsAttacked = false;
return IsAttacked;
}
private void SetQueen(int i, int j)
{
ImageBrush ib = new ImageBrush();
ib.ImageSource = new BitmapImage(new Uri("ms-appx:///Assets/chess_piece_queen2.png"));
Queens[i, j].Fill = ib;
Queens[i, j].IsTapEnabled = false;
}
private bool IsQueenPresent(int i, int j)
{
bool IsPresent = false;
if (Queens[i, j].IsTapEnabled == false)
IsPresent = true;
else
IsPresent = false;
return IsPresent;
}
public void ResetQueens()
{
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
SetIndicatorNormal(i, j);
Queens[i, j].Fill = null;
Queens[i, j].IsTapEnabled = true;
}
}
}
}
}
Here is the video of how it works :
That's the end of this blog. I hope you find it useful. Keep coding.
