#include <cstdio>
#include <cstdlib>
#include "tbb/atomic.h"
#include "tbb/tick_count.h"
#include "tbb/task_scheduler_init.h"
#include "tbb/task_group.h"

Include dependency graph for sudoku.cpp:

Classes
struct	board_element
class	PartialSolveBoard
Defines
#define	__TBB_LAMBDAS_PRESENT ( _MSC_VER >= 1600 && !__INTEL_COMPILER \|\| __INTEL_COMPILER > 1100 && _TBB_CPP0X )
Functions
void	calculate_potentials (board_element *b)
void	copy_board (board_element src, board_element dst)
bool	examine_potentials (board_element b, bool progress)
bool	fixed_board (board_element *b)
bool	in_block (board_element *b, unsigned row, unsigned col, unsigned short p)
bool	in_col (board_element *b, unsigned row, unsigned col, unsigned short p)
bool	in_row (board_element *b, unsigned row, unsigned col, unsigned short p)
void	init_board (board_element *b, unsigned short arr[81])
void	init_board (board_element *b)
void	init_potentials (board_element *b)
int	main (int argc, char *argv[])
void	ParseCommandLine (int argc, char *argv[])
void	partial_solve (board_element *b, unsigned first_potential_set)
void	print_board (board_element *b)
void	print_potential_board (board_element *b)
void	read_board (char *filename)
bool	valid_board (board_element *b)
Variables
const unsigned	BOARD_DIM = 9
const unsigned	BOARD_SIZE = 81
task_group *	g
unsigned short	init_values [BOARD_SIZE]
atomic< unsigned >	nSols
unsigned	NSolutions
unsigned	NThreads
bool	Verbose = false

Define Documentation

#define __TBB_LAMBDAS_PRESENT ( _MSC_VER >= 1600 && !__INTEL_COMPILER || __INTEL_COMPILER > 1100 && _TBB_CPP0X )

Definition at line 38 of file sudoku.cpp.

Function Documentation

void calculate_potentials ( board_element * b )

Definition at line 146 of file sudoku.cpp.

References BOARD_DIM, BOARD_SIZE, in_block(), in_col(), in_row(), and board_element::potential_set.

Referenced by partial_solve().

                                            {
    for (unsigned i=0; i<BOARD_SIZE; ++i) {
        b[i].potential_set = 0;
        if (!b[i].solved_element) { // element is not yet fixed
            unsigned row = i/BOARD_DIM, col = i%BOARD_DIM;
            for (unsigned potential=1; potential<=BOARD_DIM; ++potential) {
                if (!in_row(b, row, col, potential) && !in_col(b, row, col, potential)
                    && !in_block(b, row, col, potential))
                    b[i].potential_set |= 1<<(potential-1);
            }
        }
    }
}

void copy_board	(	board_element *	src,
		board_element *	dst
	)

Definition at line 115 of file sudoku.cpp.

References BOARD_SIZE.

Referenced by partial_solve().

                                                        {
    for (unsigned i=0; i<BOARD_SIZE; ++i)
        dst[i].solved_element = src[i].solved_element;
}

bool examine_potentials	(	board_element *	b,
		bool *	progress
	)

Definition at line 172 of file sudoku.cpp.

References BOARD_SIZE, board_element::solved_element, and valid_board().

Referenced by partial_solve().

                                                          {
    bool singletons = false;
    for (unsigned i=0; i<BOARD_SIZE; ++i) {
        if (b[i].solved_element==0 && b[i].potential_set==0) // empty set
            return false;
        switch (b[i].potential_set) {
        case 1:   { b[i].solved_element = 1; singletons=true; break; }
        case 2:   { b[i].solved_element = 2; singletons=true; break; }
        case 4:   { b[i].solved_element = 3; singletons=true; break; }
        case 8:   { b[i].solved_element = 4; singletons=true; break; }
        case 16:  { b[i].solved_element = 5; singletons=true; break; }
        case 32:  { b[i].solved_element = 6; singletons=true; break; }
        case 64:  { b[i].solved_element = 7; singletons=true; break; }
        case 128: { b[i].solved_element = 8; singletons=true; break; }
        case 256: { b[i].solved_element = 9; singletons=true; break; }
        }
    }
    *progress = singletons;
    return valid_board(b);
}

bool fixed_board ( board_element * b )

Definition at line 120 of file sudoku.cpp.

References BOARD_SIZE.

Referenced by partial_solve().

                                   {
    for (int i=BOARD_SIZE-1; i>=0; --i)
        if (b[i].solved_element==0) return false;
    return true;
}

bool in_block	(	board_element *	b,
		unsigned	row,
		unsigned	col,
		unsigned short	p
	)

Definition at line 138 of file sudoku.cpp.

References BOARD_DIM.

Referenced by calculate_potentials(), and valid_board().

                                                                              {
    unsigned b_row = row/3 * 3, b_col = col/3 * 3;
    for (unsigned i=b_row; i<b_row+3; ++i)
        for (unsigned j=b_col; j<b_col+3; ++j)
            if (!(i==row && j==col) && b[i*BOARD_DIM+j].solved_element==p) return true;
    return false;
}

bool in_col	(	board_element *	b,
		unsigned	row,
		unsigned	col,
		unsigned short	p
	)

Definition at line 132 of file sudoku.cpp.

References BOARD_DIM.

Referenced by calculate_potentials(), and valid_board().

                                                                            {
    for (unsigned r=0; r<BOARD_DIM; ++r)
        if (r!=row && b[r*BOARD_DIM+col].solved_element==p)  return true;
    return false;
}

bool in_row	(	board_element *	b,
		unsigned	row,
		unsigned	col,
		unsigned short	p
	)

Definition at line 126 of file sudoku.cpp.

References BOARD_DIM.

Referenced by calculate_potentials(), and valid_board().

                                                                            {
    for (unsigned c=0; c<BOARD_DIM; ++c)
        if (c!=col && b[row*BOARD_DIM+c].solved_element==p)  return true;
    return false;
}

void init_board	(	board_element *	b,
		unsigned short	arr[81]
	)

Definition at line 103 of file sudoku.cpp.

References BOARD_SIZE, board_element::potential_set, and board_element::solved_element.

                                                          {
    for (unsigned i=0; i<BOARD_SIZE; ++i) {
        b[i].solved_element = arr[i]; 
        b[i].potential_set = 0;
    }
}

void init_board ( board_element * b )

Definition at line 98 of file sudoku.cpp.

References BOARD_SIZE.

Referenced by main().

                                  {
    for (unsigned i=0; i<BOARD_SIZE; ++i)
        b[i].solved_element = b[i].potential_set = 0;
}

void init_potentials ( board_element * b )

Definition at line 110 of file sudoku.cpp.

References BOARD_SIZE.

                                       {
    for (unsigned i=0; i<BOARD_SIZE; ++i)
        b[i].potential_set = 0;
}

int main	(	int	argc,
		char *	argv[]
	)

Definition at line 261 of file sudoku.cpp.

References BOARD_SIZE, g, init_board(), init_values, tbb::tick_count::now(), nSols, NSolutions, NThreads, ParseCommandLine(), partial_solve(), read_board(), t0, and tbb::internal::task_group_base::wait().

                                 {
    board_element *start_board;
    start_board = (board_element *)malloc(BOARD_SIZE*sizeof(board_element));
    NThreads = 1;
    nSols = 0;
    ParseCommandLine(argc, argv);
    read_board(argv[1]);
    init_board(start_board, init_values);
    task_scheduler_init init(NThreads);
    g = new task_group;
    tick_count t0 = tick_count::now();
    partial_solve(start_board, 0);
    g->wait();
    tick_count t1 = tick_count::now();
    delete g;

    if (NSolutions == 1) {
        printf("Sudoku: Time to find first solution on %d threads: %6.6f seconds.\n", NThreads, (t1 - t0).seconds());
    }
    else {
        printf("Sudoku: Time to find all %d solutions on %d threads: %6.6f seconds.\n", (int)nSols, NThreads, (t1 - t0).seconds());
  }
};

void ParseCommandLine	(	int	argc,
		char *	argv[]
	)

Definition at line 245 of file sudoku.cpp.

References NSolutions, NThreads, and Verbose.

                                              {
    if (argc < 4) {
        fprintf(stderr, 
                "Usage: sudoku <inputfilename> <nthreads> <nSolutions> [-p]\n"
                "  nSolutions=1 stops after finding first solution\n"
                "    and any other value finds all solutions; \n"
                "  -p prints the first solution.\n");
        exit(1);
    }
    else {
        sscanf(argv[2], "%d", &NThreads);
        sscanf(argv[3], "%d", &NSolutions);
    }
    if (argc==5) Verbose = true;
}

void partial_solve	(	board_element *	b,
		unsigned	first_potential_set
	)

Referenced by main(), and partial_solve().

void print_board ( board_element * b )

Definition at line 72 of file sudoku.cpp.

References BOARD_DIM.

Referenced by partial_solve().

                                   {
    for (unsigned row=0; row<BOARD_DIM; ++row) {
        for (unsigned col=0; col<BOARD_DIM; ++col) {
            printf(" %d", b[row*BOARD_DIM+col].solved_element);
            if (col==2 || col==5) printf(" |");
        }
        printf("\n");
        if (row==2 || row==5) printf(" ---------------------\n");
    }
}

void print_potential_board ( board_element * b )

Definition at line 83 of file sudoku.cpp.

References BOARD_DIM.

                                             {
    for (unsigned row=0; row<BOARD_DIM; ++row) {
        for (unsigned col=0; col<BOARD_DIM; ++col) {
            if (b[row*BOARD_DIM+col].solved_element) 
                printf("  %4d ", b[row*BOARD_DIM+col].solved_element);
            else
                printf(" [%4d]", b[row*BOARD_DIM+col].potential_set);
            if (col==2 || col==5) printf(" |");
        }
        printf("\n");
        if (row==2 || row==5)
            printf(" ------------------------------------------------------------------\n");
    }
}

void read_board ( char * filename )

Definition at line 57 of file sudoku.cpp.

References BOARD_SIZE, and init_values.

Referenced by main().

                                {
    FILE *fp;
    int input;
    fp = fopen(filename, "r");
    for (unsigned i=0; i<BOARD_SIZE; ++i) {
        if (fscanf(fp, "%d", &input))
            init_values[i] = input;
        else {
            fprintf(stderr, "sudoku: Error in input file at entry %d, assuming 0.\n", i);
            init_values[i] = 0;
        }
    }
    fclose(fp);
}

bool valid_board ( board_element * b )

Definition at line 160 of file sudoku.cpp.

References BOARD_DIM, BOARD_SIZE, in_block(), in_col(), and in_row().

Referenced by examine_potentials().

                                   {
    bool success=true;
    for (unsigned i=0; i<BOARD_SIZE; ++i) {
        if (success && b[i].solved_element) { // element is fixed
            unsigned row = i/BOARD_DIM, col = i%BOARD_DIM;
            if (in_row(b, row, col, b[i].solved_element) || in_col(b, row, col, b[i].solved_element) || in_block(b, row, col, b[i].solved_element))
                success = false;
        }
    }
    return success;
}