Si on se fesait un petit défi ?

Voila ma bafouille, en utilisant la récursion et des pointeurs

D'abord un utilitaire:

#include "Utilities.h"
#include <regex>

std::vector<std::string> split(std::string const& data, std::string const& token)
{
	std::regex rx{ "[^" + token + "]" };
	std::sregex_iterator it(data.begin(), data.end(), rx);
	std::sregex_iterator end;
	std::vector < std::string> out;
	while (it != end)
	{
		for (size_t i = 0; i < it->size(); ++i)
			out.push_back((*it)[i]);
		++it;
	}
	return out;
}

Suivit des classes:

#include<array>

class cells
{
private:
	std::array<unsigned char*, 9> mValues;
public:
	cells(std::array<unsigned char*, 9> const&);
	bool validate(unsigned char) const;
};

#include <set>

cells::cells(std::array<unsigned char*, 9> const& values):
	mValues{values}
{
}

bool cells::validate(unsigned char value) const
{
	std::set<unsigned char> uniqueValues;
	for (auto item : mValues)
	{
		if (*item != 0)
			uniqueValues.insert(*item);
	}
	return uniqueValues.insert(value).second;
}

#include <array>
#include <ostream>
#include <vector>
#include "Cells.h"

class grid
{
private:
	std::array<unsigned char, 81> mValues;
	std::array<cells, 9> mColumns;
	std::array<cells, 9> mRows;
	std::array<cells, 9> mSubGrids;
	bool checkColumn(size_t, unsigned char) const;
	bool checkRow(size_t, unsigned char) const;
	bool checkSubGrid(size_t, size_t, unsigned char) const;
	bool guess(size_t, size_t, unsigned char) const;
public:
	grid();
	unsigned char& value(size_t, size_t);
	unsigned char value(size_t, size_t) const;
	bool solve(size_t x = 0, size_t y = 0);
};

std::ostream& operator<<(std::ostream&, grid const&);
bool loadGridFromFile(std::string const&, grid&);
std::vector<unsigned char> readFile(std::string const&);

#include "grid.h"
#include <fstream>
#include <string>
#include <vector>
#include <iostream>
#include "Utilities.h"

grid::grid():
	mValues{0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0},
	mColumns{ cells{std::array<unsigned char*, 9>{&mValues[0], &mValues[9],  &mValues[18], &mValues[27], &mValues[36], &mValues[45], &mValues[54], &mValues[63], &mValues[72]}},
			  cells{std::array<unsigned char*, 9>{&mValues[1], &mValues[10], &mValues[19], &mValues[28], &mValues[37], &mValues[46], &mValues[55], &mValues[64], &mValues[73]}},
			  cells{std::array<unsigned char*, 9>{&mValues[2], &mValues[11], &mValues[20], &mValues[29], &mValues[38], &mValues[47], &mValues[56], &mValues[65], &mValues[74]}},
			  cells{std::array<unsigned char*, 9>{&mValues[3], &mValues[12], &mValues[21], &mValues[30], &mValues[39], &mValues[48], &mValues[57], &mValues[66], &mValues[75]}},
			  cells{std::array<unsigned char*, 9>{&mValues[4], &mValues[13], &mValues[22], &mValues[31], &mValues[40], &mValues[49], &mValues[58], &mValues[67], &mValues[76]}},
			  cells{std::array<unsigned char*, 9>{&mValues[5], &mValues[14], &mValues[23], &mValues[32], &mValues[41], &mValues[50], &mValues[59], &mValues[68], &mValues[77]}},
			  cells{std::array<unsigned char*, 9>{&mValues[6], &mValues[15], &mValues[24], &mValues[33], &mValues[42], &mValues[51], &mValues[60], &mValues[69], &mValues[78]}},
			  cells{std::array<unsigned char*, 9>{&mValues[7], &mValues[16], &mValues[25], &mValues[34], &mValues[43], &mValues[52], &mValues[61], &mValues[70], &mValues[79]}},
			  cells{std::array<unsigned char*, 9>{&mValues[8], &mValues[17], &mValues[26], &mValues[35], &mValues[44], &mValues[53], &mValues[62], &mValues[71], &mValues[80]}} },
	mRows{ cells{std::array<unsigned char*, 9>{&mValues[0],  &mValues[1],  &mValues[2],  &mValues[3],  &mValues[4],  &mValues[5],  &mValues[6],  &mValues[7],  &mValues[8]}},
		   cells{std::array<unsigned char*, 9>{&mValues[9],  &mValues[10], &mValues[11], &mValues[12], &mValues[13], &mValues[14], &mValues[15], &mValues[16], &mValues[17]}},
		   cells{std::array<unsigned char*, 9>{&mValues[18], &mValues[19], &mValues[20], &mValues[21], &mValues[22], &mValues[23], &mValues[24], &mValues[25], &mValues[26]}},
		   cells{std::array<unsigned char*, 9>{&mValues[27], &mValues[28], &mValues[29], &mValues[30], &mValues[31], &mValues[32], &mValues[33], &mValues[34], &mValues[35]}},
		   cells{std::array<unsigned char*, 9>{&mValues[36], &mValues[37], &mValues[38], &mValues[39], &mValues[40], &mValues[41], &mValues[42], &mValues[43], &mValues[44]}},
		   cells{std::array<unsigned char*, 9>{&mValues[45], &mValues[46], &mValues[47], &mValues[48], &mValues[49], &mValues[50], &mValues[51], &mValues[52], &mValues[53]}},
		   cells{std::array<unsigned char*, 9>{&mValues[54], &mValues[55], &mValues[56], &mValues[57], &mValues[58], &mValues[59], &mValues[60], &mValues[61], &mValues[62]}},
		   cells{std::array<unsigned char*, 9>{&mValues[63], &mValues[64], &mValues[65], &mValues[66], &mValues[67], &mValues[68], &mValues[69], &mValues[70], &mValues[71]}},
		   cells{std::array<unsigned char*, 9>{&mValues[72], &mValues[73], &mValues[74], &mValues[75], &mValues[76], &mValues[77], &mValues[78], &mValues[79], &mValues[80]}} },
	mSubGrids{ cells{std::array<unsigned char*, 9>{&mValues[0],  &mValues[1],  &mValues[2],  &mValues[9],  &mValues[10], &mValues[11], &mValues[18], &mValues[19], &mValues[20]}},
			   cells{std::array<unsigned char*, 9>{&mValues[3],  &mValues[4],  &mValues[5],  &mValues[12], &mValues[13], &mValues[14], &mValues[21], &mValues[22], &mValues[23]}},
			   cells{std::array<unsigned char*, 9>{&mValues[6],  &mValues[7],  &mValues[8],  &mValues[15], &mValues[16], &mValues[17], &mValues[24], &mValues[25], &mValues[26]}},
			   cells{std::array<unsigned char*, 9>{&mValues[27], &mValues[28], &mValues[29], &mValues[36], &mValues[37], &mValues[38], &mValues[45], &mValues[46], &mValues[47]}},
			   cells{std::array<unsigned char*, 9>{&mValues[30], &mValues[31], &mValues[32], &mValues[39], &mValues[40], &mValues[41], &mValues[48], &mValues[49], &mValues[50]}},
			   cells{std::array<unsigned char*, 9>{&mValues[33], &mValues[34], &mValues[35], &mValues[42], &mValues[43], &mValues[44], &mValues[51], &mValues[52], &mValues[53]}},
			   cells{std::array<unsigned char*, 9>{&mValues[54], &mValues[55], &mValues[56], &mValues[63], &mValues[64], &mValues[65], &mValues[72], &mValues[73], &mValues[74]}},
			   cells{std::array<unsigned char*, 9>{&mValues[57], &mValues[58], &mValues[59], &mValues[66], &mValues[67], &mValues[68], &mValues[75], &mValues[76], &mValues[77]}},
			   cells{std::array<unsigned char*, 9>{&mValues[60], &mValues[61], &mValues[62], &mValues[69], &mValues[70], &mValues[71], &mValues[78], &mValues[79], &mValues[80]}} }
{
}

bool grid::checkColumn(size_t x, unsigned char value) const
{
	return mColumns[x].validate(value);
}

bool grid::checkRow(size_t y, unsigned char value) const
{
	return mRows[y].validate(value);
}

bool grid::checkSubGrid(size_t x, size_t y, unsigned char value) const
{
	return mSubGrids[x + (y * 3)].validate(value);
}

bool grid::guess(size_t x, size_t y, unsigned char value) const
{
	return checkColumn(x, value) && checkRow(y, value) && checkSubGrid(x / 3, y / 3, value);
}

unsigned char& grid::value(size_t x, size_t y)
{
	return mValues[x + y * 9];
}

unsigned char grid::value(size_t x, size_t y) const
{
	return mValues[x + y * 9];
}

bool grid::solve(size_t x, size_t y)
{
		// Si la ligne est égale à 9,
		// tout est Ok
	if (y == 9)
		return true;
	if (value(x, y) != 0)
	{
			// si une valeur existe dans la case,
			// on passe à la suivante
		if (solve((x + 1) % 9, (x == 8 ? y + 1: y)))
			return true;
	}
	else
	{
			// essaye toutes les combinaisons
		for (unsigned char attempt = 1; attempt <= 9; ++attempt)
		{
			if (guess(x, y, attempt))
			{
					// valeur ok
					// passe à la suivante
				value(x, y) = attempt;
				if (solve((x + 1) % 9, (x == 8 ? y + 1 : y)))
					return true;
				else
						// valeur Ko
						// la re-initialise
					value(x, y) = 0;
			}
		}
	}
		// tous les essais ont échoués
	return false;
}

std::ostream& operator<<(std::ostream& s, grid const& g)
{
	for (size_t y = 0; y < 9; ++y)
	{
		if (y % 3 == 0)
			s << "|---+---+---|\n";
		s << "|";
		for (size_t x = 0; x < 9; ++x)
		{
			s << static_cast<unsigned>(g.value(x, y));
			if (x % 3 == 2)
				s << "|";
		}			
		s << "\n";
	}
	s << "|---+---+---|\n";
	return s;
}

bool loadGridFromFile(std::string const& path, grid& g)
{
	std::vector<unsigned char> data = readFile(path);
	if (data.size() > 0)
	{
		for (size_t y = 0; y < 9; ++y)
		{
			for (size_t x = 0; x < 9; ++x)
				g.value(x, y) = data[x + y * 9];
		}
		return true;
	}
	return false;
}

std::vector<unsigned char> readFile(std::string const& path)
{
	std::ifstream file{ path };
	std::string line;
	std::vector<unsigned char> data;
	while (std::getline(file, line))
	{
		std::vector<std::string> tempData = split(line, ";");
		for (auto item : tempData)
			data.push_back(std::stoi(item));
	}
	return data;
}

Enfin le point d'entrée:

#include <iostream>
include "grid.h"

int main(int argc, char** argv)
{
	if(argc <= 1)
	{ 
		std::cout << "No file input." << std::endl;
		return EXIT_SUCCESS;
	}
	grid g;
	if (loadGridFromFile(argv[1], g))
	{
		if (g.solve())
			std::cout << g << std::endl;
		else
			std::cout << "Invalid grid." << std::endl;
	}
	else
		std::cout << "Error reading file input.";
	return EXIT_SUCCESS;
}

Ce n'est peut être pas l'algo le plus efficace (ce n'est pas le but), je vous laisse critiquer la conception / l'approche.

PS: J'assume que le chemin du fichier d'entrée, et que le fichier d'entrée sont valides.

-
Edité par Deedolith 21 janvier 2019 à 14:23:28

Deedolith

16 janvier 2019 à 14:18:56

Ca fais longtemps que je n'en ai pas vu.

Je propose un solveur de sudoku en console.
Le programme prendra en ligne de commande le chemin d'un fichier csv contenant la grille à résoudre, c'est un fichier texte sans entêtes dont les champs de longueur variable sont séparés par des points virgules, comme l'exemple ci-dessous:

0;4;6;0;0;5;7;0;0
0;0;0;9;0;0;0;0;0
0;9;0;0;0;1;0;0;6
0;0;0;0;0;0;9;0;0
0;3;0;0;0;0;0;0;0
4;0;0;5;2;0;0;0;8
0;8;0;0;0;0;0;7;0
5;7;0;3;0;0;0;8;2
2;0;0;0;0;0;3;0;0

La valeur 0 indique qu'une case est vide.

Le programme devra afficher si la grille est valide, et si c'est le cas, afficher la solution trouvée.

A vos claviers.

lmghs

16 janvier 2019 à 15:16:27

Pas de suite, mais ça peut m'amuser oui -- d'ailleurs s'il y a des gens qui ont des idées pour améliorer mon solveur de ricochet robot, je suis preneur (https://github.com/LucHermitte/Rasende)

Pour avoir un peu survolé des forum dédiés, il y a plein d'astuces (patterns) dans la résolution des sudokus

Pour l'anecdote, Adam (moteur de contrainte d'Adobe qui accompagnait Eve avant que Qt se mette enfin au déclaratif (QML)) avait été détourné en solveur de Sudoku: https://github.com/stlab/adobe_source_libraries/tree/master/test/sudoku

-
Edité par lmghs 16 janvier 2019 à 15:17:04

20 janvier 2019 à 18:42:25

Pour le fun

Si on se fesait un petit défi ?

Supprimer

Modérer

Signaler le message aux modérateurs