Eight Queen Problem Solution!

This is a discussion on Eight Queen Problem Solution! within the C# Programming forums, part of the General Programming Boards category; Hello, I think this program is running fine for classical 8 Queen problem. But i want others to review my ...

  1. #1
    Registered User
    Join Date
    Jan 2008
    Posts
    225

    Eight Queen Problem Solution!

    Hello,
    I think this program is running fine for classical 8 Queen problem. But i want others to review my code and point out mistakes. Please suggest my mistakes and optimisations that could be done to improve its performance.

    Code:
    using System;
    
    namespace EightQueen
    {
        public enum SIZE
        {
            size = 8
        }
        public class EightQueen
        {
            public static int count = 0;
            public static bool isValidMove(int[,] boardArr, int row, int col)
            {
                for (int i = 0; i < SIZE.size.GetHashCode(); i++)
                    if (boardArr[row,i] == 1)
                        return false;
    
                for (int i = 0; i < SIZE.size.GetHashCode(); i++)
                    if (boardArr[i,col] == 1)
                        return false;
                int tempCol = col + 1, tempRow = row ;
    
                for (int i = row + 1; i < SIZE.size.GetHashCode(); i++)
                {
                    if (tempCol < SIZE.size.GetHashCode())
                    {
                        if (boardArr[i,tempCol] == 1)
                            return false;
                        else
                            tempCol++;
                    }
                    else
                        break;
                }
                tempCol = col - 1;
                for (int i = row - 1; i >= 0; i--)
                {
                    if (tempCol >= 0)
                    {
                        if (boardArr[i,tempCol] == 1)
                            return false;
                        else
                            tempCol --;
                    }
                    else
                        break;
                }
                tempCol = col - 1;
                for (int i = row + 1; i < SIZE.size.GetHashCode(); i++)
                {
                    if (tempCol >= 0)
                    {
                        if (boardArr[i, tempCol] == 1)
                            return false;
                        else
                            tempCol--;
                    }
                    else
                        break;
                }
                tempCol = col + 1;
                for (int i = row - 1; i >= 0; i--)
                {
                    if (tempCol < SIZE.size.GetHashCode())
                    {
                        if (boardArr[i, tempCol] == 1)
                            return false;
                        else
                            tempCol++;
                    }
                    else
                        break;
                }
    
                return true;
            }
    
            public static void ShouldPrintBoard(int[,] boardArr)
            {
                int count = 0;
                for (int i = 0; i < SIZE.size.GetHashCode(); i++)
                    for(int j = 0; j < SIZE.size.GetHashCode() ;j++)
                        if (boardArr[i,j] == 1)
                            count++;
                if (count >= 8)
                    PrintBoard(boardArr);
            }
            public static void PrintBoard(int[,] boardArray)
            {
                for (int i = 0; i < SIZE.size.GetHashCode(); i++)
                {
                    for (int j = 0; j < SIZE.size.GetHashCode(); j++)
                        Console.Write("{0} ", boardArray[i, j]);
                    Console.WriteLine();
                }
                count++;
                Console.WriteLine();
                //Console.ReadKey();
            }
            public static void PermuteBoard(int[,] boardArr, int row, int col)
            {
                for (int i = row; i < SIZE.size.GetHashCode(); i++)
                {
                    for (int j = 0; j < SIZE.size.GetHashCode(); j++)
                    {
                        if (isValidMove(boardArr, i, j))
                        {
                            boardArr[i, j] = 1;
                            ShouldPrintBoard(boardArr);
                            PermuteBoard(boardArr, i + 1, j + 1);
                            boardArr[i, j] = 0;
                        }
    
                    }
                }
            }
            static void Main(string[] args)
            {
                int [,]boardArr = new int[SIZE.size.GetHashCode(),SIZE.size.GetHashCode()];
                for(int i = 0 ; i < SIZE.size.GetHashCode() ; i++)
                    for(int j = 0 ; j < SIZE.size.GetHashCode() ; j++)
                        boardArr[i,j] = 0;
                PermuteBoard(boardArr, 0, 0);
    
                Console.WriteLine("Total Solutions {0}", count);
                Console.ReadKey();
            }
        }
    }

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Whenever placing a queen on the board, I would mark the squares it affects. (Since any square can and will be affected by many queens you could add one to affected squares and when removing the queen subtract one.) This way testing whether a square is attacked becomes very easy: you just see whether the value is one.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    Registered User
    Join Date
    Jan 2008
    Posts
    225
    Ok anon!
    agreed but still "marking the squares attacked" would still mean the same, I mean i need to again repeat those four loops for "finding the squares attacked and incrementing its value by 1".? So how will that optimise my code?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Optimisations required for 8 queen problem.
    By chottachatri in forum C Programming
    Replies: 2
    Last Post: 06-28-2009, 10:19 PM
  2. Simple problem - my solution correct?
    By spadez in forum C Programming
    Replies: 15
    Last Post: 04-18-2009, 11:08 PM
  3. annoying problem, solution should be simple...
    By Captain Penguin in forum C++ Programming
    Replies: 0
    Last Post: 10-18-2002, 04:41 PM
  4. Replies: 4
    Last Post: 10-17-2002, 10:09 PM
  5. beginner problem
    By The_Nymph in forum C Programming
    Replies: 4
    Last Post: 03-05-2002, 04:46 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21