N-Queen Problem

Duration: 42 min

This video lesson is available to enrolled students.

Return to /learn/NTA-UGC-NET-PAPER-2/unit-7-data-structures-and-algorithms/advanced-algorithms/backtracking-technique/asset-n-queen-problem after enrolling

Inside: a video lesson and guided study material.

Module outline

  1. Course Overview: About the Course
  2. Paper - 1 | Unit - 1 | Teaching Aptitude: Concept and Objectives of Teaching / शिक्षण की अवधारणा एवं उद्देश्य, Levels of Teaching / शिक्षण के स्तर, Learner's Characteristics / शिक्षार्थी की विशेषताएँ, Learning: Nature and Theories / अधिगम: प्रकृति एवं सिद्धांत, Cognition, Memory and Metacognition / संज्ञान, स्मृति एवं अधिसंज्ञान, Factors Affecting Teaching / शिक्षण को प्रभावित करने वाले कारक, Effective Teaching and the Teacher / प्रभावी शिक्षण एवं शिक्षक, Instructional Objectives and Lesson Planning / अनुदेशनात्मक उद्देश्य एवं पाठ नियोजन, Methods of Teaching / शिक्षण विधियाँ, Offline and Online Teaching Methods / ऑफ़लाइन एवं ऑनलाइन शिक्षण विधियाँ, Teaching Support System / शिक्षण सहायक प्रणाली, Evaluation Systems / मूल्यांकन प्रणाली, Sāṃkhya / सांख्य, Individual Behaviour / व्यक्तिगत व्यवहार, Human Resource Management / मानव संसाधन प्रबंधन, Domains of Child Development / बाल्यावस्था में विकास के क्षेत्र, Biological Basis of Emotion / संवेग का जैविक आधार, Upanishads and Bhagavad Gita / उपनिषद और भगवद्गीता, Central and Peripheral Nervous Systems / केन्द्रीय और परिधीय तंत्रिका तंत्र
  3. Paper - 1 | Unit - 2 | Research Aptitude: Research: Meaning, Features and Scientific Method / अनुसंधान: अर्थ, लक्षण व वैज्ञानिक विधि, Research Paradigms and Approaches / अनुसंधान के प्रतिमान एवं उपागम, Types of Research / अनुसंधान के प्रकार, Variables and Measurement / चर एवं मापन, Methods of Research / अनुसंधान की विधियाँ, Steps of Research / अनुसंधान के चरण, Sampling / प्रतिचयन, Tools and Methods of Data Collection / आँकड़ा संग्रह के उपकरण एवं विधियाँ, Data Analysis and Statistics in Research / आँकड़ा विश्लेषण एवं शोध सांख्यिकी, Thesis and Article Writing / शोध-प्रबंध एवं लेख लेखन, Application of ICT in Research / अनुसंधान में ICT का अनुप्रयोग, Research Ethics / शोध नैतिकता
  4. Paper - 1 | Unit - 3 | Comprehension: Literal Comprehension, Vocabulary and Language in Context, Inferential Comprehension, Critical Comprehension, Comprehension / Reading Comprehension / Unseen Passages (Critical Reasoning) (Paragraph Questions), Restoration and Eighteenth-Century Drama, Modern British Fiction, William Shakespeare, Mid-Twentieth-Century and Contemporary British Fiction, American Drama
  5. Paper - 1 | Unit - 4 | Communication: Communication: Meaning, Nature and Process / संचार: अर्थ, प्रकृति एवं प्रक्रिया, Types and Levels of Communication / संचार के प्रकार एवं स्तर, Verbal and Non-verbal Communication / मौखिक एवं अमौखिक संचार, Semiotics and Meaning / संकेत विज्ञान एवं अर्थ, Models and Theories of Communication / संचार के मॉडल एवं सिद्धांत, Effective Communication / प्रभावी संचार, Barriers to Communication / संचार की बाधाएँ, Classroom Communication / कक्षा संचार, Mass Media: Types and Evolution / जनसंचार माध्यम: प्रकार एवं विकास, Mass Media and Society / जनसंचार एवं समाज, Digital and New Media / डिजिटल एवं नव माध्यम, Static General Knowledge / स्थैतिक सामान्य ज्ञान, Morphology and Syntax, Public Health Nutrition / जन स्वास्थ्य पोषण, Newtonian Motion and Stability, GK- Current Affairs / GK- समसामयिकी, Indian Economy / भारतीय अर्थव्यवस्था, Art and Architecture / कला और स्थापत्य, India after Independence / स्वतंत्रता के बाद भारत
  6. Paper - 1 | Unit - 5 | Mathematical Reasoning and Aptitude: Number System and Simplification / संख्या पद्धति एवं सरलीकरण, Algebra and Ages / बीजगणित एवं आयु, Percentage / प्रतिशतता, Ratio, Proportion, Partnership and Mixtures / अनुपात, समानुपात, साझेदारी एवं मिश्रण, Averages / औसत, Profit, Loss and Discount / लाभ, हानि एवं बट्टा, Simple and Compound Interest / साधारण एवं चक्रवृद्धि ब्याज, Time and Work / समय एवं कार्य, Speed, Time and Distance / चाल, समय एवं दूरी, Mensuration and Geometry / क्षेत्रमिति एवं ज्यामिति, Series / श्रेणी, Coding-Decoding / कूटलेखन-कूटवाचन, Relationships, Directions and Ranking / संबंध, दिशा एवं क्रम, Arrangements, Puzzles, Clock and Calendar / व्यवस्था, पहेलियाँ, घड़ी एवं कैलेंडर, Mathematical Foundations, Polity / राजव्यवस्था, जीवनी, Deconstruction, Gender and Queer Theory, Modern British and Irish Poetry, Central Force and Scattering, Chemical thermodynamics, Microscopic techniques, Philosophy of the Constitution / संविधान का दर्शन, Waves, Optics and Charged-Particle Motion, Membrane structure and function, Analysis
  7. Paper - 1 | Unit - 6 | Logical Reasoning: Structure of Arguments / युक्ति की संरचना, Terms, Definitions and Uses of Language / पद, परिभाषा एवं भाषा के उपयोग, Categorical Propositions / निरुपाधिक प्रतिज्ञप्तियाँ, Categorical Syllogism / निरुपाधिक न्यायवाक्य, Venn Diagrams / वेन आरेख, Deduction, Induction and Analogy / निगमन, आगमन एवं सादृश्यता, Fallacies / तर्कदोष, Indian Logic: Pramanas / भारतीय तर्कशास्त्र: प्रमाण, Anumana and Vyapti / अनुमान एवं व्याप्ति, Hetvabhasa / हेत्वाभास, Non Verbal Reasoning (Spatial Aptitude) (Spatial Reasoning) (Visual Reasoning), Aristotle / अरस्तू, Western Schools of Philosophy / पाश्चात्य दर्शन की विचारधाराएँ, Kant / कांट, Sadhana Paada, Vaiśeṣika / वैशेषिक
  8. Paper - 1 | Unit - 7 | Data Interpretation: Data and Graphical Representation / आँकड़े एवं आलेखीय निरूपण, Data Interpretation: Tables / आँकड़ा निर्वचन: तालिका
  9. Paper - 1 | Unit - 8 | Information and Communication Technology: Computer Fundamentals and Hardware, Memory, Storage and Data Representation, Computer Software, Office Applications, Multimedia and File Formats, Computer Networks, Internet and World Wide Web, Email and Online Communication, Cyber Security, Digital Ethics, IPR and Society, Cloud and Distributed Computing, Emerging Technologies, ICT in Education and Governance, Cyber Threats and Malware Attacks, Role of Internet and Web Services, Electronic Data Interchange and E-Commerce, Internet Fundamentals, Web Design & Development, Web Publishing & Hosting, Emerging Technologies, Terms & Abbreviations, Society, Law & Ethics, Keyboard Shortcuts, Website, Browser & Services, Protection of Geographical Indications / भौगोलिक संकेतों का संरक्षण
  10. Paper - 1 | Unit - 9 | People Development and Environment: Ecosystems and Biodiversity / पारितंत्र और जैव विविधता, Human and Environment Interaction / मानव और पर्यावरण की अंतःक्रिया, Development and Environment / विकास और पर्यावरण, Natural Resources – Forests, Water and Soil / प्राकृतिक संसाधन: वन, जल और मृदा, Energy Resources / ऊर्जा संसाधन, Air Pollution / वायु प्रदूषण, Water Pollution and Treatment / जल प्रदूषण और उपचार, Noise Pollution / ध्वनि प्रदूषण, Waste Management / अपशिष्ट प्रबंधन, Environmental Health and Toxicology / पर्यावरणीय स्वास्थ्य और विषविज्ञान, Climate Change and Global Environmental Issues / जलवायु परिवर्तन और वैश्विक पर्यावरणीय समस्याएँ, Natural Hazards and Disaster Management / प्राकृतिक प्रकोप और आपदा प्रबंधन, Indian Environmental Laws and Policies / भारतीय पर्यावरण कानून और नीतियाँ, International Environmental Agreements / अंतर्राष्ट्रीय पर्यावरण समझौते, Environment / पर्यावरण, Geography / भूगोल, Factory and Industry Systems / कारखाना और उद्योग व्यवस्थाएँ, Earth Materials, Surface Features and Processes, Communicable Diseases and Immunization / संक्रामक रोग और प्रतिरक्षण
  11. Paper - 1 | Unit - 10 | Higher Education System: Education in Ancient India / प्राचीन भारत में शिक्षा, Ancient Centres of Higher Learning / प्राचीन भारत के उच्च शिक्षा केंद्र, Colonial Education Policies and Commissions / औपनिवेशिक काल की शिक्षा नीतियाँ और आयोग, Colonial Colleges, Universities and Reformers / औपनिवेशिक कॉलेज, विश्वविद्यालय व सुधारक, Education Commissions and Policies after Independence / स्वतंत्र भारत में शिक्षा आयोग और नीतियाँ, National Education Policy 2020 / राष्ट्रीय शिक्षा नीति 2020, Types of Higher Education Institutions / उच्च शिक्षा संस्थानों के प्रकार, Learning Programmes and Academic Credits / अधिगम कार्यक्रम और अकादमिक क्रेडिट, Professional, Technical and Skill-Based Education / व्यावसायिक, तकनीकी और कौशल आधारित शिक्षा, Value Education and Environmental Education / मूल्य शिक्षा और पर्यावरण शिक्षा, Governance, Administration and Financing / शासन, प्रशासन और वित्तपोषण, Regulation, Accreditation and Ranking / उच्च शिक्षा का नियमन, प्रत्यायन और रैंकिंग
  12. Paper 2 | Unit 1 | Discrete Structures and Optimization: Propositional and Predicate Logic, Set Theory, Relations, Functions, Permutation, Combination and Probability / क्रमचय, संचय एवं प्रायिकता, Graph Theory, Group Theory, Digital Systems & Boolean Basics, Boolean Expression, Boolean Minimization, Optimization, Markov Chains
  13. Paper 2 | Unit 2 | Computer System Architecture: Logic Gates & Hardware, Combinational Circuit, Sequential Circuits, Number System, Number Representation, Floating Point Rep, Basics of COA, Register Transfer and Microoperations, Programming the Basic Computer, Instr Formats & Modes, Control Unit Design, Pipelining, Input Output Organisation, Cache Memory Organization, Multiprocessors
  14. Paper 2 | Unit 3 | Programming Languages and Computer Graphics: Language Design, C Fundamentals, Control Flow, Functions, Arrays & Pointers, Storage Classes, Structures & Enums, DMA, Macros, Scoping & File Handling, HTML Basics, XML, JavaScript-Basics, Java, Basics of Computer Graphics, 2-D Geometrical Transforms and Viewing, 3-D Object Representation, Geometric Transformations and Viewing, OOPS with C++, Java Fundamentals, Array, String, IO & References, OOPS with Java
  15. Paper 2 | Unit 4 | Database Management Systems: Basics of DBMS, ER Diagram, Relational Model & Functional Dependencies, Keys & Integrity Constraints, Normalization (1NF - BCNF), Decomposition Properties & 4NF, File Organization & Indexing, Relational Algebra, SQL, Relational Calculus, Transaction Management, Concurrency Control, Database Recovery, ORDBMS, Database Security & Authorization, Query Processing & Optimization, Enhanced Data Models, Data Warehousing & Mining, Big Data Systems, NoSQL
  16. Paper 2 | Unit 5 | System Software and Operating System: Introduction to OS, Process Management, CPU Scheduling, Process Synchronization, Threads & Process Creation, Deadlock, Memory Management, Virtual Memory, Disc Scheduling, File Management, Windows OS, Linux OS, Security, Distributed Systems, Virtual Machines
  17. Paper 2 | Unit 6 | Software Engineering: Fundamentals of Software Engineering, Software Requirements and Quality Assurance, Software Design, Estimation and Metrics, Software Testing, Software Maintenance and Configuration Management
  18. Paper 2 | Unit 7 | Data Structures and Algorithms: Introduction to DS, Array, Stack, Queue, Linked List, Tree, Graphs, Hashing, Algorithm Analysis, Time Complexity Analysis, Sorting Algorithms, Greedy Algorithms, Dynamic Programming, Minimum Spanning Trees, Shortest Path Algos, Advanced Algorithms
  19. Paper 2 | Unit 8 | Theory of Computation and Compilers: Introduction to TOC, Deterministic FA (DFA), Non-Deterministic FA, Regular Expressions, Grammar, Regular Language Properties, Moore & Mealy Machines, Pushdown Automata & CFG, Turing Machines, Complexity Theory, Intro to Compilers, Lexical Analysis, Grammar & CFG, Syntax Analysis: Top-Down, Syntax Analysis: Bottom-Up, Semantic Analysis & SDT, Intermediate Code Gen, Code Optimization, Run Time Environment
  20. Paper 2 | Unit 9 | Data Communication and Computer Networks: Introduction to CN, Data Communication, DLL: Access Control, DLL: Flow Control, DLL: Error Control, DLL: Framing, Data Link Layer - Ethernet, Net Layer: IPv4 & Proto, Net Layer: IP Addressing, Net Layer:Routing Protocol, Transport Layer Services, TL: Congestion & UDP, Application Layer, Hardware basics, Network Security, Cloud Computing, Mobile Computing
  21. Paper 2 | Unit 10 | Artificial Intelligence: Approaches to AI, Search Algorithms, Game Playing, Knowledge Representation, Planning, Multi Agent Systems, Fuzzy Sets, Natural Language Processing, Artificial Neural Networks, Genetic Algorithms
  22. Live Classes: NTA UGC NET 2025 Live Class
  23. Paper 1 | Full Mock Tests:
  24. Paper 2 | Full Mock Tests:
  25. Paper 1 | Previous Year Papers:
  26. Paper 2 | Previous Year Papers:
AI summary & chapters

AI Summary

An AI-generated summary of this video lecture.

This lecture provides a comprehensive introduction to the N-Queen Problem, a classic constraint satisfaction problem in computer science. The instructor begins by defining the core objective: placing N queens on an N x N chessboard such that no two queens attack each other. The teaching flow systematically breaks down the movement rules of a queen, emphasizing that it attacks horizontally (row), vertically (column), and diagonally. This establishes the fundamental constraints for valid placement: no two queens can share the same row, column, or diagonal. The instructor uses a 4x4 grid as a concrete example to visualize these constraints, labeling rows and columns with indices i and j. A key mathematical insight is introduced to handle diagonal checks efficiently: two cells (i, j) and (x, y) share the same main diagonal if i - j equals x - y, and they share the same anti-diagonal if i + j equals x + y. The lecture then transitions into a backtracking algorithm to solve the problem, demonstrating how to place queens row by row. The instructor constructs a decision tree where each branch represents a potential placement, and invalid paths are pruned immediately upon detecting a constraint violation. Visual aids include grids with queens marked as Q1, Q2, etc., and 'X' marks indicating invalid positions. The session culminates in identifying a valid solution configuration for the 4-Queen problem, verifying it through coordinate calculations and diagonal difference checks. The final segment discusses the complexity of the search space, contrasting total permutations (4^4 = 256) with valid factorial arrangements to highlight the efficiency of backtracking over brute force methods.

Chapters

  1. 0:00 – 2:00 00:00-02:00

    The instructor introduces the N-Queen Problem as a classical constraint satisfaction problem, defining it as placing N queens on an N x N chessboard such that no two queens attack each other. He details the movement rules of a queen, noting it attacks horizontally (row), vertically (column), and diagonally. The instructor begins to write on the screen, likely illustrating the constraints or an example setup. On-screen text explicitly states: 'N-Queen Problem', 'constraint satisfaction problem', and lists the attack rules. The instructor draws a 4x4 grid to visualize the board, labeling rows and columns to illustrate how queens attack horizontally, vertically, and diagonally. The lesson focuses on ensuring no two queens share the same row, column, or diagonal.

  2. 2:00 – 5:00 02:00-05:00

    The instructor continues to explain the N-Queen problem constraints on a 4x4 grid. He defines that queens attack horizontally, vertically, and diagonally, meaning no two queens can share a row, column, or diagonal. He then introduces the concept of main and anti-diagonals by labeling grid coordinates with indices i and j. The instructor draws multiple 4x4 grids to visualize the problem space and begins labeling rows and columns. On-screen text reinforces: 'No two queens in the same row', 'No two queens in the same column'. The instructor writes coordinate differences (i-j) to identify diagonal properties, setting up the mathematical foundation for constraint checking.

  3. 5:00 – 10:00 05:00-10:00

    The instructor explains the N-Queens problem, specifically focusing on how to identify diagonal and anti-diagonal constraints for placing queens on a chessboard. He demonstrates that two cells (i, j) and (x, y) share the same diagonal if i - j equals x - y, and they share the same anti-diagonal if i + j equals x + y. The visual aids include a 4x4 grid with queens placed and two auxiliary grids showing the calculated values for main diagonals (i-j) and anti-diagonals (i+j). The instructor points to specific cells in the auxiliary grids showing diagonal values. On-screen text highlights: 'Main Diagonal (i-j)' and 'Anti Diagonal (i+j)'. This section establishes the mathematical formulas required to programmatically check for diagonal conflicts.

  4. 10:00 – 15:00 10:00-15:00

    The instructor explains the constraints for placing N queens on a chessboard, specifically focusing on the 4-Queen problem. He demonstrates how to check for diagonal conflicts using mathematical formulas involving row and column indices (i-j and i+j). The visual progression shows the instructor writing down coordinates for queens Q2 and Q4 to verify they do not violate diagonal attack rules. On-screen text includes: 'Row', 'Column', and 'Diagonal (i-j) constraints'. The instructor writes coordinates Q2 = (2,3) and Q4 = (4,1), calculating diagonal values 5 for both queens to show conflict or lack thereof. This segment bridges the gap between theoretical constraints and practical coordinate verification.

  5. 15:00 – 20:00 15:00-20:00

    The instructor is explaining the N-Queen problem using a backtracking approach on a 4x4 board. He demonstrates placing the first queen (Q1) in the top-left cell of a grid and then proceeds to place subsequent queens row by row. The visual aids include multiple 4x4 grids representing different stages of the solution, with annotations indicating row numbers and queen placements. On-screen text shows: 'Row 1 Place Q1', 'Q1', 'Q2', 'Row 2 Place Q2', 'Row 3 Place Q3'. The instructor begins writing for 'Row 3 Place Q3', illustrating the step-by-step placement of queens and row-wise constraint checking. This marks the transition from problem definition to algorithmic solution.

  6. 20:00 – 25:00 20:00-25:00

    The instructor is demonstrating the N-Queen problem using a backtracking approach on a 4x4 grid. He systematically places queens (Q1, Q2, etc.) in rows and checks for validity by marking invalid positions with 'X' or calculating differences to ensure no two queens attack each other. The visual progression shows a decision tree where branches represent placing a queen in different columns, and invalid paths are pruned. On-screen text includes: 'Row 2 Place Q2', 'Row 3 Place Q3', 'Row 4 Place Q4', and calculations like '2+3=5', '3+2=5'. The instructor marks invalid positions with '(1) X' and draws a decision tree structure for backtracking, visualizing the pruning of invalid branches.

  7. 25:00 – 30:00 25:00-30:00

    The instructor is demonstrating the N-Queen problem using a backtracking approach on a 4x4 grid. He systematically places queens (Q1, Q2, Q3) in rows 1 through 4 to find valid configurations where no two queens attack each other. The visual tree structure shows branching paths representing different placement attempts, with some branches marked invalid (indicated by 'X' marks) when constraints are violated. On-screen text shows: 'Row1 Place Q1', 'Row2 Place Q2', 'Row3 Place Q3', 'Row4 Place Q4'. The instructor calculates differences like '1 - 2 = -1' and marks invalid configurations with 'X X X'. This segment emphasizes the iterative nature of backtracking and constraint validation.

  8. 30:00 – 35:00 30:00-35:00

    The instructor is demonstrating the N-Queen problem using a backtracking approach on a 4x4 grid. He illustrates placing queens (Q1, Q2, Q3, Q4) row by row and shows how invalid placements are pruned from the search tree. The final valid solution is highlighted with a green checkmark and specific coordinates are calculated to verify the placement. On-screen text includes: 'Row 2 Place Q2', 'Row 3 Place Q3', 'Row 4 Place Q4'. The instructor calculates coordinates for queens Q1 through Q4, such as 'Q1 (1,2) = 3', 'Q2 (2,4) = 6'. The visual aids highlight the final valid solution configuration with green text and arrows showing the flow of the backtracking algorithm.

  9. 35:00 – 40:00 35:00-40:00

    The instructor explains the N-Queen problem as a constraint satisfaction task where N queens must be placed on an NxN board without attacking each other. He details the constraints: no two queens can share a row, column, or diagonal. The visual progression shows the application of these rules to a 4x4 board, calculating total permutations (4^4) versus valid solutions using factorial logic (4!), and illustrating the backtracking search tree. On-screen text displays: 'N-Queen Problem', 'constraint satisfaction problem', and mathematical expressions like '4 x 4 x 4 x 4 = 256'. The instructor points to specific cells on the grid and writes mathematical formulas for permutations, contrasting brute force complexity with backtracking efficiency.

  10. 40:00 – 42:07 40:00-42:07

    The instructor concludes the lecture by summarizing the N-Queen problem constraints and the backtracking solution method. He reiterates that no two queens can share a row, column, or diagonal. The visual progression shows the application of these rules to a 4x4 board, calculating total permutations (4^4) versus valid solutions using factorial logic (4!), and illustrating the backtracking search tree. On-screen text displays: 'N-Queen Problem', 'constraint satisfaction problem', and mathematical expressions like '4 x 4 x 4 x 4 = 256'. The instructor points to specific cells on the grid and writes mathematical formulas for permutations, contrasting brute force complexity with backtracking efficiency. The session ends with a clear understanding of the problem's constraints and the algorithmic approach to solving it.

The lecture effectively guides students through the N-Queen Problem, starting from a clear definition of constraints to an algorithmic solution using backtracking. The instructor uses visual aids like 4x4 grids and decision trees to make abstract concepts concrete. Key takeaways include the mathematical formulas for diagonal checks (i-j and i+j) and the importance of pruning invalid branches in a search tree. The progression from problem definition to solution verification ensures students understand both the 'why' and 'how' of the algorithm. The final discussion on complexity highlights the efficiency gains of backtracking over brute force methods.

Loading lesson…