Latin-Square-Completion

Introduction

A Latin square of order n is a nxn matrix consisting of n symbols (i.e., {1, 2, . . . , n}) in which each symbol occurs exactly once in each row and exactly once in each column. If some grids are empty, then the Latin square complete (LSC) problem of order n aims to complete the empty grids with n symbols to obtain an arbitrary legal Latin square.

NP-Complete Problem

Latin Square Completion is a Constraint Satisfaction Problem and hence is NP Complete in nature. This is because it can be solved only in non-deterministic polynomial time, but easy to verify in linear time (O(n)) time complexity.

It can be defined as a Constraint Satisfaction Problem (CSP) as follows:

Variables: Each cell in NxN matrix

Domains: {1, 2, . . . , n}

Constraints: Each symbol (1-n) can occur exactly once in a row and column

In this project, we aim to explore various state space reduction techniques and heuristics which can be used to solve this LSC problem, using graph-coloring representation, to reduce the computational complexity of the problem.

Approach

1. Transforming the problem as a Graph Colouring problem

Here, the nodes represt the cells, and the edges represent the constraints. The color of the node represents the value of the symbol in the cell.

2. Reduction of Graph

We reduce the search space by filling those cells for which the domain is not greater than 1. This allows us to significantly reduce the search space.

3. Best First Search

File Structure

👨‍💻Latin-Square-Completion
 ┣ 📂assets                            // Contains all the reference gifs, images
 ┣ 📂include                           
 ┃ ┣ 📄lsc.hpp                         // Header file for LSC
 ┃ ┣ 📄plits.hpp                       // Header file for PLITS 
 ┣ 📂src                          
 ┃ ┣ 📄bfs.cpp                         // Breadth-First Search
 ┃ ┣ 📄dfs.cpp                         // Depth-First Search 
 ┃ ┣ 📄bestfs.cpp                      // Best-First Search
 ┃ ┣ 📄plits_seq.cpp                   // Partial Legal and Illegal Tabu Search (PLITS), Sequential
 ┃ ┣ 📄plits_par.cpp                   // PLITS, Parallelised using OpenMP
 ┣ 📄Makefile       
 ┣ 📄README.md   

Getting Started

Prerequisites

To download and use this code, the minimum requirements are:

• make: A build automation tool.
• g++: The GNU C++ compiler.
• Operating System: Windows 7 or later (64-bit) or Ubuntu 20.04 or later.

Installation

Clone the project by typing the following command in your Terminal/CommandPrompt

git clone https://github.com/PritK99/Latin-Square-Completion

Navigate to the Latin-Square-Completion folder

cd Latin-Square-Completion

Usage

Once you have installed the prerequisites and cloned the project, you can start using it. Follow these commands:

To compile all targets / algorithms, run

make all

To list all targets, run

$ make list
Targets (Algorithms): 
- bfs (Breadth First Search)
- dfs (Depth First Search)
- bestfs (Best First Search)
- plits_seq (Partial Legal & Illegal Tabu Search)
- plits_par (Parallelised Partial Legal & Illegal Tabu Search)

To compile only a specific target / algorithm (from BFS, DFS, BestFS or PLITS {sequential & parallel}), run (e.g. for bestfs)

$ make bestfs

To execute any program, run (e.g. for bfs)

$ ./bfs

Note: When running the parallel PLITS algorithm, you can specify the number of threads as an argument. For example:

$ ./plits_par 4

To remove any executables, run

$ make clean

Output

1. BFS implementation

Screencast-from-18-11-23-11_15_28-PM-IST.mp4

2. DFS implementation

Screencast-from-22-11-23-02_31_29-PM-IST.mp4

3. Best First Search Implementation

Screencast-from-02-01-24-10_53_50-PM-IST.mp4

4. Reduction and Smart Solving Techniques

Screencast-from-02-01-24-10_54_42-PM-IST.mp4

5. 4x4 LSC using Heuristics and Reductions

Screencast-from-02-01-24-10_58_33-PM-IST.mp4

References

A Fast Local Search Algorithm for the Latin Square Completion Problem (AAAI 22) by Shiwei Pan, Yiyuan Wang, Minghao Yin