Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Invalid (Jigsaw) Puzzle Recognition

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> The mathematics of sudoku
View previous topic :: View next topic  
Author Message
Pjotr

Joined: 18 Oct 2008
Posts: 7
:
Location: Tilburg (NL)

Items
PostPosted: Sat Oct 18, 2008 9:51 pm    Post subject: Invalid (Jigsaw) Puzzle Recognition Reply with quote

Hello!

I am trying to make a flexible Sudoku Solver/Creator. In the program you can 'draw' your puzzle and then Create or Solve the Sudoku.

The reason I am making it is because in the newspaper of my mum and dad the puzzles have a lot of different shapes. So I thought, I have to be able to solve them all!

Some examples of the shapes:


1)


2)


3)


4)


5)



1 - 4 are solvable. 5 I'm not sure. When a Create a Sudoku, and I'm stuck I will guess one and then try if I then can Solve it. I'l keep guessing untill I get an error or I 'Solved' the puzzle. When an error came, I 'ungues' the last I guessed and choose another number. The program stops if I guessed everiting with no 'Solved' puzzle or when I Solved the puzzle.

A normal 3x3 Sudoku is done in less then a second. With a 3x3 Sudoku I know it can be maked. But with puzzle #5 I can't. I just keep guessing. I stopped it after 5 minutes..

Oke, my question (a long intro..). Can I know if an puzzle is invalid by looking at 'something'?

An example:



Here the 2 purple squares will have the same number, so it can't be solved. I know this even though I did not try and guessed..

So, is there a way to systematicly analyse if an puzzle shape can become an valid puzzle?
Back to top
View user's profile Send private message
Pjotr

Joined: 18 Oct 2008
Posts: 7
:
Location: Tilburg (NL)

Items
PostPosted: Tue Oct 21, 2008 4:15 pm    Post subject: Reply with quote

Didn't I explain it well?

Doesn't anyone know it?

Or am I to impatient?
Back to top
View user's profile Send private message
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Wed Oct 22, 2008 10:31 am    Post subject: Reply with quote

The only way is to solve them, with logic, brute force or a combination of both. Solving with logic: for the very difficult ones (mostly not those that are published in newspapers or magazines) you will sometimes need a "trial and error" approach. In your program you sure need brute force like Dancing Links to solve them all in a short amount of time, just to know if the sudoku is valid or not. If you want to "draw by hand" your own sudokus, make a grid with pencilmarks with automatic update based upon the sudoku type. You also must be able to check validity at any stage of the drawing, which means: if you have multiple solutions, you have to add more givens; No solution, remove the last added given(s); Unique solution, done.
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Pjotr

Joined: 18 Oct 2008
Posts: 7
:
Location: Tilburg (NL)

Items
PostPosted: Sun Oct 26, 2008 11:15 am    Post subject: Reply with quote

How I solved it was with some logic and some brute force. In the Solving mode I only use Logic. In the Creating mode I use some logic (Not the complex stuff, takes to long Smile) and some brute force. But I hoped it was possible to know if a puzzle shape was valid before trying to make a Sudoku.

Guess I'll stick to the brute force with trail and error. Guess I have to improve the effectness(??) of my brute force. I'll take a look at Dancing Links. Maybe that can make it faster. Thanks!
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> The mathematics of sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron