Problems on creating a sudoku verifier

This is a discussion on Problems on creating a sudoku verifier within the C Programming forums, part of the General Programming Boards category; Hi there.I'm quite new to C and these boards. I have a question on sudoku(9x9): You'll input 81 digits like, ...

  1. #1
    Registered User
    Join Date
    Aug 2011
    Posts
    6

    Unhappy Problems on creating a sudoku verifier

    Hi there.I'm quite new to C and these boards.

    I have a question on sudoku(9x9):

    You'll input 81 digits like, 123412314523452345.......79687689.And the program will verify if these sequence is a valid sudoku board.It will suppose to read
    1 2 3 4 1 2 3 1 4
    5 2 3 4 5 2 3 4 5
    and so on...
    My first problem is that integers can't hold this value this large.What should I do to store this value?

    I was thinking,in order to verify if it's a sudoku board,the program needs to add numbers in a row,column or a 3x3 box,and if the sum is not equal to 45,then the program will say that it is not a valid board.Is this algorithm right?Like if and else statements.

    And in using arrays,do you add like a[0] + a[8]? How do you add from box 0 to box 8?

    I'm just confused about this.Any reply would be really appreciated.

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,434
    Read 81 digits as a string, then extract one digit at a time.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Sudoku solvers can use the 45, but few do. Most use the ONE rule of Sudoku - that each row, column or box, can have only one value of 1-9.

    This clearly violates the one rule:
    Code:
    1 2 3 | 4 1 2 | 3 1 4
    5 2 3 | 4 5 2 | 3 4 5
    Don't even think about programming a "human" type of solver. Sudoku has so many subtleties to solving it the "human" way, that it's astonishing. That makes writing a robust human type of solver, extremely difficult. Think brute force solver.
    Last edited by Adak; 08-16-2011 at 06:22 AM.

  4. #4
    Registered User
    Join Date
    Aug 2011
    Posts
    6
    I know how sudoku works.
    It's just an example ,and I know that example is gonna make the program display that it's not a valid board.
    I was talking about the sum of each row,column,and board.

    Thanks for the replies.
    Sorry if I don't know much about programming yet.

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    First, Welcome to the board, Twoxacross!

    I've seen programs that used the 45 sum test, yes.

    You don't need to apologize. Nobody is born able to program in C!

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    The problem with the 45 rule is that it doesn't work. "555555555" adds up to 45, but it isn't legal sudoku.

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Exactly. The 45 sum can be used as a preliminary check, and as a final check for the last digit in a row, column, or box that is otherwise, legal. It can't be used as the only check, however.

  8. #8
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    Quote Originally Posted by Adak View Post
    Exactly. The 45 sum can be used as a preliminary check, and as a final check for the last digit in a row, column, or box that is otherwise, legal. It can't be used as the only check, however.
    Why use two checks for the same thing when they need the same loop to run ?
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  9. #9
    Registered User
    Join Date
    May 2011
    Location
    Around 8.3 light-minutes from the Sun
    Posts
    1,866
    Quote Originally Posted by twoxacross View Post
    I was talking about the sum of each row,column,and board.

    Thanks for the replies.
    Sorry if I don't know much about programming yet.
    You will need to sum the elements of the array up yourself using a loop. You should read: Lesson 3 - Loops and Lesson 8 -Arrays. These lessons will show you what you need to do.
    Quote Originally Posted by anduril462 View Post
    Now, please, for the love of all things good and holy, think about what you're doing! Don't just run around willy-nilly, coding like a drunk two-year-old....
    Quote Originally Posted by quzah View Post
    ..... Just don't be surprised when I say you aren't using standard C anymore, and as such,are off in your own little universe that I will completely disregard.
    Warning: Some or all of my posted code may be non-standard and as such should not be used and in no case looked at.

  10. #10
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by manasij7479 View Post
    Why use two checks for the same thing when they need the same loop to run ?
    Say you are trying the next candidate digit, for the last empty position, in a row. It's faster to check whether the rest of the row + the candidate digit equals 45, then it is to check for the candidate digit equals any of the other eight values for the row.

    Why? Because you've already summed up the row digits previously. Just add the last candidate, and make one comparison.

    There are faster ways to do this in a Sudoku program - several actually, some of which are blindingly fast ways - but the programming is not as intuitive.

  11. #11
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by Adak View Post
    Why? Because you've already summed up the row digits previously. Just add the last candidate, and make one comparison.
    That is a really really really really really really really really really really really really really really really really really really really really big assumption -- you won't have needed the sum for anything, ever, before now; so why did you add it up?

  12. #12
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    This CAN be a relatively fast way to solve a puzzle, IF you design your program, to use it. It is NOT one of the fastest ways, imo.

    The two fastest ways involve bit fiddling or using Knuth's "Dancing Links". Neither of these algorithms are suited for beginners, however. With some very carefully chosen optimizations, they are absolute SCREAMERS.

  13. #13
    Registered User
    Join Date
    Aug 2011
    Posts
    6
    Thanks for the replies,and the lessons would really help a lot.

  14. #14
    Registered User
    Join Date
    Aug 2011
    Posts
    6
    last question:
    How can I add a whole row,column or box?(Should I do if(a[0]+a[1]+...+a[8] = 45)
    printf(...

    or is there a shorter way to do it?

    And how can I make the program verify if a number is not repeated in a row,column,and a box?

  15. #15
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,434
    Use some for() loops.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problems creating new line
    By cjohnson412 in forum C++ Programming
    Replies: 4
    Last Post: 02-03-2008, 10:31 PM
  2. having problems with creating a file
    By jackmanplus in forum C++ Programming
    Replies: 6
    Last Post: 07-24-2006, 08:47 PM
  3. Problems creating a new class
    By nickname_changed in forum C++ Programming
    Replies: 3
    Last Post: 05-22-2003, 01:47 AM
  4. Equation Verifier! Almost complete!
    By Nakeerb in forum C++ Programming
    Replies: 5
    Last Post: 11-30-2002, 01:26 PM
  5. Idea: Formula Verifier
    By vasanth in forum Contests Board
    Replies: 2
    Last Post: 10-08-2002, 06:43 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21