SudokuSolver Forum http://www.rcbroughton.co.uk/sudoku/forum/ |
|
Irregular Clueless Explosion Special #1 http://www.rcbroughton.co.uk/sudoku/forum/viewtopic.php?f=4&t=115 |
Page 1 of 1 |
Author: | Børge [ Sat Jun 07, 2008 7:38 pm ] |
Post subject: | Irregular Clueless Explosion Special #1 |
All sudoku puzzles in this forum post are the intellectual property of Børge Alexander Tetlie Anderssen. Irregular Clueless Explosion Special #1 THIS PUZZLE IS NOT CENTER DOT! Rating based on required solving techniques: Moderate 000050000001000300004006070800000010000000004200000090020000500000009000400002007 070000000400700000000980740000000300000000000600000007096000100000002000020009500 000000000002000604040310007000000000400000000900000060008006030106000002000000006 070008200000003100090000000001000023200000000000000040005300008007600000000800004 006087000003000000000500009000000090000000300802000000000000600000005001520060900 002000004000002500500060900080000010000000000390000060004000002000007000008530009 000180000002005006010000040000000000000000000240000007003000260004803500000004000 000050002400000000500020000809000300000000900001000080000005030000008007054006008 064000000008000000000207300050000006000000000940000005400070100100500900000800040 |
Author: | udosuk [ Sun Jun 08, 2008 12:32 pm ] |
Post subject: | Re: Unregular Clueless Explosion Special #1 |
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. 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? |
Author: | Glyn [ Sun Jun 08, 2008 1:17 pm ] |
Post subject: | Re: Unregular Clueless Explosion Special #1 |
Breeding a Clueless Explosion and Clueless Special must be a Clueless SExplosion. |
Author: | Børge [ Sun Jun 08, 2008 2:06 pm ] |
Post subject: | Re: Unregular Clueless Explosion Special #1 |
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: HERE Jean-Christophe wrote: 1. Fill in all cells with a valid solution. 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: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. Code: Private used_column_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) <> 0Private used_nonet_values(1 To 9, 1 To 9) As Long Private used_row_values(1 To 9, 1 To 9) As Long 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:
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 |
Author: | Oscar [ Mon Jun 09, 2008 8:15 pm ] |
Post subject: | Re: Unregular Clueless Explosion Special #1 |
Børge wrote: Rating based on required solving techniques: Moderate "Moderate" is to be appllied only to the solving techniques, but not easy 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: Another consideration: The solutions: It was very interesting to mix both Clueless. Some times I mixed both concepts and So a couple of re-starts were necesary before organizing my ideas But the final result is that I got more confident with the Clueless now Thanks Børge, very creative job |
Author: | Børge [ Mon Jun 09, 2008 8:48 pm ] |
Post subject: | Re: Unregular Clueless Explosion Special #1 |
Oscar wrote: Børge wrote: Rating based on required solving techniques: Moderate 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. |
Author: | Oscar [ Tue Jun 10, 2008 7:25 am ] |
Post subject: | Re: Unregular Clueless Explosion Special #1 |
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 between greeds 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 holidays on July and I have a huge backlog due to the time I spent on the Clueless Explosion Special #1
|
Page 1 of 1 | All times are UTC |
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |