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?
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) <> 0So 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) = 0Due 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:
- 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).
- Read the 81 character sudoku code (with 9 givens) from the 11th Clueless Special grid and initialize the (brute force) solver with it.
- 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. - 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]