22:
294:
177:
The easiest starting place is to find a "maximum cell"; that is, a numbered cell which if the walls are not at the maximum distance possible, the number is not satisfied. For example, in a 10x10 grid which has not started to be solved, a 19-cell is a maximum cell, since if the four walls are not at
168:
The object is to draw a single, continuous loop along the lines of the grid that contains all the numbers on the grid. Each number indicates the total number of cells visible in any orthogonal direction before a line of the loop is reached, plus the cell itself. For example, a 2-cell will have one
119:
127:
178:
the edges of the grid, the number of cells visible wouldn't be enough. After making some progress, "minimum cells" appear, where if the walls are not at the minimum distance possible, the number is not satisfied.
185:, as the rules are also very similar. The most notable difference is the use of the loop as a part of the solution, as opposed to shaded cells.
239:
335:
105:
43:
364:
39:
86:
276:
58:
213:
65:
32:
359:
328:
165:
Bag is played on a rectangular grid, usually of dashed lines, in which numbers appear in some of the cells.
72:
354:
218:
54:
369:
321:
154:
243:
305:
193:
Decision question (Friedman, 2002): Does a given instance of Corral Puzzle have a solution?
197:
79:
201:
348:
150:
118:
126:
21:
282:
268:
182:
293:
181:
Many of the solution methods for Bag are very similar to those used for
301:
15:
204:, which is known to be NP-complete, to a Corral Puzzle.
309:
200:. This is proven by reducing the decision problem of
169:
cell adjacent to it, followed by a wall of the loop.
46:. Unsourced material may be challenged and removed.
329:
283:Informative page on Corral, mostly in German.
279:- describes some helpful solution strategies.
202:deciding the 3-colorability of a planar graph
8:
336:
322:
106:Learn how and when to remove this message
125:
117:
230:
7:
290:
288:
44:adding citations to reliable sources
308:. You can help Knowledge (XXG) by
14:
292:
240:"Corral Puzzles are NP-complete"
20:
31:needs additional citations for
1:
149:) is a binary-determination
214:List of Nikoli puzzle types
386:
287:
269:Nikoli's Japanese page on
196:This decision question is
189:Computational complexity
130:The same puzzle, solved
304:-related article is a
219:Category:Logic puzzles
131:
123:
122:An unsolved Bag puzzle
129:
121:
365:NP-complete problems
277:Better Know a Corral
40:improve this article
132:
124:
317:
316:
238:Friedman, Erich.
116:
115:
108:
90:
55:"Bag" puzzle
377:
338:
331:
324:
296:
289:
256:
255:
253:
251:
242:. Archived from
235:
173:Solution methods
111:
104:
100:
97:
91:
89:
48:
24:
16:
385:
384:
380:
379:
378:
376:
375:
374:
345:
344:
343:
342:
265:
260:
259:
249:
247:
246:on 13 June 2012
237:
236:
232:
227:
210:
191:
175:
163:
112:
101:
95:
92:
49:
47:
37:
25:
12:
11:
5:
383:
381:
373:
372:
367:
362:
360:Japanese games
357:
347:
346:
341:
340:
333:
326:
318:
315:
314:
297:
286:
285:
280:
274:
264:
263:External links
261:
258:
257:
229:
228:
226:
223:
222:
221:
216:
209:
206:
190:
187:
174:
171:
162:
159:
114:
113:
96:September 2012
28:
26:
19:
13:
10:
9:
6:
4:
3:
2:
382:
371:
368:
366:
363:
361:
358:
356:
355:Logic puzzles
353:
352:
350:
339:
334:
332:
327:
325:
320:
319:
313:
311:
307:
303:
298:
295:
291:
284:
281:
278:
275:
273:
272:
267:
266:
262:
245:
241:
234:
231:
224:
220:
217:
215:
212:
211:
207:
205:
203:
199:
194:
188:
186:
184:
179:
172:
170:
166:
160:
158:
156:
153:published by
152:
148:
147:
142:
141:
137:(also called
136:
128:
120:
110:
107:
99:
88:
85:
81:
78:
74:
71:
67:
64:
60:
57: –
56:
52:
51:Find sources:
45:
41:
35:
34:
29:This article
27:
23:
18:
17:
310:expanding it
299:
270:
248:. Retrieved
244:the original
233:
195:
192:
180:
176:
167:
164:
151:logic puzzle
145:
144:
139:
138:
134:
133:
102:
93:
83:
76:
69:
62:
50:
38:Please help
33:verification
30:
198:NP-complete
370:Game stubs
349:Categories
225:References
66:newspapers
208:See also
183:Kuromasu
250:10 July
80:scholar
155:Nikoli
140:Corral
82:
75:
68:
61:
53:
300:This
161:Rules
87:JSTOR
73:books
306:stub
302:game
252:2016
146:Cave
59:news
271:Bag
143:or
135:Bag
42:by
351::
157:.
337:e
330:t
323:v
312:.
254:.
109:)
103:(
98:)
94:(
84:·
77:·
70:·
63:·
36:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
