NxN Queens Puzzle

Problem details: https://en.wikipedia.org/wiki/Eight_queens_puzzle

1. Determine all possible solutions for a given N where N ≥ 8 (within 10 mins on a laptop). Bonus points for a higher N where N is the size of the board / number of queens
2. Iterate over N and store the solutions in postgres using SQLAlchemy
3. Write basic tests that at least verify the number of solutions for a given N match what's online. I recommend using pytest
4. Docker-ize the solution, so that I can run the code and tests without any assumption of my local setup (including running a postgres instance in docker-compose)
5. Setup Travis CI (or similar) for your public GitHub repo to run the tests automatically

Summary

• Demo N Queens
• Project solution
  • File structure
  • The algorithm
    • Steps to solve this
  • Results of algorithm
    • For 14*14 board
    • For 15*15 board
• How it is build?
  • Dependencies
  • Features
  • Development
    • Considerations
• Cookiecutter
• How to use
  • How to clone
  • Development configuration
  • Use on local
  • Install app
  • Dockerized app
  • Run migrations
  • Prepare enviroments
  • Run tests
  • Ejecute coverage report
• To develop
• How to contribute
• License

Demo N Queens

Main view, choise n board and simulate the game, if it has been calculated, the answer show in moment

All possible solutions paginated, with option to regenerate. (You can improve the algorithm and see the new result)

See board of processed solutions with your elapsed time, support n queens until 10 mins

Project solution

File structure

• core (Flask configurations project)
  • envs (Configuration environments)
  • requirements (Project dependencies)
  • extensions (Instance for access to db in modules)
  • img (Images of project)
  • init (Base config app)
  • database (Settings for SQLAlchemy)
  • settings (Injectable settings in app)
• modules Project modules
  • queens (Main blueprint with clean implementation)
    • algorithms (Switch algorithm)
    • connections (Utilities for database connection)
    • simulation (Core elements of the project)
    • solutions (Manage results of the algorithm)
    • utilities (Project utilities)
    • templates (Project templates)
    • views
    • models
    • forms
• migrations (Database version app - Don't tracked)
• labs (Codding problem and test solutions to pass in module queens, this folder won't pass for testing)
• tests (Test of project)

The algorithm

You can see the algorithm in modules/queens/algorithms

This is the solution Number 4, see all solutions in labs folder

def __n_queens(self, board, col, positions):
    """Last N Queens Algorithm
    Development by @eocode
    Version 4
    """
    if col == len(board):
        self.__solutions.add_solution(
            board, len(self.__solutions.get_solutions()) + 1
        )
        return True

    for row in range(len(board)):
        if row in positions.keys() and col in positions[row]:
            apply, values = Queen.attack(row, col, copy.deepcopy(positions))
            if apply:
                board[row][col] = 1
                self.__n_queens(board, col + 1, values)
                board[row][col] = 0

Steps to solve this

• Brute force
• Minimum conflict
• Memorization
• Backtracking

Results of algorithm

For 14*14 board

Test algorithm with n boards > 8

Time in minutes

For 15*15 board

Time in minutes

How it is build?

Dependencies

• Flask
• python-dotenv
• Flask-sqlalchemy
• Psycopg2
• Pytest
• Flask-migrate
• Bootstrap
• Pytest
• Coverage
• Setuptools
• Numpy

Features

• N Queens Problem algorithm with labs to analyze problem
• Dockerized (test and development envs)
• Travis-CI and codecov integration
• Flask Blueprints
• TDD (Test Driven Development) Testing with 10 n*n and every core part of the app for up coverage
• Divide envs
• Extensible
• PostgreSQL
• Paginate results for show solutions
• Web application for view solutions and interact
• Show list of board with all solutions procesed
• Simulate n*n boards until 10 minutes

Development

• Pycharm - IDE
• Black - Code style
• Conventional commits - https://www.conventionalcommits.org/en/v1.0.0/
• Full documented app

Considerations

• Coverage > 85%

Cookiecutter

This microservice has been generated since a cookiecutter development by eocode (me) for this project with the next command

cookiecutter https://github.com/ActivandoIdeas/Cookiecutter-Flask

See the details here: https://github.com/ActivandoIdeas/Cookiecutter-Flask

You can base your next developments on that template or contribute to improve it

# Only execute this (keep the code cleen)
black .

How to use

How to clone

You can clone this repository

git clone https://github.com/eocode/queens

Development configuration

Rename .env.example to .env file

And add your configuration

Use on local

To install this project just type

Create virtual enviroment:

$ python -m venv env

Active your enviroment

Install dependencies

$ pip install -r app/requirements/prod.txt
$ pip install -r app/requirements/test.txt

Run the project

$ flask run

Install app

If you want to install the app use

python setup.py develop

Dockerized app

Start app

docker compose up -d

Stop app

docker compose down

Rebuild app

docker-compose up -d --build

Access to command line interface

docker exec -it flask-app bash

Run migrations

By default migrations foldar has been add to .gitignore

Open Terminal

docker exec -it flask-app bash

Init database migrations

flask db init

Generate migrations

flask db migrate

Run migrations

flask db upgrade

Show more commands

flask db

Prepare enviroments

Configure for test, execute sqlite db

python app/enviroment.py test

Configure for dev or production, execute data in postgresql instance

python app/enviroment.py prod

Run tests

On Docker

docker-compose exec queens-app pytest

or only

pytest

Ejecute coverage report

coverage run -m pytest
coverage report
coverage html

To develop

• Improve algorithm
• Create API (optional)
• Add production env
• Configure deploy

How to contribute

• See contributting file

https://github.com/eocode/Queens/blob/master/CONTRIBUTTING.md

License

View in https://github.com/eocode/Queens/blob/master/LICENSE