/* A recursive Sudoku solver in C++ Copyright (C) 2013 Marc St-Jacques This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see . */ #include #include #include #include using namespace std; #define MAX 81 vector grid; // This is a stencil of all boxes positions in the grid. vector boxes { 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 3, 3, 3, 4, 4, 4, 5, 5, 5, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 6, 6, 6, 7, 7, 7, 8, 8, 8, 6, 6, 6, 7, 7, 7, 8, 8, 8, }; // A simple data reader: ASCII-based data from 1 to 9, whitespace separated, // up to v.size() characters (a sudoku grid has 81 values). You can either put // '0' or '.' to represent an empty cell. istream& operator >> (istream& iss, vector& v) { for (int i=0; i> x; if (x == '.') v[i] = 0; else v[i] = (int)(x - '0'); } return iss; } // Check if a vector has all unique numbers in the vector (but ignore zeros) bool uniq(const vector& vect) { bitset<9> mybits; for (int i=0; i<9; i++) { int val = vect[i]; // If value is 0 (empty), ignore if (val) { // If number is already found in the vector, uniqueness test failed. if (mybits.test(val-1)) return false; // Set number mybits.set(val-1); } } return true; } // Given a vector of grid positions, store values of said positions in a vector // and validate uniqueness of values. bool Check(vector pos) { vector vect; for (int i=0; i& v) { for (int i=0; i is located. bool CheckHorz(int i) { int j = i/9*9; // row starting at no. j int k = j+9; // row ending at no. k vector pos; while (j < k) pos.push_back(j++); return Check(pos); } // Check the values of the column where is located. bool CheckVert(int i) { int j = i%9; // column starting at no. j vector pos; while (j < MAX) { pos.push_back(j); j+=9; } return Check(pos); } // Check the values of the box where is located. bool CheckBox(int i) { int box = boxes[i]; // Get box no. at location i vector pos; for (int j=0; j is the current cell no // in the grid. void Solve(int i) { // If we reach this, this means the sudoku was solved. if (i == MAX) { PrintGrid(grid); exit(0); } // If cell already has a value, go to next cell if (grid[i]) Solve(i+1); else { // We will iterate through all numbers and set the current grid with this value. // If it passes all tests, we will recurse to the next cell. // If not, we simply set the cell back to and go back to the previous cell. for (int j=1; j<=9; j++) { grid[i] = j; if (CheckBox(i) && CheckVert(i) && CheckHorz(i)) Solve(i+1); } // Set to empty. grid[i] = 0; } } int main(int argc, char **argv) { if (argc < 2) { cerr << "Usage: " << argv << " " << endl; return 1; } // Open file: the first parameter is the filename ifstream ifs(argv); if (!ifs) { cerr << "Could not read data file '" << argv << "'" << endl; return 1; } // Resize grid and read from file up to MAX values to grid. grid.resize(MAX); ifs >> grid; Solve(0); // Program should abort at the 81'st recursion. // If it comes back to here, something went wrong. cerr << "Sudoku resolving failed." << endl; return 1; }