IBM Mainframe Forum Index
 
Log In
 
IBM Mainframe Forum Index Mainframe: Search IBM Mainframe Forum: FAQ Register
 

SUDOKU Killer
IBM Mainframe Forums -> FAQ & Basics
Post new topic   Reply to topic Quick References
View previous topic :: View next topic  
Author Message
lkhiger

New User


Joined: 28 Oct 2005
Posts: 89
PostPosted: Thu Sep 24, 2009 7:52 am
 Reply with quote
I want present to you Sudoku Solver, created by me today, which find solution for any level of Sudoku in very short time from 2 to 80 seconds, depends on difficulty level.

This solution prevents from infinite loop. So if solution exists it'll be found.

In this example I used the very hard sudoku and got solution in 2 minutes.

Sudoku Line

Quote:
XXX7X29X4
4X1X687XX
XXXXXXXX8
6X7XX142X
XXXXXXXXX
X236XX1X5
1XXXXXXXX
XX827X5X1
7X24X6XXX


Result Lines

Quote:
Line 1: | 8 | 6 | 5 | 7 | 3 | 2 | 9 | 1 | 4 |
Line 2: | 4 | 3 | 1 | 9 | 6 | 8 | 7 | 5 | 2 |
Line 3: | 2 | 7 | 9 | 1 | 4 | 5 | 6 | 3 | 8 |
Line 4: | 6 | 8 | 7 | 5 | 9 | 1 | 4 | 2 | 3 |
Line 5: | 5 | 1 | 4 | 3 | 2 | 7 | 8 | 9 | 6 |
Line 6: | 9 | 2 | 3 | 6 | 8 | 4 | 1 | 7 | 5 |
Line 7: | 1 | 9 | 6 | 8 | 5 | 3 | 2 | 4 | 7 |
Line 8: | 3 | 4 | 8 | 2 | 7 | 9 | 5 | 6 | 1 |
Line 9: | 7 | 5 | 2 | 4 | 1 | 6 | 3 | 8 | 9 |


Code in attachment:

I had to open the new topic because code is too long and I can use attachment only one time in topic (by rules of Forum).
Leonid Khiger
Back to top
View user's profile Send private message
lkhiger

New User


Joined: 28 Oct 2005
Posts: 89
PostPosted: Thu Sep 24, 2009 8:32 am
 Reply with quote
You can try yourself, trying to solve Valentine Sudoku:

Quote:
x59xxx38x
2xx9x1xx6
8xxx7xxx2
9xxxxxxx3
1xxxxxxx5
x2xxxxx7x
xx1xxx8xx
xxx5x6xxx
xxxx2xxxx



Then we'll compare result and time
(Sudoku Killer solved this hard level sudoku in 1 minute).... icon_exclaim.gif

Lenny
Back to top
View user's profile Send private message
lkhiger

New User


Joined: 28 Oct 2005
Posts: 89
PostPosted: Fri Sep 25, 2009 7:51 am
 Reply with quote
For Sudoku-level <= 3 elapse time <= 15 second.

Lenny icon_idea.gif
Back to top
View user's profile Send private message
lkhiger

New User


Joined: 28 Oct 2005
Posts: 89
PostPosted: Mon Sep 28, 2009 9:32 pm
 Reply with quote
There is level 3 sudoku, having 2 empty lines:

Sudoku Line

XXXXXXXXX
X7XXX6X3X
X3X72XX4X
7XXXX8XX1
6XX3X7XX5
5X91XXXXX
X8XX91X2X
X916XXX7X
XXXXXXXXX
Line 1: | 9 | 6 | 2 | 8 | 3 | 4 | 1 | 5 | 7 |
Line 2: | 8 | 7 | 4 | 5 | 1 | 6 | 9 | 3 | 2 |
Line 3: | 1 | 3 | 5 | 7 | 2 | 9 | 6 | 4 | 8 |
Line 4: | 7 | 2 | 3 | 9 | 5 | 8 | 4 | 6 | 1 |
Line 5: | 6 | 1 | 8 | 3 | 4 | 7 | 2 | 9 | 5 |
Line 6: | 5 | 4 | 9 | 1 | 6 | 2 | 7 | 8 | 3 |
Line 7: | 3 | 8 | 7 | 4 | 9 | 1 | 5 | 2 | 6 |
Line 8: | 2 | 9 | 1 | 6 | 8 | 5 | 3 | 7 | 4 |
Line 9: | 4 | 5 | 6 | 2 | 7 | 3 | 8 | 1 | 9 |

Our solver spent 10 second to find this single solution.

Now we make simple experiment: we'll change line 4 by remove 1 from source string:

7XXXX8XX1 ==> 7XXXX8XX0

We expect the same single solution, but not.

Because we have 2 empty lines we'll have multiple solutions.

Ok, every solution will shown to you, but how ?

Line 1: ........
Line 1: ........
..................
Line 1: ........
Line 2: ........
Line 2: ........
..................
Line 2: ........ etc.

How combine these lines in complete sudoku solutions ?

For this I created the new conception (column) named Weight.

The weight has to be unique for every single solution.;)

Weight = 'Line 1:... ' || 'Line 2:... ' ||.... || 'Line 9:... '.

Then I used Group By and Order BY for Weight & Line##.

As Result:

Sudoku Line
XXXXXXXXX
X7XXX6X3X
X3X72XX4X
7XXXX8XXX
6XX3X7XX5
5X91XXXXX
X8XX91X2X
X916XXX7X
XXXXXXXXX
Line 1: | 1 | 6 | 2 | 8 | 3 | 4 | 7 | 5 | 9 |
Line 2: | 9 | 7 | 4 | 5 | 1 | 6 | 8 | 3 | 2 |
Line 3: | 8 | 3 | 5 | 7 | 2 | 9 | 6 | 4 | 1 |
Line 4: | 7 | 1 | 3 | 9 | 5 | 8 | 2 | 6 | 4 |
Line 5: | 6 | 2 | 8 | 3 | 4 | 7 | 1 | 9 | 5 |
Line 6: | 5 | 4 | 9 | 1 | 6 | 2 | 3 | 8 | 7 |
Line 7: | 3 | 8 | 7 | 4 | 9 | 1 | 5 | 2 | 6 |
Line 8: | 2 | 9 | 1 | 6 | 8 | 5 | 4 | 7 | 3 |
Line 9: | 4 | 5 | 6 | 2 | 7 | 3 | 9 | 1 | 8 |

Line 1: | 1 | 6 | 2 | 8 | 3 | 4 | 7 | 5 | 9 |
Line 2: | 9 | 7 | 4 | 5 | 1 | 6 | 8 | 3 | 2 |
Line 3: | 8 | 3 | 5 | 7 | 2 | 9 | 6 | 4 | 1 |
Line 4: | 7 | 1 | 3 | 9 | 5 | 8 | 2 | 6 | 4 |
Line 5: | 6 | 2 | 8 | 3 | 4 | 7 | 9 | 1 | 5 |
Line 6: | 5 | 4 | 9 | 1 | 6 | 2 | 3 | 8 | 7 |
Line 7: | 3 | 8 | 7 | 4 | 9 | 1 | 5 | 2 | 6 |
Line 8: | 2 | 9 | 1 | 6 | 8 | 5 | 4 | 7 | 3 |
Line 9: | 4 | 5 | 6 | 2 | 7 | 3 | 1 | 9 | 8 |

Line 1: | 1 | 6 | 2 | 8 | 3 | 4 | 7 | 5 | 9 |
Line 2: | 9 | 7 | 4 | 5 | 1 | 6 | 8 | 3 | 2 |
Line 3: | 8 | 3 | 5 | 7 | 2 | 9 | 6 | 4 | 1 |
Line 4: | 7 | 2 | 3 | 9 | 5 | 8 | 1 | 6 | 4 |
Line 5: | 6 | 1 | 8 | 3 | 4 | 7 | 2 | 9 | 5 |
Line 6: | 5 | 4 | 9 | 1 | 6 | 2 | 3 | 8 | 7 |
Line 7: | 3 | 8 | 7 | 4 | 9 | 1 | 5 | 2 | 6 |
Line 8: | 2 | 9 | 1 | 6 | 8 | 5 | 4 | 7 | 3 |
Line 9: | 4 | 5 | 6 | 2 | 7 | 3 | 9 | 1 | 8 |

Line 1: | 1 | 6 | 2 | 8 | 3 | 4 | 9 | 5 | 7 |
Line 2: | 9 | 7 | 4 | 5 | 1 | 6 | 2 | 3 | 8 |
Line 3: | 8 | 3 | 5 | 7 | 2 | 9 | 6 | 4 | 1 |
Line 4: | 7 | 1 | 3 | 9 | 5 | 8 | 4 | 6 | 2 |
Line 5: | 6 | 2 | 8 | 3 | 4 | 7 | 1 | 9 | 5 |
Line 6: | 5 | 4 | 9 | 1 | 6 | 2 | 7 | 8 | 3 |
Line 7: | 3 | 8 | 7 | 4 | 9 | 1 | 5 | 2 | 6 |
Line 8: | 2 | 9 | 1 | 6 | 8 | 5 | 3 | 7 | 4 |
Line 9: | 4 | 5 | 6 | 2 | 7 | 3 | 8 | 1 | 9 |

Line 1: | 9 | 6 | 2 | 8 | 3 | 4 | 1 | 5 | 7 |
Line 2: | 8 | 7 | 4 | 5 | 1 | 6 | 2 | 3 | 9 |
Line 3: | 1 | 3 | 5 | 7 | 2 | 9 | 6 | 4 | 8 |
Line 4: | 7 | 1 | 3 | 9 | 5 | 8 | 4 | 6 | 2 |
Line 5: | 6 | 2 | 8 | 3 | 4 | 7 | 9 | 1 | 5 |
Line 6: | 5 | 4 | 9 | 1 | 6 | 2 | 7 | 8 | 3 |
Line 7: | 3 | 8 | 7 | 4 | 9 | 1 | 5 | 2 | 6 |
Line 8: | 2 | 9 | 1 | 6 | 8 | 5 | 3 | 7 | 4 |
Line 9: | 4 | 5 | 6 | 2 | 7 | 3 | 8 | 9 | 1 |

Line 1: | 9 | 6 | 2 | 8 | 3 | 4 | 1 | 5 | 7 |
Line 2: | 8 | 7 | 4 | 5 | 1 | 6 | 9 | 3 | 2 |
Line 3: | 1 | 3 | 5 | 7 | 2 | 9 | 6 | 4 | 8 |
Line 4: | 7 | 2 | 3 | 9 | 5 | 8 | 4 | 6 | 1 |
Line 5: | 6 | 1 | 8 | 3 | 4 | 7 | 2 | 9 | 5 |
Line 6: | 5 | 4 | 9 | 1 | 6 | 2 | 7 | 8 | 3 |
Line 7: | 3 | 8 | 7 | 4 | 9 | 1 | 5 | 2 | 6 |
Line 8: | 2 | 9 | 1 | 6 | 8 | 5 | 3 | 7 | 4 |
Line 9: | 4 | 5 | 6 | 2 | 7 | 3 | 8 | 1 | 9 |

Line 1: | 9 | 6 | 2 | 8 | 3 | 4 | 7 | 5 | 1 |
Line 2: | 8 | 7 | 4 | 5 | 1 | 6 | 9 | 3 | 2 |
Line 3: | 1 | 3 | 5 | 7 | 2 | 9 | 6 | 4 | 8 |
Line 4: | 7 | 1 | 3 | 9 | 5 | 8 | 2 | 6 | 4 |
Line 5: | 6 | 2 | 8 | 3 | 4 | 7 | 1 | 9 | 5 |
Line 6: | 5 | 4 | 9 | 1 | 6 | 2 | 3 | 8 | 7 |
Line 7: | 3 | 8 | 7 | 4 | 9 | 1 | 5 | 2 | 6 |
Line 8: | 2 | 9 | 1 | 6 | 8 | 5 | 4 | 7 | 3 |
Line 9: | 4 | 5 | 6 | 2 | 7 | 3 | 8 | 1 | 9 |

Line 1: | 9 | 6 | 2 | 8 | 3 | 4 | 7 | 5 | 1 |
Line 2: | 8 | 7 | 4 | 5 | 1 | 6 | 9 | 3 | 2 |
Line 3: | 1 | 3 | 5 | 7 | 2 | 9 | 6 | 4 | 8 |
Line 4: | 7 | 2 | 3 | 9 | 5 | 8 | 1 | 6 | 4 |
Line 5: | 6 | 1 | 8 | 3 | 4 | 7 | 2 | 9 | 5 |
Line 6: | 5 | 4 | 9 | 1 | 6 | 2 | 3 | 8 | 7 |
Line 7: | 3 | 8 | 7 | 4 | 9 | 1 | 5 | 2 | 6 |
Line 8: | 2 | 9 | 1 | 6 | 8 | 5 | 4 | 7 | 3 |
Line 9: | 4 | 5 | 6 | 2 | 7 | 3 | 8 | 1 | 9 |

we got 8 different solutions in 1 minute.

So, what we have to change in Sudoku-killer (see an attachment):

Code:
Sudoku_Final (Line_1, Line_2, Line_3, Line_4, Line_5, Line_6, Line_7, Line_8, Line_9, stopper, Weight) as
(
select varchar('', 100), varchar('', 100), varchar('', 100), varchar('', 100), varchar('', 100),
       varchar('', 100), varchar('', 100), varchar('', 100), varchar('', 100), varchar('N', 1),
       varchar('', 1000)
  from sysibm.sysdummy1

Union All
select
ii.Line_1, ii.Line_2, ii.Line_3, ii.Line_4, ii.Line_5,
ii.Line_6, ii.Line_7, ii.Line_8, ii.Line_9, nullif('', ''),
ii.Line_1 || ii.Line_2 || ii.Line_3 || ii.Line_4 ||  ii.Line_5 ||
ii.Line_6 || ii.Line_7 || ii.Line_8 || ii.Line_9 as Weight


also

Code:
select tt."Sudoku Line"
from
(
select  replace(sudoku_str, '0', 'X') as "Sudoku Line" , ' ' || varchar(line) Weight
from Source
Union all
select Line_1 as "Sudoku Line", Weight from Sudoku_Final
where  Line_1  > ' '
Union All
select Line_2 as "Sudoku Line", Weight from Sudoku_Final
where  Line_2  > ' '
Union All
select Line_3 as "Sudoku Line", Weight from Sudoku_Final
where  Line_3  > ' '
Union All
select Line_4 as "Sudoku Line", Weight from Sudoku_Final
where  Line_4  > ' '
Union All
select Line_5 as "Sudoku Line", Weight from Sudoku_Final
where  Line_5  > ' '
Union All
select Line_6 as "Sudoku Line", Weight from Sudoku_Final
where  Line_6  > ' '
Union All
select Line_7 as "Sudoku Line", Weight from Sudoku_Final
where  Line_7  > ' '
Union All
select Line_8 as "Sudoku Line", Weight from Sudoku_Final
where  Line_8  > ' '
Union All
select Line_9 as "Sudoku Line", Weight from Sudoku_Final
where  Line_9  > ' ' ) tt
group by tt."Sudoku Line", Weight
order by Weight, "Sudoku Line"


That's it.
Back to top
View user's profile Send private message
View previous topic :: :: View next topic  
Post new topic   Reply to topic View Bookmarks
All times are GMT + 6 Hours
Forum Index -> FAQ & Basics

 

Similar Topics
Topic Forum Replies
No new posts Forces of DB2 nature: SUDOKU Solver (... DB2 29
Search our Forums:

Back to Top
IBMMainframes.com is not an official and/or affiliated with IBM® in anyway
Board Rules | FAQ | Downloads | Wiki | SiteMap | Contact Us