The New Sudoku Players' Forum

[Mathimagics]

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


[coloin]

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

Command was SudokuP [-u] test.txt

C

[Mathimagics]

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

[coloin]

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

yes
that works now ! Thank-you

[coloin]

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 ?

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

does the solver do this 6^4 ?

[Mathimagics]

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.

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.

[coloin]

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.

[tarek]

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

[Mathimagics]

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

[Mathimagics]

.
I have added the -p command line option and updated the zip file above with the new versions.

[Serg]

Hi, Mathimagics!

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

[Mathimagics]

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)

[Serg]

Hi, Mathimagics!

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.

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.

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

[Mathimagics]

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

[Mathimagics]

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