sudoku solver

seprich · #1 15-Oct-2007, 12:41

Hi,

In order to practice using ncurses I wrote a little sudoku solver:

CPP / C++ / C Code:

#include <stdlib.h>
#include <string.h>
#include <ncurses.h>


void print_board( char (*board)[][] );

void remove_impossibles( char (*matrix)[][][], int n, int x, int y ); 
void solution_finder_1( char (*board)[][], char (*matrix)[][][] );
int crosscheck( char (*matrix)[][][], int n, int x, int y );
void solution_finder_2( char (*board)[][], char (*matrix)[][][] );
void find_solutions( char (*board)[][], char (*matrix)[][][] );
void solve( char (*board)[][], char (*matrix)[][][] );

/* n ranges 1 - 9 */
void remove_impossibles( char (*matrix)[9][9][9], int n, int x, int y ) {
    int cnt, i, j;
    
    for( cnt=0; cnt<9; cnt++ ) {
        (*matrix)[cnt][y][x] = 0;
        (*matrix)[n-1][y][cnt] = 0;
        (*matrix)[n-1][cnt][x] = 0;
    }
    for( j=0; j<3; j++ ) {
        for( i=0; i<3; i++ ) {
            (*matrix)[n-1][((int)(y/3))*3+j][((int)(x/3))*3+i] = 0;
        }
    }
    (*matrix)[n-1][y][x] = 1;
}

void solution_finder_1( char (*board)[9][9], char (*matrix)[9][9][9] ) {
    int x,y;
    int num, sum, candidate;
    
    for( y=0; y<9; y++ ) {
        for( x=0; x<9; x++ ) {
            if( (*board)[y][x] == 0 ) {
                sum = 0;
                for( num=1; num <= 9; num++ ) {
                    if( (*matrix)[num-1][y][x] != 0 ) {
                        candidate = num;
                        sum++;
                    }
                }
                if( sum == 1 ) {
                    /* only one possible value: */
                    (*board)[y][x] = candidate;
                    remove_impossibles( matrix, candidate, x, y );
                    find_solutions( board, matrix );
                }
            }
        }
    }
}

/* n values 1-9 */
int crosscheck( char (*matrix)[9][9][9], int n, int x, int y ) {
    int cnt, sum;
    int i, j;
    
    if( (*matrix)[n-1][y][x] == 1 ) {
        sum = 0;
        for( cnt=0; cnt<9; cnt++ ) sum += (*matrix)[n-1][y][cnt];
        if( sum == 1 ) return 1;
        
        sum = 0;
        for( cnt=0; cnt<9; cnt++ ) sum += (*matrix)[n-1][cnt][x];
        if( sum == 1 ) return 1;
        
        sum = 0;
        for( j=0; j<3; j++ ) {
            for( i=0; i<3; i++ ) {
                sum += (*matrix)[n-1][((int)(y/3))*3+j][((int)(x/3))*3+i];
            }
        }
        if( sum == 1 ) return 1;
    }
    return 0;
}

void solution_finder_2( char (*board)[9][9], char (*matrix)[9][9][9] ) {
    int x,y;
    int n;
    
    for( y=0; y<9; y++ ) {
        for( x=0; x<9; x++ ) {
            if( (*board)[y][x] == 0 ) {
                for( n=1; n <= 9; n++ ) {
                    if( crosscheck(matrix,n,x,y) == 1 ) {
                        (*board)[y][x] = n;
                        remove_impossibles( matrix, n, x, y );
                        find_solutions( board, matrix );
                    }
                }
            }
        }
    }
}

void find_solutions( char (*board)[][], char (*matrix)[][][] ) {
    solution_finder_1( board, matrix );
    solution_finder_2( board, matrix );
}

void solve( char (*board)[9][9], char (*matrix)[9][9][9] ) {
    int x, y;
    
    memset( (*matrix), 1, 9*9*9 );
    for( y=0; y<9; y++ ) {
        for( x=0; x<9; x++ ) {
            if( (*board)[y][x] != 0 ) remove_impossibles( matrix, (*board)[y][x], x, y );
        }
    }
    find_solutions( board, matrix );
}
 
int main(int argc, char *argv[])
{
    char board[9][9];
    char matrix[9][9][9];
    /* possibility matrix. if matrix[n][y][x]==1 it means that it is possible that in location (x,y) exists value n. */
    
    int x=0, y=0;
    int key = 0;
    int dx[9] = { 2,4,6, 10,12,14, 18,20,22 };
    int dy[9] = { 1,2,3, 5,6,7, 9,10,11 };
    
    initscr();
    cbreak();
    keypad( stdscr, TRUE );
    noecho();
    
    memset( board,  0, 9*9 );
    
    print_board( &board );
    while( key != (int)'q' ) {
        move( dy[y], dx[x] );
        
        key = getch();
        switch( key ) {
            case KEY_RIGHT:
                if( ++x >= 9 ) x=0;
                break;
            case KEY_LEFT:
                if( --x < 0 ) x=8;
                break;
            case KEY_UP:
                if( --y < 0 ) y=8;
                break;
            case KEY_DOWN:
                if( ++y >= 9 ) y=0;
                break;
            case '0':
            case '.':
            case ' ':
                board[y][x] = 0;
                printw( "\xB7" );
                refresh();
                break;
            case '1':
            case '2':
            case '3':
            case '4':
            case '5':
            case '6':
            case '7':
            case '8':
            case '9':
                board[y][x] = (key-(int)'0');
                printw( "%c",key );
                refresh();
                break;
            case 's':
                solve( &board, &matrix );
                print_board( &board );
                break;
        }
    }

    
    endwin();
    
    return EXIT_SUCCESS;
}


void print_board( char (*board)[9][9] ) {
    int x, y;
    
    move( 0, 0 );
    printw( "-------------------------\n" );
    for( y=0; y<9; y++ ) {
        printw( "|" );
        for( x=0; x<9; x++ ) {
            printw( " " );
            if( (*board)[y][x] == 0 ) printw( "\xB7" );
            else printw( "%d", (*board)[y][x] );
            if( x==2 || x==5 ) printw( " |" );
        }
        printw( " |\n" );
        if( y==2 || y==5 ) printw( "|-----------------------|\n" );
    }
    printw( "-------------------------\n" );
    printw( "\nUse arrow keys, numbers and space to edit.\nPress 's' to solve, 'q' to quit.\n" );
    refresh();
}

It can solve e.g. the following problem:

Code:

8 1 0 0 0 0 7 0 3
0 0 0 6 0 7 0 0 8
9 0 2 3 1 0 6 0 0
0 4 0 0 7 0 5 6 0
0 0 7 9 0 1 2 0 0
0 6 3 0 4 0 0 9 0
0 0 4 0 9 2 1 0 6
6 0 0 5 0 4 0 0 0
7 0 8 0 0 0 0 5 9

for which solution:

Code:

-------------------------
| 8 1 6 | 4 5 9 | 7 2 3 |
| 4 3 5 | 6 2 7 | 9 1 8 |
| 9 7 2 | 3 1 8 | 6 4 5 |
|-----------------------|
| 2 4 9 | 8 7 3 | 5 6 1 |
| 5 8 7 | 9 6 1 | 2 3 4 |
| 1 6 3 | 2 4 5 | 8 9 7 |
|-----------------------|
| 3 5 4 | 7 9 2 | 1 8 6 |
| 6 9 1 | 5 8 4 | 3 7 2 |
| 7 2 8 | 1 3 6 | 4 5 9 |
-------------------------

however there still exists many sudoku problems for which there is only one solution but my solver cannot solve. Like:

Code:

3 0 7 0 4 0 0 0 0
0 0 0 0 0 0 0 9 1
8 0 0 0 0 0 0 0 0
4 0 0 0 0 0 7 0 0
0 0 0 1 6 0 0 0 0
0 0 0 2 5 0 0 0 0
0 0 0 0 0 0 3 8 0
0 9 0 0 0 0 5 0 0
0 2 0 6 0 0 0 0 0

and using brute force solving is less elegant than using logical solving..

Any ideas how to improve the solving without brute force method?

davekw7x · #2 15-Oct-2007, 19:01

Quote:

Originally Posted by seprich

In order to practice using ncurses I wrote a little sudoku solver...

Well, it won't even come close to compiling (at least not for me, and, possibly, with other C compilers), since all of the function prototype declarations have "incomplete element type" errors.

So, for those playing at home, if you have problems getting it to compile, you could try a few changes along the following lines:

CPP / C++ / C Code:

void print_board( char (*board)[][9] );

void remove_impossibles( char (*matrix)[][9][9], int n, int x, int y ); 
void solution_finder_1( char (*board)[][9], char (*matrix)[][9][9] );
int crosscheck( char (*matrix)[][9][9], int n, int x, int y );
void solution_finder_2( char (*board)[][9], char (*matrix)[][9][9] );
void find_solutions( char (*board)[][9], char (*matrix)[][9][9] );
void solve( char (*board)[][9], char (*matrix)[][9][9] );
.
.
.
void find_solutions( char (*board)[][9], char (*matrix)[][9][9] ) {
.
.
.

See footnotes.

Quote:

Originally Posted by seprich

...many...problems...my solver cannot solve...

By my count, this puzzle has exactly zero cells that can be filled by simple elimination or filling. Something over 40 trial-and-error attempts are required (I think).

The simplest brute-force program that I could come up with (Just start at the top left and go to the bottom right, calling a solver function recursively by iterating through all legal values for unfilled cells) required 4,480,699 recursions for that puzzle. (It took a smidgen over one second on my modest Linux system).

If you want to see some ideas, you might consider an "exact cover" approach. Here is an interesting forum: Sudoku Programmers Forum

Go to short C-solver with source (exact-cover-algorithm)

A program derived from code there solved that problem in something like four milliseconds real time (User time only goes down to a measurement precision of 1 millisecond, and that is what it showed.) It also verified that the solution is unique. For "puzzles" with more than one solution, it can find them all if you want. (Although by most people's definitions, I think, in order to call it Sudoku, it must have a unique solution.)

One reason I like that forum: Lots of good ideas. I learned a lot (and still had a lot to learn when my all-too-evanescent fancy drifted on to other things).

Two reasons I like the particular piece of code of the first post in that thread:

1. Precious little white space, indentation, etc. Whenever someone issues a challenge about my spending too much effort trying to make source code "pretty", I show them this. (The author was following a tradition among a certain group of above-average programmers who wanted to be able to get the whole program on one page.)

2. Whenever someone points out that "goto" is part of the language and that certain people are too strident in their criticism if frivolous or other gratuitous of goto's, I like to introduce a subtle bug in the middle of the code and ask them to debug it.

Now, in defense of the program and programmer: They certainly don't need me to defend them, but I will make a comment.

This is a complicated sequence of steps. Getting rid of goto statements won't necessarily make it less complicated or easier to understand. I invite any and all to try it.

(No, I will not post my structured programming version of the exact cover solver derived from this. After all, I think that other people should not be deprived of that kind of fun.)

It might soothe the sensibilities of the "goto commandos," but it's still pretty intricate. Sometimes people get mad when we can't explain a complicated sequence in "25 words or less," but that's the way it goes...

Bottom line: If you look for information from experienced puzzle makers and puzzle solvers (get a book or look on the web), you may find lots of non-recursive, non-random-trial-and-error methods that might be someting to put in your program.

Good Luck!

Regards,

Dave

Footnote number 1: In this problem there is one board array and one matrix array. This is one of those places where I might consider use of global variables for these things, therefore eliminating problems of function definitions and eliminating the overhead of their parameters every time. Just a thought

Footnote number 2: In a program like this, where I am likely to run it many, many (many) times during the course of development/debugging, I hate having to enter the puzzle interactively. I would always allow for a command line argument that would allow the puzzle to be read from a file. Just a thought.

Footnote number 3: How much experience do you have in solving very hard Sudoku puzzles, like your second example, "by hand?" Have you tried X-wing? Swordfish? ...
The forum for which I gave the link has a sticky titled "Solving Technique Index." See whether any of those might suggest reasonable additions to your program. There are, of course many other web sites with more-or-less useful solving methodologies. Just a thought.

(Three thoughts in a row! No extra charge! Feel free to disagree/ignore. No hard feelings.)

seprich · #3 15-Oct-2007, 23:58

Thanks Dave! That is very good site indeed. I have not spent much time solving sudokus by hand so it is plain to see that my technique is amateurish. But now I can try implementing some X-wing etc.
Thanks for the suggestions too.. not (yet) runned it many times but will be so as you said will need file input included.

davekw7x · #4 16-Oct-2007, 05:39

Quote:

Originally Posted by davekw7x

Footnote number 2: ...I hate having to enter the puzzle interactively...

I hope you understood my wording. Actually, I like the way the interactive part works. Furthermore, by using ncurses, you created a program that will work on Linux platforms (which usually come with the ncurses library already installed) and Windows (If you have or if you install ncurses).

I appreciate the effort and I admire the results. I just like the option of using a file input for something that I will use over and over. Besides the convenience of multiple runs with the same or slightly different data during development and debugging, I can also use the same input file with other implementations of various sudoku solvers for comparison purposes.

Regards,

Dave

seprich · #5 16-Oct-2007, 11:06

Hi,
The project goes on and after meditating some time I desided to split the program into two parts. One is solver program which eats files and prints results to stdout. The other is ncurses interactive editor which also can launch the solver to solve the puzzle:

sudokueditor.c:

CPP / C++ / C Code:

#include <stdio.h>
#include <ncurses.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#define DIM 9

char board[DIM][DIM];

void load_file( const char *filename );
int  write_file( const char *filename );
void show_board();

void load_file( const char *filename ) {
    FILE *fp;
    int fret;
    int x, y, ch;
    
    if( (fp = fopen( filename, "r" )) ) {
        for( y=0; y<DIM && !feof(fp); ++y ) {
            for( x=0; x<DIM && !feof(fp); ++x ) {
                do {
                    ch = fgetc(fp);
                } while( ch!=EOF && strchr("0123456789-.*",ch)==NULL );
                if( ch!=EOF ) {
                    if( ch=='-' || ch=='.' || ch=='*' ) board[y][x] = 0;
                    else board[y][x] = ch - '0';
                }
            }
        }
        fret = fclose( fp );
        assert( fret==0 );
    }
    /* else do nothing */
}

int  write_file( const char *filename ) {
    int retval = OK;
    int fret, x, y;
    FILE *fp;
    
    if( (fp = fopen( filename, "w" )) ) {
        for( y=0; y<DIM; ++y ) {
            for( x=0; x<DIM; ++x ) {
                fret = fputc( (board[y][x]+'0'), fp );
                assert( fret!=EOF );
            }
            fret = fputc( '\n', fp );
            assert( fret!=EOF );
        }
        
        fret = fclose( fp );
        assert( fret==0 );
    }
    else retval = !OK;
    
    return retval;
}

void show_board() {
    int x, y;
    
    move( 0, 0 );
    if( DIM == 9 ) printw( " ------- ------- ------- \n" );
    for( y=0; y<DIM; y++ ) {
        if( DIM == 9 ) printw( "|" );
        for( x=0; x<DIM; x++ ) {
            printw( " " );
            if( board[y][x] == 0 ) printw( "\xB7" );
            else printw( "%d", board[y][x] );
            if( DIM==9 && (x==2 || x==5) ) printw( " |" );
        }
        if( DIM==9 ) printw( " |" );
        printw( "\n" );
        if( DIM==9 && (y==2 || y==5) ) printw( " ------- ------- ------- \n" );
    }
    if( DIM == 9 ) printw( " ------- ------- ------- \n" );
    printw( "\nUse arrow keys, numbers and space to edit.\n" );
    printw( "Press 's' to save and exit, 'q' to quit without changes.\n" );
    printw( "Press 'S' to save and launch the sudoku solver" );
    refresh();
}

int main(int argc, char *argv[])
{
    int key = 0, x=0, y=0;
    int dx[] = { 2,4,6, 10,12,14, 18,20,22 };
    int dy[] = { 1,2,3, 5,6,7, 9,10,11 };
    int fret = OK;
    int solve = 0;
    char cmd[128];
    
    if( argc < 2 || argc > 3 ) {
        printf( "\nUsage:  sudokueditor <file>\n" );
        printf(   "   or:  sudokueditor <file> <solver>\n\n" );
        printf(   "        <file>   File which is loaded for editing. May also not exist.\n" );
        printf(   "                 Is created upon saving if do not exist.\n" );
        printf(   "        <solver> Program which is called to solve the puzzle.\n" );
        printf(   "                 If this parameter is omitted then tries to use 'sudokusolver'\n\n" );
    }
    else {
        memset( board, 0, DIM*DIM );
        /* Next attempt to load board information from file if it exists. */
        load_file( argv[1] );
        
        /* Interactive mode: */
        initscr();
        cbreak();
        keypad( stdscr, TRUE );
        noecho();
        
        show_board();
        while( key != 'q' ) {
            if( DIM == 9 ) move( dy[y], dx[x] );
            else move( y, 2*x+1 );
            key = getch();
            if( key >= '1' && key <= '9' ) {
                board[y][x] = key - '0';
                printw( "%c",key );
                refresh();
            }
            else {
                switch( key ) {
                    case KEY_RIGHT:
                        if( ++x >= DIM ) x=0;
                        break;
                    case KEY_LEFT:
                        if( --x < 0 ) x=DIM-1;
                        break;
                    case KEY_UP:
                        if( --y < 0 ) y=DIM-1;
                        break;
                    case KEY_DOWN:
                        if( ++y >= DIM ) y=0;
                        break;
                    case '0':
                    case '.':
                    case ' ':
                        board[y][x] = 0;
                        printw( "\xB7" );
                        refresh();
                        break;
                    case 's':
                        fret = write_file( argv[1] );
                        key = 'q';
                        break;
                    case 'S':
                        fret = write_file( argv[1] );
                        solve = 1;
                        key = 'q';
                        break;
                }
            }
        }
        
        endwin();
        /* Interactive mode ended. */
        
        if( fret == OK ) {
            if( solve ) {
                if( argc == 3 ) sprintf( cmd, "./%s %s", argv[2], argv[1] );
                else sprintf( cmd, "./sudokusolver %s", argv[1] );
                system( cmd );
            }
        }
        else {
            printf( "Unable to write file %s\n", argv[1] );
        }
    }
    return EXIT_SUCCESS;
}

This above program can be launched without parameters in order to get instructions... in other words it takes parameters. ha.
Name of the solver program can be given as parameter or if omitted then assumes it is called "sudokusolver".

The other part is then the puzzle solver... but there I haven't yet done much anything new.. anyway it takes filename as commandline parameter and attempts solving... (well the TODO list is quite long still ) (also the current ..finder_1 and ..finder_2 can be combined I think and it will become much shorter that way )

sudokusolver.c

CPP / C++ / C Code:

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
//#include <getopt.h>  TODO
#include <time.h>
#include <assert.h>

char board[9][9];
/* For matrix solving method: */
char matrix[9][9][9];
/* possibility matrix. if matrix[n][y][x]==1 it means that it is possible that in location (x,y) exists value n. */

int verb=0; /* verbosity level (0==succint) */

/* ********************************************************************************************** */
void print_solution( const char (*board)[][9] );
void load_file( const char *filename );
void remove_impossibles( int n, int x, int y ); 
void solution_finder_1();
int crosscheck( int n, int x, int y );
void solution_finder_2();
void find_solutions();
void solve();
/* ********************************************************************************************** */

/**
 * print to stdout the given board
 */
void print_solution( const char (*brd)[9][9] ) {
    int x, y;
    
    if( verb > 4 ) printf( " ------- ------- ------- \n" );
    for( y=0; y<9; y++ ) {
        if( verb > 4 ) printf( "|" );
        for( x=0; x<9; x++ ) {
            if( verb > 4 ) printf( " " );
            printf( "%d", abs( (*brd)[y][x] ) );
            if( verb>4 && (x==2 || x==5) ) printf( " |" );
        }
        if( verb>4 ) printf( " |" );
        printf( "\n" );
        if( verb>4 && (y==2 || y==5) ) printf( " ------- ------- ------- \n" );
    }
    if( verb>4 ) printf( " ------- ------- ------- \n" );
}

/**
 *
 */
void load_file( const char *filename ) {
    FILE *fp;
    int fret;
    int x, y, ch;
    
    memset( board, 0, 81 );
    if( (fp = fopen( filename, "r" )) ) {
        for( y=0; y<9 && !feof(fp); ++y ) {
            for( x=0; x<9 && !feof(fp); ++x ) {
                do {
                    ch = fgetc(fp);
                } while( ch!=EOF && strchr("0123456789-.*",ch)==NULL );
                if( ch!=EOF ) {
                    if( ch=='-' || ch=='.' || ch=='*' ) board[y][x] = 0;
                    else board[y][x] = ch - '0';
                }
            }
        }
        fret = fclose( fp );
        assert( fret==0 );
    }
    /* else do nothing */
}

/* n ranges 1 - 9 */
void remove_impossibles( int n, int x, int y ) {
    int cnt, i, j;
    
    for( cnt=0; cnt<9; cnt++ ) {
        matrix[cnt][y][x] = 0;
        matrix[n-1][y][cnt] = 0;
        matrix[n-1][cnt][x] = 0;
    }
    for( j=0; j<3; j++ ) {
        for( i=0; i<3; i++ ) {
            matrix[n-1][((int)(y/3))*3+j][((int)(x/3))*3+i] = 0;
        }
    }
    matrix[n-1][y][x] = 1;
}

void solution_finder_1() {
    int x,y;
    int num, sum, candidate;
    
    for( y=0; y<9; y++ ) {
        for( x=0; x<9; x++ ) {
            if( board[y][x] == 0 ) {
                sum = 0;
                for( num=1; num <= 9; num++ ) {
                    if( matrix[num-1][y][x] != 0 ) {
                        candidate = num;
                        sum++;
                    }
                }
                if( sum == 1 ) {
                    /* only one possible value: */
                    board[y][x] = candidate;
                    remove_impossibles( candidate, x, y );
                    find_solutions();
                }
            }
        }
    }
}

/* n values 1-9 */
int crosscheck( int n, int x, int y ) {
    int cnt, sum;
    int i, j;
    
    if( matrix[n-1][y][x] == 1 ) {
        sum = 0;
        for( cnt=0; cnt<9; cnt++ ) sum += matrix[n-1][y][cnt];
        if( sum == 1 ) return 1;
        
        sum = 0;
        for( cnt=0; cnt<9; cnt++ ) sum += matrix[n-1][cnt][x];
        if( sum == 1 ) return 1;
        
        sum = 0;
        for( j=0; j<3; j++ ) {
            for( i=0; i<3; i++ ) {
                sum += matrix[n-1][((int)(y/3))*3+j][((int)(x/3))*3+i];
            }
        }
        if( sum == 1 ) return 1;
    }
    return 0;
}

void solution_finder_2() {
    int x,y;
    int n;
    
    for( y=0; y<9; y++ ) {
        for( x=0; x<9; x++ ) {
            if( board[y][x] == 0 ) {
                for( n=1; n <= 9; n++ ) {
                    if( crosscheck(n,x,y) == 1 ) {
                        board[y][x] = n;
                        remove_impossibles( n, x, y );
                        find_solutions();
                    }
                }
            }
        }
    }
}

void find_solutions() {
    solution_finder_1();
    solution_finder_2();
}

void solve() {
    int x, y;
    
    memset( matrix, 1, 9*9*9 );
    for( y=0; y<9; y++ ) {
        for( x=0; x<9; x++ ) {
            if( board[y][x] != 0 ) remove_impossibles( board[y][x], x, y );
        }
    }
    find_solutions();
}
 
int main( int argc, char *argv[] ) {
    FILE *fp;
    //int optch;
    //static char optstring[] = "";   /TODO ..put full featured command option handling
    
    
    verb = 5;
    if( argc > 1 ) {
        load_file( argv[1] );
        solve();
        print_solution( &board );
    }
    else {
        printf("Usage: sudokusolver [-vb] <file>\n" );
    }
    return EXIT_SUCCESS;
}

Howard_L · #6 17-Oct-2007, 01:05

Just thought I'd let you guys know that I compiled this (with the modifications as dave suggested) using pdcurses for win32 which I installed into my mingw setup last month but haven't really gotten to yet. (determined to conquer more msdn console api first)
It compiles and runs ok... pretty cool. So anyone running win32 can write & run in ncurses too.

I did wonder about something though. For me the starting grid looks like this:

Code:

RedHat 9 curses:
|       |       |       |
|       |       |       |
|       |       |       |
|-----------------------|
|       |       |       |
|       |       |       |
|       |       |       |
|-----------------------|
|       |       |       |
|       |       |       |
|       |       |       |
-------------------------

pdcurses blank:
| + + + | + + + | + + + |  +'s are squigly n's ; I think dos extended ascii 0xfc
| + + + | + + + | + + + |
| + + + | + + + | + + + |
|-----------------------|
| + + + | + + + | + + + |
| + + + | + + + | + + + |
| + + + | + + + | + + + |
|-----------------------|
| + + + | + + + | + + + |
| + + + | + + + | + + + |
| + + + | + + + | + + + |
-------------------------

Is that what you get in linux? whitespace?
...and does that pdcurses 0xfc output make sense? (maybe I should look at the code huh...)
++Howard;

seprich · #7 17-Oct-2007, 08:55

Quote:

Originally Posted by Howard_L

Is that what you get in linux? whitespace?
...and does that pdcurses 0xfc output make sense? (maybe I should look at the code huh...)
++Howard;

I developed in debian and the initial empty table looks like:

Code:

 ------- ------- -------
| · · · | · · · | · · · |
| · · · | · · · | · · · |
| · · · | · · · | · · · |
 ------- ------- -------
| · · · | · · · | · · · |
| · · · | · · · | · · · |
| · · · | · · · | · · · |
 ------- ------- -------
| · · · | · · · | · · · |
| · · · | · · · | · · · |
| · · · | · · · | · · · |
 ------- ------- -------

Instead of using 0's to mark the empty places in sudoku board I used '\xB7' as a placeholder.
That '\xB7' is supposed to be shown as a centered dot glyph.. If I limited my strings to standard ASCII codes (0-127) it would be more likely that it shows 'correctly' in other environments.

Source: http://invisible-island.net/ncurses/ncurses.faq.html
From chapter "Line-drawing characters come out as x's and q's" forward explains some of the reasons why the characters may not show the way expected.

I am a bit confused what would be the best solution though... One option is that I limit myself to use plain ASCII to ensure that it shows properly on other systems (what a pity). Other possibility is that I try to somehow write code that can adapt to the expected encoding... no clue yet how to do that, maybe someone can help me out with this ?

Howard_L · #8 17-Oct-2007, 09:27

Yes plain ascii makes sense but 0xB7 is into the extended ascii set which will show different characters for different systems.
I think a value between 0x20 and 0x7e should show the same character on all systems.
I guess the only thing centered though is the - or maybe a + or = or * .
Not as nifty as a centered dot... oh well.
I guess the another thing to do would be a slew of #ifdef's which seems overkill unless you feel need to spend time learning more about that...
It's not a deal, I was just curious. It works well! Solved Wikipedia's example.
Howard;

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Sudoku - Lite version	MiZaRiZ	C++ Forum	6	03-Mar-2007 07:40
sudoku C++, need lots of help :S	3shtar	C++ Forum	3	06-Apr-2006 11:10
sudoku help	kris5683	C++ Forum	2	18-Nov-2005 07:58
sudoku	kris5683	C++ Forum	1	08-Nov-2005 09:48

sudoku solver

Re: sudoku solver

Re: sudoku solver

Re: sudoku solver

Re: sudoku solver

Re: sudoku solver

Re: sudoku solver

Re: sudoku solver