N-QUEENS RESEARCH ENVIRONMENT: AN INTERDISCIPLINARY APPROACH TO PROBLEM SOLVING

O. Aktunc and M.M. Tanik

Department of Electrical and Computer Engineering

University of Alabama at Birmingham

1150 10th Avenue South, 261 C BEC Complex, Birmingham, AL, 35294

Abstract

In this paper we provide a brief review of knowledge integration and explain our environment as a prototype of an interdisciplinary approach to solve problems. Our prototype is built on a Java three-tier architecture with an Oracle database storing a large number of N-Queens solutions. The N-Queens problem is a type of problem that is commonly used for variety of demonstration purposes in many disciplines. For example it is used in computer design, program development methodology, VLSI testing, traffic control, and deadlock prevention, among others. In our research group, we have created a Web-based environment on this problem, which can be used for research and educational purposes. In this paper we report our progress in designing this Web-based system and its implications to the field of education in the 21st century. This paper is also partially based on the masters thesis research of O. Aktunc.

Historical Perspective

The scientific method of knowledge generation and problem solving [1, 2, 3] based on deductive reasoning, observation, and experimentation has been in development since the era of Thales around 600 B.C. The early historical figures of science history were philosophers, such as Euclid, Plato or Aristotle, who studied mathematics and natural phenomena. Plato was the first to suggest the generation of knowledge through mathematical activity. Another important footstep was the discovery of using observation and logical inference in scientific activities by Aristotle. These contributions were the milestones of the Platonic/Aristotelian era in which education was done in a rather ad-hoc way compared to the present time. Automation was not a necessity for the application and success of methods for deductive reasoning and observation [4].

Plato’s Academy was a critical social machinery that continued until 500 A.D. The Academy is generally acknowledged to be the forerunner to the modern universities of the West. Although the main method of education was the discussion of philosophy and mathematics, teaching was primarily based on authority. It was Aristotle who decided that knowledge could grow more easily if it were divided into separate domains, each with its own area of discourse and methodology. Aristotle established the Lyceum in 335 B.C. with its particular emphasis on scientific research and training. This concept of domains of knowledge, has been instrumental in solving many problems as it means that the appropriate methodology or discipline can be identified for a particular problem. A practical example of what may happen when the inappropriate methodology is used in problem solving would be attempting to treat a poisonous snake-bite with stoic philosophy alone. This misunderstanding could result in the death of the unlucky person. In this case, now we know that the knowledge-domain of medicine developed methods to solve this problem. A medical doctor who has the proper antivenin can solve this problem [5].

In the Cartesian-Mechanistic era starting around 1600’s, philosopher and mathematician Descartes presented systematic experimentation as a method of science, in particular problem solving. Traditional social machinery became the universities, and the teaching methods were transformed from the authoritative way to the instructional methods. With the increasing number of researchers and the information, the need for automation increased. During this era the disciplines started to form from general knowledge. A simplistic historical morphology of the evolution of disciplines (Fig. 1) could start with a pre-disciplinary general knowledge which then expands along preferential directions, as was in the case of the Middle Ages. The trivium (grammar, rhetoric, logic) and quadrivium (algebra, music, geometry, and astronomy) encompassed what was the important knowledge for the times [6]. Given the limited amount of knowledge available, those preferential directions could all be encompassed by an accomplished individual. Leonardo da Vinci represented an ideal which is no longer attainable: the "Renaissance man,” who was able to master simultaneously many forms and domains of knowledge. Leonardo was a remarkable painter, writer, philosopher, engineer, and cosmologist.

Figure 1- Historical morphology of the evolution of disciplines

From a small curriculum of several liberal arts and a few scientific disciplines of Aristotle's time, there has been a huge expansion in our knowledge. The number of disciplines offered at universities or polytechnics today reveal a vast increase compared to that era. The number of cross-disciplinary and interdisciplinary subjects has significantly increased and new ones are being established as collaboration between scientists increases. The explosion of knowledge which started in the Cartesian-Mechanistic era continues at terrifying pace in our current Information Era. For instance, the National Library of Medicine estimates that published medical knowledge is doubling in size every four years, making it very hard for any single scientist to encompass anything larger than his or her field of specialty [7].

In some ways, it seems that our understanding of knowledge may be coming back to the times of Aristotelian discourse. Perhaps we have the technological ability and appropriate frame-of-mind now to answer questions that could not be answered before. The education system is still characterized by the physical campus: the easiest method of discourse is still face-to-face communication. However, now that we have the inexpensive ability to communicate by emails, bulletin boards and cyberspace discussion groups, in some ways we may have returned to the days of Socrates, Aristotle's predecessor, who taught by discourse and argument.

Table 1 - Historical progress in knowledge-generation and education

Method / Era / Teaching / Automation Need / Social Machinery / Education
a)Deductive Reasoning (Plato)
b)Observation and logic (Aristotle) / Platonic/ Aristotelian / Primarily based on authority and regurgitation / Minimal / Plato’s Academy
Aristotle’s Lyceum / Ad-hoc
Experimentation (Descartes) / Cartesian-Mechanistic / Primarily based on instruction / Increased / Universities/
Research Labs / Disciplinary/
Interdisciplinary
Meta-fusion (systematic knowledge integration) / Combinatorics/ Integration / Primarily based on facilitation / An integral part of the method / Integrated Universities and polytechs / Transdisciplinary

The Need for an Interdisciplinary Approach

According to Moti Nissani, a discipline is "any comparatively self-contained and isolated domain of human experience which possesses its own community of experts, with distinctive components such as shared goals, concepts, facts, tacit skills, and methodologies" [8].

Interdisciplinarity, on the other hand, is "the bringing together of distinctive components of two or more disciplines" in research or education, leading to new knowledge which would not be possible without this integration. Multidisciplinarity occurs when disciplines work side by side on distinct parts of a single problem. Interdisciplinarity occurs when disciplines intermesh, integrate, and collaborate among themselves. Interdisciplinary creates new knowledge and uses of knowledge across boundaries of disciplines and institutions. But beyond being a powerful engine of creativity, interdisciplinarity is also an instrument of integration of the uses as well as of the users of knowledge [6]. Along the same line of thought, the notion of transdisciplinary implies that to achieve “Interdisciplinary collaborative success” one has to increase the abstraction levels of disciplinary knowledge using meta-level abstraction tools. A practical current technology which enables this abstraction is XML (Extensible Markup Language) [11].

To utilize Albert Borgmann's distinction, “information about reality (science) and information for reality (engineering) have morphed into information as reality. But the information society appears to have little or no program for how to live in or with this information rich possibility space other than to affirm some automatic synthesis” [9]. Since the times of Descartes, so much information, knowledge and technology have been produced that haven’t been in the history of man. The next era will be in the assessment and integration of information in an intelligent way, while continuing to produce even more information. As we have given in Table 1, two potential mechanisms to do this are systems integration (through abstract design and process notions) [15,16] and use of combinatorics (interconnection mechanisms through the study of combination). In the new era of integration the instructor plays the role of facilitator rather than fact-introducer. An instructor should provide methods and techniques to the students so they can reach and comprehend the information they need. Automated tools are integrated into the learning process. Integrated universities and polytechs guided by institutes of technosciences will be the leading mechanisms for knowledge generation and integration. The institute of technosciences establishes a super-structure integrating educational institutes (the science motivation) and industry (technology motivation) into a value-added entity for the information value-chain of the society at large [7].

Another important mechanism for problem solving will be the use of Internet and Intranets in the educational institutes. The convenient and inexpensive use of Internet facilitates the communication between scientists and researchers both from the same discipline or disparate disciplines. Regular tools such as e-mail, bulletin boards, or websites are widely used for this purpose nowadays. However, the main challenge will be using intelligent and powerful tools to make this communication easy and effective; especially building environments that will not only be used by people from the same discipline, but will make people from different disciplines understand each other. This level of interdisciplinary collaboration will be an important milestone in the history of problem solving. In our research group, we have created a web-based environment on N-Queens problem, a problem that is commonly used for variety of demonstration purposes in many disciplines, which can be used for research and educational purposes. In the next section we report our progress in designing this Web-based system and its implications on education in the 21st century.

N Queens Problem

The N-Queens problem, which is a general case of the 8-Queens problem, has been studied for more than a century. The 8-Queens problem was first introduced by a chess player, Max Bezzel, in 1848. The N-Queens problem, as generalization of the 8-Queens problem, was first proposed in 1867. Since 1850, the problem has attracted the attention of several famous mathematicians including Gauss, Polya, and Lucas.

The N-Queens problem can be defined as follows: place N queens on an NxN chessboard, one queen on each square, so that no queen captures any of the others, that is, a configuration in which there exists at most one queen on the same row, column or diagonals. A representation of N-Queens problem is given on a chessboard in Figure 2.

Figure 2 – Representation of N- Queens problem where N=8

During the last three decades, the problem has been discussed in the context of computer science and used as an example of backtrack algorithms, permutation generation, divide and conquer paradigm, program development methodology, constraint satisfaction problems, integer programming, specification and neural networks . Some practical applications of the N-Queens problem such as,VLSI testing, traffic control, and deadlockpreventionare mentioned in the website [10].

Our Environment

The algorithms subgroup in our Component-Based Software Engineering (CBSE) research group makes extensive use of N-Queens solutions in their research into combinatorial relationships betweens N-Queens solutions and communication channels. Also the component based subgroup of the research group studies this problem for various reasons. Thus, we elected to build an experimental Research-to-Research (R2R) test-bed using N-Queens as our domain of application. Not only we use this collaboration environment for our research purposes, but also we designed this environment as a prototype of an interdisciplinary approach to solve problems. Our prototype is built on a Java three-tier architecture powered by a large database of N-Queens solutions [11]. In this environment, we will provide research services to the graduate students working in this domain. Services represent units of work, and R2R processes specify the sequence and definition of services and research documents.

Though the service needs change from research group to research group, a general classification of services can be listed as follows:

Type 1: Relevant information sources for the research topic (papers, books, periodicals)

Type 2: Raw information (raw data, experiments, values)

Type 3: Calculations based on raw information (i.e. Miscellaneous solutions using software such as Matlab)

Type 4: Analysis of raw information.

Type 5: Visuals from raw info (i.e. charts, graphs, tables)

Type 6: Report based on any combination of the above.

Type 7: Simulation or testing (application service providing) [11]

In our research group the most common need of the students is to access the information sources on the N-Queens problem. They can easily access all the information found on the Internet or get a detailed explanation of the problem from the website. All the hard-copy documents about the problem (papers, articles) are electronically available in different formats in our database. Several of these documents are very hard to find even in many libraries. In this way, the students working on this problem have the chance to concentrate on the problem and accessing the important documents without getting lost under the large volume of information. The result sets of the N-Queens problem are also readily available in our database. The result sets are frequently used by the students studying the relationship of the problem with other mathematical structures, such as Chebychev polynomials, and polygons. Several other additions are being developed to meet the students’ requirements, such as adding the Matlab figures about the problem to the database, and modifying the environment according to the student’s preferences. The students benefited in several ways by building and developing this environment:

  • Accessing the information in a timely and efficient manner.
  • Experiencing several technologies by building a R2R environment.
  • Developing a methodology to solve scientific problems.

The architecture of N-queens research domain is shown in Figure 3. It is constructed on the three-tier architecture model of Web applications. Thus it basically consists of three distinct components: User Interface, Server, and Data Storage. We will briefly discuss all these parts. The technical details of this architecture can be found in our paper about this environment [11].

User interface is the front end of the N-queens research domain. It consists of all the user interface files which are needed to construct the front face of the application. This is the portion of the application which the researcher uses to access the N-queens research domain.

Figure 3- Implementation of N-Queens Application as a three-tier model [12]

The server is the bridge between the other two components of the system, User Interface and Data storage. It consists of a Web server and enabling technologies. The server component contains five servlets, the LMX processor and JDBC APIs [see list of acronyms used following "Conclusion"]:

1. InputDoc Servlet:

InputDoc servlet accepts the data entered by the user, converts the data into XML format and stores it at the specified location. This servlet parses the entered data into W3C specified XML format.

2. Database Servlet:

Database servlet is used to communicate with Queen solution database through JDBC TM APIs. This servlet takes the parameters specified by user, then search for Queen Solutions matching the specified parameters in the database and display the matched solutions in the web browser.

3. ListDoc servlet:

ListDoc servlet lists all the available XML documents in the N-queens research domain. When the user wants to see any of these listed documents, this servlet redirects the user request to the ViewDoc servlet, which shows the document to the user in HTML format.

4. ViewDoc Servlet:

ViewDoc servlet shows the document requested by the user in HTML format. The documents are stored originally in XML format. Before showing, the documents are passed through the LMX processor which converts the document to HTML format and then it is displayed to the user through ViewDoc servlet.

5. MakeCDF Servlet:

MakeCDF servlet converts the available XML document information, into the CDF (Channel Definition Format) which can be monitored through the user interface and permits the user to add the information to the browser’s favorites menu. This feature is only supported by MSIE 4 and MSIE 5.

6. LMX Processor:

This component converts the information from XML format to XML, WML or HTML. In our application, the function of the processor is converting XML information into HTML format.

7. JDBC TM APIs:

JDBC TM is the set of APIs used to connect the servlets to databases.

We use two types of data storage in our application:

1. XML data storage:

This is the data storage on the directory structure to store the XML documents.

2. Queen database:

This is the database storage to store Queen Solutions. More technical information about the whole environment, and also about the N-Queens problem is available in the technical reports of the members of the CBSE Research group on the website [13], [14]

Conclusion

Our environment is available on our website: although it is in continuous development. The final objectives of this work are:

  • Global access to the research results on a centralized server in the domain.
  • Support for specific experimentation such as simulation and testing.
  • Database support for reaching previous results and documentation.

We believe that in the next era of scientific development, the use of collaboration environments over the Internet will facilitate the communication between scientists and researchers both from the same discipline or disparate disciplines. A main challenge will be creating intelligent and powerful tools to make this communication easy and effective. Especially building environments that will not only be used by people from the same discipline, but will make people from different disciplines understand each other. This level of interdisciplinary collaboration will be an important milestone in the history of problem solving.