Bitwise/Boolean Sudoku Solver - to solve a single sudoku

Programs which generate, solve, and analyze Sudoku puzzles

Bitwise/Boolean Sudoku Solver - to solve a single sudoku

Postby 1to9only » Sat May 26, 2018 8:27 am

First, thanks to rjamil for making the source of his 'Bitwise/Boolean Sudoku Solver' available here. I've downloaded his latest code - it's an excellent (and fast) solver (and much better than mine that solves up to the basic fishes!). The program solves a batch of sudokus.

I've modified rjamil's 'Bitwise/Boolean Sudoku Solver' to solve a single sudoku, by replacing the program main() function with this:
Hidden Text: Show
Code: Select all
#include <string.h>
#include <stdlib.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <fcntl.h>
#include <io.h>
int main(int argc, char *argv[])
{
// This program is free software: you can redistribute it and/or modify it under the terms of the GNU general public License.
// This program is distributed without any warrenty; without even the implied warrant of Merchantability or fitness for a particular purpose.
// See the GNU general public license for more details: https://www.gnu.org/licenses/

// this program is based on RJSolBit.c, Bitwise/Boolean Sudoku Solver written by rjamil
// see http://forum.enjoysudoku.com/bitwise-boolean-sudoku-solver-t32616.html

   char         *psudoku = (char*)0;
   char         buffer[ 100] = { 0, };
   struct _stat st = { 0, };
   int          rc = 0, len = 0, f = 0;
   int          i, m;
   float        c;

   if (argc == 2)
   {
      if (strlen(argv[1]) == 81)             // is sudoku line
      {
         psudoku = argv[1];
      }
      else                                   // is sudoku file
      {
         rc  = _stat(argv[1], &st);
         len = st.st_size;
         if (rc == 0 && len >= 81)
         {
            f = _open(argv[1], _O_RDONLY | _O_BINARY);
            if (f != -1)
            {
               rc          = _read(f, buffer, 81); // read 81 bytes only
               rc          = close(f);
               buffer[ 81] = 0;                    // null terminate after 81 chars
               psudoku     = buffer;
            }
         }
         else
         {
            printf("file '%s' not found!\n", argv[1]);
            exit(1);
         }
      }
   }

   if (psudoku != (char*)0)
   {
      for (i = 0; i < 81; i++)
      {
         m     = (int)psudoku[ i];
         s[ i] = m < 49 || m > 57 ? 0 : 1 << (m - 49);   // Assign given Cell positions
      }
      q = n[0] = n[1] = n[2] = n[3] = n[4] = 0;
      if (invalid())
      {
         printf("error: invalid!\n");
      }
      else
      if (!q)
      {
         for (i = 0; i < 81; i++)
         {
            printf("%c", psudoku[ i]);
         }
         printf("\n");
         printf("valid!\n");
      }
      else
      {
         c = clock();
         m = solve(0);
         c = (clock() - c) / CLOCKS_PER_SEC;
         if (m)
         {
            for (i = 0; i < 81; i++)
            {
               printf("%c", psudoku[ i]);
            }
            printf("\n");
            for (i = 0; i < 81; i++)
            {
               printf("%d", b[ s[ i]]);
            }
            printf("\n");
            printf("# C:%d # N:%ld # H:%ld # G:%ld # D:%ld # T:%f\n", 81 - q, n[0], n[1], n[2], n[4], c);
         }
         else
         {
            printf("error: unsolvable!\n");
         }
      }
   }
   else
   {
      printf("nothing to solve!\n");
   }

   return 0;
}

I've renamed my modified program RJBitSolve.c

In Windows with Visual Studio, I compile with this command: cl.exe /TpRJBitSolve.c

Run the modified program, passing it either: 1) a sudoku string (of 81 characters) as argument,
Code: Select all
RJBitSolve.exe ..5..2..9.83....7.4.987.1.......5.6...7.8.2...3.4.......8.247.3.7....95.3..7..8..

or 2) a filename containing a sudoku (only the first 81 characters are read),
Code: Select all
RJBitSolve.exe test.sud

The program displays the sudoku solution:
Code: Select all
..5..2..9.83....7.4.987.1.......5.6...7.8.2...3.4.......8.247.3.7....95.3..7..8..
715342689683591472429876135894215367567983241132467598958624713276138954341759826
# C:29 # N:5 # H:47 # G:0 # D:0 # T:0.000000

The last line of stats give details:
# C: number of givens
# N: number of naked singles solved
# H: number of hidden singles solved
# G: number of guesses
# D: maximum guess and depth
# T: time in seconds to solve!

I also have RJBitSolve3.c (with #define RJ 3) and RJBitSolve4.c (with #define RJ 4) compiled and ready to print the solving steps and pencil marks, if these are needed... RJ 1 and 2 are no longer available as they were used in the old main() function.

The program has a 50% success rate with solving the last few recent sudokus posted in the Puzzles section:

Historical Daily 22 - SOLVED
Code: Select all
4.....82...3...1.958....3.4..7.2........76.9..68.....1...7.563.....1.54....3..9.8
479163825623458179581297364397521486145876293268934751914785632832619547756342918
# C:28 # N:2 # H:51 # G:0 # D:0 # T:0.000000

May 25, 2018 - 2 GUESSES
Code: Select all
2....97......1..6....4....3....7..2...83.65...4..8....9....2....6..5......38....1
215639748834715962679428153391574826728396514546281379987142635162953487453867291
# C:22 # N:1 # H:66 # G:2 # D:1 # T:0.000000

Historical Daily 23 - 4 GUESSES
Code: Select all
.19.2..83.538.1.29.28..351..6...219...21....5.41.59.62.......3..349.8.56.86.3.9..
419527683753861429628493517365742198972186345841359762297615834134978256586234971
# C:40 # N:0 # H:58 # G:4 # D:3 # T:0.000000

Historical Daily 24 - SOLVED
Code: Select all
.3.....8...79826..6.......737.2.......1.78..2..86...9.7...9.1...6.1.48......2..36
235761489147982653689345217376219548591478362428653791753896124962134875814527936
# C:29 # N:0 # H:52 # G:0 # D:0 # T:0.000000

Enjoy!
Attachments
RJBitSolve.c
my modified RJSolBit.c
(169.3 KiB) Downloaded 8 times
1to9only
 
Posts: 80
Joined: 04 April 2018

Return to Software