Sudoku Solver with Backtracking

[haglerchristopher]

Hello everyone,
I am working on a sudoku solver program, and I am having a little trouble. I have been banging my head on the keyboard for about an hour now, so I figure maybe a new set of eyes would help.

I am not sure what is happening, but the function solve seems to recurse through the first two rows of the puzzle then backtrack all the way to the beginning before exiting. From debugging the program with gdb, somehow, the cell_positions, previous cell_posiiton struct, seems to be incorrect on each time the solve function returns INVALID. I am not sure how it can be incorrect because the code looks fine. Any help is greatly appreciated.

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

#define SOLVED 10
#define FULL   11
#define INVALID -1
#define VALID 0

#define BOARD_WIDTH 9
#define BOARD_HEIGHT 9

#define BOARD_LOW 1
#define BOARD_HIGH 9

#define EMPTY 0

int board[BOARD_WIDTH][BOARD_HEIGHT] = {
    0, 2, 0, 7, 8, 9, 0, 0, 0,
    0, 0, 7, 3, 2, 0, 0, 0, 0,
    0, 8, 4, 5, 0, 0, 2, 0, 0,
    8, 0, 0, 0, 9, 2, 0, 0, 6,
    0, 1, 6, 0, 0, 0, 7, 4, 0,
    4, 0, 0, 1, 7, 0, 0, 0, 8,
    0, 0, 3, 0, 0, 8, 5, 7, 0,
    0, 0, 0, 0, 5, 3, 4, 0, 0,
    0, 0, 0, 9, 4, 7, 0, 2, 0
};

struct cell_position {
    int x;
    int y;
};

void printb()
{
    int i, j;
    printf("------------------------------\n");
    for(i = 0; i < BOARD_HEIGHT; i++) {
        for (j = 0; j < BOARD_WIDTH; j++) {
            if ((j % 3) == 0)
                printf("|");
            
            printf(" %i ", board[i][j]);
        }
        
        if (((i + 1) % 3) == 0)
            printf("\n------------------------------");
        
        printf("|\n");
    }
}

void get_next_empty(struct cell_position *p)
{
    int i, j;
    for(i = 0; i < BOARD_HEIGHT; i++) {
        for(j = 0; j < BOARD_WIDTH; j++) {
            if (board[i][j] == EMPTY) {
                p->x = i;
                p->y = j;
				return;
            }
        }
    }
    p->x = FULL;
    p->y = FULL;
}

//check row p->x and column p->y to see if num is already present
int column_row_valid(struct cell_position *p, int num)
{    
    int i;
    for(i = 0; i < BOARD_WIDTH; i++) {
        if (board[i][p->y] == num || board[p->x][i] == num)
            return INVALID;
    }
    return VALID;
}

//block positions:
// (0,0), (1,0), (2,0)
// (0,1), (1,1), (2,1)
// (0,2), (1,2), (2,2)
int valid_for_block(struct cell_position *p, int num)
{
    int block_x = floor(p->x / 3);
    int block_y = floor(p->y / 3);
    
    int row_start, row_end;
    int column_start, column_end;
    
    if (block_x == 0) {
        column_start = 0;
        column_end = 3;
    }
    
    else if (block_x == 1) {
        column_start = 3;
        column_end = 6;
    }
    
    else {
        column_start = 6;
        column_end = 9;
    }
    
    if (block_y == 0) {
        row_start = 0;
        row_end = 3;
    }
    
    else if (block_y == 1) {
        row_start = 3;
        row_end = 6;
    }
    
    else {
        row_start = 6;
        row_end = 9;
    }
    
	int i, j;
    for(i = row_start; i < row_end; i++) {
        for(j = column_start; j < column_end; j++) {
            if (board[i][j] == num)
                return INVALID;
        }
    }
    
    return VALID;
}

int valid_for_empty(struct cell_position *p, int tried)
{
    if (tried < BOARD_LOW || tried > BOARD_HIGH)
        return INVALID;
    
    if(column_row_valid(p, tried) != INVALID && valid_for_block(p, tried) != INVALID)
        return VALID;
    
    return INVALID;
}

int solve(int board[][BOARD_WIDTH], struct cell_position *p)
{
	static int call_count = -1;
	call_count++;

	struct cell_position previous;
	previous.x =p->x;
	previous.y = p->y;

	get_next_empty(p);
		
	if (p->x == FULL && p->y == FULL)
		return SOLVED;
		
	int tried_number;
	for(tried_number = BOARD_LOW; tried_number <= BOARD_HIGH; tried_number++) {
		if (valid_for_empty(p, tried_number) == VALID) {
			board[p->x][p->y] = tried_number;
			printf("Set board posiiton (%i, %i) to %i for iteration %i\n", p->x, p->y, tried_number, call_count);
			if (solve(board, p) == SOLVED) {
				printf("YAY WE SOLVED THE PUZZLE\n");
				printb();
				return SOLVED;
			}
			
			//if the solve returns INVALID, we must reset the current board position to EMPTY
			//to ensure that on the next iteration that the valid_for_empty will return our current
			//board position.
			printf("we have encountered an invalid number. reseting board position (%i, %i) whose number is %i to %i for interation %i\n",previous.x, previous.y, board[p->x][p->y], EMPTY, call_count);
			board[p->x][p->y] = EMPTY;
			p->x = previous.x;
			p->y = previous.y;
		}
	}
	//printf("We have exited the loop\n");
	return INVALID;
}

int main(void) 
{
    printf("Unsolved Puzzle\n");
    printb();
    
    struct cell_position p;
    p.x = EMPTY;
    p.y = EMPTY;
    
    solve(board, &p);
    
    printf("\n");
    printf("Solved Puzzle\n");
    printb();
    return 0;
}

[xismn]

It's hard to follow your code. Perhaps you could provide some more detail on the logic of your code, and how it is structured?

At a glance, one thing that seems odd is in your get_next_empty() function. I've copy-and-pasted it here verbatim from your original post:

void get_next_empty(struct cell_position *p)
{
    int i, j;
    for(i = 0; i < BOARD_HEIGHT; i++) {
        for(j = 0; j < BOARD_WIDTH; j++) {
            if (board[i][j] == EMPTY) {
                p->x = i;
                p->y = j;
				return;
            }
        }
    }
    p->x = FULL;
    p->y = FULL;
}

On line 7 you assign i to p->x, and on line 8 you assign j to p->y. Should it not be reversed, since the variable i is what's being used to traverse the height of the board, and the variable j is used to traverse the width of the board?

[haglerchristopher]

p->x = i; //this is the row
p->y = j; //this is the column

Height == the number of rows in the grid
width == the number of columns in the grid

get_next_empty walks the grid from the origin to the bottom right row by row.

this is just walking a two dimensional array, pretty standard stuff:
the indexes are
(0,0), (0,1), (0,2), (0,3), ...
(1,0), (1,1), (1,2), (1,3), ...


The only method that might seem hard to follow is the valid_for block function, but if you look at the block positions you can tell why the block_x is used to set the column and not the row. Is there any part in particular you need me to explain?

[xismn]

The only method that might seem hard to follow is the valid_for block function

I can see that you're using a recursive approach in your solve function, but that's about it. Your code might make sense to you since you wrote it, but nobody else will want to look through every line of your code and decipher it. We help people in our free time, we're not being paid - this isn't meant as ad hominem by the way, it's just the nature of this forum (or maybe the nature of myself).

I'll start out with some questions then:

1.) Since solve() is recursively called, I'm assuming with each recursion it takes a more and more narrow look at a section of the board to determine whether it has been solved - does that sound right at all? Explain your intention behind the recursive approach and how you expect it to operate.

2.) What is BOARD_LOW and BOARD_HIGH? I can see that they are macros, but what is their purpose?

3.) What's the difference between a "block" and a "cell"? Is a block a 3x3 collection of cells?

[haglerchristopher]

After debugging through the code, when the for loop exhaust all of the numbers BOARD_LOW to BOARD_HIGH, 1 to 9, the function exits without reseting the position. Therefore, when solve returns back to the previous call, position previous is two empty cells behind position p. This causes the positions to get all out-of-wack while trying to solve the puzzle. I can tell I was up past my bedtime.

[TheIdeasMan]

If I could mention something :+)

A sudoku solver really needs to have each cell record up to 9 possible candidates. One removes numbers from this list if they exist in the row, column or block. Without that, only the most simple soduko can be solved. For example how does one otherwise identify locked pairs and triples or implement any of the other more advanced solving techniques?

Also, it's better practise to not use #define for constant values, make them const variables instead.

Good Luck !!

[haglerchristopher]

Thanks for the tip. I am only implementing the backtracking as a stepping stone. After this I am going to give the Algorithm Dancing Links a try.