Scribd
Upload
30 views2 pages

C Program

The document contains C++ code that defines a class X for solving Sudoku puzzles. Class X contains methods for checking if a number can be placed in a cell, recursively solving the puzzle, printing the solved puzzle, and a method k that is run by multiple threads to solve different parts of the puzzle in parallel.

Uploaded by

blackpanther00
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
30 views2 pages

C Program

The document contains C++ code that defines a class X for solving Sudoku puzzles. Class X contains methods for checking if a number can be placed in a cell, recursively solving the puzzle, printing the solved puzzle, and a method k that is run by multiple threads to solve different parts of the puzzle in parallel.

Uploaded by

blackpanther00
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd

#include <iostream>

#include <vector>
#include <thread>
#include <mutex>
#include <memory>
#include <condition_variable>

#define P 9

class X {
std::vector<std::vector<int>> z;
std::mutex m;
std::condition_variable cv;
bool solved;
public:
X(std::vector<std::vector<int>> w) : z(w), solved(false) {}

bool d(int q, int r, int s) {


for (int i = 0; i < P; ++i) {
if (z[q][i] == s || z[i][r] == s) return false;
}
int u = q - q % 3, v = r - r % 3;
for (int i = 0; i < 3; ++i)
for (int j = 0; j < 3; ++j)
if (z[i + u][j + v] == s) return false;
return true;
}

bool e(int q, int r) {


if (q == P - 1 && r == P) return true;
if (r == P) { ++q; r = 0; }
if (z[q][r] > 0) return e(q, r + 1);
for (int s = 1; s <= P; ++s) {
if (d(q, r, s)) {
z[q][r] = s;
if (e(q, r + 1)) return true;
}
z[q][r] = 0;
}
return false;
}

void f() {
for (const auto& g : z) {
for (int h : g) std::cout << h << " ";
std::cout << "\n";
}
}

void k(int n) {
std::unique_lock<std::mutex> lock(m);
for (int i = 0; i < P; ++i) {
for (int j = 0; j < P; ++j) {
if (z[i][j] == 0) {
for (int s = 1; s <= P; ++s) {
if (d(i, j, s)) {
z[i][j] = s;
if (e(i, j + 1)) {
solved = true;
cv.notify_all();
f();
return;
}
z[i][j] = 0;
}
}
return;
}
}
}
cv.notify_all();
}

void solve() {
std::vector<std::thread> threads;
for (int i = 0; i < 4; ++i) {
threads.push_back(std::thread(&X::k, this, i));
}

for (auto& th : threads) {


[Link]();
}
}
};

int main() {
std::vector<std::vector<int>> y = {
{5, 3, 0, 0, 7, 0, 0, 0, 0},
{6, 0, 0, 1, 9, 5, 0, 0, 0},
{0, 9, 8, 0, 0, 0, 0, 6, 0},
{8, 0, 0, 0, 6, 0, 0, 0, 3},
{4, 0, 0, 8, 0, 3, 0, 0, 1},
{7, 0, 0, 0, 2, 0, 0, 0, 6},
{0, 6, 0, 0, 0, 0, 2, 8, 0},
{0, 0, 0, 4, 1, 9, 0, 0, 5},
{0, 0, 0, 0, 8, 0, 0, 7, 9}
};

std::unique_ptr<X> x = std::make_unique<X>(y);
x->solve();

return 0;
}

You might also like