Solving N-Queen Problem by DFS and BFS and Show Goal On Panel Control

• Download N-Queen by BFS with show detail Steps - 66.5 KB
• Download N-Queen by DFS - 100.1 KB

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:

1. If current state is goal state return Board
2. 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.
3. 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

• N-Queen problem definition
• DFS on Wikipedia