Sudoku solving solution in C++

The class of Sudoku puzzles consists of a partially completed row-column grid of cells partitioned into N regions or zones each of size N cells, to be filled in using a prescribed set of N distinct symbols (typically the numbers {1, …, N}), so that each row, column and region contains exactly one of each element of the set. The puzzle can be solved using a variety of algorithms. Couple of solutions I referred are Here and excellent article by Peter Norvig can be found here. A completed Sudoku grid is a special type of Latin square with the additional property of no repeated values in any of the 9 blocks of contiguous 3×3 cells. The general problem of solving Sudoku puzzles on n2 x n2 boards of n x n blocks is known to be NP-complete. This gives some indication of why Sudoku is difficult to solve, although on boards of finite size the problem is finite and can be solved by a deterministic finite automaton that knows the entire game tree.
I have solved the puzzle using C++, but I found another interesting solution which is done in only 3 lines. See Sudoku solver in three lines explained.
Program expect Sudoku puzzle grid in following format

000075400000000008080190000300001060000000034000068170204000603900000020530200000

where 0 represent the space to insert a new solution number.
Source Code:

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <sstream>
#include <set>
#include <algorithm>
#include <iterator>
#include <iomanip>
#include "Timer.h"
bool same_row ( int row, int col ) {
    return ( (row / 9 )== (col / 9 ));
}
bool same_col(int row, int col ) {
    return (((row - col) % 9) == 0);
}
bool same_block(int row, int col) {
    return ( (((row/27) == (col/27)))&&(((row % 9)/3) == ((col % 9)/3)));
}
void solve_r(std::vector<int> data) {
    std::vector<int>::iterator found = std::find(data.begin(), data.end(), 0);
    if ( found == data.end()) {
        std::cout << "---+---+---+---+---+---+---+---+---+" << std::endl;
        int limit = 0;
        for ( std::vector<int>::iterator itr = data.begin(); itr != data.end(); ++itr) {
            std::cout << std::setw(3) << *itr  << "|" ;
            if ( limit == 8 ){
                std::cout << std::endl;
                std::cout << "---+---+---+---+---+---+---+---+---+" << std::endl;
                limit  = 0;
            } else {
                limit++;
            }
        }
        std::cout << std::endl << std::endl;
        return;
    }
    int i = (int)(found - data.begin());
    std::set<int> excluded_numbers;
    for ( int j = 0; j < 81; j++) {
        if ( same_row(i,j) || same_col(i,j) || same_block(i,j)) {
            excluded_numbers.insert(data[j]);
        }
    }
    for ( int m = 1; m <= 9; m++) {
        std::set<int>::iterator found = excluded_numbers.find(m);
        if ( found == excluded_numbers.end()) {
            data[i] = m;
            solve_r(data);
        }
    }
}
int main( int argc, char** argv) {
    std::ifstream inFile(argv[1]);
    if(!inFile) {
        exit ( 0 );
    }
    std::vector<int> data;
    std::string str = "";
    while(std::getline(inFile, str)) {
        data.clear();
        for ( std::string::iterator itr = str.begin(); itr != str.end(); ++itr) {
            std::string s;
            s.push_back(*itr);
            std::stringstream ss(s);
            int i = 0;
            ss >> i;
            data.push_back(i);
        }
        Timer t("Solving");
        solve_r(data);
        t.stop();
    }
}

Download code from Here
Ouput and Time taken for various size puzzles:
Solution for 45 number Suduku puzzle :
Input

001700509573024106800501002700295018009400305652800007465080071000159004908007053

Output:

avinash@avinash-laptop:~/work/suduko$ ./suduko 45.inp 
---+---+---+---+---+---+---+---+---+
  2|  4|  1|  7|  6|  8|  5|  3|  9|
---+---+---+---+---+---+---+---+---+
  5|  7|  3|  9|  2|  4|  1|  8|  6|
---+---+---+---+---+---+---+---+---+
  8|  9|  6|  5|  3|  1|  7|  4|  2|
---+---+---+---+---+---+---+---+---+
  7|  3|  4|  2|  9|  5|  6|  1|  8|
---+---+---+---+---+---+---+---+---+
  1|  8|  9|  4|  7|  6|  3|  2|  5|
---+---+---+---+---+---+---+---+---+
  6|  5|  2|  8|  1|  3|  4|  9|  7|
---+---+---+---+---+---+---+---+---+
  4|  6|  5|  3|  8|  2|  9|  7|  1|
---+---+---+---+---+---+---+---+---+
  3|  2|  7|  1|  5|  9|  8|  6|  4|
---+---+---+---+---+---+---+---+---+
  9|  1|  8|  6|  4|  7|  2|  5|  3|
---+---+---+---+---+---+---+---+---+
  Solving
  -------------------------------
  User CPU Time  : 0 s
  System CPU Time: 0 s
  Wait Time      : 0.001 s
  -------------------------------
  Elapsed Time   : 0.001 s

avinash@avinash-laptop:~/work/suduko$ cat 40.inp 
096040001100060004504810390007950043030080000405023018010630059059070830003590007
avinash@avinash-laptop:~/work/suduko$ ./suduko 40.inp 
---+---+---+---+---+---+---+---+---+
  3|  9|  6|  2|  4|  5|  7|  8|  1|
---+---+---+---+---+---+---+---+---+
  1|  7|  8|  3|  6|  9|  5|  2|  4|
---+---+---+---+---+---+---+---+---+
  5|  2|  4|  8|  1|  7|  3|  9|  6|
---+---+---+---+---+---+---+---+---+
  2|  8|  7|  9|  5|  1|  6|  4|  3|
---+---+---+---+---+---+---+---+---+
  9|  3|  1|  4|  8|  6|  2|  7|  5|
---+---+---+---+---+---+---+---+---+
  4|  6|  5|  7|  2|  3|  9|  1|  8|
---+---+---+---+---+---+---+---+---+
  7|  1|  2|  6|  3|  8|  4|  5|  9|
---+---+---+---+---+---+---+---+---+
  6|  5|  9|  1|  7|  4|  8|  3|  2|
---+---+---+---+---+---+---+---+---+
  8|  4|  3|  5|  9|  2|  1|  6|  7|
---+---+---+---+---+---+---+---+---+
  Solving
  -------------------------------
  User CPU Time  : 0 s
  System CPU Time: 0 s
  Wait Time      : 0.001 s
  -------------------------------
  Elapsed Time   : 0.001 s
avinash@avinash-laptop:~/work/suduko$ cat 35.inp 
290500007700000400004738012902003064800050070500067200309004005000080700087005109
avinash@avinash-laptop:~/work/suduko$ ./suduko 35.inp 
---+---+---+---+---+---+---+---+---+
  2|  9|  3|  5|  4|  1|  6|  8|  7|
---+---+---+---+---+---+---+---+---+
  7|  1|  8|  2|  9|  6|  4|  5|  3|
---+---+---+---+---+---+---+---+---+
  6|  5|  4|  7|  3|  8|  9|  1|  2|
---+---+---+---+---+---+---+---+---+
  9|  7|  2|  8|  1|  3|  5|  6|  4|
---+---+---+---+---+---+---+---+---+
  8|  4|  6|  9|  5|  2|  3|  7|  1|
---+---+---+---+---+---+---+---+---+
  5|  3|  1|  4|  6|  7|  2|  9|  8|
---+---+---+---+---+---+---+---+---+
  3|  6|  9|  1|  7|  4|  8|  2|  5|
---+---+---+---+---+---+---+---+---+
  1|  2|  5|  3|  8|  9|  7|  4|  6|
---+---+---+---+---+---+---+---+---+
  4|  8|  7|  6|  2|  5|  1|  3|  9|
---+---+---+---+---+---+---+---+---+
  Solving
  -------------------------------
  User CPU Time  : 0 s
  System CPU Time: 0 s
  Wait Time      : 0.001 s
  -------------------------------
  Elapsed Time   : 0.001 s
avinash@avinash-laptop:~/work/suduko$ cat 30.inp 
370000001000700005408061090000010000050090460086002030000000000694005203800149500
avinash@avinash-laptop:~/work/suduko$ ./suduko 30.inp 
---+---+---+---+---+---+---+---+---+
  3|  7|  5|  9|  8|  4|  6|  2|  1|
---+---+---+---+---+---+---+---+---+
  1|  6|  9|  7|  2|  3|  8|  4|  5|
---+---+---+---+---+---+---+---+---+
  4|  2|  8|  5|  6|  1|  3|  9|  7|
---+---+---+---+---+---+---+---+---+
  9|  4|  3|  6|  1|  8|  7|  5|  2|
---+---+---+---+---+---+---+---+---+
  2|  5|  1|  3|  9|  7|  4|  6|  8|
---+---+---+---+---+---+---+---+---+
  7|  8|  6|  4|  5|  2|  1|  3|  9|
---+---+---+---+---+---+---+---+---+
  5|  1|  7|  2|  3|  6|  9|  8|  4|
---+---+---+---+---+---+---+---+---+
  6|  9|  4|  8|  7|  5|  2|  1|  3|
---+---+---+---+---+---+---+---+---+
  8|  3|  2|  1|  4|  9|  5|  7|  6|
---+---+---+---+---+---+---+---+---+
  Solving
  -------------------------------
  User CPU Time  : 0 s
  System CPU Time: 0 s
  Wait Time      : 0.001 s
  -------------------------------
  Elapsed Time   : 0.001 s
avinash@avinash-laptop:~/work/suduko$ cat 25.inp 
000075400000000008080190000300001060000000034000068170204000603900000020530200000
avinash@avinash-laptop:~/work/suduko$ ./suduko 25.inp 
---+---+---+---+---+---+---+---+---+
  6|  9|  3|  8|  7|  5|  4|  1|  2|
---+---+---+---+---+---+---+---+---+
  1|  4|  5|  6|  3|  2|  7|  9|  8|
---+---+---+---+---+---+---+---+---+
  7|  8|  2|  1|  9|  4|  3|  5|  6|
---+---+---+---+---+---+---+---+---+
  3|  5|  7|  4|  2|  1|  8|  6|  9|
---+---+---+---+---+---+---+---+---+
  8|  1|  6|  9|  5|  7|  2|  3|  4|
---+---+---+---+---+---+---+---+---+
  4|  2|  9|  3|  6|  8|  1|  7|  5|
---+---+---+---+---+---+---+---+---+
  2|  7|  4|  5|  1|  9|  6|  8|  3|
---+---+---+---+---+---+---+---+---+
  9|  6|  8|  7|  4|  3|  5|  2|  1|
---+---+---+---+---+---+---+---+---+
  5|  3|  1|  2|  8|  6|  9|  4|  7|
---+---+---+---+---+---+---+---+---+
  Solving
  -------------------------------
  User CPU Time  : 0.1 s
  System CPU Time: 0.01 s
  Wait Time      : 0.01 s
  -------------------------------
  Elapsed Time   : 0.12 s
Advertisements

2 thoughts on “Sudoku solving solution in C++

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s