Sudoku solver in C using backtracking

A 9×9 sudoku solver in C. The algorithm incorporates backtracking. Backtracking is a great technique to use when the problem is NP complete and the state space isn’t huge. It takes only a few seconds to solve a hard 9×9 sudoku puzzle on a 1.4GHz machine. The program in txt can be found here. Sadly I can only upload image files so the file is a PDF.

The program first reads in the sudoku puzzle from a file named “myfile.txt”. The algorithm begins by recursively fills up the puzzle, and if no feasible input can be found for an empty block before a solution is reached, it returns to the previous empty block and attempts with another feasible input. The heuristic is very straighforward, it just ensures the input does not appear in the same row, the same column, and the same square.

An important lesson I learnt after is that for NP complete problems, if brute force isn’t working, that’s because you’re not using enough, or you just need more hardware.

About these ads

  1. #1 by joxi on November 22, 2007 - 1:19 am

    very thx for this code. useful!

  2. #2 by Brandon on January 26, 2008 - 9:40 pm

    The code is helpful for a class I am taking to get the idea of backtracking to solve NP problems. However I don’t know if this is a problem or not, but I attempted to give it a puzzle to complete and it was unable to do so. It was capable of placing 6 digits in locations but only 3 of which are in correct locations. Any suggestions?

  3. #3 by Fazlay Rabbi on March 17, 2008 - 7:19 pm

    Thanx for your code. It helps me to solve the 8 queens problem and gives me the implementation of backtracking.

  4. #4 by nadia on April 18, 2008 - 8:35 am

    #include
    //#include
    //#include

    int i,j,k,a[10,10],o,x[100],y[100];

    void display();
    int getnum();
    void solve(int [],int [],int);
    int check(int ,int );

    void main()
    {
    clrscr();
    printf(“\n\nEnter the elements of SUDOKU in rowwise.\n[ Enter '0' if element is absent. ]“);
    for(i=1;i<=9;i++)
    for(j=1;j<=9;j++)
    scanf(“%d”,&a[i][j]);
    printf(“\n\nEntered SUDOKU\n\n”);
    display();
    printf(“\nEnter any key for solution….\n”);
    getch();
    o=getnum();
    solve(x,y,1);
    }

    int getnum()
    {
    int c=0;
    for(i=1;i<=9;i++)
    {
    for(j=1;j<=9;j++)
    {
    if(a[i][j]==0)
    {
    c++;
    x[c]=i;
    y[c]=j;
    }
    }
    }
    return(c);
    }

    void display()
    {
    for(i=1;i<=9;i++)
    {
    for(j=1;j<=9;j++)
    {
    if(a[i][j]!=0)
    printf(” %d”,a[i][j]);
    else
    printf(” “);
    }
    printf(“\n\n”);
    }
    }

    void solve(int p[100],int q[100],int n)
    {
    for(k=1;k<=9;k++)
    for(i=p[n];i<=p[n];i++)
    for(j=q[n];j<=q[n];j++)
    {
    a[i][j]=k;
    if(n<0)
    solve(p,q,n++);
    int ch=check(1,0);
    if(ch!=0)
    {
    display();
    getch();
    //exit(0);
    }
    }
    }
    }

    int check(int n,int r)
    {
    int f=0,cont=0;
    if(r==1)
    {
    for(k=1;k<=9;k++)
    {
    for(i=n;i<=n;i++)
    for(j=1;j<=9;j++)
    {
    if(k==a[i][j])
    f++;
    }
    if(f!=1)
    return(0);
    else
    cont++;
    f=0;
    }
    if(cont!=9)
    return(0);
    else if(n==9)
    check(1,0);
    else
    check(n++,1);
    }
    else
    {
    for(k=1;k<=9;k++)
    {
    for(i=1;i<=9;i++)
    for(j=n;j<=n;j++)
    {
    if(k==a[i][j])
    f++;
    }
    if(f!=1)
    return(0);
    else
    cont++;
    f=0;
    }
    if(cont!=9)
    return(0);
    else if(n!=9)
    check(n++,1);
    }
    }

  5. #5 by oduikq bqjkl on July 10, 2008 - 1:03 am

    ofxkq diyonfuk jlxmikzen xbspjnmv velqdg lemu dnqohguxt

  6. #6 by george on February 6, 2009 - 6:19 pm

    Your “input_value” can definitely be waaay simpler.
    Try something like this:

    /*Returns 1 if n is allowed in position [a,b] of sudoku[9][9]
    and 0 if not*/
    int can_put_n_here(int n, int sdku[][9] ,int a, int b)
    {
    int i;
    for(i=0; i<9; ++i){
    if(sdku[a][i]==n || sdku[i][b]==n || sdku[3*(a/3)][3*(b/3)+9*(i/3)+(i % 3)]==n)
    return(0);
    }
    return(1);
    }

    For a given n, a and b and for a given 9X9 matrix sdku,
    it checks if n is allowed to be put in the position[a][b].
    If it is, it returns 1. If it is not, it returns 0.

  7. #7 by Boss Resurfacing on September 6, 2009 - 9:00 pm

    Off topic – Help with PM?
    lost password
    Boss Resurfacing
    Boss Resurfacing

  8. #8 by narendra umate on April 23, 2010 - 4:45 pm

    [compact code for input_value]

    int input_value(int ipos,int jpos,int value)
    {

    for(int k=0;k<9;k++)
    if(outputArray[k][jpos]==value||outputArray[ipos][k]==value)
    return 0;

    int istart=(ipos/3)*3;
    int jstart=(jpos/3)*3;

    for(int i=istart;i<istart+3;i++)
    for(int j=jstart;j<jstart+3;j++)
    if(outputArray[i][j]==value)
    return 0;

    return value;
    }

    [also insert 'return 0;' before 2nd end bracket of the function backtrack]
    saying this because my code worked well on ubuntu gcc but solaris was acting funny. so adding insert 0 explicitly does not hurt at all.

    great code by the way helped me a lot. thanks

  9. #9 by Anand on September 30, 2010 - 6:59 pm

    I am unable to find the source code. Would you please let me know where the code is?

  10. #10 by vital on December 15, 2010 - 7:13 am

    just click on “here” in the text…

    … The program in txt can be found –>here<– …

  11. #11 by Me on January 14, 2011 - 4:37 am

    How can i see the code? Clicking on “here”… doesn`t work..

  12. #12 by Cyrus on April 4, 2011 - 10:15 am

    //
    // The following code is public domain (written in 2005 by Nick Smallbone)
    // It can be found at http://www.8325.org/sudoku/
    //

    // It works by keeping track of which numbers can be used to fill the remaining
    // cells in each row, column and block. It then will only fill a cell with a
    // number that is valid for that row, column and block.

    // On every recursion, it chooses the cell with the least possible number
    // available to choose from. This has the rather nice effect that impossible
    // cells are noticed straight away without any special cases, and cells with
    // only one possibility are filled in straight away.

    #include
    #include

    using namespace std;

    FILE*input;
    input=fopen(“input.txt”,”r”);

    while((fscanf(input,”%d”,&ary[i])) !=EOF){
    printf(“%d “,ary[i]);
    i++ ;

    }
    // The size of the Sudoku game
    static const unsigned blockSize = 3;
    static const unsigned gridSize = blockSize * blockSize;

    //
    // Some functions for representing sets as bitfields
    // (counting from 0)
    //

    typedef unsigned long bitfield;

    // No bit we’ll be using is above this
    static const bitfield maskMax = 1 << gridSize;

    // A bitfield with all bits set
    static const bitfield allSet = maskMax – 1;

    // Returns the size of the set
    static unsigned bitCount(bitfield bits) {
    unsigned result = 0;
    bitfield mask = 1;

    while(mask != maskMax) {
    if (bits & mask)
    result++;
    mask *= 2;
    }

    return result;
    }

    // Returns a bitfield representing {num}
    static inline bitfield bitFor(unsigned num) {
    return 1 << (num – 1);
    }

    class Puzzle {
    // The value of any empty cell (i, j) comes from
    // rows[i] & cols[j] & blocks[i/3][j/3]
    bitfield rows[gridSize];
    bitfield cols[gridSize];
    bitfield blocks[blockSize][blockSize];

    // This contains invalid if the cell is empty,
    // its value otherwise.
    unsigned cells[gridSize][gridSize];

    public:
    // This number is invalid, and represents an empty cell
    static const unsigned invalid = gridSize + 1;

    Puzzle() {
    // Better initialise the arrays
    unsigned i, j;

    for (i = 0; i < gridSize; i++) rows[i] = allSet;
    for (i = 0; i < gridSize; i++) cols[i] = allSet;

    for (i = 0; i < blockSize; i++)
    for (j = 0; j < blockSize; j++)
    blocks[i][j] = allSet;

    for (i = 0; i < gridSize; i++)
    for (j = 0; j < gridSize; j++)
    cells[i][j] = invalid;
    }

    // Return the set of values which could be at (i, j)
    inline bitfield candidates(unsigned i, unsigned j) {
    assert(cells[i][j] == invalid);

    return rows[i] & cols[j] &
    blocks[i/blockSize][j/blockSize];
    }

    // Fill in the cell at (i, j)
    inline void set(unsigned i, unsigned j, unsigned n) {
    bitfield bit = bitFor(n);

    // Check this is a valid value for the cell
    assert((candidates(i, j) & bit) != 0);

    // No other cells in the row, column or block
    // can now have this value
    rows[i] &= ~bit;
    cols[j] &= ~bit;
    blocks[i/blockSize][j/blockSize] &= ~bit;
    cells[i][j] = n;
    }

    // Erase the cell at (i, j)
    inline void unset(unsigned i, unsigned j, unsigned n) {
    bitfield bit = bitFor(n);

    // Make sure it was already set
    assert(cells[i][j] == n);

    rows[i] |= bit;
    cols[j] |= bit;
    blocks[i/blockSize][j/blockSize] |= bit;
    cells[i][j] = invalid;
    }

    // Find the cell with the lowest number of candidates
    // in the specified rectangular area.
    // It searches in iMin <= i < iMax
    // and jMin <= j < jMax
    // Return false if the grid is full.
    bool findMin(unsigned iMin, unsigned iMax, unsigned jMin, unsigned jMax,
    unsigned &outI, unsigned &outJ)
    {
    bool found = false;
    unsigned count = 0;

    for (unsigned i = iMin; i < iMax; i++)
    for (unsigned j = jMin; j < jMax; j++)
    if (cells[i][j] == invalid &&
    (!found || bitCount(candidates(i, j)) < count))
    {
    count = bitCount(candidates(i, j));
    outI = i;
    outJ = j;
    found = true;
    }

    return found;
    }

    // Returns the value of a certain cell, or invalid
    inline unsigned getCell(unsigned i, unsigned j) { return cells[i][j]; }
    };

    // Tries to solve the puzzle in-place. It returns true if it could fill in
    // all the squares between iMin and iMax and jMin and jMax, false otherwise.
    // If destructive is false it will reverse all its changes once it
    // finds a solution or gives up.
    // If checkBlocks is true it will try to fill in each 3×3 block separately
    // before it starts – if it can't do that then it can't solve the puzzle

    bool solve(Puzzle &puzzle, unsigned iMin, unsigned iMax,
    unsigned jMin, unsigned jMax, bool destructive, bool checkBlocks)
    {
    // Check that each block can be filled if we've been asked to
    if (checkBlocks) {
    for (unsigned i = 0; i < blockSize; i++)
    for (unsigned j = 0; j < blockSize; j++)
    if (!solve(puzzle,
    i*blockSize, i*blockSize + blockSize,
    j*blockSize, j*blockSize + blockSize,
    false, false))
    return false;
    }

    // Guess a good cell to brute-force with
    unsigned i;
    unsigned j;

    if (!puzzle.findMin(iMin, iMax, jMin, jMax, i, j))
    // We must have finished
    return true;

    // Iterate through the possible values this cell could have
    unsigned num = 1;
    unsigned mask = bitFor(num);

    while(mask != maskMax) {
    if (puzzle.candidates(i, j) & mask) {

    // Try this number
    puzzle.set(i, j, num);

    bool solved = (solve(puzzle, iMin, iMax, jMin, jMax,
    destructive, checkBlocks));

    // Reverse the changes if needed
    if (!solved || !destructive)
    puzzle.unset(i, j, num);

    if (solved)
    return true;

    }

    // Advance to the next number
    mask *= 2;
    num++;
    }

    // None of the possibilities for cell (i,j) work
    return false;
    }

    // Reads in a puzzle from standard input
    void readPuzzle(Puzzle &p) {
    for (unsigned i = 0; i < gridSize; i++) {
    for (unsigned j = 0; j > c;
    if (c >= ‘1’ && c > endl;
    }
    }

    // Prints out a (hopefully) completed puzzle
    void printPuzzle(Puzzle &p) {
    for (unsigned i = 0; i < gridSize; i++) {
    for (unsigned j = 0; j < gridSize; j++) {
    if (p.getCell(i, j) == p.invalid)
    cout << " ";
    else
    cout << p.getCell(i, j);
    }

    cout << endl;
    }
    }

    // Solve and print out a puzzle
    void outputSolution(Puzzle &p) {
    if (solve(p, 0, gridSize, 0, gridSize, true, true))
    printPuzzle(p);
    }

    int main() {
    Puzzle p;

    readPuzzle(p);
    outputSolution(p);

    system ("pause");
    return 0;
    }
    Does anyone can teach me how to put file*input and how to write the code inside this program..

  13. #13 by manik on August 17, 2011 - 6:57 am

    cn u plzz explain backtrack function a bit in detail…i could not understand it…how backtracking is occuring…??

  14. #14 by kjh on December 21, 2011 - 4:58 pm

    what do i need to do if i want to chenge the range of thevalid number from 1-9 to 0-8.

  15. #15 by Hung on May 18, 2013 - 6:22 am

    Wow, fantastic blog layout! How long have you been blogging for?
    you make blogging look easy. The overall look of your
    web site is wonderful, let alone the content!

  16. #16 by tablettegraphique123.net on July 3, 2013 - 9:33 am

    These are really enormous ideas in concerning blogging.
    You have touched some pleasant things here.
    Any way keep up wrinting.

  17. #17 by maddy on July 18, 2013 - 7:17 pm

    sir..ur prgm is just brilliant … could u please explain the scanning its own square in the input_value() and backtack() in a bit more detail

  1. Nixie Sudoku « Trashbear Labs

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

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: