## Universal sudoku solver

Programs which generate, solve, and analyze Sudoku puzzles

### Universal sudoku solver

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.
horybori

Posts: 15
Joined: 26 February 2016

### Re: Universal sudoku solver

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 :

Surendra
surendra.jain

Posts: 27
Joined: 15 August 2015
Location: India

### Re: Universal sudoku solver

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: 15
Joined: 26 February 2016

### Re: Universal sudoku solver

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

tarek

Posts: 3097
Joined: 05 January 2006

### Re: Universal sudoku solver

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.
horybori

Posts: 15
Joined: 26 February 2016

### Re: Universal sudoku solver

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

tarek

Posts: 3097
Joined: 05 January 2006

### Re: Universal sudoku solver

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
`953216874718594326264837159491672538876359412325481967189725643637148295542963781953126874718594326264783159491672538876359412325841967189265743637418295542937681`
Attachments
killer_sudoku_41.rar
The puzzle.
Last edited by horybori on Mon Feb 29, 2016 8:45 pm, edited 1 time in total.
horybori

Posts: 15
Joined: 26 February 2016

### Re: Universal sudoku solver

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

tarek

Posts: 3097
Joined: 05 January 2006

### Re: Universal sudoku solver

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 (18.9 KiB) Viewed 1862 times
horybori

Posts: 15
Joined: 26 February 2016

### Re: Universal sudoku solver

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

tarek

Posts: 3097
Joined: 05 January 2006

### Re: Universal sudoku solver

horybori

Posts: 15
Joined: 26 February 2016