Sudoku Solver and Generator: Java and Assembly Implementations

Overview

This repository presents two distinct implementations for solving and generating Sudoku puzzles: a Java version and an Assembly version. Both implementations leverage fundamental algorithmic techniques like backtracking and constraint propagation to efficiently tackle Sudoku challenges.

Features

Common Features

• Sudoku Solver:
  • Efficiently solves Sudoku puzzles of varying difficulty levels.
  • Utilizes backtracking and constraint propagation algorithms.
  • Can handle both partially filled and completely empty grids.
• Sudoku Generator:
  • Generates new Sudoku puzzles of different difficulty levels.
  • Employs a technique of solving a puzzle and then removing cells to create a solvable puzzle.
  • Ensures generated puzzles have unique solutions.

Language-Specific Features

• Java Implementation:
  • Leverages Java's object-oriented paradigm for modular and maintainable code.
  • Provides a user-friendly interface for inputting puzzles and visualizing the solving process.
• Assembly Implementation:
  • Demonstrates low-level control and optimization techniques.
  • Offers insights into the core algorithms and data structures involved.

Getting Started

1. Clone the Repository:

   Bash

   git clone https://github.com/your-username/sudoku-solver-generator.git
   
   

2. Set Up Environment:

   • Java: Ensure you have a Java Development Kit (JDK) installed.
   • Assembly: Install an appropriate assembler and linker for your target architecture (e.g., NASM, GCC).

3. Build and Run:

   • Java:

     Bash

     javac Solver.java Generator.java
     java Solver
     java Generator
     
     

   • Assembly:

     Bash

     nasm -f elf64 solver.asm
     ld solver.o -o solver
     ./solver
     # Similar steps for the generator
     
     

Implementation Details

Common Algorithms

• Backtracking: Explores different possibilities by making a choice, checking its validity, and backtracking if it leads to a dead end.
• Constraint Propagation: Reduces the search space by eliminating impossible values for cells based on existing constraints.

Language-Specific Implementations

• Java:
  • Utilizes Java's standard libraries for data structures and algorithms.
  • Leverages object-oriented principles to model Sudoku grids and solving strategies.
• Assembly:
  • Directly manipulates memory and registers to implement the algorithms.
  • Optimizes performance through careful instruction selection and memory access patterns.

Potential Improvements

• Performance Optimization: Explore techniques like caching, pruning, and parallel processing.
• Difficulty Level Calibration: Fine-tune the difficulty level generation algorithm for more precise control.
• User Interface: Develop a user-friendly interface for inputting puzzles and visualizing the solving process (Java).
• Puzzle Analysis: Implement features to analyze puzzle statistics and identify patterns.
• Assembly Optimization: Further optimize the Assembly code by leveraging assembly-specific techniques and hardware features.

Contributions

Contributions to this project are welcome! Feel free to fork the repository, make improvements, and submit pull requests.

License

This project is licensed under the MIT License.