Thread: simple sudoku

  1. #16
    Registered User
    Join Date
    Jul 2009
    Posts
    19
    both...

  2. #17
    Registered User
    Join Date
    Jun 2009
    Posts
    15
    Quote Originally Posted by legit View Post
    Dude, post your code and your problem... Your trying to make us find treasure with no map here!
    Fyi, she hasn't start her coding.
    Else, she would have shown it here.
    All she needs is the whole concept about it.
    And where and how she should start it.

  3. #18
    Student legit's Avatar
    Join Date
    Aug 2008
    Location
    UK -> Newcastle
    Posts
    156
    Quote Originally Posted by Erica View Post
    Fyi, she hasn't start her coding.
    Else, she would have shown it here.
    All she needs is the whole concept about it.
    And where and how she should start it.
    Yes I realise that
    MSDN <- Programmers Haven!

  4. #19
    Registered User
    Join Date
    Jun 2009
    Posts
    15
    help her on.

  5. #20
    Student legit's Avatar
    Join Date
    Aug 2008
    Location
    UK -> Newcastle
    Posts
    156
    Quote Originally Posted by Erica View Post
    help her on.
    I would if I had ever made a sodoku solver before, maybe I should have a go now and see where I get.
    MSDN <- Programmers Haven!

  6. #21
    Registered User
    Join Date
    Jun 2009
    Posts
    15
    ahaha
    cool.

    btw, the main thing is it allow user to enter 16 numbers without repetition at each column and row?

  7. #22
    Student legit's Avatar
    Join Date
    Aug 2008
    Location
    UK -> Newcastle
    Posts
    156
    Lemmi guess, you guys are in the same class? And it depends, the sodoku may be larger than 16x16. A sodoku solver, from my point of view, should solve a pre-set/pre-loaded incomplete sodoku.
    MSDN <- Programmers Haven!

  8. #23
    Registered User
    Join Date
    Jun 2009
    Posts
    15
    Quote Originally Posted by legit View Post
    A sodoku solver, from my point of view, should solve a pre-set/pre-loaded incomplete sodoku.
    Hurm...
    I don't get what do you mean by pre-set/pre-loaded incomplete sudoku..
    Further explanation please..

  9. #24
    Student legit's Avatar
    Join Date
    Aug 2008
    Location
    UK -> Newcastle
    Posts
    156
    Opinions may vary, but mine is that a sodoku solver should be able to complete an incomplete sodoku either loaded to the program, or defined by the user at run-time.
    MSDN <- Programmers Haven!

  10. #25
    Registered User
    Join Date
    Jun 2009
    Posts
    15
    meaning I need to came out with an algorithm of the game itself first?

  11. #26
    Student legit's Avatar
    Join Date
    Aug 2008
    Location
    UK -> Newcastle
    Posts
    156
    Well what do you have so far, design wise?
    MSDN <- Programmers Haven!

  12. #27
    Registered User
    Join Date
    Jun 2009
    Posts
    15
    just started the design phase..
    but still kinda stuck with the whole thingy.

    what kind of condition should I assign to in order to check if the user repeated the number?

  13. #28
    Student legit's Avatar
    Join Date
    Aug 2008
    Location
    UK -> Newcastle
    Posts
    156
    I've been thinking - creating a sodoku solver would be difficult without using arrays? I can't seem to find a way without arrays, using arrays is still pretty tough!
    MSDN <- Programmers Haven!

  14. #29
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    I've written a sudoku solver before, but I should mention that I wrote it out of my head without doing any research first. I'm reasonably good at solving sudoku puzzles, but I'm sure you'd find more waterproof methods if you looked around.

    Anyway, the method I used went something like this. I represented all of the data in the puzzle as a two-dimensional array, and applied various algorithms to the puzzle until it was solved or the puzzle was unchanged (in which case the program wasn't good enough to solve it). The algorithms would be strategies that you might use when solving a sudoku puzzle by hand; e.g., if eight of the nine numbers in a row are filled out, then the last number is whichever number does not appear in the row.

    As I said, it's a reasonably good method, but not perfect. For one thing, it doesn't completely model how a human sudoku-solver will think. A lot of the thought process goes something like this: "if I put this 7 here, would it create an impossibility?" Here an "impossibility" is something like two 7's in the same quadrant, column, or row. If it is impossible, you rule out that move, which narrows down your choices; maybe since the 7 can't go there, it has to go somewhere else. And so on.

    I never did look at a "real" sudoku-solving program. There are lots of them online that profess to be able to solve any sudoku puzzle (which is certainly possible). If you want more ideas you could see how some of them work.

    Well, here I was talking about automatically solving sudoku puzzles. You'll have to forgive me if that's not what you want, since you haven't been very clear on that point. Are you just trying to create a sudoku game that ensures that every move the player makes is a valid one?

    That's pretty easy. When the user asks to place a '7' in a particular spot, you just scan that row and column for other sevens, and that quadrant too. I'm not sure if "quadrant" is quite the right word, but you know what I mean. Here's the sort of code you might use.
    Code:
    /** Check to see if the user made a valid move. The user is assumed to have
        attempted to place the number @a number at position @c data[x][y].
    */
    int is_valid_move(int data[9][9], int x, int y, int number) {
        /* The x and y coordinates of the upper-left corner of the quadrant
            in which the position (x, y) lies.
        */
        int qx = (x / 3) * 3, qy = (y / 3) * 3;
    
        int i, j;
        for(i = 0; i < 9; i ++) {
            /* check this column */
            if(data[x][i] == number) return 0;
    
            /* and this row */
            if(data[i][y] == number) return 0;
        }
    
        /* check this quadrant */
        for(int i = 0; i < 3; i ++) {
            for(int j = 0; j < 3; j ++) {
                if(data[qx + i][qy + j] == number) return 0;
            }
        }
    
        /* The number wasn't duplicated in the column, row, or quadrant;
            therefore, this must be a valid move.
        */
        return 1;
    }
    That assumes you use -1 or something to represent a square which has not been given any number.

    Anyway, enough blathering. If you want more help you'd better describe what you're trying to do.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  15. #30
    Registered User
    Join Date
    Mar 2007
    Posts
    416
    In relation to the solution dwks said, I implemented a way for the solver to check if there are any numbers that absolutely cannot be any other number than a single number. After each move, since each number placement could determine the placement of another number.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. creating very simple text editor using c
    By if13121 in forum C Programming
    Replies: 9
    Last Post: 10-19-2010, 05:26 PM
  2. Simple message encryption
    By Vicious in forum C++ Programming
    Replies: 10
    Last Post: 11-07-2004, 11:48 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Simple simple program
    By Ryback in forum C++ Programming
    Replies: 10
    Last Post: 09-09-2004, 05:48 AM
  5. Need help with simple DAQ program
    By canada-paul in forum C++ Programming
    Replies: 12
    Last Post: 03-15-2002, 08:52 AM