Investigation of one-band-free patterns

Everything about Sudoku that doesn't fit in one of the other sections

Investigation of one-band-free patterns

Postby Serg » Sun Feb 06, 2011 5:02 pm

Hi, people!
It is well-known that patterns having 0, 1 or 2 empty boxes in the same band or stack can produce valid puzzles, but patterns having 3 empty boxes in the same band or stack cannot produce valid puzzles.
Here are examples of patterns which can produce valid puzzles ("x" denotes cells which must contain digits, "." denotes cells which must be empty).
Code: Select all
+-----+-----+-----+        +-----+-----+-----+
|x x x|. . .|. . .|        |x x x|x x x|. . .|
|x x x|. . .|. . .|        |x x x|x x x|. . .|
|x x x|. . .|. . .|        |x x x|x x x|. . .|
+-----+-----+-----+        +-----+-----+-----+
|x x x|x x x|x x x|        |x x x|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+
|x x x|x x x|x x x|        |x x x|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+

+-----+-----+-----+
|x x x|x x x|x x x|
|x x x|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+
|x x x|x x x|x x x|
|x x x|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+
|x x x|x x x|x x x|
|x x x|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+

Example of pattern having empty band (such pattern cannot produce valid puzzles).
Code: Select all
+-----+-----+-----+
|. . .|. . .|. . .|
|. . .|. . .|. . .|
|. . .|. . .|. . .|
+-----+-----+-----+
|x x x|x x x|x x x|
|x x x|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+
|x x x|x x x|x x x|
|x x x|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+

I investigated all "intermediate" patterns between patterns posted above, having partitially filled boxes in B123 band. For example, can posted below pattern produce valid puzzles (L-shape of the B1 box pattern)?
Code: Select all
+-----+-----+-----+
|x . .|. . .|. . .|
|x . .|. . .|. . .|
|x x x|. . .|. . .|
+-----+-----+-----+
|x x x|x x x|x x x|
|x x x|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+
|x x x|x x x|x x x|
|x x x|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+

I call such "intermediate" patterns as "one-band-free" patterns because they have 2 whole filled bands and 1 partitially filled ("free")
I'll post my results in a short time.

Serg
Last edited by Serg on Sun Feb 06, 2011 9:02 pm, edited 1 time in total.
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-band-free patterns

Postby coloin » Sun Feb 06, 2011 8:06 pm

Looks like its a "pattern which cant have a puzzle"

Which means there is always an unavoidable set in those empty cells

C
coloin
 
Posts: 1638
Joined: 05 May 2005

Re: Investigation of one-band-free patterns

Postby Serg » Mon Feb 07, 2011 12:48 am

First, I investigated patterns, having 2 empty boxes in the same band.
Code: Select all
+-----+-----+-----+
|A A A|. . .|. . .|
|A A A|. . .|. . .|
|A A A|. . .|. . .|
+-----+-----+-----+
|x x x|x x x|x x x|
|x x x|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+
|x x x|x x x|x x x|
|x x x|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+

Let's consider all possible configurations of filled cells in the box B1, denoted by letters "A". I'll treat 2 box patterns being isomorphic if second box pattern can be reduced to the first box pattern by box rows/columns permutations (but not by transposing!). There are 36 possible box patterns.
Code: Select all
                 . . .
0 filled cells   . . .
                 . . .

                 . . .
1 filled cells   . . .
                 x . .

                 . . .   . . .   . . .
2 filled cells   . . .   x . .   . x .
                 x x .   x . .   x . .

                 . . .   . . .   . . .   x . .   . x .   . . x
3 filled cells   . . .   x . .   . . x   x . .   x . .   . x .
                 x x x   x x .   x x .   x . .   x . .   x . .

                 . . .   . . .   . . .   x . .   . x .   . . x   . . x
4 filled cells   x . .   x x .   x . x   x . .   x . .   x . .   . . x
                 x x x   x x .   x x .   x x .   x x .   x x .   x x .

                 . . .   x . .   x . .   x . .   . x .   . . x   . x .
5 filled cells   x x .   x x .   x . x   x . .   x . x   x x .   x . .
                 x x x   x x .   x x .   x x x   x x .   x x .   x x x

                 . . .   x . .   . . x   x x .   . x x   x . x
6 filled cells   x x x   x x .   x x .   x x .   x . x   x x .
                 x x x   x x x   x x x   x x .   x x .   x x .

                 x . .   x x .   x . x
7 filled cells   x x x   x x .   x x .
                 x x x   x x x   x x x

                 x x .
8 filled cells   x x x
                 x x x

                 x x x
9 filled cells   x x x
                 x x x

I've done exhaustive search for all box patterns. (Really not for all patterns, because it is possible to determine - does a box pattern have valid puzzle - using other box patterns which are subsets or supersers of the considered pattern.)
Here is the list of box B1 patterns, which have no valid puzzles.
Code: Select all
                 . . .
0 filled cells   . . .
                 . . .

                 . . .
1 filled cells   . . .
                 x . .

                 . . .   . . .   . . .
2 filled cells   . . .   x . .   . x .
                 x x .   x . .   x . .

                 . . .   . . .   . . .   x . .   . x .   . . x
3 filled cells   . . .   x . .   . . x   x . .   x . .   . x .
                 x x x   x x .   x x .   x . .   x . .   x . .

                 . . .   x . .   . . x
4 filled cells   x . .   x . .   . . x
                 x x x   x x .   x x .

                 x . .
5 filled cells   x . .
                 x x x

Here is the list of patterns, having valid puzzles.
Code: Select all
                 . . .   . . .   . x .   . . x
4 filled cells   x x .   x . x   x . .   x . .
                 x x .   x x .   x x .   x x .

                 . . .   x . .   x . .   . x .   . . x   . x .
5 filled cells   x x .   x x .   x . x   x . x   x x .   x . .
                 x x x   x x .   x x .   x x .   x x .   x x x

                 . . .   x . .   . . x   x x .   . x x   x . x
6 filled cells   x x x   x x .   x x .   x x .   x . x   x x .
                 x x x   x x x   x x x   x x .   x x .   x x .

                 x . .   x x .   x . x
7 filled cells   x x x   x x .   x x .
                 x x x   x x x   x x x

                 x x .
8 filled cells   x x x
                 x x x

                 x x x
9 filled cells   x x x
                 x x x

It is possible to devide (by asterisk line) general 36-patterns diagram into 2 areas, containing box patterns having no valid puzzles and box patterns having valid puzzles.
Code: Select all
                 . . .
0 filled cells   . . .
                 . . .

                 . . .
1 filled cells   . . .
                 x . .

                 . . .   . . .   . . .
2 filled cells   . . .   x . .   . x .
                 x x .   x . .   x . .

                 . . .   . . .   . . .   x . .   . x .   . . x
3 filled cells   . . .   x . .   . . x   x . .   x . .   . x .
                 x x x   x x .   x x .   x . .   x . .   x . .
                       *****************       *****************       *****
                 . . . * . . .   . . . * x . . * . x .   . . x * . . x *
4 filled cells   x . . * x x .   x . x * x . . * x . .   x . . * . . x *
                 x x x * x x .   x x . * x x . * x x .   x x . * x x . *
************************               *       *               *********
                 . . .   x . .   x . . * x . . * . x .   . . x   . x .
5 filled cells   x x .   x x .   x . x * x . . * x . x   x x .   x . .
                 x x x   x x .   x x . * x x x * x x .   x x .   x x x
                                       *********
                 . . .   x . .   . . x   x x .   . x x   x . x
6 filled cells   x x x   x x .   x x .   x x .   x . x   x x .
                 x x x   x x x   x x x   x x .   x x .   x x .

                 x . .   x x .   x . x
7 filled cells   x x x   x x .   x x .
                 x x x   x x x   x x x

                 x x .
8 filled cells   x x x
                 x x x

                 x x x
9 filled cells   x x x
                 x x x

Box patterns placed upper asterisk line have no valid puzzles, box patterns placed lower asterisk line have valid puzzles.
It turns out, it is sufficiently to publish examples for box patterns having valid puzzles with 4 filled cells only to prove that all other "right" patterns have valid puzzles. Here are examples of valid puzzles having 4 filled cells in the box B1.
Code: Select all
+-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . .|        |. . .|. . .|. . .|
|. 5 6|. . .|. . .|        |4 . 6|. . .|. . .|
|. 8 9|. . .|. . .|        |7 8 .|. . .|. . .|
+-----+-----+-----+        +-----+-----+-----+
|2 1 4|5 3 7|8 9 6|        |2 1 4|3 6 5|7 9 8|
|3 6 5|8 9 1|2 4 7|        |3 6 7|8 9 1|5 2 4|
|8 9 7|6 2 4|3 1 5|        |5 9 8|7 2 4|1 3 6|
+-----+-----+-----+        +-----+-----+-----+
|5 3 1|7 4 2|9 6 8|        |6 3 1|5 7 8|9 4 2|
|6 4 2|9 8 3|7 5 1|        |8 4 5|9 1 2|3 6 7|
|9 7 8|1 6 5|4 3 2|        |9 7 2|6 4 3|8 1 5|
+-----+-----+-----+        +-----+-----+-----+

+-----+-----+-----+        +-----+-----+-----+
|. 2 .|. . .|. . .|        |. . 3|. . .|. . .|
|4 . .|. . .|. . .|        |4 . .|. . .|. . .|
|7 8 .|. . .|. . .|        |7 8 .|. . .|. . .|
+-----+-----+-----+        +-----+-----+-----+
|2 1 4|3 5 6|7 9 8|        |2 1 4|3 7 5|8 9 6|
|3 6 7|8 9 1|2 4 5|        |3 6 5|8 9 1|7 2 4|
|5 9 8|7 2 4|6 1 3|        |8 9 7|6 2 4|1 3 5|
+-----+-----+-----+        +-----+-----+-----+
|6 3 1|5 4 8|9 2 7|        |5 3 1|7 4 2|9 6 8|
|8 7 2|9 1 3|4 5 6|        |6 4 2|9 3 8|5 1 7|
|9 4 5|6 7 2|8 3 1|        |9 7 8|5 1 6|3 4 2|
+-----+-----+-----+        +-----+-----+-----+

Here are the same 4 examples but given in linear form.
Code: Select all
..........56.......89......214537896365891247897624315531742968642983751978165432
.........4.6......78.......214365798367891524598724136631578942845912367972643815
.2.......4........78.......214356798367891245598724613631548927872913456945672831
..3......4........78.......214375896365891724897624135531742968642938517978516342

Resulting rule for patterns, having partially filled box B1 and empty boxes B2, B3.

1. If box B1 has 6 or greater filled cells, the pattern has valid puzzles.

2. If box B1 has 5 filled cells, the pattern has valid puzzles with exception of L-shape of filled cells in the box B1, when pattern has no valid puzzles.

3. If box B1 has 4 filled cells, the pattern has valid puzzles with exception of box patterns produced from 5-cells L-shape by subtraction 1 filled cell.

4. If box B1 has 3 or less filled cells, the pattern has no valid puzzles.

Continuation follows.
Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-band-free patterns

Postby dobrichev » Mon Feb 07, 2011 8:38 am

The 416 bands fit in 16 classes by level of uncertainty.

The columns are Class number, Number of bands, Number of completions for solution grid with this band cleared.
Code: Select all
1   5   96
2  12  120
3  27  144
4  26  156
5  61  168
6  30  180
7  70  192
8  20  216
9  33  228
10 13  264
11 26  276
12 68  288
13  9  516
14  7  576
15  7  864
16  2 1728

For example, take a valid solution grid with one of its bands or stacks being isomorph of band 1 or band 413. Clear this band (or stack). The resulting puzzle has 1728 solutions.

Here are the details by band number
Hidden Text: Show
1 1728
2 576
3 192
4 864
5 192
6 288
7 192
8 516
9 864
10 288
11 288
12 228
13 228
14 168
15 276
16 120
17 192
18 192
19 192
20 288
21 192
22 168
23 144
24 168
25 276
26 228
27 96
28 144
29 516
30 96
31 228
32 192
33 288
34 192
35 288
36 276
37 276
38 180
39 264
40 180
41 264
42 288
43 288
44 168
45 288
46 168
47 288
48 288
49 288
50 156
51 168
52 156
53 168
54 288
55 288
56 168
57 288
58 168
59 288
60 288
61 180
62 288
63 180
64 228
65 228
66 168
67 288
68 168
69 168
70 168
71 228
72 288
73 228
74 276
75 276
76 228
77 228
78 228
79 264
80 288
81 288
82 288
83 516
84 516
85 216
86 276
87 216
88 168
89 192
90 288
91 192
92 264
93 276
94 216
95 228
96 180
97 228
98 228
99 180
100 288
101 192
102 192
103 156
104 192
105 288
106 276
107 192
108 168
109 288
110 168
111 276
112 168
113 216
114 228
115 180
116 228
117 288
118 180
119 192
120 192
121 156
122 288
123 192
124 168
125 168
126 228
127 288
128 168
129 276
130 228
131 264
132 288
133 516
134 276
135 288
136 288
137 264
138 288
139 168
140 276
141 276
142 168
143 192
144 144
145 168
146 144
147 192
148 192
149 288
150 168
151 288
152 288
153 156
154 168
155 156
156 168
157 288
158 144
159 192
160 192
161 228
162 144
163 228
164 144
165 180
166 180
167 168
168 228
169 168
170 156
171 216
172 216
173 180
174 216
175 168
176 168
177 168
178 168
179 168
180 180
181 180
182 276
183 276
184 276
185 180
186 180
187 228
188 228
189 180
190 168
191 180
192 288
193 264
194 156
195 228
196 276
197 216
198 156
199 156
200 180
201 180
202 180
203 180
204 168
205 168
206 168
207 156
208 156
209 120
210 192
211 120
212 192
213 192
214 168
215 144
216 192
217 192
218 288
219 516
220 516
221 276
222 288
223 516
224 864
225 864
226 288
227 216
228 276
229 288
230 288
231 216
232 216
233 276
234 276
235 228
236 288
237 288
238 288
239 288
240 228
241 516
242 288
243 264
244 192
245 264
246 288
247 864
248 180
249 288
250 228
251 192
252 576
253 192
254 576
255 192
256 192
257 288
258 192
259 288
260 192
261 156
262 156
263 276
264 228
265 156
266 216
267 216
268 228
269 288
270 180
271 180
272 276
273 288
274 288
275 288
276 168
277 168
278 288
279 192
280 144
281 144
282 288
283 156
284 228
285 192
286 144
287 192
288 144
289 192
290 192
291 264
292 192
293 264
294 192
295 264
296 180
297 216
298 216
299 156
300 192
301 156
302 168
303 288
304 192
305 576
306 192
307 576
308 192
309 192
310 276
311 180
312 168
313 180
314 288
315 228
316 144
317 192
318 144
319 288
320 192
321 156
322 156
323 144
324 288
325 168
326 168
327 288
328 276
329 216
330 192
331 192
332 144
333 156
334 192
335 144
336 144
337 192
338 168
339 168
340 192
341 192
342 120
343 120
344 168
345 216
346 216
347 192
348 96
349 144
350 168
351 120
352 120
353 120
354 168
355 144
356 156
357 120
358 156
359 120
360 144
361 168
362 192
363 156
364 156
365 144
366 180
367 192
368 168
369 180
370 192
371 168
372 192
373 144
374 168
375 168
376 168
377 228
378 228
379 144
380 168
381 120
382 156
383 216
384 216
385 180
386 168
387 168
388 96
389 120
390 264
391 168
392 192
393 192
394 144
395 192
396 168
397 192
398 192
399 288
400 192
401 144
402 192
403 192
404 96
405 168
406 192
407 288
408 144
409 192
410 288
411 288
412 576
413 1728
414 576
415 864
416 864

MD
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: Investigation of one-band-free patterns

Postby RW » Mon Feb 07, 2011 10:51 am

Serg wrote:It turns out, it is sufficiently to publish examples for box patterns having valid puzzles with 4 filled cells only to prove that all other "right" patterns have valid puzzles.

You could also say that any box pattern that isn't a subset of any of the two following patterns have valid puzzles:
Code: Select all
..x  x..
.x.  x..
x..  xxx


An interesting feature with these puzzles is that if we have a band like this:
Code: Select all
+-----+-----+-----+
|A B C|. . .|. . .|
|x x x|. . .|. . .|
|x x x|. . .|. . .|
+-----+-----+-----+
(x=may or may not be a solved cell)

then none of the other minirows in the band can be 'ABC' in a unique puzzle. If there was another minirow 'ABC' then we could swap all minirows in boxes 2 and 3 for an alternative solution. This might come in handy for the solver. It of course also rules out some bands as potential bands for finding puzzles like this.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Re: Investigation of one-band-free patterns

Postby JPF » Mon Feb 07, 2011 1:31 pm

dobrichev wrote:The 416 bands fit in 16 classes by level of uncertainty.
The columns are Class number, Number of bands, Number of completions for solution grid with this band cleared.

It is a confirmation of results given here.

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Re: Investigation of one-band-free patterns

Postby dobrichev » Mon Feb 07, 2011 5:45 pm

JPF wrote:
dobrichev wrote:The 416 bands fit in 16 classes by level of uncertainty.
The columns are Class number, Number of bands, Number of completions for solution grid with this band cleared.

It is a confirmation of results given here.

JPF

Yes, these posts are nice presentation of some sudoku fundamentals.

When I have time, I will find all possible minimal clue combinations hitting all UA of the cleared band, which could confirm Serg's observations.
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: Investigation of one-band-free patterns

Postby Serg » Tue Feb 08, 2011 9:19 pm

Hi, RW!
RW wrote:
Serg wrote:It turns out, it is sufficiently to publish examples for box patterns having valid puzzles with 4 filled cells only to prove that all other "right" patterns have valid puzzles.

You could also say that any box pattern that isn't a subset of any of the two following patterns have valid puzzles:
Code: Select all
..x  x..
.x.  x..
x..  xxx

RW

Excellent observation! I understood that box patterns
Code: Select all
..x  x..
.x.  x..
x..  xxx

are somewhat special, but you saw them from another side ...

To explain my words I have to introduce "maximal exclusive pattern" term.
Pattern is exclusive if it has no valid puzzles. If we consider another pattern which is subset of the given exclusive pattern, we can be sure this puzzle has no valid puzzles. So, exclusive pattern excludes patterns being its subsets from set of patterns having valid puzzles. I think, it would be very useful for sudoku designers to know "exclusive patterns catalogue" to check if their self-designed patterns have valid puzzles.

Maximal exclusive pattern is exclusive pattern defined for the given patterns class such, that it cannot be extended by any filled cell provided it remains exclusive after adding a cell and it still belongs to given pattern class. For example, let's define pattern class as set of patterns having 2 whole filled bands and having 2 empty boxes in the rest (third) band. Patterns
Code: Select all
+-----+-----+-----+        +-----+-----+-----+
|x . .|. . .|. . .|        |. . x|. . .|. . .|
|x . .|. . .|. . .|        |. x .|. . .|. . .|
|x x x|. . .|. . .|        |x . .|. . .|. . .|
+-----+-----+-----+        +-----+-----+-----+
|x x x|x x x|x x x|        |x x x|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+
|x x x|x x x|x x x|        |x x x|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+

are maximal exclusive, because they have no valid puzzles and cannot be extended by adding filled cells in the B1 box (we must consider B1 filled cells additions only because we must consider patterns beloning to the given class only). Maximal exclusive patterns are irreducible to each other by sequential adding (subtracting) filled cells. So, knowing of all maximal exclusive patterns for the given patterns class enable us to formulate the rule for separation patterns having or not having valid puzzles in the simplest way:

There exist only 2 maximal exclusive patterns for the class of patterns having 2 whole filled bands and having 2 empty boxes in the rest (third) band (both patterns are posted above - "L-shape" and "minidiagonal" patterns). Each pattern having 2 whole filled bands and having 2 empty boxes in the rest band has no valid puzzles if it can be reduced to maximal exclusive patterns subset by rows/columns permutations in the B1 box. If it cannot be reduced to maximal exclusive patterns subset, it has valid puzzles.

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-band-free patterns

Postby ronk » Wed Feb 09, 2011 12:38 am

Serg wrote:To explain my words I have to introduce "maximal exclusive pattern" term.
Pattern is exclusive if it has no valid puzzles. If we consider another pattern which is subset of the given exclusive pattern, we can be sure this puzzle has no valid puzzles. So, exclusive pattern excludes patterns being its subsets from set of patterns having valid puzzles. I think, it would be very useful for sudoku designers to know "exclusive patterns catalogue" to check if their self-designed patterns have valid puzzles.

The passage of time has not lessened the inappropriateness of the exclusive term IMO.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Investigation of one-band-free patterns

Postby Serg » Wed Feb 09, 2011 8:06 am

Hi, ronk!
ronk wrote:
Serg wrote:To explain my words I have to introduce "maximal exclusive pattern" term.
Pattern is exclusive if it has no valid puzzles. If we consider another pattern which is subset of the given exclusive pattern, we can be sure this puzzle has no valid puzzles. So, exclusive pattern excludes patterns being its subsets from set of patterns having valid puzzles. I think, it would be very useful for sudoku designers to know "exclusive patterns catalogue" to check if their self-designed patterns have valid puzzles.

The passage of time has not lessened the inappropriateness of the exclusive term IMO.

Maybe the term "exclusive" is not good. But in what way can I show that a pattern has no valid puzzles? Should I write every time "pattern having no valid puzzles"? What can you advise?

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-band-free patterns

Postby RW » Wed Feb 09, 2011 10:39 am

Regardless of terminology, I kind of like your idea of maximal exclusive patterns. I wonder how small such patterns we could find for the full grid, patterns that cannot produce valid puzzles, but add any one cell to the pattern and it can produce valid puzzles. Sounds like a good challenge for the programmers around! :ugeek: A good place to start would probably the known patterns with full dihedral symmetry that cannot produce valid puzzles, they don't require the examination of that many new patterns with one clue added.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Re: Investigation of one-band-free patterns

Postby JPF » Wed Feb 09, 2011 10:45 am

May I suggest these definitions :

1. a pattern is valid if there exists at least one valid puzzle with this pattern.
a pattern that is not valid is said invalid.

If PT is invalid, every pattern PT' included in PT is invalid.

2. an invalid pattern PT is maximal if there exist {x} such that PT + {x} is a valid pattern.

This pattern is invalid maximal :
Code: Select all
+-----+-----+-----+ 
|x . .|. . .|. . .| 
|x . .|. . .|. . .| 
|x x x|. . .|. . .| 
+-----+-----+-----+ 
|x x x|x x x|x x x| 
|x x x|x x x|x x x| 
|x x x|x x x|x x x| 
+-----+-----+-----+ 
|x x x|x x x|x x x| 
|x x x|x x x|x x x| 
|x x x|x x x|x x x| 
+-----+-----+-----+ 


This pattern is invalid not maximal :
Code: Select all
+-----+-----+-----+ 
|. . .|. . .|. . .| 
|. . .|. . .|. . .| 
|. . .|. . .|. . .| 
+-----+-----+-----+ 
|x x x|x x x|x x x| 
|x x x|x x x|x x x| 
|x x x|x x x|x x x| 
+-----+-----+-----+ 
|x x x|x x x|x x x| 
|x x x|x x x|x x x| 
|x x x|x x x|x x x| 
+-----+-----+-----+ 

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Re: Investigation of one-band-free patterns

Postby dobrichev » Wed Feb 09, 2011 10:59 am

JPF wrote:2. an invalid pattern PT is maximal if there exist {x} such that PT + {x} is a valid pattern.

What is "{x}" and " + {x}" ?
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: Investigation of one-band-free patterns

Postby JPF » Wed Feb 09, 2011 11:15 am

OK
{x} is a pattern with one clue, such as :
Code: Select all
+-----+-----+-----+
|. . .|. x .|. . .|
|. . .|. . .|. . .|
|. . .|. . .|. . .|
+-----+-----+-----+
|. . .|. . .|. . .|
|. . .|. . .|. . .|
|. . .|. . .|. . .|
+-----+-----+-----+
|. . .|. . .|. . .|
|. . .|. . .|. . .|
|. . .|. . .|. . .|
+-----+-----+-----+

and for 2 patterns PT1 and PT2 :
PT1 + PT2 = PT1 U PT2

so, if PT1 is
Code: Select all
+-----+-----+-----+
|. . .|. . .|. . .|
|. . .|. . .|. . .|
|. . .|. . .|. . .|
+-----+-----+-----+
|x x x|x x x|x x x|
|x x x|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+
|x x x|x x x|x x x|
|x x x|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+

and PT2={x} the one-clue pattern given above

then PT1+PT2 is
Code: Select all
+-----+-----+-----+
|. . .|. x .|. . .|
|. . .|. . .|. . .|
|. . .|. . .|. . .|
+-----+-----+-----+
|x x x|x x x|x x x|
|x x x|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+
|x x x|x x x|x x x|
|x x x|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Re: Investigation of one-band-free patterns

Postby dobrichev » Wed Feb 09, 2011 11:35 am

Thank you.
Of course PT + {x} != PT ;)
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Next

Return to General