Author Topic: Sudoku solver  (Read 280 times)

Offline jalih

  • Advocate
  • Posts: 52
Sudoku solver
« on: November 06, 2018, 12:08:10 PM »
Your challenge is to write a simple Sudoku solver. Input data for the solver should be given as 81 character string or record.

You can use this Sudoku puzzle for testing purposes: "000020078800073009020500063502000806103000054600857000017300045248910037306700901"

Here is my PL/I version that can also be found from Rosetta Code:

Code: [Select]
*PROCESS MARGINS(1,120) LIBS(SINGLE,STATIC);
*PROCESS OPTIMIZE(2) DFT(REORDER);


 sudoku: proc(parms) options(main);
   dcl parms char (100) var;

   /* Sudoku board presentation from the book: The New PL/I. */
   define alias bits bit (9) aligned;
   dcl total (81) type bits;
   dcl matrix (9, 9) type bits based(addr(total));
   dcl box (9, 3, 3) type bits defined (total(trunc((1sub-1) /3) * 27 + mod(1sub-1, 3) * 3 + (2sub-1) * 9 + 3sub));

   dcl posbit (0:9) type bits init('000000000'b, '100000000'b, '010000000'b, '001000000'b,
                                   '000100000'b, '000010000'b, '000001000'b, '000000100'b,
                                   '000000010'b, '000000001'b);

   dcl (i, j, k) fixed bin(31);
   dcl buffer char(81);
   dcl in file;

   /* ON UNIT for the Sudoku data conversion */
   on conversion
     begin;
       put skip
         list('Sudoku data not valid.');
       stop;
     end;

   /* ON UNIT to display info about the usage */
   on undefinedfile(in)
     begin;
       put skip
         list('Usage: ' || procedurename() || ' /filename');
       stop;
     end;

   open file(in)
     title ('/'||parms||',type(fixed), recsize(81)') record input;

   /* Ignore the endfile condition */
   on endfile(in);

   /* Read the Sudoku data into buffer as one record */
   read file(in) into(buffer);
   close file(in);

   /* Convert numbers -> position bit presentation and assign into the Sudoku board */
   do k = 1 to 81;
     total(k) = posbit(substr(buffer, k, 1));
   end;

   /* Start solving the Sudoku */
   start = secs();
   if solve() then
     do;
       put skip list('Sudoku solved!');
       put skip(2);

   /* display the solved Sudoku if solution exist */
       do i = 1 to 9;
         do j = 1 to 9;
           put edit(trim(index(matrix(i, j), '1'b))) (a(3));
         end;
         put skip(2);
       end;
     end;
   else put skip list('Impossible!');


   /*************************************/
   /* Simple backtracking sudoku solver */
   /*************************************/
   solve: proc recursive returns(bit(1));
     dcl (i, j, k) fixed bin(31);
     dcl result type bits;

     /* find free cell */
     do i = 1 to 9;
       do j = 1 to 9;
         if matrix(i, j) = posbit(0) then goto skip;
       end;
     end;

     /* No more free cells. Check if the completed Sudoku is valid.      */
     /* Number in the cell is valid if the matching position bit is set. */
     do i = 1 to 9;
       do j = 1 to 9;
       k = index(matrix(i, j), '1'b);
       matrix(i, j) = posbit(0);
       result = ^(any(matrix(i, *)) | any(matrix(*, j)) | any(box(numbox(i, j), *, *)));
       if substr(result, k, 1) = '0'b then return('0'b);
       matrix(i, j) = posbit(k);
       end;
     end;

     return('1'b);
    skip:

     /* Go through and test possible values for the free cell untill the Sudoku is completed */
     result = ^(any(matrix(i, *)) | any(matrix(*, j)) | any(box(numbox(i, j), *, *)));
     k = 0;
     do forever;
       k = search(result, '1'b, k+1);
       if k = 0 then leave;
       matrix(i, j) = posbit(k);
       if solve() then return('1'b);
       else matrix(i, j) = posbit(0);
     end;

     return('0'b);
   end solve;


   /********************************************/
   /* Returns box number for the sudoku coords */
   /********************************************/
   numbox: proc(i, j) returns(fixed bin(31));
     dcl (i, j) fixed bin(31);

     dcl lookup (9, 9) fixed bin(31) static init( (3)1, (3)2, (3)3,
                                                  (3)1, (3)2, (3)3,
                                                  (3)1, (3)2, (3)3,
                                                  (3)4, (3)5, (3)6,
                                                  (3)4, (3)5, (3)6,
                                                  (3)4, (3)5, (3)6,
                                                  (3)7, (3)8, (3)9,
                                                  (3)7, (3)8, (3)9,
                                                  (3)7, (3)8, (3)9 );

     return(lookup(i, j));
   end numbox;

 end sudoku;

Offline John

  • Forum Support / SB Dev
  • Posts: 2745
    • ScriptBasic Open Source Project
Re: Sudoku solver
« Reply #1 on: November 06, 2018, 01:21:21 PM »
This is more of a hobby code challenge. The RetroB forum is a better place for this.
« Last Edit: November 06, 2018, 01:24:36 PM by John »