• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Sudoku puzzle

 
Ranch Hand
Posts: 999
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
This Japanse puzzle is becoming popular day by day everywhere.Solving this is not very difficult but surely challenging.First step is very important.



www.sudoku.com
For those who are unaware of Sudoku,its simple.
" Fill in the grid so that every row,
every column, and every 3x3 box
contains the digits 1 through 9. with no digit repeated "
1)Is it possible to write a program which can solve Sudoku puzzle?


[ June 26, 2005: Message edited by: Arjunkumar Shastry ]
 
Ranch Hand
Posts: 539
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
While I don't want to dive into the details, you could write a backtracking solution along the lines of "8 queens", I reckon.

....but I have a thesis to work on, so I'll leave the fun up to someone else


-Tim
 
Ranch Hand
Posts: 1228
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
It's very interesting. I'm seeing this puzzle daily in, NewYork Post & www.thehindu.com , news papers.

Is it possible to write a program which can solve Sudoku puzzle

In our college days we have writtern program for this,
Magic Square program was so popular in those days..
[ June 26, 2005: Message edited by: Srinivasa Raghavan ]
 
Rancher
Posts: 13459
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Arjunkumar Shastry:
1)Is it possible to write a program which can solve Sudoku puzzle?



Yes, although this may be a question for the Programming Diversions forum
Theoretically (if they have provided a correct problem) there is a single solution so a brute-force approach will work. This depends on the efficiency of creating all possible solutions and filtering to find the only one left.

There is no reason you can't use the usual solution method to provide an intelligent algorithm, it all depends on what you know

The page here suggests that it is also the unique solution to a linear equation, which is probably the most efficient approach. ( the 'parent page' is here )
[ June 26, 2005: Message edited by: David O'Meara ]
 
Ranch Hand
Posts: 2937
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The straightforward way would probably take a very long time to calculate, so I implemented it using backtracing, as Tim suggested. It ttok only a quarter of a second for the answer to come out:

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

Unfortunately, MD doesn't accept code, but if you post it in Programming Diversions, I'll be happy to post it in there.
reply
    Bookmark Topic Watch Topic
  • New Topic