Universal sudoku solver

Programs which generate, solve, and analyze Sudoku puzzles

Universal sudoku solver

Postby horybori » Sat Feb 27, 2016 1:39 am

Hi all,

First of all, I'm glad to publish my sudoku solver here for the first time. My program differs from every other solver that I have been already known. It uses an universal algorithm to solve "every" popular variations of sudoku.
It can solve sudokus with...
- irregular units/regions: x-sudoku, hyper-sudoku/windoku, jigsaw, nonomino...
- multiple boards: like samurai sudokus
- cages: e.g. killer sudokus (every four operations are supported: addition, multiplication, division, and subtraction)
- relations between cages: greater, less, equal relations (supported, but user cannot set yet)
- additional rules: greater than sudokus, consecutive sudokus
- additional restrictions: custom candidate set can be specified for every cell (e.g. even or odd numbers only)
- custom symbols: wordoku
...in every size (from mini to giant and more...).


I'm looking forward to your feedback.


P.S.: English isn’t my first language, so please excuse any mistakes and feel free to send translation corrections too. I plan to make a usable documentation about every little feature if it will be needed.
Attachments
USudoku.rar
Executable.
(181.74 KiB) Downloaded 116 times
horybori
 
Posts: 6
Joined: 26 February 2016

Re: Universal sudoku solver

Postby surendra.jain » Sat Feb 27, 2016 7:28 am

Does your solver uses brute force algorithm for solving all these kind of puzzles or it solves the puzzles by logic. I have written codes to solve sudoku, killer sudoku, iaognal sudoku, irregular sudoku, samurai sudoku, kakuro, calcudoku etc.. I have also developed a software that solves sudoku puzzles from pure logic. The source code can be downloaded from my webite :

sites.google.com/site/skjgeek

Surendra
surendra.jain
 
Posts: 19
Joined: 15 August 2015
Location: India

Re: Universal sudoku solver

Postby horybori » Sat Feb 27, 2016 6:28 pm

It's basically a simple backtrack algorithm. It uses naked/hidden single techniques only because advanced techniques can't be used efficiently. They would be very costly (both implement and use) compared to the number of examined candidates. Instead it tries to guess which is faster and more effective in the vast majority.
horybori
 
Posts: 6
Joined: 26 February 2016

Re: Universal sudoku solver

Postby tarek » Sat Feb 27, 2016 10:07 pm

horybori wrote:My program differs from every other solver that I have been already known. It uses an universal algorithm to solve "every" popular variations of sudoku.


Welcome to the forum,

How fast does your solver prove that this Kazaguruma WIndoku X has 1 solution so:
1. Kazaguruma (Windmill)
2. Each board is Windoku X (Hyper-Sudoku X) (4 windows & Diagonals)

This was posted in another thread with an image but the image no longer exists


Code: Select all
..................4...8........3................5.......6......5.................
.2....3.............8.........1..........91......................................
.................................................................................
......................................75..........3.........1.............4....7.
.................9......7.......5................8........3...7..................


Tarek
User avatar
tarek
 
Posts: 2576
Joined: 05 January 2006

Re: Universal sudoku solver

Postby horybori » Sun Feb 28, 2016 9:27 am

I haven't heard about this puzzle variation yet, but I managed to found an example here: http://forum.enjoysudoku.com/tarek-s-windoku-kazaguruma-windmill-x-t30283.html

(Intel® Core™ i5-2410M Processor (3M Cache, up to 2.90 GHz), 8 GB RAM, Windows 10)

Results:
- first solution only: 76 ms
- with uniqueness check: 472 ms

I also solved the other sudoku and I got similar results (94 ms and 610 ms).

I attached the puzzle so you can try it out for yourself easily.
Attachments
attachment.rar
Puzzle.
(35.14 KiB) Downloaded 39 times
horybori
 
Posts: 6
Joined: 26 February 2016

Re: Universal sudoku solver

Postby tarek » Sun Feb 28, 2016 4:57 pm

Great. The puzzle I posted for you to test is actually puzzle 3 in that thread. It is the same puzzle variant as puzzle 1

The 5 line representation is to make it easy to load, share and store these puzzles. My suggestion would be to implement this easy feature in your solver as it more or less universal between solvers.

Puzzle 3 is a Machine challenging puzzle. So it was a good benchmark to test your solver!!!

Another puzzle to test is the Unsolvable killer sudoku #41 from the list I posted in this thread http://www.rcbroughton.co.uk/sudoku/forum/viewtopic.php?f=3&t=434

Tarek
User avatar
tarek
 
Posts: 2576
Joined: 05 January 2006

Re: Universal sudoku solver

Postby horybori » Sun Feb 28, 2016 10:15 pm

I have a good news and a bad news. The good is that I finally managed to solve the puzzle after ~1 hour computing, but the bad news is that the puzzle isn't unique.

My first two (wrong) solutions (repeating values in cages):
Code: Select all
953216874718594326264837159491672538876359412325481967189725643637148295542963781
953126874718594326264783159491672538876359412325841967189265743637418295542937681
Attachments
killer_sudoku_41.rar
The puzzle.
(40.45 KiB) Downloaded 37 times
Last edited by horybori on Mon Feb 29, 2016 8:45 pm, edited 1 time in total.
horybori
 
Posts: 6
Joined: 26 February 2016

Re: Universal sudoku solver

Postby tarek » Sun Feb 28, 2016 11:38 pm

horybori wrote:I have a good news and a bad news. The good is that I finally managed to solve the puzzle after ~1 hour computing, but the bad news is that the puzzle isn't unique.

I agree and disagree :) .... I probably should have mentioned it but in most cases it is implied:

The original published Killer sudokus in the Times (& that is why most players follow that convention) had also a sum-cage constraint where you can't repeat a symbol in the cage & this was the reason most players know the number combinations based on that. So unless specified; the convention is that there should be no repeated symbols in the sum cages.

This again can be modified easily in your solver to accept both possibilities but you should set the default to: not accepting symbol repetitions in cages.

Tarek
User avatar
tarek
 
Posts: 2576
Joined: 05 January 2006

Re: Universal sudoku solver

Postby horybori » Sat Mar 12, 2016 8:56 pm

I'm here again. I modified my solver as you suggested.
Furthermore, I've implemented some advanced cage solving techniques, so it's a little bit faster now.

Solution of the unsolvable #41 (without repeating symbols):
Code: Select all
283197546967542813415368729591726384876439152324851967149275638752683491638914275

Hidden Text: Show
puzzle.png
puzzle.png (18.9 KiB) Viewed 670 times
horybori
 
Posts: 6
Joined: 26 February 2016

Re: Universal sudoku solver

Postby tarek » Sun Mar 13, 2016 2:28 pm

Excellent. Well done!!! This was designed to test machine solving so you can use it also to test the timings following any improvements in your solver in the future.

Your programming path is as follows:

1. Solving
2. Generating
3. Rating/analyzing

Good luck,

Tarek
User avatar
tarek
 
Posts: 2576
Joined: 05 January 2006


Return to Software