Sudoku

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

MindTheGap
Posts: 79
Joined: Mon Nov 05, 2007 10:30 pm UTC

Sudoku

Postby MindTheGap » Fri Feb 15, 2008 11:40 pm UTC

I have a working C++ Sudoku Solver:
Spoiler:

Code: Select all


// Assignment 4-4
// Introduction to Computer Science
// Sudoku Solver

#include <stdlib.h>
#include <string.h>
#include <fstream.h>

#define DBLOCATION "board2.txt"

void displayGrid( int [ 9 ] [ 9 ] );
bool isDone ( int [ 9 ] [ 9 ] );
bool isValid ( int [ 9 ] [ 9 ] );
bool solve ( int [ 9 ] [ 9 ] );
bool serch ( int, int[] );
void reset ( int[]);

int main(){
   int grid [9][9];
   char input [ 80 ];
   ifstream DataInFile;
   int MAXLEN = 80;
   DataInFile.open( DBLOCATION, ios::nocreate );
   if ( DataInFile.fail() ){
      cout << "Fatal Error! Puzzle input file could not be opened." << endl;
      exit(0);
   }
   for ( int row = 0; row < 9; row++ ){
      DataInFile.getline ( input, MAXLEN );
      for ( int col = 0; col < 9; col++ ){
         grid [ row ] [ col ] = ( int ) ( input [ (col * 2) ] - 48 );
      }
   }
   displayGrid ( grid );
   solve( grid );
   cout << "Here is the solved grid!" << endl;
   displayGrid ( grid );
   DataInFile.close();   
   return 0;
}

void displayGrid( int grid [] [9] ){
   cout << "______________________" << endl << endl;;;
   for ( int r = 0; r < 9; r++ ){
      cout << "|";
      for ( int c = 0; c < 9; c++ ){
         if ( grid [ r ] [ c ] == 0 ){
            cout <<  " -" ;
         }
         else{
         cout << " " << grid [ r ] [ c ] << "";
         }
         if ((c + 1) % 3 == 0 && c != 0){
            cout << "|";
         }
      }
      if ((r + 1) % 3 == 0 && r != 0){
         cout << endl;
         cout << "______________________"  << endl;;
      }
      cout << endl;
   }
   cout << endl;
}

bool isDone( int grid [] [9])  // Checks if puzzle is complete
{      
   // Check if rows add up to 45
   int total = 0;
   for (int r=0;r<9;r++){
      for (int i=0;i<9;i++){
         total += grid[r][i]; 
      }
      if(total!=45) return false; 
      total=0;   
   }
   // Check if columns add up to 45
   for (int a=0;a<9;a++){
      for (int b=0;b<9;b++){
         total+=grid[b][a];
      }                     
      if (total!=45) return false;
      total=0;
   }
   // Check if 3x3 boxes add up to 45
   int x=1; 
   int y=1;
   for (int c=0;c<9;c++){
      if(y==10){
         y=1; 
         x+=3;
      }
      total+=grid[x][y]+grid[x-1][y-1]+grid[x-1][y]+grid[x-1][y+1]+grid[x][y-1]+grid[x][y+1]+grid[x+1][y-1]+grid[x+1][y]+grid[x+1][y+1];
      if (total!=45) return false;
      y+=3;
      total=0;
   }
   return true;
}

bool solve ( int grid [9] [ 9 ] )  // Solves using backtracking technique
{
   if (!isValid(grid)) return false;
   if (isDone(grid)) return true;
   for (int i=0;i<9;i++) {
      for (int j=0;j<9;j++) {
         if (grid[i][j]==0) {
            for (int guess=1;guess<=9;guess++){
               grid[i][j]=guess;
               if (solve(grid)) return true;
            }
            grid[i][j]=0;
            return false;
         }
      }
   }
   return true;
}

bool isValid ( int grid[9][9] ){  // checks is puzzle is valid (does not have to be solved)
   int templist[9];
   int hold;
   int count = 0;
   // Check rows for no repeating numbers
   for (int x = 0; x < 9; x++){
      count = 0;
      reset(templist);
      for (int i = 0; i < 9; i++){
         if ( grid[x][i] != 0){
            hold = grid[x][i];
            if (serch(hold, templist)){
               return false;
            }
            templist[count] = hold;
            count++;
         }
      }
   }
   // Check columns for no repeating numbers
   int flag;
   for (int y = 0; y < 9; y++){
      count = 0;
      reset(templist);
      for (int x = 0; x < 9; x++){
         flag = grid[x][y];
         if ( flag != 0){
            if (serch(flag, templist)){
               return false;
            }
            templist[count] = flag;
            count++;
         }
      }
   }
   // Check 3x3 boxes for no repeating numbers
   x = 1;
   y = 1;
   for (int var = 0; var < 9; var++){
      count = 0;
      reset(templist);
      if(y == 10){
         y = 1; 
         x += 3;
      }
      int lol[9] = {grid[x][y],grid[x-1][y-1],grid[x-1][y],grid[x-1][y+1],grid[x][y-1],grid[x][y+1],grid[x+1][y-1],grid[x+1][y],grid[x+1][y+1]};
      for (int r = 0; r < 9; r++){
         if (lol[r] != 0){
            if (serch(lol[r], templist)){
               return false;
            }
            templist[count] = lol[r];
            count++;
         }
      }
      y += 3;
   }
   return true;
}
bool serch ( int x, int a[] ){  // Linear Search Function
   for (int i = 0; i < 9; i++){
      if (x == a[i]){
         return true;
      }
   }
   return false;
}
void reset ( int b[] ){  // Resets all elements of a 9 element array to -1
   for (int i = 0; i < 9; i++){
      b[i] = -1;
   }
}


As of right now, it uses a backtracking/recursion technique to solve the puzzle (guesses a number 1-9, continues puzzle until error found and then backtracks). Is there a better way to solve this?

orangeperson
Posts: 117
Joined: Sun May 13, 2007 2:17 am UTC

Re: Sudoku

Postby orangeperson » Sat Feb 16, 2008 12:29 am UTC

Try to think of an algorithm that you would be willing to perform without a computer. Even if you can't solve it with such an algorithm, maybe you can fill in some squares and then use the algorithm you have now.
spjork.

User avatar
musicinmybrain
Posts: 96
Joined: Sun Dec 31, 2006 2:50 am UTC
Location: Greensboro, NC

Re: Sudoku

Postby musicinmybrain » Sun Feb 17, 2008 7:31 pm UTC

Here is a Python Sudoku solver. It's 100 lines long and can solve any valid Sudoku with frightening speed.
+ + + + + + + + [ > + + + + [ > + + > + + + > + + + > + < < < < - ] > + > - > + > > + [ < ] < - ] > > . > > - - - . + + + + + + + . . + + + . > . < < - . > . + + + . - - - - - - . - - - - - - - - . > + . > + + .

MindTheGap
Posts: 79
Joined: Mon Nov 05, 2007 10:30 pm UTC

Re: Sudoku

Postby MindTheGap » Sun Feb 17, 2008 8:19 pm UTC

Sure beats my python solver. :(
Mine solves in about 10 seconds.

Python code:
Spoiler:

Code: Select all

def isValid(grid):
    for x in range(0,9):
        temp_list = []
        for i in grid[x]:
            if i != 0:
                if i in temp_list:
                    return 2
                temp_list.append(i)
    for y in range(0,9):
        temp_list = []
        for x in range(0,9):
            i = grid[x][y]
            if i != 0:
                if i in temp_list:
                    return 2
                temp_list.append(i)                             
    return 1               
def isDone(grid):
    total = 0
    for r in range(0,9):
        for c in range(0,9):
            total += grid[r][c]
        if total != 45:
            return 2
        total = 0
    for c in range(0,9):
        for r in range(0,9):
            total += grid[r][c]
        if total != 45:
            return 2
        total = 0
    x, y=1, 1
    for a in range(0,9):
        if y==10:
            y=1
            x+=3
        total += grid[x][y]+grid[x-1][y-1]+grid[x-1][y]+grid[x-1][y+1]+grid[x][y-1]+grid[x][y+1]+grid[x+1][y-1]+grid[x+1][y]+grid[x+1][y+1]
        if total != 45:
            return 2
        y += 3
        total = 0
    return 1
def solve(grid):
    if isValid(grid) == 2:
        return 2
    if isDone(grid) == 1:
        return 1
    for i in range(0,9):
        for j in range(0,9):
            if grid[i][j] == 0:
                for g in range(1,10):
                    grid[i][j] = g
                    if solve(grid) == 1:
                        return 1
                grid[i][j] = 0
                return 2
def display(g):
    for i in range(0,9):
        print str(g[i][0])+" "+str(g[i][1])+" "+str(g[i][2])+" | "+str(g[i][3])+" "+str(g[i][4])+" "+str(g[i][5])+ " | "+str(g[i][6])+" "+str(g[i][7])+" "+str(g[i][8])
        if i == 2 or i == 5:
           print "______________________"
grid = [ [8,0,4,0,7,0,2,0,5],
         [5,0,0,4,0,2,1,7,6],
         [7,2,6,0,3,1,4,9,8],
         [9,6,7,1,2,5,3,8,4],
         [4,0,0,0,0,0,0,0,1],
         [0,0,0,6,4,0,0,5,0],
         [6,7,0,0,0,0,0,0,0],
         [0,0,0,0,0,0,0,1,9],
         [1,9,2,0,5,4,8,0,0] ]
print "Here is what the Sudoku grid looks like: "
display(grid)
if isValid(grid) == 1:
    solve(grid)
    print "Here is the solved Sudoku Puzzle!: "
    print "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!"
    display(grid)
else:
    print "Error: Invalid Sudoku Puzzle!"

K^2
Posts: 68
Joined: Mon Feb 18, 2008 6:33 am UTC

Re: Sudoku

Postby K^2 » Mon Feb 18, 2008 12:44 pm UTC

Well, what I did in my version is check each square to see how many alternative digits can be placed there. That involved simply marking off every digit already in the row, column, and the 3x3. Once that is done for every square, find the one with the least options. Try each option, and repeat recursively for remaining squares. When done this way, the problem really doesn't branch a whole lot, and the solution is lightning fast even if you start with a completely clean board.

ot:
+ + + + + + + + [ > + + + + [ > + + > + + + > + + + > + < < < < - ] > + > - > + > > + [ < ] < - ] > > . > > - - - . + + + + + + + . . + + + . > . < < - . > . + + + . - - - - - - . - - - - - - - - . > + . > + + .

That does not seem like an efficient way of doing that.

User avatar
sunami
Posts: 239
Joined: Sat Jul 21, 2007 4:52 am UTC
Location: Arlington. The state of Northern Virginia.

Re: Sudoku

Postby sunami » Tue Feb 19, 2008 6:28 pm UTC

K^2 wrote:Well, what I did in my version is check each square to see how many alternative digits can be placed there. That involved simply marking off every digit already in the row, column, and the 3x3.

I did what you did, up to there. Then, rather than guessing numbers and seeing how it plays out, I had it eliminate numbers based on the 3 rules that I use to solve puzzles.

Each spot was given a list of possible numbers that could go there, which was changed by each set (row, column, box) that it's a part of. Initially I'd just remove possible numbers based on other numbers in each set, but when that was done, progress to the more complex rules to eliminating possible values. When a spot has only one number left that it could be, set it's value to that int, and start over (this was definitely not the most efficient way, but I didn't mind). With this, I never had the computer guessing, it would always remove possibilites and place real numbers, then remove more possibilities, and so on.

The starting from the beginning of the puzzle bit could definitely be improved on, but when I solved what's considered the 'hardest' puzzle

Code: Select all

+-----------------------+
| 8 5 . | . . 2 | 4 . . |
| 7 2 . | . . . | . . 9 |
| . . 4 | . . . | . . . |
|-----------------------|
| . . . | 1 . 7 | . . 2 |
| 3 . 5 | . . . | 9 . . |
| . 4 . | . . . | . . . |
|-----------------------|
| . . . | . 8 . | . 7 . |
| . 1 7 | . . . | . . . |
| . . . | . 3 6 | . 4 . |
+-----------------------+

in 0.2 seconds, I was happy enough.
"You heard it here first: all my software is shitty."

MindTheGap
Posts: 79
Joined: Mon Nov 05, 2007 10:30 pm UTC

PySudoku

Postby MindTheGap » Thu Feb 21, 2008 12:11 am UTC

I've been learning Python for a month now, and decided to make this Sudoku Solver.

Spoiler:

Code: Select all

def isValid(grid):
    for x in range(0,9):
        temp_list = []
        for i in grid[x]:
            if i != 0:
                if i in temp_list:
                    return 2
                temp_list.append(i)
    for y in range(0,9):
        temp_list = []
        for x in range(0,9):
            i = grid[x][y]
            if i != 0:
                if i in temp_list:
                    return 2
                temp_list.append(i)                             
    return 1               
def isDone(grid):
    total = 0
    for r in range(0,9):
        for c in range(0,9):
            total += grid[r][c]
        if total != 45:
            return 2
        total = 0
    for c in range(0,9):
        for r in range(0,9):
            total += grid[r][c]
        if total != 45:
            return 2
        total = 0
    x, y=1, 1
    for a in range(0,9):
        if y==10:
            y=1
            x+=3
        total += grid[x][y]+grid[x-1][y-1]+grid[x-1][y]+grid[x-1][y+1]+grid[x][y-1]+grid[x][y+1]+grid[x+1][y-1]+grid[x+1][y]+grid[x+1][y+1]
        if total != 45:
            return 2
        y += 3
        total = 0
    return 1
def solve(grid):
    if isValid(grid) == 2:
        return 2
    if isDone(grid) == 1:
        return 1
    for i in range(0,9):
        for j in range(0,9):
            if grid[i][j] == 0:
                for g in range(1,10):
                    grid[i][j] = g
                    if solve(grid) == 1:
                        return 1
                grid[i][j] = 0
                return 2
def display(g):
    for i in range(0,9):
        print str(g[i][0])+" "+str(g[i][1])+" "+str(g[i][2])+" | "+str(g[i][3])+" "+str(g[i][4])+" "+str(g[i][5])+ " | "+str(g[i][6])+" "+str(g[i][7])+" "+str(g[i][8])
        if i == 2 or i == 5:
           print "______________________"
#######################################################################
#ENTER YOUR PUZZLE ON THE NEXT LINE! MAKE SURE TO LEAVE COMMAS AND BRACKETS INTACT!!!##############################################################
# use zeroes for blank spaces.
grid = [ [8,0,4,0,7,0,2,0,5],
         [5,0,0,4,0,2,1,7,6],
         [7,2,6,0,3,1,4,9,8],
         [9,6,7,1,2,5,3,8,4],
         [4,0,0,0,0,0,0,0,1],
         [0,0,0,6,4,0,0,5,0],
         [6,7,0,0,0,0,0,0,0],
         [0,0,0,0,0,0,0,1,9],
         [1,9,2,0,5,4,8,0,0] ]
print "Here is what the Sudoku grid looks like: "
display(grid)
if isValid(grid) == 1:
    solve(grid)
    print "Here is the solved Sudoku Puzzle!: "
    print "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!"
    display(grid)
else:
    print "Error: Invalid Sudoku Puzzle!"


You have the option to write in your own sudoku puzzle or see it sovle the pre-loaded one. Let me know what you think (any improvements, criticism, compliments, complaints, fears, worries...I'm open to anything).

HappySmileMan
Posts: 52
Joined: Fri Nov 09, 2007 11:46 pm UTC

Re: Sudoku

Postby HappySmileMan » Thu Feb 21, 2008 11:34 pm UTC

What's with the elaborate "isDone()" functions... Mine is:
Spoiler:

Code: Select all

bool Solver::isDone()
{
    int count[9];
    for (int i=0; i<9; ++i) {
        for (int j=0; j<9; ++j) {
            count[(board[i][j] - 1)]++;
            for (int k=0; k<9; ++k) {
                if (count[k] != 9) { return false; }
            }
        }
    }
    return true;
}


And if it's run right after "isValid()" then there's no need to worry about everything else as far as I can see, but my solver isn't done yet, so maybe that's wrong?

coppro
Posts: 117
Joined: Mon Feb 04, 2008 6:04 am UTC

Re: Sudoku

Postby coppro » Fri Feb 22, 2008 12:01 am UTC

As far as I can tell, neither of those functions work... the first one will trigger on any arrangement where the total of all the rows is 45, such as a grid of 81 5s, and the second doesn't check individual rows, just for the frequency of numbers - so a grid composed of a column full of 1s, a column full of 2s, a column full of 3s, etc. will trigger a false positive.

Also, that' s an awful implementation - what's with the for loop for k? Can't you check only the count index that you actually changed?

HappySmileMan
Posts: 52
Joined: Fri Nov 09, 2007 11:46 pm UTC

Re: Sudoku

Postby HappySmileMan » Fri Feb 22, 2008 12:10 am UTC

coppro wrote:As far as I can tell, neither of those functions work... the first one will trigger on any arrangement where the total of all the rows is 45, such as a grid of 81 5s, and the second doesn't check individual rows, just for the frequency of numbers - so a grid composed of a column full of 1s, a column full of 2s, a column full of 3s, etc. will trigger a false positive.


That's checked for in "isValid()" which is called before this function, so it's already taken care of.

Also, that' s an awful implementation - what's with the for loop for k? Can't you check only the count index that you actually changed?


The loop for k was supposed to be a few lines down, after the loop... Just realised it doesn't work in that code.

Edit: Finished it now, appears to work:

Spoiler:

Code: Select all

Solver::Solver(char input[9][9])
{
    for (int i=0; i<9; ++i) {
        for (int j=0; j<9; ++j) {
            board[i][j] = (input[i][j] - 48);
        }
    }
}

bool Solver::isDone()
{
    int count[9];
    for (int i=0; i<9; ++i) {
        for (int j=0; j<9; ++j) {
            if (board[i][j] == 0) { return false; }
            count[(board[i][j] - 1)]++;
        }
    }
    for (int k=0; k<9; ++k) {
        if (count[k] != 9) { return false; }
    }
    return true;
}

bool Solver::isValid() {
    for (int i=0; i<9; ++i) {
        for (int j=0; j<9; ++j) {
            if (board[i][j] == 0) { continue; }
            for (int k=(i+1); k<9; ++k) {
                if (board[k][j] == board[i][j]) { return false; }
            }
            for (int k=(j+1); k<9; ++k) {
                if (board[i][k] == board[i][j]) { return false; }
            }
        }
    }
    for (int i=1; i<9; i+=3) {
        for (int j=1; j<9; j+=3) {
            int set[9] = { board[i-1][j-1], board[i][j-1], board[i+1][j-1],
                           board[i-1][j], board[i][j], board[i+1][j],
                           board[i-1][j+1], board[i][j+1], board[i+1][j+1],};
            for (int k=0; k<9; ++k) {
                if (set[k] == 0) { continue; }
                for (int l=(k+1); l<9; ++l) {
                    if (set[k] == set[l]) { return false; }
                }
            }
        }
    }
    return true;
}

bool Solver::solve()
{
    if (!isValid()) { return false; }
    if (isDone()) { return true; }
    for (int i=0; i<9; ++i) {
        for (int j=0; j<9; ++j) {
            if (board[i][j] == 0) {
                for (int guess=1; guess<10; ++guess) {
                    board[i][j] = guess;
                    if (solve()) {return true;}
                }
                board[i][j] = 0;
                return false;
            }
        }
    }
    return true;
}

void Solver::printBoard()
{
    for (int i=0; i<9; ++i) {
        for (int j=0; j<9; ++j) {
            cout << int(board[i][j]) << " ";
        }
        cout << endl;
    }
    cout << endl;
}

Solver::~Solver()
{
}


I'm assuming the header file wouldn't be necessary. there's just those functions and a "char board[9][9]" for now.

It solves sudokus at well under 0.1 of a second, however when it solves 50 of them in a row it takes 16 seconds, I don't see why there's this slowdown, I can't see a reason for it.

Damaki
Posts: 1
Joined: Fri Feb 22, 2008 8:03 pm UTC

Re: Sudoku

Postby Damaki » Fri Feb 22, 2008 8:13 pm UTC

sunami wrote:

Code: Select all

+-----------------------+
| 8 5 . | . . 2 | 4 . . |
| 7 2 . | . . . | . . 9 |
| . . 4 | . . . | . . . |
|-----------------------|
| . . . | 1 . 7 | . . 2 |
| 3 . 5 | . . . | 9 . . |
| . 4 . | . . . | . . . |
|-----------------------|
| . . . | . 8 . | . 7 . |
| . 1 7 | . . . | . . . |
| . . . | . 3 6 | . 4 . |
+-----------------------+


I ran this puzzle through my solver and it solved it in a reported time of 0.001 seconds.

I used Java to write this solver and the solver solves puzzles logically. Currently it doesn't use any guessing whatsoever, but I may implement guessing later. I made my solve store data about the grid, so it takes up quite a bit of memory compared to just a 2D array. The data it stores is:
- The number of available spaces (for each number) on each row and column
- The number of possible numbers that can be put in each cell of the grid
- The number of possible numbers that can be put in each region (small 3x3 grid).
- A 3D array of booleans represening the grid for each number (think of it as a layered 2D grid), which represents if a number can be placed in each space.

When a number is placed in a cell, this data is updated using several methods. The solver then has to simply iterate through the grid data looking for a row, column, cell or region which contains only one logical space for a number. When it finds one it locates the space and inserts the number there (which also updates the grid data for the next pass). The solver halts when either the grid has been solved or no new spaces were found during a full pass of the grid.

The speed of this solver comes from the fact that it only has to scan through an entire row/column/region whenever it is inserting a value, and when it is expecting a single space for a value on a row/column/region. I'm quite proud of this accomplisment! I may post source code later once I've cleaned it up a bit more and with a few optimisations.

HappySmileMan
Posts: 52
Joined: Fri Nov 09, 2007 11:46 pm UTC

Re: Sudoku

Postby HappySmileMan » Fri Feb 22, 2008 9:16 pm UTC

Damaki wrote:

Code: Select all

+-----------------------+
| 8 5 . | . . 2 | 4 . . |
| 7 2 . | . . . | . . 9 |
| . . 4 | . . . | . . . |
|-----------------------|
| . . . | 1 . 7 | . . 2 |
| 3 . 5 | . . . | 9 . . |
| . 4 . | . . . | . . . |
|-----------------------|
| . . . | . 8 . | . 7 . |
| . 1 7 | . . . | . . . |
| . . . | . 3 6 | . 4 . |
+-----------------------+


I ran this puzzle through my solver and it solved it in a reported time of 0.001 seconds.


4.603s for me using guessing

User avatar
Dingbats
Posts: 921
Joined: Tue Mar 20, 2007 12:46 pm UTC
Location: Sweden
Contact:

Re: Sudoku

Postby Dingbats » Fri Feb 22, 2008 10:52 pm UTC

HappySmileMan wrote:
Damaki wrote:

Code: Select all

+-----------------------+
| 8 5 . | . . 2 | 4 . . |
| 7 2 . | . . . | . . 9 |
| . . 4 | . . . | . . . |
|-----------------------|
| . . . | 1 . 7 | . . 2 |
| 3 . 5 | . . . | 9 . . |
| . 4 . | . . . | . . . |
|-----------------------|
| . . . | . 8 . | . 7 . |
| . 1 7 | . . . | . . . |
| . . . | . 3 6 | . 4 . |
+-----------------------+


I ran this puzzle through my solver and it solved it in a reported time of 0.001 seconds.


4.603s for me using guessing


3.698 for me by hand

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Sudoku

Postby Berengal » Fri Feb 22, 2008 11:09 pm UTC

I doubt you could write that fast.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
sunami
Posts: 239
Joined: Sat Jul 21, 2007 4:52 am UTC
Location: Arlington. The state of Northern Virginia.

Re: Sudoku

Postby sunami » Sat Feb 23, 2008 1:04 am UTC

Berengal wrote:I doubt you could write that fast.

Didn't specify a time unit.
"You heard it here first: all my software is shitty."

arcoain
Posts: 56
Joined: Thu Dec 20, 2007 12:34 am UTC

Re: Sudoku

Postby arcoain » Sat Feb 23, 2008 2:04 am UTC

I wrote a sudoku solver in VB.net a while back, and then rewrote and used it as the premise of a learn to program / learn VB.NET book. It solved any puzzle, including ones that required guessing in around .1 seconds.
arcoain

User avatar
Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Sudoku

Postby Xanthir » Sat Feb 23, 2008 4:35 am UTC

I spent a *lot* of time on my sudoku solver, because I saved the "guess and backtrack" method for the very end. Before I added that in, it could still solve *almost* any sudoku puzzle I threw at it. Anything that came out of one of those crappy sudoku compilations was mincemeat. Instead of guessing, I decompiled my own personal heuristics (I'm pretty skilled at sudoku) and turned them into code. It was much harder than it sounds when you get to the more obscure heuristics.

What's more, I didn't code to a specific board. Instead, I have two hashes which capture the fundamental shape of the boardstate at any time - one that tells me what values are possible for a given cell to have, and one that tells me what cells are in a given constraint. (I also use the reverse of these for ease, but I don't count them as unique hashes.) This lets me model arbitrary sudoku boards of any size and shape with any values at all, and my solver tackles them just fine. Frex, I threw Sudoku-On-A-Plane and X-Sudoku puzzles at it, and it handled them without a speck of extra code. I just had to initialize the hash structure appropriately (for x-sudoku that just involved adding two values to the constraint-cell hash, but sudoku-on-a-plane required me to rewrite the entire hash ^_^).

Thought it was a bit more abstract (and involved a lot of set operations), I think it made the overall coding a much simpler process. Having to keep track of whether you're looking at a row, a column, or a box just makes a lot of weird edge cases, I think, and you're prone to accidentally skip a combination that you've never personally seen.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Sudoku

Postby Berengal » Fri Feb 29, 2008 12:06 am UTC

Okay, so I decided to try my hand at this, mainly to code something in python that can't (read: shouldn't) be expressed in a single script. It's actually turning out pretty nice, and I'm learning lots about code structure.

I started by defining the structure of a puzzle: A 9*9 board with 9 rows, 9 columns and 9 boxes, each containing 9 squares, and each square being contained in 3 containers with no two squares being contained in the three same containers.
The clue here is that the structure part of the code cannot ask itself about anything, but can only modify itself based on what it's told. This means that if a square is told it's a number, then it can tell the containers it belongs to that that number is now not possible and the containers in turn tell every square in them that the number is unavailable. When the squares are told the number is unavailable to them, however, they are prohibited from asking themselves about the remaining numbers, so that even if there's only one possible number they could be, they do not set themselves to that number.

I then proceeded to code the rules. I'm not a very skilled sudoku solver, and my methods are intuitive anyway, so I turned to a website for more structure. Trying to make my own rules could very easily turn messy, and that isn't the point either.
So far I've coded the Initial Board rule (when a square is a number, it is that number (duh)), the Single Solution rule (when a square can only be one number, it is that number) and the Single Cell rule (when a container only has one square that can be a number, it is that number), and it solves everything I've thrown at it quite elegantly (obviously, I've only thrown puzzles that can be solved by those rules alone at it).

I also got tired of typing in coordinate-number pairs manually, so I wrote a simple parsing function that takes a file as input, regexpes all digits and (?|.)'s and makes coordinate-number pairs for me.

Next is some more rules.

What I love about this is that my brother's been working on his c-version for two days now, and in just a couple of hours I did something equivalent in python. Better actually, since his is bugged. For some reason he decided using threads would be neat...

Oh well, here's the main module. It's not much to look at, but that's actually something I'm proud of. It means I managed to separate different functions into their own modules. The fact that each module itself looks boring means the complexity is not just swept under the carpet, but actually removed through modularization, something I've been very bad at.

Code: Select all

from SudokuStructure import Board
from SudokuRules import *
from SudokuParser import parseSudokuBoard

initialBoardCoordinates = parseSudokuBoard(open('Board1.txt', 'r'))

board = Board()
rules = (SingleSolutionRule(), SingleCellRule())
initialBoardRule = InitialBoardRule(initialBoardCoordinates)
initialBoardRule.apply(board)

print 'Initial board:'
print '-----------------------'
print board

maxIterations = 20
iterations = 0
while iterations < maxIterations and not board.isSolved():
    iterations += 1
    for rule in rules:
        rule.apply(board)
    print 'Generation %d:' % iterations
    print '-----------------------'
    print board

print '======================='
status = 'Puzzle solved in %d iterations.' % iterations if board.isSolved() else 'Failed to solve puzzle in %d iterations' % iterations
print status
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

mrkite
Posts: 336
Joined: Tue Sep 04, 2007 8:48 pm UTC

Re: Sudoku

Postby mrkite » Wed Mar 05, 2008 11:09 pm UTC

Judging from the answers on projecteuler, a constraint-based solver (like the one I wrote for that problem) will be slower than a solver that solves like a human. My constraint-based one, averaged 7ms per puzzle. Someone else's logical one, averaged 0.8ms per puzzle.

His logical one could perform the following techniques:
Naked Pairs/Triples/Quads
Hidden Pairs/Triples/Quads
X-Wing

If you want to really put your algorithm to the test, you can download a file containing over 40,000 *very difficult* puzzles from here

zahlman
Posts: 638
Joined: Wed Jan 30, 2008 5:15 pm UTC

Re: Sudoku

Postby zahlman » Thu Mar 06, 2008 12:48 am UTC

Why do people keep putting code boxes inside spoiler tags? The code box is constant-size.

MindTheGap wrote:#include <stdlib.h>
#include <string.h>
#include <fstream.h>


What on earth are those? Two headers for C code, and one that doesn't properly exist, that's what. The proper, corresponding headers for C++ code are <cstdlib> and <cstring> for the first two, but (a) you're not actually using any of those C-style string manipulation functions, and (b) in C++, we have a real string type, called std::string, that lives in <string>. (Actually, you're not using any "C standard library" functions, either.) As for fstream.h, it doesn't exist in modern C++; you want <fstream>, which will provide the std::fstream type. Note the 'std' namespace, for 'standard library' components.

And by "modern", I mean as standardized ten years ago.

#define DBLOCATION "board2.txt"

void displayGrid( int [ 9 ] [ 9 ] );
bool isDone ( int [ 9 ] [ 9 ] );
bool isValid ( int [ 9 ] [ 9 ] );
bool solve ( int [ 9 ] [ 9 ] );
bool serch ( int, int[] );
void reset ( int[]);


In C++, we can define real constants, by just using const identifiers. That way, they have a type and a scope, and are not simply relying on a dumb text substitution engine to hack our code into submission. Also, passing arrays to functions is needlessly tricky. We can make a structure that represents the Sudoku grid instead, and given that, make the functions be member functions instead.

Here's how things look in modern C++, with the original algorithms:

Code: Select all

#include <fstream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std; // Please note that this is *being lazy*.

class Sudoku {
   int grid[9][9];
   bool valid();
   // There is no longer a "done" function because it was never needed...

   // Instead of keeping track of a position within a temporary array,
   // we can use a standard library container that already knows its length:
   typedef std::vector<int> Templist;
   // We now don't need to fill it with special -1 values, either.

   public:
   // Instead of a "print" function, or setting the data manually after reading
   // it, we overload the stream operators, so that we can treat this type just
   // like we do primitive types.
   friend ostream& operator<<(ostream& os, const Sudoku& sudoku); // display
   friend istream& operator>>(istream& is, Sudoku& sudoku); // input
   bool solve();
};

// I will make a little helper function here to make the code more readable:
bool contains(const Sudoku::Templist& templist, int value) {
   return std::find(templist.begin(), templist.end(), value) != templist.end();
} // Notice, that's a free function, not a member of the Sudoku class.

bool Sudoku::valid() {
   // Check rows for no repeating numbers
   for (int x = 0; x < 9; ++x) {
      Templist templist;
      for (int i = 0; i < 9; ++i) {
         int value = grid[x][i];
         if (value != 0) {
            if (contains(templist, value)) {
               return false;
            }
            templist.push_back(value); // appends it to the vector.
         }
      }
   }
   // Check columns for no repeating numbers
   // By properly scoping variables, we get to reuse variable names...
   // We could refactor a lot of this checking logic, too, to avoid repetition.
   for (int y = 0; y < 9; ++y) {
      Templist templist;
      for (int i = 0; i < 9; ++i) {
         int value = grid[i][y];
         if (value != 0) {
            if (contains(templist, value)) {
               return false;
            }
            templist.push_back(value); // appends it to the vector.
         }
      }
   }
   // OK, this part had to get changed; it's just too tricky otherwise.
   // What I do is find the top-left coordinates of the boxes with the outer
   // two loops - they'll be 0, 3 and 6 - and add an offset within the box in
   // the inner loops. Each pair of inner loops iterates over all the elements
   // of a box.
   for (int y = 0; y < 9; y += 3) {
      for (int x = 0; x < 9; x += 3) {
         int count = 0;
         Templist templist;
         for (int y_offset = 0; y_offset < 3; ++y_offset) {
            for (int x_offset = 0; x_offset < 3; ++x_offset) {
               int value = grid[x + x_offset][y + y_offset];
               if (value != 0) {
                  if (contains(templist, value)) {
                     return false;
                  }
                  templist.push_back(value); // appends it to the vector.
               }
            }
         }
      }
   }
   return true;
}

// Public interface:

bool Sudoku::solve() {
   if (!valid()) return false;
   // Don't need to check done() here. It's implicit in the following loops:
   // either grid[i][j] will be 0 for some i, j - in which case something will
   // be returned - or none of them are 0, in which case we get to the end.
   for (int i = 0; i < 9; ++i) {
      for (int j = 0; j < 9; ++j) {
         if (grid[i][j] == 0) {
            for (int guess = 1; guess <= 9; guess++) {
               grid[i][j] = guess;
               if (solve()) return true;
            }
            // Not solved; erase the guess and backtrack. <-- example of a useful comment :)
            grid[i][j] = 0;
            return false;
         }
      }
   }
   return true;
}

// The input and output functions are also free functions, because if we tried
// to make them members, we would have to call them by putting the Sudoku
// object on the left-hand side of the operator, which is not what we want.

istream& operator>>(istream& is, Sudoku& sudoku) {
   // The free function std::getline reads into a std::string object, which
   // avoids the need to set a buffer size.
   std::string line;
   for (int row = 0; row < 9; row++) {
      std::getline(os, line);
      for (int col = 0; col < 9; col++) {
         // You can get characters of a std::string with [], just like a C "string".
         // Also, a cast is not (was not) necessary here. Also, don't use magic
         // numbers like 48; instead:
         sudoku.data[row][col] = line[col * 2] - '0';
      }
   }
}

ostream& operator<<(ostream& os, const Sudoku& sudoku) {
   // Don't use endl as a substitute for \n. It's more than that. Also, what's
   // with the extra semicolons?
   os << "______________________\n\n";
   for (int r = 0; r < 9; r++) {
      os << '|';
      for (int c = 0; c < 9; c++) {
         // This was needlessly complex before. Get the number first,
         // and then always output a space, and then either the number or a '-'.
         int value = sudoku.grid[r][c];
         os << ' ';
         if (value == 0) { os << '-'; }
         else { os << value; }
         // If (c + 1) % 3 == 0, then we *already know* c != 0,
         // since (0 + 1) % 3 != 0.
         if ((c + 1) % 3 == 0) { os << '|'; }
      }
      if ((r + 1) % 3 == 0) { os << "\n______________________\n"; }
      os << '\n';
   }
}

const char* DBLOCATION = "board2.txt";

int main() {
   Sudoku grid;
   ifstream DataInFile(DBLOCATION);
   if (!DataInFile) {
      cout << "Fatal Error! Puzzle input file could not be opened." << endl;
      return -1; // There's no need to call exit() when you're already in main().
      // Also, you should use a non-zero return value to indicate this kind of
      // failure.
   }
   DataInFile >> grid; // yes, really. The hard work is elsewhere.
   cout << grid << endl; // by doing it this way, we have flexibility to display
   // the grid elsewhere, instead of just on std::cout.
   if (!grid.solve()) { // Check for that!!!
      cout << "Could not solve this sudoku :(" << endl;
   } else {
      cout << "Here is the solved grid! :)\n" << grid << endl;
   }
   // We don't need to close the file explicitly (the stream's destructor does
   // that), nor return 0 explicitly (C++ does that specially for main()).
}


Sorry for being so harsh, and not testing anything, but I am, you know, doing work for you for free here :)
Belial wrote:I once had a series of undocumented and nonstandardized subjective experiences that indicated that anecdotal data is biased and unreliable.

MindTheGap
Posts: 79
Joined: Mon Nov 05, 2007 10:30 pm UTC

Re: Sudoku

Postby MindTheGap » Thu Mar 06, 2008 2:21 am UTC

Those headers are actually from a windows version of this solver which I used for file I/O so you could read a puzzle from a text file. I forgot to delete them in this version which I wanted to get working on my mac. Those headers are all outdated because thats what my comp sci teacher taught me. It might not be right, but it worked.

As for correcting my code, thank you. I learned so much from that. That was probably the most useful post I've seen on any message board ever for me. Thanks. :D

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Sudoku

Postby Berengal » Thu Mar 06, 2008 10:48 am UTC

So when I got to the disjoint chain subset, I did a little research on wikipedia first and found out about the exact cover problem in discreet mathematics. Two days later and I've got a C++ program that solves any sudoku with a single solution in less than 0.1s The smallest sudoku known, which only has 16 numbers in place (and two solutions, but this was deemed good enough as all other sudokus with 16 numbers have many solutions) is solved in 0.108 seconds.

Actually, my brother wrote the program, and we both designed it. The python version I wrote chokes on exact cover problems the size of sudokus.

Now we're building an enigma machine, and then we're going to crack it.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

SirNotApearingOnThisForum
Posts: 29
Joined: Sun Apr 01, 2007 4:01 pm UTC

Re: Sudoku

Postby SirNotApearingOnThisForum » Sun Mar 09, 2008 8:07 pm UTC

here's one in C that takes on avg ~0.00011s per sudoku (47621 puzzles in ~5.078s) on my laptop. it uses basic logic and a few educated guesses. it could be made a lot more 'intelligent', so to speak, but I figured since it only needs to guess one or two times (if that) checking for however many special cases each pass wasn't really worth it (and there'd still be some out there which'd require guessing anyhow). I could be wrong though...

it's also specific to regular sudokus, but it wouldn't take much work to make it work for any sort of grid. come to think of it that might make for an interesting evening sometime...
Spoiler:

Code: Select all

#include <stdio.h>
#include <assert.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define SDASSERT(_c)         if(!(_c)) return -1

#define _CELL(_x, _y, _r)      ((_y) * _r + _x)
#define CELL(_x, _y)         g_sdi->cells[_CELL(_x, _y, 9)]
#define BLOCK(_x, _y)         g_sdi->blocks[_CELL(_x / 3, _y / 3, 3)]
#define COL(_x)               g_sdi->cols[_x]
#define ROW(_y)               g_sdi->rows[_y]

#define CP(_n)               ((_n) >> 16)
#define SET_CP(_n, _cp)         ((_n) = ((_n) & 0x0000ffff) | (_cp << 16))
#define DEC_CP(_n)            SET_CP(_n, CP(_n) - 1)

//to allow for easy advancements/regressions
typedef struct {
   
   //rows, cols, blocks store # potential for each #; 0 = taken
   char rows[9][9], cols[9][9], blocks[9][9];
   
   unsigned int cells[9 * 9]; //bits 0-8 represent possibilities; upper word represents # of possibilities; 0 = taken
   
} sdinfo;

sdinfo *g_sdi, final;
int mincp;
char g_first = 0;

int getdigit(int c)
{
   int i;
   
   if(CP(c)) return '.';
   
   for(i = 0; i < 9; i++)
      if(c & 1 << i) return i + '1';
   
   return '0';
}

void printcells(void)
{
   int i, j, curi;
   
   for(i = curi = 0; i < 9; i++)
   {
      for(j = 0; j < 9; j++, curi++)
         //printf("%3x ", g_sdi->cells[curi] & 0xffff);
         printf("%c ", getdigit(g_sdi->cells[curi]));
      
      printf("\n");
   }
}

int rmcell(int x, int y, int value)
{
   //if(!(CELL(x, y) & 1 << value)) return 0;
   
   CELL(x, y) &= ~(1 << value);
   DEC_CP(CELL(x, y));
   
   COL(x)[value]--;
   ROW(y)[value]--;
   BLOCK(x, y)[value]--;
   
   SDASSERT(COL(x)[value] && ROW(y)[value] && BLOCK(x, y)[value]);
   
   return 0;
}

int setcell(int x, int y, int value)
{
   int i, j, bit, blockx, blocky, tx, ty;
   
   bit = 1 << value;
   j = CELL(x, y);
   
   SDASSERT(j & bit && BLOCK(x, y)[value] && COL(x)[value] && ROW(y)[value]);
   
   //less space -> fewer possibilities
   for(i = 0; i < 9; i++)
   {
      //but only if it wasn't already cancelled out
      if(!(j & 1 << i) || i == value) continue;
      
      ROW(y)[i]--;
      COL(x)[i]--;
      BLOCK(x, y)[i]--;
   }
   
   //cp = 0
   CELL(x, y) = bit;
   
   //cells
   blockx = (x / 3) * 3;
   blocky = (y / 3) * 3;
   
   for(i = 0; i < 9; i++)
   {
      if(i != x && CELL(i, y) & bit) SDASSERT(rmcell(i, y, value) >= 0);
      
      if(i != y && CELL(x, i) & bit) SDASSERT(rmcell(x, i, value) >= 0);
      
      if((tx = blockx + i % 3) == x || (ty = blocky + i / 3) == y) continue;
      if(!(CELL(tx, ty) & bit)) continue;
      
      SDASSERT(rmcell(tx, ty, value) >= 0);
   }
   
   SDASSERT(ROW(y)[value] == 1 && COL(x)[value] == 1 && BLOCK(x, y)[value] == 1);
   
   ROW(y)[value] = 0;
   COL(x)[value] = 0;
   BLOCK(x, y)[value] = 0;
   
   return 0;
}

int dononcells(void)
{
   int i, j, k, r, t, t2, n, blockx, blocky;
   
   r = 0;
   for(i = 0; i < 9; i++)
   {
      blockx = (i % 3) * 3;
      blocky = (i / 3) * 3;
      
      for(j = 0; j < 9; j++)
      {
         //printf("%d, %d: r: %d; c: %d; b: %d\n", i, j, g_sdi->rows[i][j], g_sdi->cols[i][j], g_sdi->blocks[i][j]);
         if(ROW(i)[j] == 1)
         {
            //find winning cell!
            for(k = 0; k < 9; k++)
               if(CELL(k, i) & 1 << j) break;
            
            //SDASSERT(k < 9);
            
            SDASSERT(setcell(k, i, j) >= 0);
            r++;
         }
         
         if(COL(i)[j] == 1)
         {
            for(k = 0; k < 9; k++)
               if(CELL(i, k) & 1 << j) break;
            
            //SDASSERT(k < 9);
            
            SDASSERT(setcell(i, k, j) >= 0);
            r++;
         }
         
         if(g_sdi->blocks[i][j] == 1)
         {
            for(k = 0; k < 9; k++)
               if(CELL(k % 3 + blockx, k / 3 + blocky) & 1 << j) break;
            
            //SDASSERT(k < 9);
            
            SDASSERT(setcell(k % 3 + blockx, k / 3 + blocky, j) >= 0);
            r++;
         }
         
      }
      
   }
   
   //assert(0);
   return r;
}

int docells(void)
{
   int i, j, r;
   
   r = 0;
   mincp = -1;
   for(i = 0; i < 9 * 9; i++)
   {
      if(CP(g_sdi->cells[i]) > 1)
      {
         if(mincp == -1 || CP(g_sdi->cells[i]) < CP(g_sdi->cells[mincp])) mincp = i;
         
         continue;
      }
      else if(!CP(g_sdi->cells[i])) continue;
      
      //what value is it?
      for(j = 0; j < 9; j++)
         if(g_sdi->cells[i] & 1 << j) break;
      
      SDASSERT(j < 9);
      
      SDASSERT(setcell(i % 9, i / 9, j) >= 0);
      r++;
   }
   
   return r;
}

int run(sdinfo *psdi, int x, int y, int value)
{
   sdinfo sdi;
   int r1, r2, i, k;
   
   memcpy(&sdi, psdi, sizeof(sdinfo));
   g_sdi = &sdi;
   
   if(value != -1) setcell(x, y, value);
   
   //printf("running\n");
   start:
   while(((r1 = dononcells()) > 0 || (r2 = docells()) > 0) && r1 >= 0 && r2 >= 0) ;//printcells(), printf("\n");
   
   //error!
   if(r1 < 0 || r2 < 0) return -1;
   
   //we need to do a little guesswork...
   if(mincp >= 0)
   {
      k = rand() % CP(sdi.cells[mincp]);
      for(i = 0; k >= 0; i++)
         if(sdi.cells[mincp] & 1 << (i % 9)) k--;
      
      i = (i - 1) % 9;
      k = mincp;
      
      //printf("guessing (%d, %d) to be %d (%x)\n", mincp % 9, mincp / 9, i, 1 << i);
      //printcells();
      
      //cell can't be value
      if(run(&sdi, k % 9, k / 9, i) < 0)
      {
         g_sdi = &sdi;
         
         sdi.cells[k] &= ~(1 << i);
         DEC_CP(sdi.cells[k]);
         
         ROW(k / 9)[i]--;
         COL(k % 9)[i]--;
         BLOCK(k % 9, k / 9)[i]--;
         
         SDASSERT(ROW(k / 9)[i] && COL(k % 9)[i] && BLOCK(k % 9, k / 9)[i]);
         
         //printf("restarting...\n");
         //maybe with this newfound information we won't have to guess...
         goto start;
      }
      
      else return 0;
   }
   else
   {
      printf("result:\n");
      
      printcells();
   }
   
   //memcpy(&final, &sdi, sizeof(sdinfo));
   
   return 0;
}

//clears everything to their default value
void init(void)
{
   int i, j, curi;
   
   for(i = curi = 0; i < 9; i++)
   {
      for(j = 0; j < 9; j++, curi++)
      {
         g_sdi->cells[curi] = 0x1ff;
         SET_CP(g_sdi->cells[curi], 9);
         
         ROW(i)[j] = 9;
         COL(i)[j] = 9;
         g_sdi->blocks[i][j] = 9;
      }
   }
   
}

int readcells(char *file)
{
   FILE *fd;
   char *p, buffer[9 * 9 * 3]; //should most definitely be large enough
   int i, j;
   
   assert(fd = fopen(file, "r"));
   
   for(i = j = 0; fgets(buffer, sizeof(buffer), fd) != NULL && i < 9; )
   {
      for(p = buffer; *p; p++)
      {
         if(!(isdigit(*p) || *p == '.') || *p == '0') continue;
         
         //printf("(%d, %d): %c\n", j, i, *p);
         if(*p != '.') SDASSERT(setcell(j, i, *p - '1') >= 0);
         
         j++;
         if(j == 9) j = 0, i++;
      }
      
   }
   
   fclose(fd);
   
   printf("what I've got:\n");
   printcells();
   
   return 0;
}

int main(int argc, char *argv[])
{
   sdinfo sdi;
   int r, t, i, j;
   
   srand(time(0));
   g_sdi = &sdi;
   
   init();
   
   if(argc != 2)
   {
      //randomly seed empty sudoku
      //(not needed really, but lowers processing required)
      for(i = 0; i < 9; i++)
      {
         r = rand() % (9 * 9);
         
         for(j = 0; r >= 0; j++)
            if(CP(sdi.cells[j % (9 * 9)])) r--;
         
         j = (j - 1) % (9 * 9);
         setcell(j % 9, j / 9, i);
      }
      
      printf("seeding empty sudoku table\n");
      r = 0;
   }
   else r = readcells(argv[1]);
   
   if(r >= 0)
   {
      t = clock();
      
      r = run(&sdi, 0, 0, -1);
      
      printf("time: %f\n", (double)(clock() - t) / 1000.0f);
   }
   
   g_sdi = &final;
   if(r < 0) printf("error!\n");
   //else printcells();
   
   return 0;
}

bigpoppa2006
Posts: 3
Joined: Mon Mar 17, 2008 8:01 pm UTC

Re: Sudoku

Postby bigpoppa2006 » Mon Mar 17, 2008 8:13 pm UTC

Here is my solver in C. I've come up with an intelligent guessing system, as opposed to my previous "plug 'n chug" then check method. The code reads in a file with a specific format:
[row num] [col num] [value]
[row num] [col num] [value]
etc.

My code also uses the fields code... the guy that wrote that code (Jim Plank) is a professor at my university! Kinda cool... Anyway...
Spoiler:

Code: Select all

/*----------------------------------------------------------

Program:     sudokusolver.c
Description: This program uses recursion and backtracking to
                  solve a sudoke puzzle read in from a given text
                  file. The method used is an intelligent guess
                  that also checks entries as they're guessed.

                  I used a simple "plug and chug then check my
                  guess" method before I developed the
                  intelligent guess method.

----------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include <fields.h>
#include <string.h>

int numcalls = 0;
int linenum = 0;
//      blocknum = (((i/3)*3)+((j/3)%3));

void insert_value (IS istruct, char board[9][9], char *filename) {
//this fcn reads in the file given and inserts the values into their respective pla ces
        int row, col, entry_int;
    linenum++;

        row = atoi(istruct->fields[0]);
        col = atoi(istruct->fields[1]);
        entry_int = atoi(istruct->fields[2]);

        //error checks for incorrect input
        if (istruct->NF != 3) {
                printf("Error on line %d!\n", linenum);
                printf("Please make sure all lines have exactly 3 entries. Format:\ n");
        printf("row column entry\nrow column entry\netc. Now exiting.\n");
                exit(1);
        }
    if (row < 1 || row > 9) {
                printf("Invalid row input of \"%d\" on line %d in file \"%s\". Now exiting.\n", row, linenum, filename);
                exit(1);
        }
        if (col < 1 || col > 9) {
                printf("Invalid column input of \"%d\" on line %d in file \"%s\". N ow exiting.\n", col, linenum, filename);
                exit(1);
        }
        if (entry_int < 1 || entry_int > 9) {
                printf("Invalid entry input of \"%d\" on line %d in file \"%s\". No w exiting.\n", entry_int, linenum, filename);
                exit(1);
        }
        //end error checking for input

        board[row-1][col-1] = istruct->fields[2][0];
}

void print_board(char board[9][9]) {
//prints any board given into a basic, easy-to-read format
    int i, j;

    for (i=0; i<9; i++) {
                printf("  ");
        for (j=0; j<9; j++) {
            printf("%c ", board[i][j]);
            if (j == 2 || j == 5) {
                printf (" ");
                        }
        }
        printf("\n");
        if (i == 2 || i == 5) {
            printf("\n");
                }
    }
    printf("\n");
}

int check_row(char board[9][9], int rownum) {
//returns 0 if any row is not valid (aka, there are repeats), 1 if valid
        int i, j;

        //this loop checks for repeat numbers, making sure not to check the same en tries and '_' entries
        for (i=0; i<9; i++) {
                for (j=0; j<9; j++) {
                if (i != j && board[rownum][i] != '_' && board[rownum][j] != '_' &&  board[rownum][i] == board[rownum][j]) {
                        return 0;
                        }
                }
        }

        return 1;
}

int check_col(char board[9][9], int colnum) {
//returns 0 if any column is not valid (aka, there are repeats), 1 if valid
        int i, j;

        //this loop checks for repeat numbers, making sure not to check the same en tries and '_' entries
        for (i=0; i<9; i++) {
                for (j=0; j<9; j++) {
                        if (i != j && board[i][colnum] != '_' && board[j][colnum] ! = '_' && board[i][colnum] == board[j][colnum]) {
                                return 0;
                        }
                }
        }

        return 1;
}

int check_block(char board[9][9], int blocknum) {
//returns 0 if any block is not valid (aka, there are repeats), non-zero if valid
//blocks are assigned as follows: 0 1 2
//                                3 4 5
//                                6 7 8

        int i, j;
        char temparray[9];

        //this loop puts the block into an array
        for(i=1; i<9; i+=3) {
                for(j=1; j<9; j+=3) {
                        if (blocknum == (((i/3)*3)+((j/3)%3))) {
                                temparray[0] = board[i-1][j-1];
                                temparray[1] = board[i-1][j];
                            temparray[2] = board[i-1][j+1];
                                temparray[3] = board[i][j-1];
                    temparray[4] = board[i][j];
                        temparray[5] = board[i][j+1];
                            temparray[6] = board[i+1][j-1];
                                temparray[7] = board[i+1][j];
                        temparray[8] = board[i+1][j+1];
                        }
                }
        }

        //and this loop checks for repeat numbers, making sure not to check the sam e entries and '_' entries
        for (i=0; i<9; i++) {
                for (j=0; j<9; j++) {
                        if (i != j && temparray[i] != '_' && temparray[j] != '_' &&  temparray[i] == temparray[j]) {
                                return 0;
                        }
                }
        }

        return 1;
}

int smart_guess(int row, int col, int guess, char board[9][9]) {
//returns 1 if the guess passes the tests, 0 if not

        board[row][col] = (char) guess+48; //converts the int guess to its ASCII va lue

        if (check_row(board, row) == 0 || check_col(board, col) == 0 || check_block (board, (((row/3)*3)+((col/3)%3))) == 0) {
                board[row][col] = '_';
                return 0;
        }

        return 1;
}

int solve(char board[9][9]) {
//returns 0 if the puzzle is not solvable, 1 when it is done, and
//calls eventually itself if it is incomplete (aka '_' is found)
        int i, j, k;
        numcalls++;

        //find empty cell
        for (i=0; i<9; i++) {
                for (j=0; j<9; j++) {
                        if (board[i][j] == '_') {
                                for (k=1; k<10; k++) {
                                        while (smart_guess(i, j, k, board) == 0) {
                                                k++;
                                                if (k > 9) {
                                                        board[i][j] = '_';
                                                        return 0;
                                                }
                                        }
                                        if (solve(board)) {
                                                return 1;
                                        }
                                }
                                board[i][j] = '_';
                                return 0;
                        }
                }
        }

        return 1;
}

int main (int argc, char **argv) {
        if (argc != 2) {
        printf("Usage: ./sudokusolver file_of_puzzle\n");
                exit(1);
        }

        IS istruct;
        int i, j;
        char board[9][9];

        //initializes the board
        for (i=0; i<9; i++) {
                for(j=0;j<9;j++) {
                        board[i][j] = '_';
                }
        }

        istruct = new_inputstruct(argv[1]);
        if (istruct == NULL) {
            printf("istruct could not be malloc'd from %s.\n", argv[1]);
                printf("Please check file path and file name. Now exiting.\n");
            exit(1);
        }

    //read in values to the board
    while(get_line(istruct) >= 0) {
                insert_value(istruct, board, argv[1]);
        }

        //free istruct - you don't need it anymore
        jettison_inputstruct(istruct);

        //print original board
        printf("\nOriginal board read from the file \"%s\":\n\n", argv[1]);
        print_board(board);

        //call function to solve the board and get the result
        if (solve(board)) {
        printf("--------------------------\n");
                printf("Solution has been found!\n\n");
                print_board(board);
        }

        else {
                printf("--------------------------\n");
                printf("Solution not found. The puzzle is unsolvable.\n");
        }

        printf("Number of times solve() was called: %d\n\n", numcalls);
        return 0;
}


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 7 guests