sudoku.cpp

// Copyright (C) 2011 by Dirk Gadsden
// 
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
// 
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
// 
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.


#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <vector>


// Basic vector types used throughout (SCVector is the multidimensional vector used
// to hold the board, IVECTOR is a vector of integers).
#define SCVECTOR vector< vector< SCell > >
#define IVECTOR  vector<int>


using namespace std;


// Vector comparison methods
IVECTOR vector_difference(IVECTOR a, IVECTOR b) {
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    
    IVECTOR diff(9);
    IVECTOR::iterator iter;
    iter = set_difference(a.begin(), a.end(), b.begin(), b.end(), diff.begin());
    
    IVECTOR diff_gt_zero;
    for(int i = 0; i < diff.size(); i++) {
        if(diff[i] > 0) {
            diff_gt_zero.push_back(diff[i]);
        }
    }
    return diff_gt_zero;
}
IVECTOR vector_intersection(IVECTOR a, IVECTOR b) {
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    
    IVECTOR intsct(9);
    IVECTOR::iterator iter;
    iter = set_intersection(a.begin(), a.end(), b.begin(), b.end(), intsct.begin());
    
    IVECTOR intsct_gt_zero;
    for(int i = 0; i < intsct.size(); i++) {
        if(intsct[i] > 0) {
            intsct_gt_zero.push_back(intsct[i]);
        }
    }
    return intsct_gt_zero;
}

// Utility method
bool vector_include(IVECTOR v, int val) {
    for(int i = 0; i < v.size(); i++) {
        if(v[i] == val) {
            return true;
        }
    }
    return false;
}


// This could possibly be a struct.
class SCell {
public:
    unsigned int index, row, column, value;
    IVECTOR options;
    
    SCell(unsigned int a_index, unsigned int a_row, unsigned int a_column, unsigned int a_value) {
        index = a_index; row = a_row; column = a_column; value = a_value;
    }
    
    void inspect() {
        std::cout << (unsigned int)row << "," << (unsigned int)column << "," << (unsigned int)value;
        std::cout << "OPTS: ";
        for(int i = 0; i < options.size(); i++) {
            std::cout << options[i] << ", ";
        }
        std::cout << "\n";
        
    }
};


class SBoard {
public:
    SCVECTOR board;
    
    // Set up the board
    SBoard(unsigned int a_board[9][9]) {
        int index = 0;
        board.resize(9);
        for(int r = 0; r < 9; r++) {
            // Throws a weird error, using push_back instead.
            //board[r].resize(9);
            for(int c = 0; c < 9; c++) {
                SCell cell(index, r, c, a_board[r][c]);
                board[r].push_back(cell);
                index++;
            }
        }
    }
    
    // Check for all values filled (not zero).
    bool solved() {
        bool unsolved = false;
        for(int r = 0; r < 9; r++) {
            for(int c = 0; c < 9; c++) {
                SCell *cell = &board[r][c];
                if(cell->value == 0) {
                    unsolved = true;
                }
            }
        }
        return !unsolved;
    }
    
    // Check for a cell with no options and no existing value.
    bool unsolvable() {
        for(int r = 0; r < 9; r++) {
            for(int c = 0; c < 9; c++) {
                SCell *cell = &board[r][c];
                if(cell->options.size() == 0 && cell->value == 0) {
                    return true;
                }
            }
        }
        return false;
    }
    
    // Attempt a recursive solution.
    bool solve() {
        std::cout << "Initial board (" << &board << "):\n";
        inspect();
        std::cout << "\n\n";
        
        // Figure out the ones we know
        //std::cout << "Calculating options:\n";
        determine_available();
        
        // Check if a solution has been found.
        if(solved()) {
            std::cout << "\n\n\nSOLVED:\n";
            inspect();
            exit(1);
            return true;
            
        }
        
        // If this attempt is a failure, log that failure and return.
        // (So that if there's a higher nest it will continue to the next option.)
        if(unsolvable()) {
            std::cout << "\n\n\nHIT UNSOLVABLE\n";
            inspect();
            return false;
        }
        
        // Find the first unsolved cell (value is zero).
        SCell *first_unsolved;
        bool found = false;
        for(int r = 0; r < 9; r++) {
            for(int c = 0; c < 9; c++) {
                SCell *cell = &board[r][c];
                if(cell->value == 0) {
                    first_unsolved = cell;
                    found = true;
                    break;
                }
            }
            if(found) { break; }
        }
        
        // If there are no options available.
        if(first_unsolved->options.size() == 0) {
            std::cout << "UNSOLVABLE\n";
            inspect();
        } else {
            // Iterate through the options.
            for(int i = 0; i < first_unsolved->options.size(); i++) {
                std::cout << "\nNest to " << &board << "...\n";
                // Create a new board, fill in the unsolved cell with the option, then try to solve that board.
                SBoard n = dup();
                n.board[first_unsolved->row][first_unsolved->column].value = first_unsolved->options[i];
                n.solve();
            }
        }
        
        return false;
    }
    
    // Inspection utility method.
    IVECTOR special_options_for_cell(int r, int c) {
        SCell *cell = &board[r][c];
        IVECTOR row = available_in_row(r);
        IVECTOR column = available_in_column(c);
        IVECTOR square = available_in_square(r / 3, c / 3);
        
        std::cout << "\nROW:";
        for(int n = 0; n < row.size(); n++) {
            std::cout << row[n] << ",";
        }
        
        std::cout << "\nCOLUMN:";
        for(int n = 0; n < column.size(); n++) {
            std::cout << column[n] << ",";
        }
        
        std::cout << "\nSQUARE:";
        for(int n = 0; n < square.size(); n++) {
            std::cout << square[n] << ",";
        }
        
        IVECTOR first_options = vector_intersection(available_in_row(r), available_in_column(c));
        IVECTOR second_options = vector_intersection(first_options, available_in_square(r / 3, c / 3));
        IVECTOR self_options;
        self_options.push_back(cell->value);
        IVECTOR final = vector_difference(second_options, self_options);
        
        std::cout << "\nFINAL:";
        for(int n = 0; n < final.size(); n++) {
            std::cout << final[n] << ",";
        }
        
        return final;
    }
    
    IVECTOR options_for_cell(int r, int c) {
        //std::cout << "Checking options on " << &board << "...\n";
        SCell *cell = &board[r][c];
        // Find the options for the row and column
        IVECTOR first_options = vector_intersection(available_in_row(r), available_in_column(c));
        // Combine that with the options for the 3x3 square it's in
        IVECTOR second_options = vector_intersection(first_options, available_in_square(r / 3, c / 3));
        // Remove the current value (if it's set, this may be extraneous).
        IVECTOR self_options;
        self_options.push_back(cell->value);
        return vector_difference(second_options, self_options);
    }
    
    bool determine_available() {
        for(int r = 0; r < 9; r++) {
            for(int c = 0; c < 9; c++) {
                SCell *cell = &board[r][c];
                
                IVECTOR options = options_for_cell(r, c);
                cell->options = options;
                
                // If there is one determined option and the cell has not already been filled.
                if(options.size() == 1 && cell->value == 0) {
                    //special_options_for_cell(r, c);
                    std::cout << "Bingo! (" << r << "," << c << ") > " << options[0] << " on " << &board << "\n";
                    
                    board[r][c].value = options[0];
                    return determine_available();
                }
            }
        }
        return false;
    }
    
    
    // Self-explanatory methods for figuring out available things in rows, columns, and squares.
    
    IVECTOR all_possible_items() {
        IVECTOR all_items;
        for(int o = 1; o <= 9; o++) {
            all_items.push_back(o);
        }
        return all_items;
    }
    
    IVECTOR available_in_square(int sr, int sc) {
        int bsr = sr * 3;
        int bsc = sc * 3;
        IVECTOR all_items = all_possible_items();
        IVECTOR taken_items;
        for(int r = bsr; r < (bsr + 3); r++) {
            for(int c = bsc; c < (bsc + 3); c++) {
                SCell *cell = &board[r][c];
                if(cell->value != 0) {
                    taken_items.push_back(cell->value);
                }
            }
        }
        
        return vector_difference(all_items, taken_items);
    }
    
    IVECTOR taken_in_row(int r) {
        IVECTOR taken_items;
        for(int c = 0; c < 9; c++) {
            SCell *cell = &board[r][c];
            if(cell->value != 0) {
                taken_items.push_back(cell->value);
            }
        }
        return taken_items;
    }
    IVECTOR available_in_row(int r) {
        IVECTOR all_items   = all_possible_items();
        IVECTOR taken_items = taken_in_row(r);
        return vector_difference(all_items, taken_items);
    }
    IVECTOR taken_in_column(int c) {
        IVECTOR taken_items;
        for(int r = 0; r < 9; r++) {
            SCell *cell = &board[r][c];
            if(cell->value != 0) {
                taken_items.push_back(cell->value);
            }
        }
        return taken_items;
    }
    IVECTOR available_in_column(int c) {
        IVECTOR all_items   = all_possible_items();
        IVECTOR taken_items = taken_in_column(c);
        return vector_difference(all_items, taken_items);
    }
    
    
    
    
    // Print out the board.
    void inspect() {
        for(int r = 0; r < 9; r++) {
            for(int c = 0; c < 9; c++) {
                SCell *cell = &board[r][c];
                std::cout << cell->value;
                
                if(c != 8) {
                    std::cout << ", ";
                } else { std::cout << "\n"; }
            }
        }
    }
    
    // Copy the board (used for the recursive solving).
    SBoard dup() {
        // New blank board array
        unsigned int new_board[9][9] = {
            {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}
        };
        
        // Copying the cells into the board array.
        for(int r = 0; r < 9; r++) {
            for(int c = 0; c < 9; c++) {
                SCell *cell = &board[r][c];
                new_board[r][c] = (unsigned int)cell->value;
            }
        }
        // Initialize a new object using the board array and return that.
        return SBoard(new_board);
    }
};





int main (int argc, const char * argv[]) {
    
    // Trying things out.
    
    
    unsigned int input_board[9][9] = {
        {0, 0, 0,   7, 0, 4,   0, 0, 5},
        {0, 2, 0,   0, 1, 0,   0, 7, 0},
        {0, 0, 0,   0, 8, 0,   0, 0, 2},
        
        {0, 9, 0,   0, 0, 6,   2, 5, 0},
        {6, 0, 0,   0, 7, 0,   0, 0, 8},
        {0, 5, 3,   2, 0, 0,   0, 1, 0},
        
        {4, 0, 0,   0, 9, 0,   0, 0, 0},
        {0, 3, 0,   0, 6, 0,   0, 9, 0},
        {2, 0, 0,   4, 0, 7,   0, 0, 0}
    };
    
    
    /*unsigned int input_board[9][9] = {
        {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}
    };
    unsigned int input_board[9][9] = {
        {0, 0, 0, 1, 0, 5, 0, 0, 0},
        {1, 4, 0, 0, 0, 0, 6, 7, 0},
        {0, 8, 0, 0, 0, 2, 4, 0, 0},
        {0, 6, 3, 0, 7, 0, 0, 1, 0},
        {9, 0, 0, 0, 0, 0, 0, 0, 3},
        {0, 1, 0, 0, 9, 0, 5, 2, 0},
        {0, 0, 7, 2, 0, 0, 0, 8, 0},
        {0, 2, 6, 0, 0, 0, 0, 3, 5},
        {0, 0, 0, 4, 0, 9, 0, 0, 0}
    };
    unsigned int input_board[9][9] = {
        {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}
    };
    unsigned int input_board[9][9] = {
        {6, 7, 2, 1, 4, 5, 3, 9, 8},
        {1, 4, 5, 0, 0, 0, 6, 7, 2},
        {3, 8, 9, 7, 6, 2, 4, 5, 1},
        {2, 6, 3, 5, 7, 4, 8, 1, 9},
        {9, 5, 8, 6, 2, 1, 7, 4, 3},
        {0, 0, 0, 0, 0, 0, 0, 0, 0},
        {5, 9, 7, 2, 3, 0, 1, 8, 4},
        {4, 2, 6, 8, 1, 7, 9, 3, 5},
        {0, 0, 0, 0, 0, 0, 0, 0, 0}
    };*/
    
    SBoard board(input_board);
    board.solve();
    
    return 0;
}