Thread: Optimisations required for 8 queen problem.

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

    Optimisations required for 8 queen problem.

    Hello,
    i posted this c# version of solution in C# board also but since c# and c are near about similar only i thought of posting it here also. Please review my logic and suggest and optimisations required in it. Also if c# version is not allowed please let me know, i will convert it into C and post it here again. I posted here since most members are active here. On c# board hardly anybody can be seen :d. Also i read on google that backtracking can reduce computations and all such things but i dont understand backtracking. Also tell me if i am using any such backtracking in my solution or not. These terms confuse me more than anything else, also i would appreciate if anybody explains me term what is heuristic approach, because i would attempt for 8 Knights problem. Thanks in advance!

    Code:
    using System;
    
    namespace EightQueen
    {
        public enum SIZE
        {
            size = 8
        }
        public class EightQueen
        {
            public static int count = 0;
            public static int FunctionCalls = 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)
            {
                FunctionCalls++;
                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.WriteLine("Function Calls {0}", FunctionCalls);
                Console.ReadKey();
            }
        }
    }

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    We typically don't go for the whole "I found this code, help me make it better!" routine.


    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. code required for the problem..
    By varun_mukthi in forum C Programming
    Replies: 4
    Last Post: 01-08-2007, 01:27 PM
  2. NAQ: Everything you never wanted to know about CPP
    By evildave in forum C Programming
    Replies: 21
    Last Post: 12-12-2005, 10:56 AM
  3. Bin packing problem....
    By 81N4RY_DR460N in forum C++ Programming
    Replies: 0
    Last Post: 08-01-2005, 05:20 AM
  4. Replies: 5
    Last Post: 12-03-2003, 05:47 PM
  5. problem with output
    By Garfield in forum C Programming
    Replies: 2
    Last Post: 11-18-2001, 08:34 PM