Solving Kurosu using Perl and C

 Kurosu is a combinatorial bit seeing puzzle from the DM - but is not so hard.

** Update See how this puzzle is solved using an SMT solver. ( this is an old post )

The puzzle is just a 36 bit solver.

Each Row/Column must have 3 * 0 and 3 * X

In line positioning - No more than 2 lots of 00 or XX allowed. This could be better worded as no 3  O or X together in a row or column.

First glance:

   Using 1 as x and 0 as O.

   There are 36 cells each of which can have 2 different values.

   Each line (row or column) must have 3*1s and 3*0s
   No line with "111" or "000" is allowed 

   Number of patterns of 6 bits that have 3*0 and 3*1 = 20 ( some will have 3 in a row and need to be excluded )

    

Because of the line pattern rules:

    Total number of line patterns will be substantially less than 2^6 aka 64

    Total number of puzzle patterns will be substantially less than 2^36 aka  68,719,476,736

After research :

    Total number of actual line patterns that follow the rules above is 14.

    As each line pattern can be used more than once in the puzzle the ..

    Total number of possible puzzle patterns that follow the line rules above is = 14^6 = 7,529,536

    Actual total number of valid puzzle patterns that follow the rules above is just 11,222

By comparison all the puzzle layouts is less than the number of possible layouts for a single Sudoku line (362,879).

Sample puzzle : 

Looking in detail at the line patterns that match the rules:

#Kurosu v1.0 June 2018 estimate 11222

#Pat Count = 14

[0] 11 = 0x0b = 001011

[1] 13 = 0x0d = 010011

[2] 19 = 0x13 = 001101

[3] 21 = 0x15 = 010101

[4] 22 = 0x16 = 100101

[5] 25 = 0x19 = 011001

[6] 26 = 0x1a = 101001

[7] 37 = 0x25 = 010110

[8] 38 = 0x26 = 100110

[9] 41 = 0x29 = 011010

[10] 42 = 0x2a = 101010

[11] 44 = 0x2c = 110010

[12] 50 = 0x32 = 101100

[13] 52 = 0x34 = 110100

Board patterns that match the rules are obtained by permuting all the line patterns and testing for compilance :

Pass Permutation# result# { line numbers,... } puzzle_result_pattern.

# board lines, tableMax = 7529535

Pass 35867 1 { 13 13 0 13 0 0 } 110100110100001011110100001011001011

Pass 36049 2 { 13 12 1 13 0 0 } 110100101100010011110100001011001011

Pass 36231 3 { 13 11 2 13 0 0 } 110100110010001101110100001011001011

Pass 36413 4 { 13 10 3 13 0 0 } 110100101010010101110100001011001011

Pass 36595 5 { 13 9 4 13 0 0 } 110100011010100101110100001011001011

Pass 36777 6 { 13 8 5 13 0 0 } 110100100110011001110100001011001011

Pass 36959 7 { 13 7 6 13 0 0 } 110100010110101001110100001011001011

……snip 

Pass 7492758 11217 { 0 5 8 0 13 13 } 001011011001100110001011110100110100

Pass 7492940 11218 { 0 4 9 0 13 13 } 001011100101011010001011110100110100

Pass 7493122 11219 { 0 3 10 0 13 13 } 001011010101101010001011110100110100

Pass 7493304 11220 { 0 2 11 0 13 13 } 001011001101110010001011110100110100

Pass 7493486 11221 { 0 1 12 0 13 13 } 001011010011101100001011110100110100

Pass 7493668 11222 { 0 0 13 0 13 13 } 001011001011110100001011110100110100

Solving

Given that a line can be considered as horizontal or vertical...

Solving Rule 1: Line can be trivially completed when first showing either 3*0 or 3*1.

Solving Rule 2: A vertical or horizontal line solved contributes to all other lines that cross it.

Solving Rule 3: Only one solution should found in the board patterns.

Can be simply solved using pattern grep after all 11,222 possible board layouts are calculated.

Using a sample puzzle file

$ cat ku_dm_01062018.txt

#Kurosu6 DM 01 June 2018

...0.1

0...0.

1.1.1.

..0...

.1.0.1

0....0

Solving by shell and Perl - join up the board lines and search the possible board solutions found within the pre-calculated Tables file that holds all the possible board layout results.

1> $ for i in ku_dm_* ; 

2>   do  echo $i ; 

3>   cat $i | perl -ane '{ next if (/^#/); $b.=$_ };  

4>           END { $b=~s/\n//g; print "Board>$b\n";

5>           system "grep \" $b\$\" < ./TablesForKurosu.txt"; };'; 

6>  done

giving

ku_dm_01062018.txt

Board>...0.10...0.1.1.1...0....1.0.10....0

Pass 3980808 5844 { 6 3 10 8 5 7 } 101001010101101010100110011001010110

displayed as 

101001

010101

101010

100110

011001

010110

Solving explanation line by line

1> Run script in a loop for all the files named ku_dm_...........
2> Print the filename ( $i ) for this loop instance
3> Send the file contents to a Perl script that eats the input line by line but skips lines starting with a #. Other lines are assembled into $b.
4> At the END of the input file remove by substitution all the line ending markers. Print the board as a single line starting Board.
5> Call the unix system command grep (global regular expression print) to print all lines in the file TablesForKurosu.txt that contain a pattern match for the input board. The input board lines have . as the unknown values which is the wildcard search character in grep.

We see that this works by having a sample of input puzzle files all of which find only one and only one of the pre-calculated board layouts.

Results

ku_dm_01062018.txt

Board>...0.10...0.1.1.1...0....1.0.10....0

Pass 3980808 5844 { 6 3 10 8 5 7 } 101001010101101010100110011001010110

ku_dm_04062018.txt

Board>..1.1..0.1.....1.0...0.0..1......11.

Pass 4022564 6097 { 0 4 13 9 6 7 } 001011100101110100011010101001010110

ku_dm_05062018.txt

Board>.1...11...1..011....1.0..1.1..1..01.

Pass 5664165 8663 { 3 11 2 6 7 10 } 010101110010001101101001010110101010

ku_dm_06062018.txt

Board>......0..01.....0.1.....1....1..1.11

Pass 184379 167 { 13 9 2 11 4 0 } 110100011010001101110010100101001011

ku_dm_07062108.txt

Board>...0.0.1....0.1...0..1......1..110..

Pass 3004872 4390 { 10 13 0 3 8 5 } 101010110100001011010101100110011001

ku_dm_12062018.txt

Board>..1.....1.1.........00...1...1......

Pass 4525768 6852 { 2 9 4 11 5 8 } 001101011010100101110010011001100110

ku_dm_13062018.txt

Board>..1.0..11....1..0......10..........1

Pass 2422888 3501 { 6 9 13 0 7 4 } 101001011010110100001011010110100101

ku_dm_14062018.txt

Board>00..0..........0...1...10....1.01.0.

Pass 6502652 9800 { 2 11 10 3 1 12 } 001101110010101010010101010011101100

ku_dm_16062018.txt

Board>11..1......0...1...1.....0.1.0..0.0.

Pass 2077751 3189 { 11 10 2 1 12 3 } 110010101010001101010011101100010101

Solving using c++

1: Read the input puzzle file into an array of 6 strings.

2: For each string match against all 14 of the possible line patterns retaining a list of those that match.

3: Multiply the lengths of the lists to get the total number of pattern perms that are to be tested against the rules and input puzzle

4: Generate from the lists of sub-string patterns possible board answer layouts. 

5: Test against the board rules and input pattern until solution is found. 

Interesting coding point

Having generated a possible solution layout using horizontal sub-strings the solution needs to be transformed to enable easier checking of the solution. Equivalent to rotating the board by 90 degrees.

// l 001101 001011 001011 010011 001011 001101  Transformation from rows to cols gives

// v 000000 000100 111011 100001 011110 111111  

//   ab  becomes ax

//   xy          by

Transformation of a bit matrix is described in the seminal book Hacker's Delight by Henry S. Warren who's code is available here but only works on 32 bit machines apparently. However I just used a simpler substr char by char method.

for (j=0; j<=5; j++) { // transpose board to be able to read down the colls

        vboard = vboard + lboard.substr(j+0,1)  + lboard.substr(j+6,1) + 

                          lboard.substr(j+12,1) + lboard.substr(j+18,1) +

                          lboard.substr(j+24,1)+ lboard.substr(j+30,1);

}