Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Sudoku Solver In C++

DZone's Guide to

Sudoku Solver In C++

·
Free Resource
This is a complete implementation of a Sudoku solving programme. It reads a 9x9 matrix of ints from a text file (specified in main), and prints the completed board to stdout.

The input file should look like:
BEGIN sudoku.in
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
END sudoku.in

Full explanation: here


#include 
  
   
#include 
   
    

using namespace std;

class SudokuBoard;
void printB(SudokuBoard sb);

typedef unsigned int uint;

const uint MAXVAL = 9;
const uint L = 9;
const uint C = 9;
const uint S = L * C;
const uint ZONEL = 3;
const uint ZONEC = 3;
const uint ZONES = ZONEL * ZONEC;

const uint lineElements[L][C] = {
    { 0,  1,  2,  3,  4,  5,  6,  7,  8},
    { 9, 10, 11, 12, 13, 14, 15, 16, 17},
    {18, 19, 20, 21, 22, 23, 24, 25, 26},
    {27, 28, 29, 30, 31, 32, 33, 34, 35},
    {36, 37, 38, 39, 40, 41, 42, 43, 44},
    {45, 46, 47, 48, 49, 50, 51, 52, 53},
    {54, 55, 56, 57, 58, 59, 60, 61, 62},
    {63, 64, 65, 66, 67, 68, 68, 70, 71},
    {72, 73, 74, 75, 76, 77, 78, 79, 80}
};

const uint columnElements[C][L] = {
    { 0,  9, 18, 27, 36, 45, 54, 63, 72},
    { 1, 10, 19, 28, 37, 46, 55, 64, 73},
    { 2, 11, 20, 29, 38, 47, 56, 65, 74},
    { 3, 12, 21, 30, 39, 48, 57, 66, 75},
    { 4, 13, 22, 31, 40, 49, 58, 67, 76},
    { 5, 14, 23, 32, 41, 50, 59, 68, 77},
    { 6, 15, 24, 33, 42, 51, 60, 69, 78},
    { 7, 16, 25, 34, 43, 52, 61, 70, 79},
    { 8, 17, 26, 35, 44, 53, 62, 71, 80}
};

const uint zoneElements[S / ZONES][ZONES] = {
    { 0,  1,  2,  9, 10, 11, 18, 19, 20},
    { 3,  4,  5, 12, 13, 14, 21, 22, 23},
    { 6,  7,  8, 15, 16, 17, 24, 25, 26},
    {27, 28, 29, 36, 37, 38, 45, 46, 47},
    {30, 31, 32, 39, 40, 41, 48, 49, 50},
    {33, 34, 35, 42, 43, 44, 51, 52, 53},
    {54, 55, 56, 63, 64, 65, 72, 73, 74},
    {57, 58, 59, 66, 67, 68, 75, 76, 77},
    {60, 61, 62, 68, 70, 71, 78, 79, 80}
};

class SudokuBoard {
public:
    SudokuBoard() :
        filledIn(0)
    {
        for (uint i(0); i < S; ++i)
            table[i] = usedDigits[i] = 0;
    }

    virtual ~SudokuBoard() {
    }

    int const at(uint l, uint c) { // Returns the value at line l and row c
        if (isValidPos(l, c))
            return table[l * L + c];
        else
            return -1;
    }

    void set(uint l, uint c, uint val) { // Sets the cell at line l and row c to hold the value val
        if (isValidPos(l, c) && ((0 < val) && (val <= MAXVAL))) {
            if (table[l * C + c] == 0)
                ++filledIn;
            table[l * C + c] = val;
            for (uint i = 0; i < C; ++i) // Update lines
                usedDigits[lineElements[l][i]] |= 1<
    
      0)
                            ++d;
                        set(i / C, i % C, d); // Fill it in
                        changed = true; // The board has been changed so this step must be rerun
                    } else if (bitcount(usedDigits[i]) == MAXVAL)
                        throw 666; // Speed boost
        }
    }

    void goBruteForce() {
        int max(-1); // Find the cell with the _minimum_ number of posibilities (i.e. the one with the largest number of /used/ digits)
        for (uint i(0); i < S; ++i)
            if (table[i] == 0) // Is there a digit already written?
                if ((max == -1) || (bitcount(usedDigits[i]) > bitcount(usedDigits[max])))
                    max = i;

        if (max != -1) {
            for (uint i(1); i <= MAXVAL; ++i) // Go through each possible digit
                if ((usedDigits[max] & 1<
     
      > aux;
        sb.set(i / L, i % L, aux);
    }
    fin.close();

    printB(sb);
    sb.solve();
    printB(sb);

    return 0;
}


     
    
   
  
Topics:

Opinions expressed by DZone contributors are their own.

THE DZONE NEWSLETTER

Dev Resources & Solutions Straight to Your Inbox

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.

X

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}