Invalid (Jigsaw) Puzzle Recognition

Pjotr

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?

Pjotr · Posted: Tue Oct 21, 2008 4:15 pm Post subject:

Didn't I explain it well?

Doesn't anyone know it?

Or am I to impatient?

Lunatic · Posted: Wed Oct 22, 2008 10:31 am Post subject:

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
~~~<><~~~<><~~~<><~~~<><~~~

Pjotr · Posted: Sun Oct 26, 2008 11:15 am Post subject:

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!