brain

tamnd's digital brain — notes, problems, research

41447 notes

TAOCP 7.2.2.1 Exercise 428

A Masyu loop is a closed curve through cell centers.

taocpmathematicsalgorithmsvolume-4math-hard
TAOCP 7.2.2.1 Exercise 427

I cannot produce a correct worked solution for Exercise 7.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 426

The exercise refers to a concrete diagram, namely diagram (i), whose initial arrangement of white clues must be modified.

taocpmathematicsalgorithmsvolume-4project
TAOCP 7.2.2.1 Exercise 425

The supplied section gives the general Dancing Links machinery, but it does not contain the definitions of the five solution-tile symbols, the example $3\times3$ solution diagram, or the precise graph...

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 424

Let the cells of the $6 \times 6$ board be denoted by C=\{(i,j):0\leq i,j<6\}.

taocpmathematicsalgorithmsvolume-4project
TAOCP 7.2.2.1 Exercise 423

The construction in exercise 422 uses one Boolean variable $x_e$ for every potential edge $e$.

taocpmathematicsalgorithmsvolume-4math-medium
TAOCP 7.2.2.1 Exercise 422

Let the cells of the Masyu puzzle be the vertices of the graph $G$ whose edges join orthogonally adjacent cells.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 421

Denote a cell by its two coordinates, as in the statement.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 420

Let the cells be indexed by $(i,j)$, with $0\le i<m$ and $0\le j<n$.

taocpmathematicsalgorithmsvolume-4math-medium
TAOCP 7.2.2.1 Exercise 42

The counting algorithm of exercise 40 loses information because each database entry $(s_j,c_j)$ stores only the number of ways to obtain the set $s_j$.

taocpmathematicsalgorithmsvolume-4math-medium
TAOCP 7.2.2.1 Exercise 419

The displayed array is not merely a matter of omitted blank cells.

taocpmathematicsalgorithmsvolume-4hard
TAOCP 7.2.2.1 Exercise 418

I cannot produce a correct completed solution for parts (b)–(e) without carrying out the required exhaustive enumeration or having the enumeration output.

taocpmathematicsalgorithmsvolume-4math-hard
TAOCP 7.2.2.1 Exercise 417

Exercise 7.

taocpmathematicsalgorithmsvolume-4math-research
TAOCP 7.2.2.1 Exercise 416

A complete answer would need, at minimum: 1.

taocpmathematicsalgorithmsvolume-4math-hard
TAOCP 7.2.2.1 Exercise 415

I cannot produce a correct completed solution to this exercise from the information available here, because the required numerical enumeration results are not contained in the exercise statement or re...

taocpmathematicsalgorithmsvolume-4math-hard
TAOCP 7.2.2.1 Exercise 414

The flaw in the previous argument was that it treated the missing diagram as an obstacle instead of analyzing the counterexample.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 413

In the construction of exercise 412, the vertices of the slitherlink grid are represented by items that enforce the local degree condition.

taocpmathematicsalgorithmsvolume-4hard
TAOCP 7.2.2.1 Exercise 412

Edit Use the coordinate convention suggested by the hint.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 411

Edit The statement is false.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 410

Let the $5\times5$ diagram mean the usual slitherlink board with $5\times5$ vertices, hence $4\times4$ cells.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 41

The corrected solution below replaces the unsupported pruning argument with the actual state-merging algorithm required by the exercise, gives an implementation outline, and describes a reproducible c...

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 409

We interpret the first $20$ digits of $\pi$ as ten two-digit clue values.

taocpmathematicsalgorithmsvolume-4hard
TAOCP 7.2.2.1 Exercise 408

Working

taocpmathematicsalgorithmsvolume-4hard
TAOCP 7.2.2.1 Exercise 407

The statement of the exercise as provided is incomplete.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 406

The first step is to notice that the statement as printed cannot be correct.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 405

Let the graph be $G=(V,E)$, and let $v\in V$ be the specified starting vertex.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 404

A hidato solution is a Hamiltonian path of king moves on the $m \times n$ board.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 403

Working

taocpmathematicsalgorithmsvolume-4hard
TAOCP 7.2.2.1 Exercise 402

The exercise refers to a $12\times12$ KenKen puzzle whose cage layout is given in a figure.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 401

Working

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 400

The statement of Exercise 7.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 40

Edit Let the database after rows (1,\ldots,k-1) have been processed contain entries [ (s_j,c_j).

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 399

Algorithm C can be applied after converting the KenKen puzzle into an exact cover problem.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 398

I can write the complete solution, but the data needed to solve it is missing: Figure 398, which defines the three KenKen puzzles (a), (b), and (c), is not included in the prompt.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 397

Let the grid cells be indexed by $(r,c)$, where $1\le r,c\le n$.

taocpmathematicsalgorithmsvolume-4hard
TAOCP 7.2.2.1 Exercise 396

A $9\times9$ futoshiki solution is a Latin square on the symbols ${1,2,\ldots,9}$, together with the required strong and weak clues.

taocpmathematicsalgorithmsvolume-4hard
TAOCP 7.2.2.1 Exercise 395

Consider the Latin square L= \begin{pmatrix} 1&3&2&5&4\\ 4&1&3&2&5\\

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 394

Working

taocpmathematicsalgorithmsvolume-4hard
TAOCP 7.2.2.1 Exercise 393

A complete correction requires an exhaustive enumeration.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 392

I cannot produce a mathematically valid corrected solution with the requested numerical table and examples from the information available here.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 391

The corrected solution is given below.

taocpmathematicsalgorithmsvolume-4hard
TAOCP 7.2.2.1 Exercise 390

Edit Let the entries of an (n\times n) futoshiki puzzle be (x_{r,c}), where [ 1\le r,c\le n,\qquad x_{r,c}\in{1,\ldots,n}.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 39

Let $m$ be the number of options and let $n$ be the number of items.

taocpmathematicsalgorithmsvolume-4math-medium
TAOCP 7.2.2.1 Exercise 389

Let the entries of an $n\times n$ futoshiki puzzle be denoted by $x_{r,c}$, with every entry satisfying $1\le x_{r,c}\le n.$ Each row and column contains each of the values $1,\ldots,n$ exactly once.

taocpmathematicsalgorithmsvolume-4hard
TAOCP 7.2.2.1 Exercise 388

The three futoshiki instances in Figure 388 are required in order to produce the worked solutions.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 387

A polycube has a symmetry group consisting of those rotations of space that preserve the set of cubes.

taocpmathematicsalgorithmsvolume-4math-hard
TAOCP 7.2.2.1 Exercise 386

A symmetry of a polyiamond or a polyhex is an element of the symmetry group of the triangular lattice or hexagonal lattice.

taocpmathematicsalgorithmsvolume-4math-hard
TAOCP 7.2.2.1 Exercise 385

The statement is not presently proved.

taocpmathematicsalgorithmsvolume-4math-project
TAOCP 7.2.2.1 Exercise 384

The corrected solution must include both the exact-cover construction and the actual enumeration for the case $l=m=n=7$.

taocpmathematicsalgorithmsvolume-4hard
TAOCP 7.2.2.1 Exercise 383

A complete solution to Exercise 7.

taocpmathematicsalgorithmsvolume-4hard
TAOCP 7.2.2.1 Exercise 382

The construction cannot be recovered from the information supplied in the exercise statement alone.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 381

Place coordinates on the $12 \times n$ rectangle, with rows numbered $1,2,\ldots,12$ and columns numbered $1,2,\ldots,n$.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 380

Edit Let (Y) denote the pentomino consisting of a column of four cells with one additional cell attached to the second cell of the column.

taocpmathematicsalgorithmsvolume-4hard
TAOCP 7.2.2.1 Exercise 38

Let $g_n$ denote the lexicographically smallest solution of the $\infty$ queens problem.

taocpmathematicsalgorithmsvolume-4math-medium
TAOCP 7.2.2.1 Exercise 379

The empty submission gives no information, so the solution must begin by determining the finite basis of packable rectangles for the $Q$-pentomino.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 378

Edit Let a rectangular shape be denoted by $h\times w$, where $h,w\in\mathbb N$.

taocpmathematicsalgorithmsvolume-4math-hard
TAOCP 7.2.2.1 Exercise 377

A rectangle $h\times w$ will always mean a rectangle with positive integer side lengths.

taocpmathematicsalgorithmsvolume-4math-hard
TAOCP 7.2.2.1 Exercise 376

\textbf{Solution.

taocpmathematicsalgorithmsvolume-4math-medium
TAOCP 7.2.2.1 Exercise 375

A complete corrected solution cannot be written from the information supplied in the prompt.

taocpmathematicsalgorithmsvolume-4math-hard
TAOCP 7.2.2.1 Exercise 374

Edit Let the rectangles of an incomparable dissection be (R_i), with dimensions (h_i\times w_i).

taocpmathematicsalgorithmsvolume-4math-hard
TAOCP 7.2.2.1 Exercise 373

Understood.

taocpmathematicsalgorithmsvolume-4hard
TAOCP 7.2.2.1 Exercise 372

Edit Let (r \ge r') denote reachability through a chain of horizontal walls, with each step going from a room to the room immediately below it.

taocpmathematicsalgorithmsvolume-4math-hard
TAOCP 7.2.2.1 Exercise 371

R=[a\ldots b)\times[c\ldots d) denotes a rectangle whose horizontal interval is $[a\ldots b)$ and whose vertical interval is $[c\ldots d)$.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 370

Please provide the proposed solution and the reviewer feedback (paste the text or upload the files).

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 37

Let $\langle g_n\rangle$ denote the lexicographically smallest solution to the $\infty$ queens problem.

taocpmathematicsalgorithmsvolume-4math-research
TAOCP 7.2.2.1 Exercise 369

The data supplied do not contain enough information to produce a valid complete solution with the numerical maxima.

taocpmathematicsalgorithmsvolume-4hard
TAOCP 7.2.2.1 Exercise 368

Let the $m\times n$ rectangle be divided into $t$ subrectangles.

taocpmathematicsalgorithmsvolume-4math-medium
TAOCP 7.2.2.1 Exercise 367

Let a motley dissection of an $m\times n$ rectangle be represented by the closed coordinate intervals of its subrectangles.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 366

Edit Let the construction of Exercise 363 be regarded as a rooted search tree.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 363

A decomposition of an $m \times n$ rectangle into grid-aligned subrectangles can be represented as an exact cover problem.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 361

Edit The minimum number of subrectangles in a reduced (m\times n) pattern is [ \boxed{m+n-1}.

taocpmathematicsalgorithmsvolume-4math-medium
TAOCP 7.2.2.1 Exercise 360

Let the coordinates of the reduced $m \times n$ rectangle be 0,1,\ldots,m in the vertical direction and

taocpmathematicsalgorithmsvolume-4hard
TAOCP 7.2.2.1 Exercise 36

Let $z_k=\operatorname{TOP}(x_k)$ denote the item chosen at level $k$ of Algorithm X.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 358

Represent the centers of the spheres by coordinates in the hexagonal stacking, using two-dimensional triangular coordinates inside each layer and a layer index.

taocpmathematicsalgorithmsvolume-4hm-simple
TAOCP 7.2.2.1 Exercise 357

A truncated octahedron has $6$ square faces and $8$ hexagonal faces, so a polysplatt is determined by a connected set of cells in the truncated-octahedral honeycomb.

taocpmathematicsalgorithmsvolume-4math-immediate
TAOCP 7.2.2.1 Exercise 356

Please provide the proposed solution and the reviewer feedback (paste the text or upload the files).

taocpmathematicsalgorithmsvolume-4hard
TAOCP 7.2.2.1 Exercise 355

Solution to TAOCP 7.2.2.1 Exercise 355.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 354

I can write the requested rigorous solution, but the exercise is long and has several parts requiring derivations of specific matrices and proofs of the symmetry group statement.

taocpmathematicsalgorithmsvolume-4math-hard
TAOCP 7.2.2.1 Exercise 353

Corrected solution: Edit A weak polycube of size (3) is a connected set of three unit cubes whose centers are lattice points in (\mathbb Z^3).

taocpmathematicsalgorithmsvolume-4project
TAOCP 7.2.2.1 Exercise 352

Each pentomino is regarded as a flat $5$-cell polycube embedded in the $2 \times 2 \times 3 \times 5$ hyperbox.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 350

The proposed slab argument is a valid reduction, but the rectangle packing used in the previous solution is not.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 35

A mathematically correct solution cannot be written from the information provided because the exercise statement is incomplete.

taocpmathematicsalgorithmsvolume-4math-medium
TAOCP 7.2.2.1 Exercise 349

Let s=a+b+c, and consider the cube

taocpmathematicsalgorithmsvolume-4math-hard
TAOCP 7.2.2.1 Exercise 348

The reviewer’s principal objection is based on a misinterpretation of the exercise.

taocpmathematicsalgorithmsvolume-4math-project
TAOCP 7.2.2.1 Exercise 347

Let the cells of the $l \times m \times n$ box have coordinates $(x,y,z)$, where $0\le x<l,\qquad 0\le y<m,\qquad 0\le z<n.$ Let $\omega$ be a primitive $k$th root of unity.

taocpmathematicsalgorithmsvolume-4math-medium
TAOCP 7.2.2.1 Exercise 346

A fully corrected solution cannot be produced reliably from the information available in the prompt alone.

taocpmathematicsalgorithmsvolume-4math-hard
TAOCP 7.2.2.1 Exercise 345

The corrected solution is: Edit The supplied statement does not contain the defining data needed to determine the U-shaped dodecacube or the meaning of a forbidden cross.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 344

\textbf{Solution.

taocpmathematicsalgorithmsvolume-4simple
TAOCP 7.2.2.1 Exercise 343

Solution to TAOCP 7.2.2.1 Exercise 343.

taocpmathematicsalgorithmsvolume-4simple
TAOCP 7.2.2.1 Exercise 342

Solution to TAOCP 7.2.2.1 Exercise 342.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 341

A complete solution to this exercise must exhibit actual packings.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 340

\textbf{Solution.

taocpmathematicsalgorithmsvolume-4hard
TAOCP 7.2.2.1 Exercise 34

\textbf{Construction.

taocpmathematicsalgorithmsvolume-4math-medium
TAOCP 7.2.2.1 Exercise 339

Let $O$ be a free octomino, and let $P(O)$ be the $4$-level prism obtained by stacking four copies of $O$.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 338

The statement refers to six target shapes shown in Figure 338, but the figure itself is not included in the supplied material.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 337

Use coordinates $(x,y,z)$ for the unit cubes of the large cube, where $0\le x,y,z<3$.

taocpmathematicsalgorithmsvolume-4hard
TAOCP 7.2.2.1 Exercise 336

The statement supplied for exercise 336 is incomplete because the defining figure for the L-bert Hall piece is missing.

taocpmathematicsalgorithmsvolume-4medium
TAOCP 7.2.2.1 Exercise 335

I cannot produce a mathematically valid corrected solution from the information supplied.

taocpmathematicsalgorithmsvolume-4hard
TAOCP 7.2.2.1 Exercise 334

A complete solution to Exercise 7.

taocpmathematicsalgorithmsvolume-4math-hard
TAOCP 7.2.2.1 Exercise 333

The previous solution had the right mechanical idea but treated the crucial verifications as if they were already done.

taocpmathematicsalgorithmsvolume-4medium