Sudoku Solution in Python

curious if possible to translate C program into Python.

Page 1 of 1

3 Replies - 2174 Views - Last Post: 02 June 2009 - 04:52 PM Rate Topic: -----

#1 Steve_Schlotterer  Icon User is offline

  • New D.I.C Head

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

Sudoku Solution in Python

Post icon  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  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 24
  • View blog
  • Posts: 197
  • 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 * ).
Was This Post Helpful? 0
  • +
  • -

#3 Steve_Schlotterer  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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

View Postcode_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 * ).

Was This Post Helpful? 0
  • +
  • -

#4 code_m  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 24
  • View blog
  • Posts: 197
  • 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?

I'd be glad to help!
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1