Swapping rooks in a 4x4 board - Puzzling Stack Exchange most recent 30 from puzzling.stackexchange.com 2019-08-25T16:28:46Z https://puzzling.stackexchange.com/feeds/question/85281 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://puzzling.stackexchange.com/q/85281 29 Swapping rooks in a 4x4 board Chaotic https://puzzling.stackexchange.com/users/19446 2019-06-19T21:52:51Z 2019-06-25T08:24:06Z <p>You have a 4x4 chessboard with four black rooks on the top and four white rooks in the bottom. </p> <p><strong>Your goal is to swap these rooks using the minimum number of steps.</strong> It does not matter which rook is which, as long as there are four white rooks on the top and four black rooks in the bottom.</p> <p><a href="https://i.stack.imgur.com/t2h5o.png" rel="noreferrer"><img src="https://i.stack.imgur.com/t2h5o.png" alt="enter image description here"></a></p> <p>Chess rules apply: rooks can move any number of squares, horizontally (left and right) or vertically (up and down), as long as there is not another piece on the way. White starts. You must alternate black and white moves.</p> https://puzzling.stackexchange.com/questions/85281/swapping-rooks-in-a-4x4-board/85282#85282 4 Answer by Ted for Swapping rooks in a 4x4 board Ted https://puzzling.stackexchange.com/users/57154 2019-06-19T22:05:23Z 2019-06-19T22:05:23Z <p>Found a solution in 20, though I have no idea if it's optimal. One of my assumptions was that "Chess rules apply" meant I had to alternate black and white moves.</p> https://puzzling.stackexchange.com/questions/85281/swapping-rooks-in-a-4x4-board/85285#85285 4 Answer by SteveV for Swapping rooks in a 4x4 board SteveV https://puzzling.stackexchange.com/users/51984 2019-06-19T22:14:16Z 2019-06-19T22:14:16Z <p>Found a 19 move solution, but no idea about optimum.</p> <p>Where the columns are a, b, c, d and rows are 1, 2, 3, 4, starting from bottom left.</p> https://puzzling.stackexchange.com/questions/85281/swapping-rooks-in-a-4x4-board/85286#85286 9 Answer by shoopi for Swapping rooks in a 4x4 board shoopi https://puzzling.stackexchange.com/users/21766 2019-06-20T00:12:18Z 2019-06-20T00:24:46Z <p>Got 19 by moving around... might be possible to do better:</p> https://puzzling.stackexchange.com/questions/85281/swapping-rooks-in-a-4x4-board/85288#85288 1 Answer by Rewan Demontay for Swapping rooks in a 4x4 board Rewan Demontay https://puzzling.stackexchange.com/users/57521 2019-06-20T01:29:29Z 2019-06-20T04:59:26Z <p>EDIT: As @greenturtle pointed out in a comment, it seems that everyone else is doing the count by ply, and not the whole moves. The question is unclear to me about this on how the count is done. So thus my count is wrong by the majority's decision.</p> <p>As such, just for fun, here is a symmetrical solution of 20 moves that uses the same notations as my below answer.</p> <p>I found a solution in 12 moves. Here is a link to a GIF using <a href="https://www.apronus.com/chess/diagram/animated/?de=120&amp;a=8H8H8H8H4rrrrH8H8H4RRRR_8H8H8H8H4rrrrH6R1H8H4RR1R_8H8H8H8H4rrr1H6R1H7rH4RR1R_8H8H8H8H4rrr1H7RH7rH4RR1R_8H8H8H8H4rrr1H7RH6r1H4RR1R_8H8H8H8H4rrrRH8H6r1H4RR1R_8H8H8H8H4rrrRH8H8H4RRrR_8H8H8H8H4rrrRH7RH8H4RRr1_8H8H8H8H4rr1RH7RH6r1H4RRr1_8H8H8H8H4rr1RH6R1H6r1H4RRr1_8H8H8H8H4rr1RH6R1H7rH4RRr1_8H8H8H8H4rrRRH8H7rH4RRr1_8H8H8H8H4rrRRH8H8H4RRrr_8H8H8H8H4rrRRH4R3H8H5Rrr_8H8H8H8H4r1RRH4R3H5r2H5Rrr_8H8H8H8H4r1RRH5R2H5r2H5Rrr_8H8H8H8H4r1RRH5R2H4r3H5Rrr_8H8H8H8H4rRRRH8H4r3H5Rrr_8H8H8H8H4rRRRH8H8H4rRrr_8H8H8H8H4rRRRH5R2H8H4r1rr_8H8H8H8H5RRRH5R2H4r3H4r1rr_8H8H8H8H5RRRH4R3H4r3H4r1rr_8H8H8H8H5RRRH4R3H5r2H4r1rr_8H8H8H8H4RRRRH8H5r2H4r1rr_8H8H8H8H4RRRRH8H8H4rrrr&amp;d=A____rrrr____________________RRRR________________________________0&amp;w=8&amp;h=8&amp;f=&amp;l=%3FpEA____RRRR____________________rrrr________________________________0MmERg3_Rh2_Rh3_Rhg2_Rh4_Rg1_R1h3_R4g2_Rg3_Rh2_Rgg4_Rhh1_Re3_Rf2_Rf3_Rfe2_Rff4_Re1_R1f3_R4e2_Re3_Rf2_Ree4_Rff1" rel="nofollow noreferrer">Apronus.</a> I'm using an 8 x 8 board for convenience in the gif, but I'm treating it as 4 x 4.</p> <p>The following notation for my solution assumes that the files used are e through h and the ranks are 1 through 4, with the board being as it is from White's view on a normal chess board.</p> <p>My Solution:</p> <p>I'm fairly sure that this is optimal due to how each rook moves a minimum of three times.</p> https://puzzling.stackexchange.com/questions/85281/swapping-rooks-in-a-4x4-board/85293#85293 35 Answer by Jaap Scherphuis for Swapping rooks in a 4x4 board Jaap Scherphuis https://puzzling.stackexchange.com/users/20814 2019-06-20T08:39:50Z 2019-06-20T13:10:36Z <p>I wrote a computer program and it showed that <span class="math-container">$18$</span> moves is the optimum.</p> <p>Here is one such solution:</p> <p>Oddly enough, even if you relax the condition of alternating white and black moves, it cannot be done in fewer moves.</p> <p>For <span class="math-container">$3\times3$</span> the optimal number of moves is <span class="math-container">$16$</span>.</p> <p>Without the need to alternate moves the optimum is <span class="math-container">$14$</span> moves, for example just by doing the above solution excluding white's last two moves.</p> <p>Here is the C# source code that I wrote.</p> <pre><code>using System; using System.Collections.Generic; namespace test { class Rooks { static void Main() { Calc(true,4); } static void Calc(bool alternateMoves, int n ) { int[] dirs = {0, 1, 0, -1, 1, 0, -1, 0}; List&lt;String&gt; list = new List&lt;String&gt;(); Dictionary&lt;String, String&gt; dict = new Dictionary&lt;String, String&gt;(); string start = new string('b', n) + new string('.', n * (n - 2)) + new string('w', n); if (alternateMoves) start += '0'; string goal = new string('w', n) + new string('.', n * (n - 2)) + new string('b', n); list.Add(start); dict.Add(start, ""); int n1 = list.Count; int n2 = 0; int len = 0; while (list.Count &gt; 0) { String p = list; list.RemoveAt(0); n1--; String gen = dict[p]; char player = alternateMoves ? (p[n * n] == '0' ? 'w' : 'b') : '.'; for (int y = 0; y &lt; n; y++) { for (int x = 0; x &lt; n; x++) { if (!alternateMoves ^ p[y * n + x] == player) { for (int d = 0; d &lt; 4; d++) { int dx = dirs[d + d]; int dy = dirs[d + d + 1]; int x2 = x; int y2 = y; while (true) { x2 += dx; y2 += dy; if (y2 &lt; 0 || x2 &lt; 0 || y2 &gt;= n || x2 &gt;= n || p[y2 * n + x2] != '.') break; string q = SwapPieces(p, y * n + x, y2 * n + x2); if(alternateMoves) q = q.Substring(0, n * n) + (char) (q[n * n] ^ 1); if (!dict.ContainsKey(q)) { list.Add(q); string gen2 = gen + " " + (char)('A' + x) + (char)('1' + y) + (char)('A' + x2) + (char)('1' + y2); dict.Add(q, gen2); if (q.StartsWith(goal)) { Console.WriteLine(q + " " + gen2); } n2++; } } } } } } if (n1 == 0) { len++; Console.WriteLine("{0}: {1}",len,n2); n1 = n2; n2 = 0; } } } static String SwapPieces(String input, int i1, int i2) { if (i1 &gt; i2) return SwapPieces(input, i2, i1); return input.Substring(0, i1) + input.Substring(i2, 1) + input.Substring(i1 + 1, i2 - i1 - 1) + input.Substring(i1, 1) + input.Substring(i2 + 1); } } } </code></pre> https://puzzling.stackexchange.com/questions/85281/swapping-rooks-in-a-4x4-board/85484#85484 4 Answer by vysar for Swapping rooks in a 4x4 board vysar https://puzzling.stackexchange.com/users/61091 2019-06-25T08:24:06Z 2019-06-25T08:24:06Z <p>This is not a (new) answer to the original question, but I don't have enough reputation to comment. I tried to address the call for generalization using a similar technique as Jaap. Below the results for the board sizes that fit in my main memory. Unfortunately, 6 x 6 does not fit.</p> <pre><code>size # configs w b ========================= 3 x 2 180 12 13 3 x 3 3360 16 17 3 x 4 69300 20 19 3 x 5 1513512 24 23 3 x 6 34306272 26 27 3 x 7 798145920 30 31 4 x 2 840 10 11 4 x 3 36960 14 15 4 x 4 1801800 18 19 4 x 5 93117024 22 23 4 x 6 4997280288 26 27 5 x 2 2520 10 11 5 x 3 200200 14 13 5 x 4 17635800 18 17 5 x 5 1647455040 22 21 6 x 2 5940 10 11 6 x 3 742560 14 13 6 x 4 102965940 18 17 7 x 2 12012 10 11 7 x 3 2170560 14 13 7 x 4 435134700 18 17 8 x 2 21840 10 11 8 x 3 5383840 14 13 8 x 4 1472562000 18 17 </code></pre> <p>The last two columns give the minimal number of steps (ply) to the final position with either white (w) or black (b) to play.</p> <p>The number of configurations is given by: <span class="math-container">$2 \cdot {n \cdot m \choose m} \cdot {n \cdot m - m \choose m}$</span>, with <span class="math-container">$n$</span> the number of rows and <span class="math-container">$m$</span> the number of columns.</p>