1 reply to this topic

[Codebug]

I'm working on an old programming quiz that I was never able to figure out and I need a little help. Basically, I need to write a program that will read in a file containing a series of periods and Q's. For example, the file might contain . . Q . . . . Q etc. After the file is read in, I need to print a square chessboard and then figure out whether or not that Queen arrangement is a solution to the N Queens problem. For this quiz, I could assume that the all candidates are squares ranging in size from 1x1 to 10x10.

If the file to be read in contains the following:

. . . Q . . . . . . . . . . Q . . . Q . . . . . . . . . . . . Q . Q . . . . . . . . . . Q . . . Q . . . . . . . . . . . . Q . . 
. Q Q .
Q

The program will output:

. . . Q . . . .
. . . . . . Q .
. . Q . . . . .
. . . . . . . Q
. Q . . . . . .
. . . . Q . . .
Q . . . . . . .
. . . . . Q . .
is a solution


. Q
Q .
is not a solution


Q is a solution

I have figured out how to read in the file and print the square board with the Queens on it. Basically what I did was notice that the length and width of the board was the same as the number of Queens in the String. Now, I'm not sure how to implement a test to check whether or not the candidate is a solution. At the time we did this quiz, we had NOT been introduced to multidimensional arrays so I would like to solve this problem without using them. I'm thinking that there is a relationship between the distance between queens, the number of queens, and the length of the String that will help determine whether the candidate is a solution or not. Here is the code that I have so far. Keep in mind that this is not complete and will not scan multiple lines yet:

import java.util.Scanner;
import java.io.File;

class NQueens
{
    private Scanner scan;
    private int count;
    private String s;
    
    public NQueens( String file )
    {
        
        count = 0;
        scan = null;
                try
                {
                        scan = new Scanner( new File( file ) );
                }

                catch( java.io.FileNotFoundException e )
                {
                        System.out.println( "File not found." );
                        System.exit( -1 );
                }
                s = scan.nextLine();

    }
    
    public void countQueens()// this method counts the Queens in the String to determine the dimensions of the board
    {
        int i = 0;
        while ( i < s.length() )
        {
            if ( s.charAt( i ) == 'Q' )
            {
                count++;
            }
            i++;
        }
    }
    
    public void printBoard()
    {
        boolean solution = false;
        Scanner sc = new Scanner( s );
        for ( int i = 0; i < count; i++ )
        {
            for ( int j = 0; j < count; j++ )
            {
                System.out.print( sc.next() + " " );
            }
            System.out.println();
        }
        
       
    }
        
        
}

Thanks for the help.

[bobdark]

array of length as number of queens on the board (that is if you can assume that there are indeed N queens when N is the length of the square, otherwise add a check to make sure of it).
Element of index i in array indicates the position of queen i, i.e. (y,x), y is the row number, x is the colum number. What you have is the location of each queen. Now for each queen, search the array for a queen that "sees" the "current" queen.