sudokusolver

/******************************************************************************

Welcome to GDB Online.
  GDB online is an online compiler and debugger tool for C, C++, Python, PHP, Ruby,
  C#, OCaml, VB, Perl, Swift, Prolog, Javascript, Pascal, COBOL, HTML, CSS, JS
  Code, Compile, Run and Debug online from anywhere in world.

*******************************************************************************/
#include <stdio.h>
unsigned char* sudoku_src = "700000400020070080003008079900500300060020090001097006000300900030040060009001035";
//"001093000006000800070200051800040200400801006007050008920004010005000900000930500";
/*"001007090\
590080001\
030000080\
000005800\
050060020\
004100000\
080000030\
100020079\
020700400";*/
enum sudoku_values{
    one = 1,
    two = one << 1,
    three = two << 1,
    four = three << 1,
    five = four << 1,
    six = five << 1,
    seven = six << 1,
    eight = seven << 1,
    nine = eight << 1,
    all = one | two | three | four | five | six | seven | eight | nine
};
static enum sudoku_values map_char_to_sudoku_value[255] =
{
    ['0'] = all,
    ['1'] = one,
    ['2'] = two,
    ['3'] = three,
    ['4'] = four,
    ['5'] = five,
    ['6'] = six,
    ['7'] = seven,
    ['8'] = eight,
    ['9'] = nine,
};
static char sudoku_value_char_to_char[1024] =
{
    [all] = '0',
    [one] = '1',
    [two] = '2',
    [three] = '3',
    [four] = '4',
    [five] = '5',
    [six] = '6',
    [seven] = '7',
    [eight] = '8',
    [nine] = '9',
};
int square_index(int row_col){
    return 3 * (row_col / 3);//integer division floors
}

typedef struct sudoku_pair{
    int row;
    int col;
    int value;
}sudoku_pair;
typedef struct sudoku{
    union{
    int roster[9][9];
    int roster_line[81];
    };
    // flag[i] == 0: to be considered this
    // flag[i] == 1: never consider
    union{
    int roster_flags[9][9];
    int roster_flags_line[88];
    };
    int N;
    sudoku_pair stack[81];
}sudoku;
sudoku new_sudoku(){
    sudoku rv;
    for(int i = 0 ; i < 81; i++)
        rv.roster_line[i] = all;
    return rv;
}
sudoku sudoku_from_string(unsigned char* source){
    sudoku rv = {0};
    int* values = (rv.roster_line);

    while(*source)
        *values++ = map_char_to_sudoku_value[*source++];
    for(int i = 0; i < 9;i++)
        for(int j = 0; j < 9;j++)
            if(rv.roster[i][j] != all){
                rv.stack[rv.N++] = (sudoku_pair){i,j,rv.roster[i][j]};
                rv.roster_flags[i][j] = 1;
            }

    return rv;
}
void print_sudoku(sudoku s){
    for(int i = 0 ; i < 81; i++)
        printf("%s%c", (i%9 == 0)?"\n":"", sudoku_value_char_to_char[s.roster_line[i]] );
}

void remove_value_from_row(sudoku* s, int row, int bit_filter){
    for(int col = 0; col < 9; col++)
        s->roster[row][col] &= bit_filter;
}
void remove_value_from_col(sudoku* s, int col, int bit_filter){
    for(int row = 0; row < 9; row++)
        s->roster[row][col] &= bit_filter;
}
void remove_value_from_square(sudoku* s, int square_row,int square_col, int bit_filter){
    for(int row = square_row; row < square_row + 3; row++)
        for(int col = square_col; col < square_col + 3; col++)
           s->roster[row][col] &= bit_filter;
}
void remove_value_from_sudoku(sudoku* s,sudoku_pair pair){
    int row = pair.row;
    int col = pair.col;
    enum sudoku_values val = pair.value;
    int  bit_filter = all & (~val);
    remove_value_from_row(s,row,bit_filter);
    remove_value_from_col(s,col,bit_filter);
    remove_value_from_square(s,square_index(row),square_index(col),bit_filter);
    s->roster[row][col] = val;
}

void partial_solve(sudoku* s){
    do{
        for(int i = 0 ; i < s->N; i++)
            remove_value_from_sudoku(s,s->stack[i]);
        s->N=0;
        for(int i = 0; i < 9;i++)
            for(int j = 0; j < 9;j++)
                {
                    if(s->roster_flags[i][j])
                        continue;
                    int val = s->roster[i][j];
                    if(val == 0){
                        //printf("\nunsolvable i %i, j %i\n",i,j);
                        goto unsolvable;
                    }
                    if(val == one || val == two || val == three || val == four || val == five || val == six || val == seven || val == eight || val == nine)
                        {
                            s->stack[s->N++] = (sudoku_pair){i,j,val};
                            s->roster_flags[i][j] = 1;
                        }
                }
    }while(s->N);
    unsolvable:;
}
static int sudoku_count;
static sudoku sudoku_stack[1000];
void branch_sudoku(sudoku* s){
 //   printf("\nbranches:%i\n",sudoku_count);
    for(int i = 0; i < 9;i++)
        for(int j = 0; j < 9;j++)
            if(s->roster_flags[i][j] == 0){
                for(int val = 0; val < 9 ; val++)
                    if(s->roster[i][j] & (1 << val)){
                        sudoku_stack[sudoku_count] = *s;
                        sudoku_stack[sudoku_count].roster[i][j] = (1 << val);
                        sudoku_stack[sudoku_count].stack[sudoku_stack[sudoku_count].N++] = (sudoku_pair){i, j,  1 << val};
                        sudoku_count++;
                    }
                    return;
            }

}
int solved(sudoku* s){
    int rv=1;
    for(int i =0;i<81;i++)
        rv &= s->roster_flags_line[i];
    return rv;
}
int main()
{
    sudoku s = sudoku_from_string(sudoku_src);
    sudoku_stack[sudoku_count++] = s;

    print_sudoku(s);
    while(sudoku_count){
        s = sudoku_stack[--sudoku_count];
        partial_solve(&s);
        if(solved(&s))
            break;
        else
            branch_sudoku(&s);
    }
   print_sudoku(s);
    return 0;
}