# Sudoku Solution in Python

Page 1 of 1

## 3 Replies - 3060 Views - Last Post: 02 June 2009 - 04:52 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=107501&amp;s=45251a06f88fabeae25c0b2ea03b5668&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 Steve_Schlotterer

Reputation: 0
• Posts: 14
• Joined: 18-May 09

# Sudoku Solution in Python

Posted 28 May 2009 - 03:35 PM

The following C code implements an algorithm that solves Sudoku puzzles. This code was written by Paul Sand, a Unix system administrator from the University of New Hampshire.

I'd like to translate this code into Python. Do you know if these instructions will translate one-to-one?

In other words, does Python have language features which translate one-to-one with C features?

Does Python have bitwise operators, and assignment operators (like XOR)?

I'm using this exercise as an opportunity to learn some Python :-)

```
#include <stdio.h>
#include <stdlib.h>

#define GRIDSIZE 9
#define MAXLINE GRIDSIZE+2

unsigned int grid[GRIDSIZE][GRIDSIZE];
unsigned int col[GRIDSIZE];
unsigned int row[GRIDSIZE];
unsigned int region[GRIDSIZE];
unsigned int istack[GRIDSIZE*GRIDSIZE];
unsigned int jstack[GRIDSIZE*GRIDSIZE];
unsigned int stackp;

void grid_input(char *filename);
void grid_display();
void placenum(unsigned n, unsigned i, unsigned j);
void removenum(unsigned n, unsigned i, unsigned j);
unsigned solve();
unsigned legal(unsigned n, unsigned i, unsigned j);

main(int argc, char **argv) {
grid_input(argv[1]);
grid_display();
if (solve()) {
printf("Solution found!\n");
grid_display();
}
else {
printf("No solution found\n");
}
exit(0);
}

/* read initial grid from specified file */
void grid_input(char *filename) {

FILE *fp;
char line[MAXLINE];
unsigned i,j;

if ((fp = fopen(filename, "r")) == NULL) {
fprintf(stderr, "Couldn't open input file\n");
exit(1);
}
stackp = 0;
for (i = 0; i < GRIDSIZE; i++) {
if (fgets(line, MAXLINE, fp)) {
for (j = 0; j < GRIDSIZE; j++) {
if (line[j] >= '1' && line[j] <= '9') {
placenum(line[j] - '0', i, j);
}
else { /* assume empty */
istack[stackp] = i;
jstack[stackp] = j;
stackp++;
}
}
}
else {
fprintf(stderr, "Unexpected input error\n");
exit(1);
}
}
}

/* solve grid with current stack of empty squares */
unsigned solve() {
int n;
int i, j;

if (stackp <= 0) { /* no empty squares so */
return 1; /* solved */
}
stackp--;
i = istack[stackp];
j = jstack[stackp];

for (n = 1; n <= 9; n++) {
if (legal(n, i, j)) {
placenum(n, i, j);
if (solve()) {
return 1;
}
removenum(n, i, j);
}
}
/* no solution at all from this point */
stackp++;
return 0;
}

/* is it legal to put value n at row i, column j? */
unsigned legal(unsigned n, unsigned i, unsigned j) {
return (grid[i][j] == 0) &&
((row[i] & (1 << (n-1))) == 0) &&
((col[j] & (1 << (n-1))) == 0) &&
((region[3 * (i/3) + (j/3)] & (1 << (n-1))) == 0);
}

/* place number n at row i, column j */
void placenum(unsigned n, unsigned i, unsigned j) {
unsigned r;

grid[i][j] = n;
row[i] ^= (1 << (n-1));
col[j] ^= (1 << (n-1));
region[3 * (i/3) + (j/3)] ^= (1 << (n-1));
}

/* remove number n at row i, column j */
void removenum(unsigned n, unsigned i, unsigned j) {
unsigned r;

grid[i][j] = 0;
row[i] ^= (1 << (n-1));
col[j] ^= (1 << (n-1));
region[3 * (i/3) + (j/3)] ^= (1 << (n-1));
}

/* display current grid */
void grid_display() {
unsigned i, j;

for (i = 0; i < GRIDSIZE; i++) {
for (j = 0; j < GRIDSIZE; j++) {
printf("+---");
}
printf("+\n");
for (j = 0; j < GRIDSIZE; j++) {
if (grid[i][j] == 0) {
printf("|   ");
}
else {
printf("| %d ", grid[i][j]);
}
}
printf("|\n");
}
for (j = 0; j < GRIDSIZE; j++) {
printf("+---");
}
printf("+\n");
}

```

Is This A Good Question/Topic? 0

## Replies To: Sudoku Solution in Python

### #2 code_m

Reputation: 24
• Posts: 202
• Joined: 21-April 09

## Re: Sudoku Solution in Python

Posted 28 May 2009 - 04:22 PM

I don't know of any direct translators, but you have two option I know of:

1 - ReWrite the program from stratch (I'd use Python3, it's more intuitive, though not in common use)

2 - Learn the ctypes module, which is ment to use a C (library) and make it available to python (and pydoc in particular) though this may take some editing of your C code to get it right.

Rewriting shouldn't be as hard as it sounds, Python certainly has every you need to write such a program, I've thought about writing one myself. The problem coming from a C background is that many symbols mean multiple things depending on the use (such as * ).

### #3 Steve_Schlotterer

Reputation: 0
• Posts: 14
• Joined: 18-May 09

## Re: Sudoku Solution in Python

Posted 28 May 2009 - 08:40 PM

I'm not looking for a tool that will translate the code into Python for me. That would take all the fun out of the exercise!

Thanks for the tips =) I'll look into those things!

-Steve

code_m, on 28 May, 2009 - 03:22 PM, said:

I don't know of any direct translators, but you have two option I know of:

1 - ReWrite the program from stratch (I'd use Python3, it's more intuitive, though not in common use)

2 - Learn the ctypes module, which is ment to use a C (library) and make it available to python (and pydoc in particular) though this may take some editing of your C code to get it right.

Rewriting shouldn't be as hard as it sounds, Python certainly has every you need to write such a program, I've thought about writing one myself. The problem coming from a C background is that many symbols mean multiple things depending on the use (such as * ).

### #4 code_m

Reputation: 24
• Posts: 202
• Joined: 21-April 09

## Re: Sudoku Solution in Python

Posted 02 June 2009 - 04:52 PM

Hey, just curious if you've made any progress?