SudokuP Solver (Windows)

Everything about Sudoku that doesn't fit in one of the other sections

SudokuP Solver (Windows)

Postby Mathimagics » Sun Feb 18, 2018 3:17 am

Here is a working SudokuP solver for Windows. The zip file contains a 32-bit and 64-bit version. Pick the relevant one and rename it SudokuP.exe.

Command line: SudokuP [-u] [-p] [-a] PuzzleFile

Input file format: Puzzles, one-per-line, standard format, ie: any characters not "1" - "9" map to 0.

Options: -p => print puzzle + solutions, -u => test uniqueness, -a => show all (up to max 100) solutions

Output: Solutions, one per line. For each source puzzle:
  • if no solution the input puzzle is invalid and is printed with ": invalid" appended.

  • if -p option given, input puzzle is always printed.

  • if neither -p nor -a is given, prints first solution, untagged

  • if -u is specified, then if the solution is unique it is shown with " (u)" tag. If not unique then the first 2 solutions are printed, each with " (*)" tag.

  • if -a is specified, then output is same as for -u, but will list all solutions (up to max 100).

[Update July 3, 2018]

  • added option -m (morph generation)

This option will find all {+1,-1} morphs of the input puzzles(s). A morph is a puzzle obtained by removing one clue and adding another. This option only lists morphs that are valid puzzles (ie have unique solutions). The source puzzle(s) do not, however, have to have unique solutions.

Example: given input file "TestM.txt" containing:
Code: Select all
..3...........82.1.79......................7.2............3..............45......
.2........................2.7...........9..6.......15...1..............8.....8..3


Then command SudokuP -m TestM.txt will give following output:
Code: Select all
..3...........82.1.79......................7.2............3...........5..4.......
..3...........82.1.79......................7.2............3...........6..4.......
.2........................2.7...........9........4.15...1..............8.....8..3
.2........................2.7...........9........6.15...1..............8.....8..3
Attachments
SudokuPX.zip
Update #5 (July 14, 2018)
(56.38 KiB) Downloaded 2 times
Last edited by Mathimagics on Sat Jul 14, 2018 7:35 am, edited 9 times in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 608
Joined: 27 May 2015

Re: SudokuP Solver (Windows)

Postby coloin » Thu Mar 08, 2018 12:45 am

I tried it on the 10 11-clue puzzles - but no luck ... not sure why

Command was SudokuP [-u] test.txt

C
coloin
 
Posts: 1715
Joined: 05 May 2005

Re: SudokuP Solver (Windows)

Postby Mathimagics » Thu Mar 08, 2018 2:12 am

Can you give me the input file you used ... and can you elaborate a little on "no luck"?

It does seem odd that both you and Leren are having problems ... do you have a gcc compiler available?

Um, you didn't actually put square brackets round the -u, did you? Try without (they just indicate an optional parameter)

IE: SudokuP -u Test.txt
User avatar
Mathimagics
2017 Supporter
 
Posts: 608
Joined: 27 May 2015

Re: SudokuP Solver (Windows)

Postby coloin » Thu Mar 08, 2018 8:29 am

Mathimagics wrote:Um, you didn't actually put square brackets round the -u, did you?

:oops: yes
that works now ! Thank-you
coloin
 
Posts: 1715
Joined: 05 May 2005

Re: SudokuP Solver (Windows)

Postby coloin » Fri Mar 09, 2018 9:00 am

Mathemagics wrote:Thanks to Brian Turner, and dobrichev, I get 64K SudokuP puzzles/sec with uniqueness testing, reduced forms, on a 4.7GHz CPU. That's excluding I/O, of course, I load 100 reduced forms, then solve them over and over. But it is fast.


Yes it is fast.. no doubt
so the output
mutiple solutions = print first solution
invalid = print puzzle with *
valid puzzle = print puzzle

would it be possible to print puzzle with "#" and then the solution grid with it ? - to identify it ?

coloin wrote:We would then have to morph the potential puzzles 6^6 / 6^2 times ? ...


does the solver do this 6^4 ?
coloin
 
Posts: 1715
Joined: 05 May 2005

Re: SudokuP Solver (Windows)

Postby Mathimagics » Fri Mar 09, 2018 10:12 am

coloin wrote:mutiple solutions = print first solution
invalid = print puzzle with *
valid puzzle = print puzzle


Not quite right!

If -u is not specified:

  • invalid: print the puzzle
  • valid: print first solution

If -u is specified:

  • invalid: print the puzzle
  • 1 solution: print first solution
  • mutiple solutions: print second solution + (*) marker

So, if you really want 2-solution proof of non-uniqueness, re-solve any multiple-solution cases without the -u option to get the first solution.

coloin wrote:We would then have to morph the potential puzzles 6^6 / 6^2 times ? does the solver do this 6^4 ?

Not sure what that means, but I can safely say the solver just solves from the input given, it doesn't do any morphing.
User avatar
Mathimagics
2017 Supporter
 
Posts: 608
Joined: 27 May 2015

Re: SudokuP Solver (Windows)

Postby coloin » Sun Mar 11, 2018 11:17 am

in generating many potential puzzles, removing sub puzzles with no solutions will reduce the number of subsequent generated puzzles to solve
to test any potential puzzle with say 11 clues - one has to morph the puzzle 6^4 times and then test these.

no of ways to morph a puzzle is 6^8 * 2
no of ways to morph a puzzle and maintain sudokuP is 6^4 * 2
no of ways to morph a puzzle and test for sudokuP is 6^4
there are 6 ^6 row/col swaps in a puzzle [but 6^2 of these will maintain sudokoP] - confirms the 6^4

What would be most useful is to print the valid puzzle and its unique solution.
coloin
 
Posts: 1715
Joined: 05 May 2005

Re: SudokuP Solver (Windows)

Postby tarek » Sun Mar 11, 2018 2:17 pm

Depending on how much you want to clutter your memory. You can put as many Print options in a pre-compile code and therefore create several versions of the executable that suits your need

I’m sure all of you knew this ;)

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

Re: SudokuP Solver (Windows)

Postby Mathimagics » Sun Mar 11, 2018 4:14 pm

.
I could provide a -p command line parameter that will echo the puzzle being solved and the result on one line, like this:


1.2........3..............4.4..5.....6..............1..7...........8..........7..:
182764593493528176657193284841259637765831942329476815976315428214687359538942761


Would that do the trick?
User avatar
Mathimagics
2017 Supporter
 
Posts: 608
Joined: 27 May 2015

Re: SudokuP Solver (Windows)

Postby Mathimagics » Sun Mar 11, 2018 6:55 pm

.
I have added the -p command line option and updated the zip file above with the new versions.
User avatar
Mathimagics
2017 Supporter
 
Posts: 608
Joined: 27 May 2015

Re: SudokuP Solver (Windows)

Postby Serg » Tue Mar 20, 2018 9:03 pm

Hi, Mathimagics!
Mathimagics wrote:Here is a working SudokuP solver for Windows.
. . .
It should be quite fast at solving large batches.

I tried your solver. It is really fast. I checked it on the mix of random SudokuP puzzles (almost all puzzles had multiple solutions) in "-u" mode and got 22000 puzzles/sec on my rather old notebook.

What is the language this solver was written in? Is it traditional C?
I am planning to search for maximal/minimal patterns for SudokuP puzzles (pattern is binary matrix 9x9, having "1" for SudokuP clue cells, otherwise - "0"). So, I need fast SudokuP solver to do it. My own SudokuP solver is much more slower than yours.

Serg
Serg
2018 Supporter
 
Posts: 581
Joined: 01 June 2010
Location: Russia

Re: SudokuP Solver (Windows)

Postby Mathimagics » Wed Mar 21, 2018 5:20 am

Hi Serg,

The code is in "C++", and was made by adapting Mladen Dobrichev's fast solver (for standard Sudoku). It's really standard "C", but the table initialisation stuff doesn't compile under GCC only G++.

The speed is entirely due to Mladen's coding ...

I turned it into a SudokuP solver by extending the number of "groups" from 3 (rows/cols/boxes) to 4 (adding box-position group), and by extending the relevant lookup tables to include the extra group.

Mladen "published" his solver with GridChecker, but it would only be polite to check with him that he has no objection to my posting the source code for these solvers. Then I can post both the standard and the SudokuP solver code here (both suitably attributed)
User avatar
Mathimagics
2017 Supporter
 
Posts: 608
Joined: 27 May 2015

Re: SudokuP Solver (Windows)

Postby Serg » Wed Mar 21, 2018 8:33 am

Hi, Mathimagics!
Mathimagics wrote:The code is in "C++", and was made by adapting Mladen Dobrichev's fast solver (for standard Sudoku). It's really standard "C", but the table initialisation stuff doesn't compile under GCC only G++.

Is it famous fsss Mladen's solver?
C++ is traditional obstacle for me. So, I'll try to make my solver faster first.
Mathimagics wrote:The speed is entirely due to Mladen's coding ...

I turned it into a SudokuP solver by extending the number of "groups" from 3 (rows/cols/boxes) to 4 (adding box-position group), and by extending the relevant lookup tables to include the extra group.

Yes, lookup tables is very powerful tool in combinatorial tasks programming.
Mathimagics wrote:Mladen "published" his solver with GridChecker, but it would only be polite to check with him that he has no objection to my posting the source code for these solvers. Then I can post both the standard and the SudokuP solver code here (both suitably attributed)

I thought so. If I won't be able to speed up my solver, I'll ask Mladen's permission to use his code.

Serg
Serg
2018 Supporter
 
Posts: 581
Joined: 01 June 2010
Location: Russia

Re: SudokuP Solver (Windows)

Postby Mathimagics » Wed Mar 21, 2018 9:48 am

Serg wrote:C++ is traditional obstacle for me. So, I'll try to make my solver faster first.


The solver can be called from normal "C" programs ... no fudging necessary ... 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 608
Joined: 27 May 2015

Bug Fix!!

Postby Mathimagics » Sat Jun 30, 2018 4:47 pm

.
To my horror I have found that there was a bug in the Solver function.

The correct results (# of solutions) were being reported, BUT the solution grid returned was invalid for any mode > 0.

It has not come to my attention since invariably all my applications involve simply testing puzzles for # of solutions.

I have updated the ZIP file above with the corrected versions.
User avatar
Mathimagics
2017 Supporter
 
Posts: 608
Joined: 27 May 2015

Next

Return to General

cron