Sudoku Solver

A Sudoku solver using a backtracking algorithm.

About this project

Welcome to my very first project! It may not be the greatest, but here we have the start of my coding journey.

This Sudoku Solver is written in C++ and runs locally using JavaScript.

The project demonstrates the efficiency of backtracking in solving combinatorial problems.

Try the Sudoku Solver

C++ source code

#include <bits/stdc++.h>
using namespace std;

ifstream fin("sudoku.in");
ofstream fout("sudoku.out");

int a[9][9];

bool verif(int i, int j, int val) {
    for (int k = 0; k < 9; k++) {
        if (a[i][k] == val || a[k][j] == val) {
            return false;
        }
    }

    int k = i - (i % 3), l = j - (j % 3);
    for (int p = 0; p < 3; p++) {
        for (int q = 0; q < 3; q++) {
            if (a[k+p][l+q] == val) {
                return false;
            }
        }
    }

    return true;
}

bool solve(int i, int j) {
    if (i == 8 && j == 9) {
        return true;
    } if (j == 9) {
        return solve(i+1, 0);
    } if (a[i][j] > 0) {
        return solve(i, j+1);
    }

    for (int nr = 1; nr <= 9; nr++) {
        if (verif(i, j, nr)) {
            a[i][j] = nr;
            if(solve(i, j+1)) {
                return true;
            }
        }
        a[i][j] = 0;
    }

    return false;
}

int main() {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            fin >> a[i][j];
        }
    }

    if (solve(0, 0)) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                fout << a[i][j] << " ";
            }
            fout << "\n";
        }
    } else {
        fout << "Cannot be completed.";
    }

    exit(0);
}