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] PuzzleFile

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

Output: Solutions, one per line. If no solution the input puzzle is printed just as was read. If -u is NOT specified the solution is simply the first one found. If -u is specified, uniqueness test applies - if the solution is not unique the output solution has "(*)" appended.

It should be quite fast at solving large batches.


Enjoy!


SudokuPX.zip
(49.7 KiB) Downloaded 21 times
Last edited by Mathimagics on Sun Mar 11, 2018 6:56 pm, edited 2 times in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 549
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: 1697
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: 549
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: 1697
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: 1697
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: 549
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: 1697
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: 2644
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: 549
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: 549
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: 572
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: 549
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: 572
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: 549
Joined: 27 May 2015


Return to General