Ce projet a pour objectif d'implémenter un générateur / solveur de grilles de sudoku. Ce projet permet de renforcer vos compétences en programmation orientée objets (POO) en manipulant des classes et en faisant des traitements récursifs.

Related tags

Miscellaneous Sudoku
Overview

TP6 C++ : Sudoku Solver

Membres du groupe

Sujet proposé par M. Ginhac (https://github.com/dginhac)

Introduction

Ce TP a pour but de générer des grilles de Sudoku de taille N avec 5 niveaux de difficulté. À l'aide d'un algorithme de "backtracking", nous devons résoudre ses différentes grilles de sudoku. Nous avons plutôt bien apprécié le premier TP que nous avons réalisé et nous aimons réaliser des défis, c'est pour cela que pour notre 2e TP, nous avons choisi le plus complexe.

Déroulement du TP

Pour ce projet, nous avons commencé par lister l'ensemble des tâches à réaliser puis nous nous sommes réparti le travail. Premièrement, une personne s'occupait du générateur pendant que l'autre réalisait les 3 tests pour vérifier si un nombre peut être dans une ligne, une colonne, ou un carré. Pour la réalisation du solveur, nous avons réfléchi à deux sur le même PC pour son implementation. Pour finir, une personne c'est chargé des niveaux de difficulté et une autre personne de la possibilité de choisir une taille de grille.

Problèmes rencontrés

À travers ce TP, nous avons rencontré plusieurs problèmes :

  • la majorité des grilles générées n'était pas résolvable, elles suivaient bien les règles pour qu'il n'y est pas deux fois le même chiffre dans la même ligne, dans la même colonne et dans la même case, mais bloquait a un moment car aucun chiffre ne pouvait être placer sur une case.
  • Pour générer une grille, nous devons d'abord résoudre une grille vide, puis enlever un certain nombre de cases suivant la difficulté demandé.
  • Pour la génération des grilles supérieures à 25*25 cases, le temps de résolution de la grille vide prend un temps exponentiel suivant le nombre de case et peut prendre plusieurs minutes. Cela vient sans doute de notre façon d'avoir implementer l'algorithme.

Exploitation des résultats

Grille 9*9

Nombres d'itérations pour une grille 9*9 : 112 - 129 - 127 - 86 - 217

On observe une moyenne d'itérations vers les 120 pour resoudre une grille vierge de sudoku 9*9.

Temps d'exécutions (en ms) : 2888 - 3609 - 4015 - 2969 - 7351

Le temps observé est environ proportionnel au nombre d'itérations nécessaires.

Le nombre d'itérations nécessaires étant en moyenne faible, le temps d'exécution est assez rapide.

Grille 16*16

Nombres d'itérations pour une grille 16*16 : 5992 - 1108 - 1786 - 4304 - 2691

Temps d'exécutions (en ms) : 159566 - 33083 - 49389 - 113593 - 81608

Le temps observé est environ proportionnel au nombre d'itérations nécessaires.

Le nombre d'itérations nécéssaires étant en moyenne faible, le temps d'exécution est assez rapide.

Comparer aux grilles 9*9, le nombre d'itérations et le temps nécessaires sont exponentiels. On en déduit une compléxité O(N^(n*n)) avec N la taille de la grille.

Grille 25*25

Nombres d'itérations pour une grille 25*25 : 5616267

Temps d'exécutions (en ms) : 169760379

Rendu final

Rendu d'un sudoku 9*9

alt text

Rendu d'un sudoku 16*16

alt text

Rendu d'un sudoku 25*25

alt text

Owner
Le trio de l'enfer
Le trio de l'enfer
défi pour maitrise bien les variables

challengeC Objectif Nous allons écrire des programmes C simples en utilisant les connaissances des types de données, des opérateurs, des fonctions pri

odin 4 Feb 13, 2022
Contains a sudoku solver - OCR. Project done with classmates during third semester at EPITA.

sudokUwU sudokUwU is a sudoku solver made by 4 students at EPITA. This project is a mandatory work from S3 cycle! The Team Johan Tran Adrian Grillet V

okywu 2 May 5, 2022
Tic-Tac-Toe, Scientific calculator, Sudoku solver written in C.

Simple command line projects in C: Tic-Tac-Toe - A computer Tic-Tac-Toe player. No algorithms used, simply written using too many if statements. Sudok

Kovvuri Sai Gopal Reddy 1 Dec 25, 2021
C++ Projekt für die implementation des Brettspiel Mühle auf der Konsole

CppMuhle C++ Projekt für die implementation des Brettspiel Mühle auf der Konsole Idee der Struktur Der Controller handelt jegliche Eingaben des Nutzer

DHBW Stuttgart - Campus Horb - INF2020 3 Mar 15, 2022
Ce repo contient des exemples de code metamorphiques (ActuSecu57).

Readme Ce repo contient l'ensemble des codes tester au sein de l'ActuSecu 57 consacrer au polymorphisme: https://www.xmco.fr/actu-secu/XMCO-ActuSecu-5

XMCO 3 Jan 30, 2022
dex-vm implementation, used to protect the classes.dex file

nmmp 基于dex-vm运行dalvik字节码从而对dex进行保护,增加反编译难度。 项目分为两部分nmm-protect是纯java项目,对dex进行转换,把dex里方法及各种数据转为c结构体,处理apk生成c项目,编译生成so,输出处理后的apk。nmmvm是一个安卓项目,包含dex-vm实现

mao 227 May 9, 2022
The AudioUnitSDK contains a set of base classes as well as utility sources required for Audio Unit development.

The AudioUnitSDK contains a set of base classes as well as utility sources required for Audio Unit development.

Apple 67 May 10, 2022
(R) Efficient methods and operators for the sparse matrix classes in 'Matrix' (esp. CSR format or "RsparseMatrix")

MatrixExtra MatrixExtra is an R package which extends the sparse matrix and sparse vector types in the Matrix package, particularly the CSR or Rsparse

null 12 Jan 5, 2022
Library of useful C++ snippets and reusable classes I've created as I build out Arduino Uno and ESP32 projects.

Arduino Snippets Library of useful C++ snippets and reusable classes I've created as I build out Arduino Uno and ESP32 projects. Button A simple butto

Max Lynch 7 Feb 5, 2022
Helper C++ classes to quickly preintegrate IMU measurements between SLAM keyframes

mola-imu-preintegration Integrator of IMU angular velocity readings. This repository provides: IMUIntegrator and RotationIntegrator: C++ classes to in

The MOLA SLAM framework 9 Feb 11, 2022
This is some utility functions/classes for having a nice way to communicate with a pico board RP2040

PicoScreenTerminal This is some utility functions/classes for having a nice way to communicate with a pico board RP2040 How to build First follow the

GuillaumeG. 4 Nov 15, 2021
Itpp - IT++ library mirror/fork. C++ library of mathematical, signal processing and communication classes and functions.

Introduction ************ IT++ is a C++ library of mathematical, signal processing and communication classes and functions. Its main use is in simula

null 18 Apr 9, 2022
The Synthesis ToolKit in C++ (STK) is a set of open source audio signal processing and algorithmic synthesis classes written in the C++ programming language.

The Synthesis ToolKit in C++ (STK) By Perry R. Cook and Gary P. Scavone, 1995--2021. This distribution of the Synthesis ToolKit in C++ (STK) contains

null 766 May 16, 2022
game-tools est un petit module C++ contenant des sous-programmes utiles pour développer des petits jeux s'exécutant dans un terminal.

game-tools est un petit module C++ contenant des sous-programmes utiles pour développer des petits jeux s'exécutant dans un terminal. Ce module met à disposition des fonctionnalités simples permettant d'effacer le terminal, de mettre le programme en pause, d'afficher des éléments en couleur ou encore de générer un nombre entier aléatoire.

Tom Planche 4 Mar 1, 2022
For C++, help generate a default operator for classes whose components (base classes, data members) have the operator. Hideously intrusive.

C-plus-plus-library-default-operators Helps generate a default operator / member function for classes whose components (base classes, data members) ha

Walt Karas 2 Jul 25, 2018
Repo commun pour l'arcade toulouse promo 2024

Arcade (Promo Toulouse 2024) Pour proposer un changement / débattre sur github, suivez ce tutoriel. Les fichiers sources dont vous aurez besoin pour l

Pebloop 10 Jan 12, 2022
Creation of a sudoku in a terminal with the C language.

hack-fest-2021-sudoku Creation of a sudoku in a terminal with the C language. Genesis The idea of creating this project is multiple : first of all, I

null 1 Oct 19, 2021
A Sudoku solver made in C++ using SDL for graphics.

sudoku_solver A Sudoku solver made in C++ using SDL for graphics. What is a Sudoku puzzle? Sudoku puzzles have been around for a very long time, origi

null 1 Nov 12, 2021
C implementation of a sudoku solver with backtracking algorithm

SUDOKU SOLVER Sudoku solver using backtracking algorithm Sudoku game To solve a sudoku, you need a sudoku. So i made a basic implmentation of one with

Jonas STIRNEMANN 2 Mar 23, 2022
défi pour maitrise bien les variables

challengeC Objectif Nous allons écrire des programmes C simples en utilisant les connaissances des types de données, des opérateurs, des fonctions pri

odin 4 Feb 13, 2022
Un petit client/serveur TCP pour transférer d'image en C

MIMAGE Project Guide de démarage Prérequis Être sur un environement Linux et avoir le compilateur GCC et makefile d'installé. Installation Pour build

MrSolarius 4 Dec 21, 2021
Programme pour effectuer une régression linéaire, régression exponentielle et régression puissance en C

Régression Linéaire et Exponentielle et Puissance En C Programme pour effectuer une régression linéaire, régression exponentielle et régression puissa

Malik Makkes 1 Mar 26, 2022
Contains a sudoku solver - OCR. Project done with classmates during third semester at EPITA.

sudokUwU sudokUwU is a sudoku solver made by 4 students at EPITA. This project is a mandatory work from S3 cycle! The Team Johan Tran Adrian Grillet V

okywu 2 May 5, 2022
Tic-Tac-Toe, Scientific calculator, Sudoku solver written in C.

Simple command line projects in C: Tic-Tac-Toe - A computer Tic-Tac-Toe player. No algorithms used, simply written using too many if statements. Sudok

Kovvuri Sai Gopal Reddy 1 Dec 25, 2021
C++ Projekt für die implementation des Brettspiel Mühle auf der Konsole

CppMuhle C++ Projekt für die implementation des Brettspiel Mühle auf der Konsole Idee der Struktur Der Controller handelt jegliche Eingaben des Nutzer

DHBW Stuttgart - Campus Horb - INF2020 3 Mar 15, 2022
Ce repo contient des exemples de code metamorphiques (ActuSecu57).

Readme Ce repo contient l'ensemble des codes tester au sein de l'ActuSecu 57 consacrer au polymorphisme: https://www.xmco.fr/actu-secu/XMCO-ActuSecu-5

XMCO 3 Jan 30, 2022
Ce projet est clair et efficace. Vous devez recoder printf.

Ce projet est clair et efficace. Vous devez recoder printf. Avec un peu de chance, vous serez en mesure de le réutiliser dans des projets futurs sans la crainte d’être considéré comme un tricheur. Vous apprendrez principalement à utiliser les arguments variadiques.

REDA JAANIT 4 Dec 24, 2021
Petit projet visant à réaliser un jeu Bomberman sous OpenGL en C++

Bomberman sous OpenGL A propos Petit projet visant à réaliser un jeu Bomberman sous OpenGL en C++ (fig. 1 - Bomberman World) Modalité de réalisation L

Mohammad KHADDAN 3 Apr 15, 2022
The DirectX Tool Kit (aka DirectXTK) is a collection of helper classes for writing DirectX 11.x code in C++

DirectX Tool Kit for DirectX 11 http://go.microsoft.com/fwlink/?LinkId=248929 Copyright (c) Microsoft Corporation. All rights reserved. January 9, 202

Microsoft 2k May 12, 2022