Introduction
The N–Queens problem is a classic problem that is often used in discussions of various search strategies.
The problem is often defined in terms of a standard 8–by–8 chess board, although it can be defined for any N–by–N board and is solvable for N ³ 4.
This article tries to solve N-Queen problem by Depth First Search (DFS) algorithm and show result visually in chess board.
Background
As is the case with all such problems, the 8–queens problem is posed as an example to be used in discussing search methods, not as a
problem that has value in and of itself. Honestly, one does not even have eight chess queens, so why worry about how to place them?
In general, the problem is to place the queens on the board so that no two queens can attack each other. The method for solving the problem depends on the knowledge of the rules
for moving a queen in the game of chess. Specifically, a queen can move in any straight line, either along a row, along a column, or a diagonal. In an
N–by–N board, each queen will be located on exactly one row, one column, and two diagonals.
The requirement that no two queens be placed in the same row restricts the number of queens that can be placed on an N–by–N board to N. Thus, a standard 8–by–8 chess board can take
at most eight queens. The problem is to find an arrangement that allows placement of N queens.
DFS or Depth First Search is a search algorithm that search from tree root to sub tree in search space, recursion from sub tree when reach
to non promise state or stop search when find goal.
DFS (input state)
{
1- Check goal state
2- Check problem conditions
3-build new state and call recursive function with new states and get result
}
Using the code
First for manage chess board, create a Board class:
Properties:
N property is for queens count that trying to place. Each row can place one queen, then for saving queen places we must know their column number in each row. board
vector have N cell for saving queen places in Board ,after placing each queen we must save queen count that placed in Board that cnt property is for that.
Board
class properties:
public int N;
int[] board;
public int cnt;
Board
Class Constructor:
This
method for initializing Board class properties:
public Board(int n)
{
N = n;
board = new int[N];
for (int i = 0; i < N; i++)
board[i] = 0;
cnt = 0;
}
bool isSafe(int Clm):
Before
place next queen, we must check attack restriction:
Two queens
can attack each other when on same column or on same diagonal (queen moves in
chess game). The following method check if new queen places on column number Clm attack previous queens (true) or not (false).
public bool isSafe(int Clm)
{
for (int i = 0; i < cnt; i++)
{
if ((board[i] == Clm) || Math.Abs(Clm - board[i]) == (cnt - i))
return false;
}
return true;
}
void Place(int Clm)
method:
Place next queen in column number Clm.
public void Place(int Clm)
{
if (Clm >= 0 && Clm < N)
{
board[cnt] = Clm;
cnt++;
}
else
{
MessageBox.Show("Bad Column");
}
}
bool IsGoal() method:
If queens
that placed on chess is equal to N that is goal state.
public bool IsGoal()
{
if (cnt == N)
{
return true;
}
else
return false;
}
void UnPlace() method:
Board
class for control the recursion and get last queen from board vector call this
method that simply do that by less one unit from cnt property :
public void UnPlace()
{
if (cnt > 0)
{
cnt--;
}
}
void ShowBoard(Panel pnl)
method:
This
method is that visually show the board on input Panel control:
N–by–N
board cell width and height calculated by split width and height in N segment (divide
width on N for length and divide height on N for height). Each cell is a
picturebox control that have BackColor white or Black. After building board,
for queen places in board loading queen picture and set necessary picturebox properties:
public void ShowBoard(Panel pnl)
{
pnl.Controls.Clear();
PictureBox[,] chess = new PictureBox[N, N];
int w = 0, h = 0;
w = pnl.Width;
h = pnl.Height;
int xs = (int) ((double)w / (double)N);
int ys = (int)((double)h / (double)N);
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
{
chess[i, j] = new PictureBox();
chess[i, j].BorderStyle = BorderStyle.FixedSingle;
chess[i, j].Parent = pnl;
chess[i, j].Location = new Point(j * xs + 1, i * ys + 1);
chess[i, j].Size = new Size(xs, ys);
if ((i + j) % 2 == 0)
chess[i, j].BackColor = Color.White;
else
chess[i, j].BackColor = Color.Black;
}
for (int i = 0; i < cnt; i++)
{
chess[i, board[i]].Load(Application.StartupPath+"\\queen.jpg");
chess[i, board[i]].SizeMode = PictureBoxSizeMode.StretchImage;
}
}
Important form methods:
void btnSolve_Click(object sender, EventArgs e) method:
This
method has front end event for get input and start build the initial board then
call to recursive method DFS for solving problem. For time duration using from
System.Diagnostics.Stopwatch class:
private void btnSolve_Click(object sender, EventArgs e)
{
try
{
pnlChess.Controls.Clear();
if (txtN.Text != "")
{
int N = int.Parse(txtN.Text);
Board board = new Board(N);
System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
lblTime.Text = "";
sw.Start();
Board res = DFS(board);
sw.Stop();
lblTime.Text = sw.ElapsedMilliseconds.ToString()+" MilliSecond";
if ( res!= null)
{
res.ShowBoard(pnlChess);
}
else
{
MessageBox.Show("no Result");
}
}
}
catch
{
}
}
Board DFS(Board board) method :
This
method is the manager method for solving N-Queen problem that impement DFS
algorithm for finding goal state. Call this
method with empty board (places Queen count=0).
The DFS
method body steps:
- If
current state is goal state return Board
- For
column number zero(0) to N-1 check if that's is safe place for next queen ,
place next queen on that column and call DFS method for new state.
- If
return Board from previous call is not null that means that goal state is found
and current function also return that otherwise unplace last queen and check
other columns in this row.
Board DFS(Board board)
{
if (board.IsGoal() == true)
{
return board;
}
else
{
for (int i = 0; i < board.N; i++)
{
if (board.isSafe(i))
{
board.Place(i);
Board res= DFS(board);
if (res != null)
return res;
board.UnPlace();
}
}
}
return null;
}
In download section N-Queen problem both , with show final goal state at once by DFS or show using BFS steps by using timer and queue class exist.
Points of Interest
Build a game for placing N queen on board in specific time.
History
This code implemented in 2011.
References
