SudokuSolver Forum

A forum for Sudoku enthusiasts to share puzzles, techniques and software
It is currently Thu Mar 28, 2024 3:49 pm

All times are UTC




Post new topic Reply to topic  [ 7 posts ] 
Author Message
PostPosted: Sat Jun 07, 2008 7:38 pm 
Offline
Grand Master
Grand Master
User avatar

Joined: Mon Apr 21, 2008 10:32 am
Posts: 868
All sudoku puzzles in this forum post are the intellectual property of Børge Alexander Tetlie Anderssen.
Copyright © 2008 Børge Alexander Tetlie Anderssen. All rights reserved. Terms of Use.


Irregular Clueless Explosion Special #1

THIS PUZZLE IS NOT CENTER DOT!

Rating based on required solving techniques:  Moderate

Image

000050000001000300004006070800000010000000004200000090020000500000009000400002007
070000000400700000000980740000000300000000000600000007096000100000002000020009500
000000000002000604040310007000000000400000000900000060008006030106000002000000006
070008200000003100090000000001000023200000000000000040005300008007600000000800004
006087000003000000000500009000000090000000300802000000000000600000005001520060900
002000004000002500500060900080000010000000000390000060004000002000007000008530009
000180000002005006010000040000000000000000000240000007003000260004803500000004000
000050002400000000500020000809000300000000900001000080000005030000008007054006008
064000000008000000000207300050000006000000000940000005400070100100500900000800040

_________________
Quis custodiet ipsos custodes?
Normal: [D  Y-m-d,  G:i]     PM->email: [D, d M Y H:i:s]


Last edited by Børge on Fri May 01, 2009 8:47 pm, edited 4 times in total.

Top
 Profile  
Reply with quote  
PostPosted: Sun Jun 08, 2008 12:32 pm 
Offline
Grand Master
Grand Master
User avatar

Joined: Wed Apr 23, 2008 5:29 am
Posts: 302
Location: Sydney, Australia
It's scary. During the last few hours I was just investigating the possibility of combining Clueless Special and Clueless Explosion for a 11-grid puzzle, and you post this now. :study:

So 11 grids in all: the 9 standard grids plus the red Explosion grid plus the green Special grid. But the blue 3x3 square is allowed to have repeats. Have I understood it correctly? :geek:

_________________
ADYFNC HJPLI BVSM GgK Oa m


Top
 Profile  
Reply with quote  
PostPosted: Sun Jun 08, 2008 1:17 pm 
Offline
Expert
Expert

Joined: Mon Apr 21, 2008 8:12 pm
Posts: 90
Location: London, UK
Breeding a Clueless Explosion and Clueless Special must be a Clueless SExplosion. :)

_________________
I have 81 brain cells left, I think.


Top
 Profile  
Reply with quote  
PostPosted: Sun Jun 08, 2008 2:06 pm 
Offline
Grand Master
Grand Master
User avatar

Joined: Mon Apr 21, 2008 10:32 am
Posts: 868
udosuk wrote:
So 11 grids in all: the 9 standard grids plus the red Explosion grid plus the green Special grid. But the blue 3x3 square is allowed to have repeats. Have I understood it correctly? :geek:
You have understood everything absolute 100% correctly. In this puzzle the blue cells have repeats. One could of course generate a Clueless Explosion Special where the blue cells have no repeats, i.e. the 10th and 11th grid are both Center-Dot.


For me the challenge making a Clueless Explosion Special was programming the algorithm finding a legal solution to both the 10th and 11th grid. My method for finding a valid solution grid is very similar to Jean-Christophe's:
1. Fill in all cells with a valid solution.
Notes: for step 1 I also use DLX, stoping at first solution found. Before DLX starts "solving", all DLX candidate rows are enabled and I shuffle the mandatory DLX columns and the DLX rows within each column. This yields a random valid grid.
My brute force solver is Vector based, i.e. 9 Row vectors, 9 Column vectors and 9 Nonet vectors. Each vector is of length 9, i.e. one member for each of the digits 1-9. I have a C implementation using pointers. The Visual Basic implementation uses matrices because it is faster than pointers:
Code:
Private used_column_values(1 To 9, 1 To 9)   As Long
Private used_nonet_values(1 To 9, 1 To 9)    As Long
Private used_row_values(1 To 9, 1 To 9)      As Long
If for instance Row 4 has the digit 7 as a given/solution Then: used_row_values(4,7) <> 0

So checking if a given cell can have a certain value is fast and simple.
Checking if the cell r4c7 can have the digit 5 becomes: used_row_values(4,5) + used_column_values(7,5) + used_nonet_values(6,5) = 0
Due to the Intel branch prediction, here ADDING is MUCH faster than a NESTED IF. The Intel branch prediction is only extremely good when a branch almost always goes in the same direction. With several branches within a loop where each branch randomly goes in one of its two possible directions the instruction decoding pipeline(s) will be emptied and reloaded too often, each time loosing up to around 30 processor cycles, depending on the CPU model (newer CPUs have longer pipelines).

When generating a random valid solution grid, the possible digits for a cell are not tried in sequence from 1 to 9 but in random. The average number of recursions for finding a random valid solution grid (with no givens) is around 130. The minimum number of recursions is of course 82. When generating a random solution grid I have seen number of recursions < 90.

When making a Clueless Explosion Special the basic algorithm is:
  1. Generate a valid solution for the 10th Clueless Explosion grid and paste it into the 10th grid. When pasting/entering a number into a red, green or blue cell, it is automatically duplicated to its twin-cell(s).
  2. Read the 81 character sudoku code (with 9 givens) from the 11th Clueless Special grid and initialize the (brute force) solver with it.
  3. For the 2nd cell in every nonet in the 11th grid, remove the values in the 2nd and 8th cell in the corresponding nonet in the 10th grid as possible solutions from the (brute force) solver data structures.
    For the 8th cell in every nonet in the 11th grid, remove the values in the 2nd and 8th cell in the corresponding nonet in the 10th grid as possible solutions from the (brute force) solver data structures.
    For the 4th cell in every nonet in the 11th grid, remove the values in the 4nd and 6th cell in the corresponding nonet in the 10th grid as possible solutions from the (brute force) solver data structures.
    For the 6th cell in every nonet in the 11th grid, remove the values in the 4nd and 6th cell in the corresponding nonet in the 10th grid as possible solutions from the (brute force) solver data structures.
  4. Generate a valid solution for the 11th grid, but if this takes longer than 5 seconds stop the attempt and goto step 1.

Here is the complete subroutine that generates a Clueless Explosion Special (taken out of its context):
Code:
Public Sub MakeNewCluelessExplosionSpecialPuzzle(Optional ByVal dummy_to_prevent_this_sub_from_beeing_listed_in_Tools_Macro_Macros As Boolean = True)

    Dim ii                             As Long
    Dim illegal_value_1                As Long
    Dim illegal_value_2                As Long
    Dim nonet_cell                     As Long
    Dim nonet_given                    As Long
    Dim sudoku_9x9_solution            As String
    Dim sudoku_char                    As Long
    Dim sudoku_char_first_nonet_cell   As Long



    Application.EnableCancelKey = xlDisabled
    Call CLEAR_AND_RESET_GRID

    Do
        Call StopCurrentOperation.CheckIfUserWantsTo
        Call SolutionsTo9x9Sudoku(empty_sudoku_9x9_code, do_init:=True, find_first_solution_only:=True, save_solution:=True, solve_randomly:=True)   ' Step 1.
        sudoku_9x9_solution = SolutionTo9x9Sudoku                                                                                                    ' Step 1.
        Call PasteCodeInto9x9Grid(p_sudokus_9x9(10), sudoku_9x9_solution)                                                                            ' Step 1.
        Call InitializeSolverDataStructures(sudoku_9x9_code:=CopyCodeFromGrid(p_sudokus_9x9(11), True, True), solve_randomly:=True)   ' Step 2.

        ' Step 3.
        For sudoku_char_first_nonet_cell = 1 To 61 Step 3
            nonet_given = Mid(sudoku_9x9_solution, sudoku_char_first_nonet_cell + 10, 1)

            For nonet_cell = 2 To 8 Step 2

                Select Case nonet_cell

                    Case 2, 8
                        illegal_value_1 = Mid(sudoku_9x9_solution, sudoku_char_first_nonet_cell + 1, 1)
                        illegal_value_2 = Mid(sudoku_9x9_solution, sudoku_char_first_nonet_cell + 19, 1)

                    Case 4, 6
                        illegal_value_1 = Mid(sudoku_9x9_solution, sudoku_char_first_nonet_cell + 9, 1)
                        illegal_value_2 = Mid(sudoku_9x9_solution, sudoku_char_first_nonet_cell + 11, 1)

                End Select

                Select Case nonet_cell
                    Case 2:   sudoku_char = sudoku_char_first_nonet_cell + 1
                    Case 4:   sudoku_char = sudoku_char_first_nonet_cell + 9
                    Case 6:   sudoku_char = sudoku_char_first_nonet_cell + 11
                    Case 8:   sudoku_char = sudoku_char_first_nonet_cell + 19
                End Select

                For ii = 1 To num_nonet_cells

                    If random_solving_sequence(sudoku_char, ii) = illegal_value_1 Then
                        random_solving_sequence(sudoku_char, ii) = nonet_given
                    ElseIf random_solving_sequence(sudoku_char, ii) = illegal_value_2 Then
                        random_solving_sequence(sudoku_char, ii) = nonet_given
                    End If

                Next

            Next

            If ((sudoku_char_first_nonet_cell + 2) Mod 9) = 0 Then sudoku_char_first_nonet_cell = sudoku_char_first_nonet_cell + 18
        Next

    Loop Until SolutionsTo9x9Sudoku(vbNullString, do_init:=False, find_first_solution_only:=True, save_solution:=True, solve_randomly:=True, time_out:=5000)   ' Step 4.

    Call PasteCodeInto9x9Grid(p_sudokus_9x9(11), SolutionTo9x9Sudoku)
    Call GenerateCodeForAllNormal9x9Grids
    Call HighlightDispensableCluesInAllNormalGrids
End Sub

_________________
Quis custodiet ipsos custodes?
Normal: [D  Y-m-d,  G:i]     PM->email: [D, d M Y H:i:s]


Last edited by Børge on Sat Jun 28, 2008 12:42 pm, edited 2 times in total.

Top
 Profile  
Reply with quote  
PostPosted: Mon Jun 09, 2008 8:15 pm 
Offline
Addict
Addict

Joined: Mon Apr 21, 2008 4:42 pm
Posts: 39
Location: Montesson
Børge wrote:
Rating based on required solving techniques:  Moderate

"Moderate" is to be appllied only to the solving techniques, but not easy :naughty: Since both Clueless, Explosion and Special, have to be considered simultaneously the task is rather complicated!
Consider more than two times a single Clueless
First consideration:
Obvious, but I missed it at the begining :oops: Do NOT consider that both clueless are the same!
Another consideration:
Start with the Explosion, it moves faster into the solution ;)
Once blocked of simple techniques, apply the Special restrictions and exploit the Clueless Special grid.
The solutions:
Clueless Explosion
674529381
395841267
182367954
257498613
836152479
419673528
948216735
563784192
721935846

Clueless Special
245617839
897243561
613895427
786124953
134958276
529736148
978562314
462381795
351479682

It was very interesting to mix both Clueless. Some times I mixed both concepts and :brickwall:
So a couple of re-starts were necesary before organizing my ideas :oops:
But the final result is that I got more confident with the Clueless now :D
Thanks Børge, very creative job ;clapclap;

_________________
Nothing can both be and not be


Top
 Profile  
Reply with quote  
PostPosted: Mon Jun 09, 2008 8:48 pm 
Offline
Grand Master
Grand Master
User avatar

Joined: Mon Apr 21, 2008 10:32 am
Posts: 868
Oscar wrote:
Børge wrote:
Rating based on required solving techniques:  Moderate
"Moderate" is to be applied only to the solving techniques, but not easy :naughty: Since both Clueless, Explosion and Special, have to be considered simultaneously the task is rather complicated!
I stated the level of required solving techniques only and said absolutely nothing about rating based on actual solving.

I knew solving this one would not be easy, especially since there AFAIK currently are no helper/solvers for a Clueless Explosion Special. Lack of such also made the creation complicated since I had to copy forth and back between a Clueless Explosion and a Clueless Special solver and hence had no count of the required number of Intersections, which in my experience is a very good indication of how hard a puzzle with Naked and Hidden Singles only is and how long it will take to solve it.

I have already generated the basic puzzle for Irregular Clueless Explosion Special #2, were both Clueless grids (10 and 11) are Center-Dot, but I will not publish it before sometime in July, at the earliest.

_________________
Quis custodiet ipsos custodes?
Normal: [D  Y-m-d,  G:i]     PM->email: [D, d M Y H:i:s]


Top
 Profile  
Reply with quote  
PostPosted: Tue Jun 10, 2008 7:25 am 
Offline
Addict
Addict

Joined: Mon Apr 21, 2008 4:42 pm
Posts: 39
Location: Montesson
Børge wrote:
... I had to copy forth and back between a Clueless Explosion and a Clueless Special solver...
So you experience the "pleasure" of :bouncy: between greeds :lol:
Børge wrote:
... for Irregular Clueless Explosion Special #2, were both Clueless grids (10 and 11) are Center-Dot, but I will not publish it before sometime in July, at the earliest.
that's fine for me since I will be on :sun: holidays on July ;) and I have a huge backlog due to the time I spent on the Clueless Explosion Special #1 :thumbs:

_________________
Nothing can both be and not be


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 7 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 6 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB® Forum Software © phpBB Group