Bitwise/Boolean Sudoku Solver

Programs which generate, solve, and analyze Sudoku puzzles

Re: Bitwise/Boolean Sudoku Solver

Postby rjamil » Fri Nov 17, 2017 5:17 pm

Hi,

Pleased to share latest RJSolBit.c and RJSolBit.cpp program.

In this release:
Minor bug fix: In line # 41, replace bits to digits value from 378 to 678 at first position as typo error. It only effects debug pencil mark output of cells that contain 678 as clues.

Added: Empty Rectangle strategy.

R. Jamil
Attachments
RJSolBit.cpp
C++ Language
(83.07 KiB) Downloaded 214 times
RJSolBit.c
C Language
(83.19 KiB) Downloaded 221 times
rjamil
 
Posts: 729
Joined: 15 October 2014
Location: Karachi, Pakistan

Re: Bitwise/Boolean Sudoku Solver

Postby rjamil » Sun May 20, 2018 8:07 pm

Hi all,

Pleased to share attached herewith the latest RJSolBit.c program (after half year). This time, discontinued development in C++ version of the same.

Now, this version search strategies as per following order:
1) Zero State check;
2) Hidden Single;
3) Naked Single (or guess from minimum clue cell position);
4) Naked & Hidden Tuples (pair, triplet & quad);
5) Locked Candidate 1 & 2;
6) Basic Fishes (X-Wing, Sword Fish & Jelly Fish);
7) Skyscraper & Grouped Skyscraper;
8) 2-String Kite and Grouped 2-String Kite;
9) Empty Rectangle, Dual Linked Empty Rectangle, Grouped Empty Rectangle & Dual Linked Grouped Empty Rectangle;
10) XY-Wings Type 1 (Row-Column wise) & XY-Wings Type 1 Transport;
11) XY-Wings Type 2 (Box-Line wise), XYZ-Wings & XYZ-Wings Hybrid Type 1 & 2;
12) W-Wings Type 1 & 2;
13) WXYZ-Wings Type 1 (Row-Column wise); and
14) WXYZ-Wings Type 2a, 2b, 3, 4a & 4b (Box-Line wise).

Note:-
a) I have switched hidden single routine search before naked single routine. By doing this, add 2 more Ruud's 50K puzzles solved without guess.
b) Now, the solver is able to solve 7267 out of Ruud's 50K puzzles without guess.

R. Jamil

Added on 20180608:
Hidden Text: Show
Noticed that few Naked Singles are reported as Hidden Singles due routines switched. Therefore, adding following one line to distinguish them as Naked Single:

Replace line 403:
y = 1; // 1 Represent Hidden single Cell position
With Line 403 and 404:
if (B[g[r[a]]] > 1)
y = 1; // 1 Represent Hidden single Cell position

Added on 20181003:
Hidden Text: Show
Found minor bug in detecting W-Wings Type 1 ERi exemplar 4 and Type 2 ERI exemplar 4
Replace old Line number from 3092 to 3099:
Code: Select all
          if ((Z = (g[w[K[0]][L]] | g[w[w[K[0]][L]][6]] | g[w[w[K[0]][L]][7]]) &
            (g[w[K[0]][L]] | g[w[w[K[0]][L]][12]] | g[w[w[K[0]][L]][13]]) &
            ~(g[w[w[K[0]][L]][8]] | g[w[w[K[0]][L]][9]] | g[w[w[K[0]][L]][10]] |
            g[w[w[K[0]][L]][11]] | g[w[w[K[3 + a]][L]][12]] | g[w[w[K[3 + a]][L]][8]] |
            g[w[w[K[3 + a]][L]][9]] | g[w[w[K[3 + a]][L]][10]] | g[w[w[K[3 + a]][L]][11]] |
            g[w[w[K[3 + a]][L]][12]]) & (g[w[K[3 + a]][L]] | g[w[w[K[3 + a]][L]][6]] | g[w[w[K[3 + a]][L]][7]]) &
            (g[w[K[3 + a]][L]] | g[w[w[K[3 + a]][L]][12]] | g[w[w[K[3 + a]][L]][13]]) & K[2]) &&
            ((k[0] | k[1] | k[2] | k[3] | k[4] | k[5]) & (K[2] - Z)))

With new Line number from 3092 to 3099:
Code: Select all
          if ((Z = (g[w[K[0]][L]] | g[w[w[K[0]][L]][6]] | g[w[w[K[0]][L]][7]]) &
            (g[w[K[0]][L]] | g[w[w[K[0]][L]][12]] | g[w[w[K[0]][L]][13]]) &
            ~(g[w[w[K[0]][L]][8]] | g[w[w[K[0]][L]][9]] | g[w[w[K[0]][L]][10]] |
            g[w[w[K[0]][L]][11]] | g[w[w[K[3 + a]][L]][8]] | g[w[w[K[3 + a]][L]][9]] |
            g[w[w[K[3 + a]][L]][10]] | g[w[w[K[3 + a]][L]][11]]) &
            (g[w[K[3 + a]][L]] | g[w[w[K[3 + a]][L]][6]] | g[w[w[K[3 + a]][L]][7]]) &
            (g[w[K[3 + a]][L]] | g[w[w[K[3 + a]][L]][12]] | g[w[w[K[3 + a]][L]][13]]) & K[2]) &&
            ((k[0] | k[1] | k[2] | k[3] | k[4] | k[5]) & (K[2] - Z)))

Ruud's 50K specialty puzzles solved without guess increased from 7267 to 7307.
Attachments
RJSolBit.c
(169.75 KiB) Downloaded 203 times
rjamil
 
Posts: 729
Joined: 15 October 2014
Location: Karachi, Pakistan

Re: Bitwise/Boolean Sudoku Solver

Postby rjamil » Mon May 18, 2020 3:07 am

Hi all,

Wish to inform that I am sharing herewith my latest source codes of vanilla Sudoku solver RJSolBit.c (Recursive step-by-step backtracking) and RJSudoku.c (Iterative guess backtracking) programs.

Both the programs are now search following techniques:
01) Zero State check (fully implemented);
02) Hidden Single;
03) Naked Single (or guess from minimum values cell position);
04) Naked & Hidden Tuples (pair, triplet & quad);
05) Locked Candidate Type 1 (Pointing) & Type 2 (Claiming);
06) Almost Locked Candidates (pair, triplet & quad);
07) Basic Fishes (X-Wing, Sword Fish & Jelly Fish);
08) Skyscraper & Grouped Skyscraper;
09) 2-String Kite and Grouped 2-String Kite;
10) 2-String Kite+ERI Ring and Grouped 2-String Kite+ERI Ring;
11) 2-String Kite+ERI and Grouped 2-String Kite+ERI;
12) 2-String Kite+Box and Grouped 2-String Kite+Box;
13) Empty Rectangle, Dual Empty Rectangle, Grouped Empty Rectangle & Grouped Linked Empty Rectangle;
14) W-Wing Type 1 (Row-Column wise), Type 2 (Box-Line wise), Grouped W-Wing Type 1 & Type 2, W-Ring (1 exemplar);
15) Strong Wing Type 1 (Row-Column wise) & Type 2 (Box-Line wise), Strong Ring Type 1 (Row-Column wise) & Type 2 (Box-Line wise);
16) XY-Wing Type 1 (Row-Column wise), XY-Wing Type 1 Transport, XYZ-Transport, XYZ-Hybrid & Dual XYZ-Hybrid;
17) XY-Wing Type 2 (Box-Line wise), XY-Wing Type 2 Transport, XYZ-Wing, XYZ-Wing Transport, XYZ-Wing Hybrid & Dual XYZ-Wing Hybrid;
18) WXYZ-Wing Type 1 (Row-Column wise);
19) WXYZ-Wing Type 2a, 2b, 3, 4a & 4b (Box-Line wise);
20) XY-Ring Type 1 (Row-Column wise) & Type 2 (Box-Line wise);
21) Bivalue Universal Grave Type 1;
22) All known total 4 digits in 4 cells patterns of Almost Locked Set move Type 1 (Row-Column wise) & Type 2 (Box-Line wise);
23) Trial & Error via recursive step-by-step backtracking (RJSolBit.c) & iterative guess backtracking (RJSudoku.c).

Added:
a. Number of possibilities (pencil marks) for each puzzle at initial state;
b. Debug printing initial given clues puzzle grid.

Sharing some statistics for easy reference:
Code: Select all
Collection       Puzzles W/o guess
---------------- ------- ---------
Ruud's Specialty  50000    12520
17 clue puzzles   49158    48180
Tarek Pearls      6000     0
Mike's PG         26855    11075
1to9only PG       4279     1277

R. Jamil
----------
GitHub
Attachments
RJSudoku.zip
Iterative guess backtracking
(32.65 KiB) Downloaded 153 times
RJSolBit.zip
Recursive step-by-step backtracking
(39.02 KiB) Downloaded 140 times
rjamil
 
Posts: 729
Joined: 15 October 2014
Location: Karachi, Pakistan

Re: Bitwise/Boolean Sudoku Solver

Postby tarek » Mon May 18, 2020 2:04 pm

Great job rjamil!!!

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

Re: Bitwise/Boolean Sudoku Solver

Postby rjamil » Wed May 20, 2020 1:04 pm

Hi Tarek,

tarek wrote:Great job rjamil!!!

Tarek

Many thanks for your kind appreciation.

R. Jamil
rjamil
 
Posts: 729
Joined: 15 October 2014
Location: Karachi, Pakistan

Bitwise/Boolean Sukaku Solver

Postby rjamil » Wed May 20, 2020 1:30 pm

Hi all,

Pleased to share herewith my first attempt to solve iterative backtracking vanilla RJSukaku.c Sukaku Solver program with pattern based logic.

Based on Tom's suggestion, I have finally decided to convert my RJSolBit.c program to solve bulk Sukaku puzzles.

I look forward to receiving expert feedback.

R. Jamil
----------
GitHub
Attachments
RJSukaku.zip
Iterative backtracking vanilla Sukaku Solver with pattern based logic
(32.34 KiB) Downloaded 151 times
rjamil
 
Posts: 729
Joined: 15 October 2014
Location: Karachi, Pakistan

Previous

Return to Software