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

• 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

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

• 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)

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

• Brute force
• Minimum conflict
• Memorization
• Backtracking

Test algorithm with n boards > 8

Time in minutes

Time in minutes

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

• 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

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

• Coverage > 85%

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 .

You can clone this repository

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

Rename .env.example to .env file

And add your configuration

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

If you want to install the app use

python setup.py develop

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

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

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

On Docker

docker-compose exec queens-app pytest

or only

pytest

coverage run -m pytest
coverage report
coverage html

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

• See contributting file

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

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