Swapping rooks in a 4x4 boardRook game on chessboardThe Erasmus rook tourTwo rooks for Bobby FischerSwitch The KnightsFour free rooks for checkmateThe King's Routes Problem: How many possibilities?Interchanging Knights and RooksThe Minimized DropmateA Chess Lock Puzzle?Placing rooks on a chessboard
Bin Packing with Relational Penalization
Why was Mal so quick to drop Bester in favour of Kaylee?
Sharing referee/AE report online to point out a grievous error in refereeing
How to plan the font size in a fiction?
How to describe POV characters?
Adjective for 'made of pus' or 'corrupted by pus' or something of something of pus
13th chords on guitar
Is it okay to fade a human face just to create some space to place important content over it?
Who voices the character "Finger" in The Fifth Element?
Comment traduire « That screams X »
Are gliders susceptible to bird strikes?
Is it okay to submit a paper from a master's thesis without informing the advisor?
Is it possible to have a character with proficiency in all martial weapons without proficiency in Medium armor?
Can SOCPs approximate better than LPs?
How could a satellite follow earth around the sun while staying outside of earth's orbit?
Can you actually break an FPGA by programming it wrong?
I just started should I accept a farewell lunch for a coworker I don't know?
What's the safest way to inform a new user of their password on an invite-only website?
Are all commands with an optional argument fragile?
Security Patch SUPEE-11155 - Possible issues?
Why did NASA wet the road in front of the Space Shuttle crawler?
Is there a legal way for US presidents to extend their terms beyond two terms of four years?
"Vector quantity" --More than two dimensions?
If two black hole event horizons overlap (touch) can they ever separate again?
Swapping rooks in a 4x4 board
Rook game on chessboardThe Erasmus rook tourTwo rooks for Bobby FischerSwitch The KnightsFour free rooks for checkmateThe King's Routes Problem: How many possibilities?Interchanging Knights and RooksThe Minimized DropmateA Chess Lock Puzzle?Placing rooks on a chessboard
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;
$begingroup$
You have a 4x4 chessboard with four black rooks on the top and four white rooks in the bottom.
Your goal is to swap these rooks using the minimum number of steps. 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.
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.
chess optimization
asked Jun 19 at 21:52
ChaoticChaotic
7635 silver badges18 bronze badges
$endgroup$
|
show 4 more comments
$begingroup$
You have a 4x4 chessboard with four black rooks on the top and four white rooks in the bottom.
Your goal is to swap these rooks using the minimum number of steps. 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.
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.
chess optimization
asked Jun 19 at 21:52
ChaoticChaotic
7635 silver badges18 bronze badges
$endgroup$
4
$begingroup$
This is the type of question which might make a good secondary puzzle along the lines of "how many steps does it take to swap rooks on an nxn board"! (+1)
$endgroup$
– Adam
Jun 19 at 22:25
2
$begingroup$
Yes, I thought about that. In a 3x3 board I was able to do in 14 moves, but I'm not sure if it is the optimal solution. I also don't think it would be a good idea to open a new question for a 3x3, 5x5, 8x8, etc.
$endgroup$
– Chaotic
Jun 19 at 22:33
$begingroup$
Not necessarily, but the generalization is a worthy question to ask, though perhaps not by itself not that you've asked the instance for n = 4. Still, I do believe this should generalize quite nicely.
$endgroup$
– greenturtle3141
Jun 20 at 0:16
1
$begingroup$
I'm fairly sure that for a 3*3, 9 is optimal. Set up the rooks on the f-h files and ranks 1-3 and follow these moves: 1. Rh2 Rg2 2. Rgh3 Rg3 3. Rff2 Rhg1 4. Rh1 R1g2 5. Rg1 Rh2 6. Rfg2 Rff3 7. Rf2 Rhg2 8. Rhh1 Rh2 9. Rff1 Rhh3.
$endgroup$
– Rewan Demontay
Jun 20 at 1:52
4
$begingroup$
@Adam: the sequence R(n) of minimum rook moves R(n) for an n x n board swapping n rooks on top/bottom rows would make a great series in OEIS. I just checked and it doesn't exist.
$endgroup$
– smci
Jun 21 at 0:02
|
show 4 more comments
$begingroup$
You have a 4x4 chessboard with four black rooks on the top and four white rooks in the bottom.
Your goal is to swap these rooks using the minimum number of steps. 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.
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.
chess optimization
asked Jun 19 at 21:52
ChaoticChaotic
7635 silver badges18 bronze badges
$endgroup$
You have a 4x4 chessboard with four black rooks on the top and four white rooks in the bottom.
Your goal is to swap these rooks using the minimum number of steps. 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.
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.
chess optimization
chess optimization
asked Jun 19 at 21:52
ChaoticChaotic
7635 silver badges18 bronze badges
asked Jun 19 at 21:52
ChaoticChaotic
7635 silver badges18 bronze badges
edited Jun 19 at 22:07
Chaotic
asked Jun 19 at 21:52
ChaoticChaotic
7635 silver badges18 bronze badges
asked Jun 19 at 21:52
ChaoticChaotic
7635 silver badges18 bronze badges
asked Jun 19 at 21:52
ChaoticChaotic
7635 silver badges18 bronze badges
7635 silver badges18 bronze badges
4
$begingroup$
This is the type of question which might make a good secondary puzzle along the lines of "how many steps does it take to swap rooks on an nxn board"! (+1)
$endgroup$
– Adam
Jun 19 at 22:25
2
$begingroup$
Yes, I thought about that. In a 3x3 board I was able to do in 14 moves, but I'm not sure if it is the optimal solution. I also don't think it would be a good idea to open a new question for a 3x3, 5x5, 8x8, etc.
$endgroup$
– Chaotic
Jun 19 at 22:33
$begingroup$
Not necessarily, but the generalization is a worthy question to ask, though perhaps not by itself not that you've asked the instance for n = 4. Still, I do believe this should generalize quite nicely.
$endgroup$
– greenturtle3141
Jun 20 at 0:16
1
$begingroup$
I'm fairly sure that for a 3*3, 9 is optimal. Set up the rooks on the f-h files and ranks 1-3 and follow these moves: 1. Rh2 Rg2 2. Rgh3 Rg3 3. Rff2 Rhg1 4. Rh1 R1g2 5. Rg1 Rh2 6. Rfg2 Rff3 7. Rf2 Rhg2 8. Rhh1 Rh2 9. Rff1 Rhh3.
$endgroup$
– Rewan Demontay
Jun 20 at 1:52
4
$begingroup$
@Adam: the sequence R(n) of minimum rook moves R(n) for an n x n board swapping n rooks on top/bottom rows would make a great series in OEIS. I just checked and it doesn't exist.
$endgroup$
– smci
Jun 21 at 0:02
|
show 4 more comments
4
$begingroup$
This is the type of question which might make a good secondary puzzle along the lines of "how many steps does it take to swap rooks on an nxn board"! (+1)
$endgroup$
– Adam
Jun 19 at 22:25
2
$begingroup$
Yes, I thought about that. In a 3x3 board I was able to do in 14 moves, but I'm not sure if it is the optimal solution. I also don't think it would be a good idea to open a new question for a 3x3, 5x5, 8x8, etc.
$endgroup$
– Chaotic
Jun 19 at 22:33
$begingroup$
Not necessarily, but the generalization is a worthy question to ask, though perhaps not by itself not that you've asked the instance for n = 4. Still, I do believe this should generalize quite nicely.
$endgroup$
– greenturtle3141
Jun 20 at 0:16
1
$begingroup$
I'm fairly sure that for a 3*3, 9 is optimal. Set up the rooks on the f-h files and ranks 1-3 and follow these moves: 1. Rh2 Rg2 2. Rgh3 Rg3 3. Rff2 Rhg1 4. Rh1 R1g2 5. Rg1 Rh2 6. Rfg2 Rff3 7. Rf2 Rhg2 8. Rhh1 Rh2 9. Rff1 Rhh3.
$endgroup$
– Rewan Demontay
Jun 20 at 1:52
4
$begingroup$
@Adam: the sequence R(n) of minimum rook moves R(n) for an n x n board swapping n rooks on top/bottom rows would make a great series in OEIS. I just checked and it doesn't exist.
$endgroup$
– smci
Jun 21 at 0:02
4
4
$begingroup$
This is the type of question which might make a good secondary puzzle along the lines of "how many steps does it take to swap rooks on an nxn board"! (+1)
$endgroup$
– Adam
Jun 19 at 22:25
$begingroup$
This is the type of question which might make a good secondary puzzle along the lines of "how many steps does it take to swap rooks on an nxn board"! (+1)
$endgroup$
– Adam
Jun 19 at 22:25
2
2
$begingroup$
Yes, I thought about that. In a 3x3 board I was able to do in 14 moves, but I'm not sure if it is the optimal solution. I also don't think it would be a good idea to open a new question for a 3x3, 5x5, 8x8, etc.
$endgroup$
– Chaotic
Jun 19 at 22:33
$begingroup$
Yes, I thought about that. In a 3x3 board I was able to do in 14 moves, but I'm not sure if it is the optimal solution. I also don't think it would be a good idea to open a new question for a 3x3, 5x5, 8x8, etc.
$endgroup$
– Chaotic
Jun 19 at 22:33
$begingroup$
Not necessarily, but the generalization is a worthy question to ask, though perhaps not by itself not that you've asked the instance for n = 4. Still, I do believe this should generalize quite nicely.
$endgroup$
– greenturtle3141
Jun 20 at 0:16
$begingroup$
Not necessarily, but the generalization is a worthy question to ask, though perhaps not by itself not that you've asked the instance for n = 4. Still, I do believe this should generalize quite nicely.
$endgroup$
– greenturtle3141
Jun 20 at 0:16
1
1
$begingroup$
I'm fairly sure that for a 3*3, 9 is optimal. Set up the rooks on the f-h files and ranks 1-3 and follow these moves: 1. Rh2 Rg2 2. Rgh3 Rg3 3. Rff2 Rhg1 4. Rh1 R1g2 5. Rg1 Rh2 6. Rfg2 Rff3 7. Rf2 Rhg2 8. Rhh1 Rh2 9. Rff1 Rhh3.
$endgroup$
– Rewan Demontay
Jun 20 at 1:52
$begingroup$
I'm fairly sure that for a 3*3, 9 is optimal. Set up the rooks on the f-h files and ranks 1-3 and follow these moves: 1. Rh2 Rg2 2. Rgh3 Rg3 3. Rff2 Rhg1 4. Rh1 R1g2 5. Rg1 Rh2 6. Rfg2 Rff3 7. Rf2 Rhg2 8. Rhh1 Rh2 9. Rff1 Rhh3.
$endgroup$
– Rewan Demontay
Jun 20 at 1:52
4
4
$begingroup$
@Adam: the sequence R(n) of minimum rook moves R(n) for an n x n board swapping n rooks on top/bottom rows would make a great series in OEIS. I just checked and it doesn't exist.
$endgroup$
– smci
Jun 21 at 0:02
$begingroup$
@Adam: the sequence R(n) of minimum rook moves R(n) for an n x n board swapping n rooks on top/bottom rows would make a great series in OEIS. I just checked and it doesn't exist.
$endgroup$
– smci
Jun 21 at 0:02
|
show 4 more comments
6 Answers
6
active
oldest
votes
$begingroup$
I wrote a computer program and it showed that $18$ moves is the optimum.
Here is one such solution:
bbbb bbbb .bbb .bbb .bb. .bb.
.... .... b... bw.. bw.. b..w
.... w... w... w... w..b w..b
wwww .www .www ..ww ..ww ..ww
..b. ..bw .b.w .bww .bww .bww
b..w b... b... b... b... b...
w..b w..b w..b w..b w..b w..b
.bww .bww .bww .b.w b..w b.w.
..ww .w.w .w.w .www .www wwww wwww
b... b... b... b... ..b. ..b. ....
w..b w..b w... w... w... .... ....
bbw. bbw. bbwb bb.b bb.b bb.b bbbb
Oddly enough, even if you relax the condition of alternating white and black moves, it cannot be done in fewer moves.
For $3times3$ the optimal number of moves is $16$.
bbb bbb bb. bb. .b. .b. ... w..
... w.. w.b .wb .wb w.b wbb .bb
www .ww .ww .ww bww bww bww bww
w.. ww. ww. www www ww. ww. www www
b.b b.b bb. bb. bb. bbw b.w b.. ...
bww b.w b.w b.. ..b ..b .bb .bb bbb
Without the need to alternate moves the optimum is $14$ moves, for example just by doing the above solution excluding white's last two moves.
Here is the C# source code that I wrote.
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<String> list = new List<String>();
Dictionary<String, String> dict = new Dictionary<String, String>();
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 > 0)
String p = list[0];
list.RemoveAt(0);
n1--;
String gen = dict[p];
char player = alternateMoves ? (p[n * n] == '0' ? 'w' : 'b') : '.';
for (int y = 0; y < n; y++)
for (int x = 0; x < n; x++)
if (!alternateMoves ^ p[y * n + x] == player)
for (int d = 0; d < 4; d++)
int dx = dirs[d + d];
int dy = dirs[d + d + 1];
int x2 = x;
int y2 = y;
while (true)
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 > 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);
answered Jun 20 at 8:39
Jaap ScherphuisJaap Scherphuis
18.2k1 gold badge33 silver badges80 bronze badges
$endgroup$
$begingroup$
Clever! How did you write this program? Was there some logic or just brute force?
$endgroup$
– shoopi
Jun 20 at 10:10
$begingroup$
I'd be curious to the results for 3x3, 5x5, 6x6, etc. Is your program flexible enough to find the answers with little effort? I wonder if the answer appears in oeis.org
$endgroup$
– David Dubois
Jun 20 at 10:36
3
$begingroup$
My program was brute force, simply a breadth first search. There are fewer than a million possible positions (twice that if you include whose turn it is to move) so it can be done in memory. I have added the $3times3$ results to my answer. $5times5$ is theoretically feasible by the same method but my program would require a rewrite to be much more memory efficient. Larger boards need a very different method because the number of positions is too great.
$endgroup$
– Jaap Scherphuis
Jun 20 at 11:25
3
$begingroup$
@Kebabman I have added the C# source code to my answer.
$endgroup$
– Jaap Scherphuis
Jun 20 at 13:11
2
$begingroup$
@MikeTheLiar I know, and I think that is only possible if you allow consecutive moves to use the same colour pieces, and not possible if you strictly alternate the colours of the moved pieces.
$endgroup$
– Jaap Scherphuis
Jun 21 at 14:23
|
show 4 more comments
$begingroup$
Got 19 by moving around... might be possible to do better:
1) a1-a3
2) d4-d2
3) b1-b3
4) d2-a2
5) d1-d4
6) a2-a1
7) c1-d1
8) c4-c1
9) b3-c3
10) b4-b1
11) a3-b3
12) a4-a2
13) d4-a4
14) a2-c2
15) d1-d4
16) c2-d2
17) b3-b4
18) d2-d1
19) c3-c4
answered Jun 20 at 0:12
shoopishoopi
9665 silver badges15 bronze badges
$endgroup$
1
$begingroup$
Step 14 seems to be a pointless move. Just do step 15 first and then a2-d2.
$endgroup$
– James Coyle
Jun 20 at 11:19
1
$begingroup$
@JamesCoyle Step 14 is indeed a pointless move just to pass the turn. But I can't play move 15 (d1-d4) before I play move 13 (d4-a4) because the square is occupied. This is why I suspected a more optimal solution exists, as proven in Jaap's solution.
$endgroup$
– shoopi
Jun 20 at 11:55
2
$begingroup$
Ah I totally forgot about alternating moves...
$endgroup$
– James Coyle
Jun 20 at 12:02
add a comment |
$begingroup$
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.
answered Jun 19 at 22:05
TedTed
936 bronze badges
$endgroup$
$begingroup$
I have 2 that are different and 20 and I am not sure either.
$endgroup$
– Duck
Jun 19 at 22:06
$begingroup$
Thanks, I've added the clarification.
$endgroup$
– Chaotic
Jun 19 at 22:15
add a comment |
$begingroup$
Found a 19 move solution, but no idea about optimum.
a1-a3
a3-d3
b1-b2
b2-d2
a4-a1
b4-b1
c1-c2
c2-a2
a2-a4
c4-c1
d4-c4
c4-c3
d3-d4
d4-b4
d2-d4
d4-c4
d1-d4
c3-d3
d3-d1
Where the columns are a, b, c, d and rows are 1, 2, 3, 4, starting from bottom left.
answered Jun 19 at 22:14
SteveVSteveV
7,2482 gold badges6 silver badges36 bronze badges
$endgroup$
1
$begingroup$
OP made an edit - moves must alternate between White and Black.
$endgroup$
– shoopi
Jun 19 at 23:11
add a comment |
$begingroup$
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.
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
The last two columns give the minimal number of steps (ply) to the final position with either white (w) or black (b) to play.
The number of configurations is given by: $2 cdot n cdot m choose m cdot n cdot m - m choose m$, with $n$ the number of rows and $m$ the number of columns.
answered yesterday
vysarvysar
212 bronze badges
New contributor
vysar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
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.
As such, just for fun, here is a symmetrical solution of 20 moves that uses the same notations as my below answer.
$1.$ Rh2 Rg3 $2.$ Rff2 Ree3 $3.$ Re2 Rh3 $4.$ Rg1 Rf4 $5.$ Rhf2 Reg3 $6.$ Rff1 Rgg4 $7.$ Ree1 Rhh4 $8.$ R4e2 R1h3 $9.$ Rh2 Re3 $10.$ Rhh1 Ree4
I found a solution in 12 moves. Here is a link to a GIF using Apronus. I'm using an 8 x 8 board for convenience in the gif, but I'm treating it as 4 x 4.
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.
My Solution:
$1.$ Rg3 Rh2 $2.$ Rh3 Rhg2 $3.$ Rh4 Rg1 $4.$ R1h3 R4g2 $5.$ Rg3 Rh2 $6.$ Rgg4 Rhh1 $7.$ Re3 Rf2 $8.$ Rf3 Rfe2 $9.$ Rff4 Re1 $10.$ R1f3 R4e2 $11.$ Re3 Rf2 $12.$ Ree4 Rff1
I'm fairly sure that this is optimal due to how each rook moves a minimum of three times.
edited Jun 20 at 4:59
Duck
1,6931 silver badge17 bronze badges
answered Jun 20 at 1:29
Rewan DemontayRewan Demontay
1,3402 silver badges21 bronze badges
$endgroup$
2
$begingroup$
Seems like the metric everyone else has adopted is total number of rook moves, in which case you'd have 24. I think people are reducing this to 20 by cleverly getting some rooks to the other side in one move.
$endgroup$
– greenturtle3141
Jun 20 at 2:06
1
$begingroup$
Oh. Well than the question should speifcy that the count is in ply, not in whole moves as I thought.
$endgroup$
– Rewan Demontay
Jun 20 at 2:40
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "559"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f85281%2fswapping-rooks-in-a-4x4-board%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
6 Answers
6
active
oldest
votes
6 Answers
6
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I wrote a computer program and it showed that $18$ moves is the optimum.
Here is one such solution:
bbbb bbbb .bbb .bbb .bb. .bb.
.... .... b... bw.. bw.. b..w
.... w... w... w... w..b w..b
wwww .www .www ..ww ..ww ..ww
..b. ..bw .b.w .bww .bww .bww
b..w b... b... b... b... b...
w..b w..b w..b w..b w..b w..b
.bww .bww .bww .b.w b..w b.w.
..ww .w.w .w.w .www .www wwww wwww
b... b... b... b... ..b. ..b. ....
w..b w..b w... w... w... .... ....
bbw. bbw. bbwb bb.b bb.b bb.b bbbb
Oddly enough, even if you relax the condition of alternating white and black moves, it cannot be done in fewer moves.
For $3times3$ the optimal number of moves is $16$.
bbb bbb bb. bb. .b. .b. ... w..
... w.. w.b .wb .wb w.b wbb .bb
www .ww .ww .ww bww bww bww bww
w.. ww. ww. www www ww. ww. www www
b.b b.b bb. bb. bb. bbw b.w b.. ...
bww b.w b.w b.. ..b ..b .bb .bb bbb
Without the need to alternate moves the optimum is $14$ moves, for example just by doing the above solution excluding white's last two moves.
Here is the C# source code that I wrote.
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<String> list = new List<String>();
Dictionary<String, String> dict = new Dictionary<String, String>();
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 > 0)
String p = list[0];
list.RemoveAt(0);
n1--;
String gen = dict[p];
char player = alternateMoves ? (p[n * n] == '0' ? 'w' : 'b') : '.';
for (int y = 0; y < n; y++)
for (int x = 0; x < n; x++)
if (!alternateMoves ^ p[y * n + x] == player)
for (int d = 0; d < 4; d++)
int dx = dirs[d + d];
int dy = dirs[d + d + 1];
int x2 = x;
int y2 = y;
while (true)
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 > 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);
answered Jun 20 at 8:39
Jaap ScherphuisJaap Scherphuis
18.2k1 gold badge33 silver badges80 bronze badges
$endgroup$
$begingroup$
Clever! How did you write this program? Was there some logic or just brute force?
$endgroup$
– shoopi
Jun 20 at 10:10
$begingroup$
I'd be curious to the results for 3x3, 5x5, 6x6, etc. Is your program flexible enough to find the answers with little effort? I wonder if the answer appears in oeis.org
$endgroup$
– David Dubois
Jun 20 at 10:36
3
$begingroup$
My program was brute force, simply a breadth first search. There are fewer than a million possible positions (twice that if you include whose turn it is to move) so it can be done in memory. I have added the $3times3$ results to my answer. $5times5$ is theoretically feasible by the same method but my program would require a rewrite to be much more memory efficient. Larger boards need a very different method because the number of positions is too great.
$endgroup$
– Jaap Scherphuis
Jun 20 at 11:25
3
$begingroup$
@Kebabman I have added the C# source code to my answer.
$endgroup$
– Jaap Scherphuis
Jun 20 at 13:11
2
$begingroup$
@MikeTheLiar I know, and I think that is only possible if you allow consecutive moves to use the same colour pieces, and not possible if you strictly alternate the colours of the moved pieces.
$endgroup$
– Jaap Scherphuis
Jun 21 at 14:23
|
show 4 more comments
$begingroup$
I wrote a computer program and it showed that $18$ moves is the optimum.
Here is one such solution:
bbbb bbbb .bbb .bbb .bb. .bb.
.... .... b... bw.. bw.. b..w
.... w... w... w... w..b w..b
wwww .www .www ..ww ..ww ..ww
..b. ..bw .b.w .bww .bww .bww
b..w b... b... b... b... b...
w..b w..b w..b w..b w..b w..b
.bww .bww .bww .b.w b..w b.w.
..ww .w.w .w.w .www .www wwww wwww
b... b... b... b... ..b. ..b. ....
w..b w..b w... w... w... .... ....
bbw. bbw. bbwb bb.b bb.b bb.b bbbb
Oddly enough, even if you relax the condition of alternating white and black moves, it cannot be done in fewer moves.
For $3times3$ the optimal number of moves is $16$.
bbb bbb bb. bb. .b. .b. ... w..
... w.. w.b .wb .wb w.b wbb .bb
www .ww .ww .ww bww bww bww bww
w.. ww. ww. www www ww. ww. www www
b.b b.b bb. bb. bb. bbw b.w b.. ...
bww b.w b.w b.. ..b ..b .bb .bb bbb
Without the need to alternate moves the optimum is $14$ moves, for example just by doing the above solution excluding white's last two moves.
Here is the C# source code that I wrote.
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<String> list = new List<String>();
Dictionary<String, String> dict = new Dictionary<String, String>();
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 > 0)
String p = list[0];
list.RemoveAt(0);
n1--;
String gen = dict[p];
char player = alternateMoves ? (p[n * n] == '0' ? 'w' : 'b') : '.';
for (int y = 0; y < n; y++)
for (int x = 0; x < n; x++)
if (!alternateMoves ^ p[y * n + x] == player)
for (int d = 0; d < 4; d++)
int dx = dirs[d + d];
int dy = dirs[d + d + 1];
int x2 = x;
int y2 = y;
while (true)
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 > 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);
answered Jun 20 at 8:39
Jaap ScherphuisJaap Scherphuis
18.2k1 gold badge33 silver badges80 bronze badges
$endgroup$
$begingroup$
Clever! How did you write this program? Was there some logic or just brute force?
$endgroup$
– shoopi
Jun 20 at 10:10
$begingroup$
I'd be curious to the results for 3x3, 5x5, 6x6, etc. Is your program flexible enough to find the answers with little effort? I wonder if the answer appears in oeis.org
$endgroup$
– David Dubois
Jun 20 at 10:36
3
$begingroup$
My program was brute force, simply a breadth first search. There are fewer than a million possible positions (twice that if you include whose turn it is to move) so it can be done in memory. I have added the $3times3$ results to my answer. $5times5$ is theoretically feasible by the same method but my program would require a rewrite to be much more memory efficient. Larger boards need a very different method because the number of positions is too great.
$endgroup$
– Jaap Scherphuis
Jun 20 at 11:25
3
$begingroup$
@Kebabman I have added the C# source code to my answer.
$endgroup$
– Jaap Scherphuis
Jun 20 at 13:11
2
$begingroup$
@MikeTheLiar I know, and I think that is only possible if you allow consecutive moves to use the same colour pieces, and not possible if you strictly alternate the colours of the moved pieces.
$endgroup$
– Jaap Scherphuis
Jun 21 at 14:23
|
show 4 more comments
$begingroup$
I wrote a computer program and it showed that $18$ moves is the optimum.
Here is one such solution:
bbbb bbbb .bbb .bbb .bb. .bb.
.... .... b... bw.. bw.. b..w
.... w... w... w... w..b w..b
wwww .www .www ..ww ..ww ..ww
..b. ..bw .b.w .bww .bww .bww
b..w b... b... b... b... b...
w..b w..b w..b w..b w..b w..b
.bww .bww .bww .b.w b..w b.w.
..ww .w.w .w.w .www .www wwww wwww
b... b... b... b... ..b. ..b. ....
w..b w..b w... w... w... .... ....
bbw. bbw. bbwb bb.b bb.b bb.b bbbb
Oddly enough, even if you relax the condition of alternating white and black moves, it cannot be done in fewer moves.
For $3times3$ the optimal number of moves is $16$.
bbb bbb bb. bb. .b. .b. ... w..
... w.. w.b .wb .wb w.b wbb .bb
www .ww .ww .ww bww bww bww bww
w.. ww. ww. www www ww. ww. www www
b.b b.b bb. bb. bb. bbw b.w b.. ...
bww b.w b.w b.. ..b ..b .bb .bb bbb
Without the need to alternate moves the optimum is $14$ moves, for example just by doing the above solution excluding white's last two moves.
Here is the C# source code that I wrote.
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<String> list = new List<String>();
Dictionary<String, String> dict = new Dictionary<String, String>();
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 > 0)
String p = list[0];
list.RemoveAt(0);
n1--;
String gen = dict[p];
char player = alternateMoves ? (p[n * n] == '0' ? 'w' : 'b') : '.';
for (int y = 0; y < n; y++)
for (int x = 0; x < n; x++)
if (!alternateMoves ^ p[y * n + x] == player)
for (int d = 0; d < 4; d++)
int dx = dirs[d + d];
int dy = dirs[d + d + 1];
int x2 = x;
int y2 = y;
while (true)
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 > 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);
answered Jun 20 at 8:39
Jaap ScherphuisJaap Scherphuis
18.2k1 gold badge33 silver badges80 bronze badges
$endgroup$
I wrote a computer program and it showed that $18$ moves is the optimum.
Here is one such solution:
bbbb bbbb .bbb .bbb .bb. .bb.
.... .... b... bw.. bw.. b..w
.... w... w... w... w..b w..b
wwww .www .www ..ww ..ww ..ww
..b. ..bw .b.w .bww .bww .bww
b..w b... b... b... b... b...
w..b w..b w..b w..b w..b w..b
.bww .bww .bww .b.w b..w b.w.
..ww .w.w .w.w .www .www wwww wwww
b... b... b... b... ..b. ..b. ....
w..b w..b w... w... w... .... ....
bbw. bbw. bbwb bb.b bb.b bb.b bbbb
Oddly enough, even if you relax the condition of alternating white and black moves, it cannot be done in fewer moves.
For $3times3$ the optimal number of moves is $16$.
bbb bbb bb. bb. .b. .b. ... w..
... w.. w.b .wb .wb w.b wbb .bb
www .ww .ww .ww bww bww bww bww
w.. ww. ww. www www ww. ww. www www
b.b b.b bb. bb. bb. bbw b.w b.. ...
bww b.w b.w b.. ..b ..b .bb .bb bbb
Without the need to alternate moves the optimum is $14$ moves, for example just by doing the above solution excluding white's last two moves.
Here is the C# source code that I wrote.
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<String> list = new List<String>();
Dictionary<String, String> dict = new Dictionary<String, String>();
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 > 0)
String p = list[0];
list.RemoveAt(0);
n1--;
String gen = dict[p];
char player = alternateMoves ? (p[n * n] == '0' ? 'w' : 'b') : '.';
for (int y = 0; y < n; y++)
for (int x = 0; x < n; x++)
if (!alternateMoves ^ p[y * n + x] == player)
for (int d = 0; d < 4; d++)
int dx = dirs[d + d];
int dy = dirs[d + d + 1];
int x2 = x;
int y2 = y;
while (true)
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 > 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);
answered Jun 20 at 8:39
Jaap ScherphuisJaap Scherphuis
18.2k1 gold badge33 silver badges80 bronze badges
edited Jun 20 at 13:10
answered Jun 20 at 8:39
Jaap ScherphuisJaap Scherphuis
18.2k1 gold badge33 silver badges80 bronze badges
answered Jun 20 at 8:39
Jaap ScherphuisJaap Scherphuis
18.2k1 gold badge33 silver badges80 bronze badges
answered Jun 20 at 8:39
Jaap ScherphuisJaap Scherphuis
18.2k1 gold badge33 silver badges80 bronze badges
18.2k1 gold badge33 silver badges80 bronze badges
$begingroup$
Clever! How did you write this program? Was there some logic or just brute force?
$endgroup$
– shoopi
Jun 20 at 10:10
$begingroup$
I'd be curious to the results for 3x3, 5x5, 6x6, etc. Is your program flexible enough to find the answers with little effort? I wonder if the answer appears in oeis.org
$endgroup$
– David Dubois
Jun 20 at 10:36
3
$begingroup$
My program was brute force, simply a breadth first search. There are fewer than a million possible positions (twice that if you include whose turn it is to move) so it can be done in memory. I have added the $3times3$ results to my answer. $5times5$ is theoretically feasible by the same method but my program would require a rewrite to be much more memory efficient. Larger boards need a very different method because the number of positions is too great.
$endgroup$
– Jaap Scherphuis
Jun 20 at 11:25
3
$begingroup$
@Kebabman I have added the C# source code to my answer.
$endgroup$
– Jaap Scherphuis
Jun 20 at 13:11
2
$begingroup$
@MikeTheLiar I know, and I think that is only possible if you allow consecutive moves to use the same colour pieces, and not possible if you strictly alternate the colours of the moved pieces.
$endgroup$
– Jaap Scherphuis
Jun 21 at 14:23
|
show 4 more comments
$begingroup$
Clever! How did you write this program? Was there some logic or just brute force?
$endgroup$
– shoopi
Jun 20 at 10:10
$begingroup$
I'd be curious to the results for 3x3, 5x5, 6x6, etc. Is your program flexible enough to find the answers with little effort? I wonder if the answer appears in oeis.org
$endgroup$
– David Dubois
Jun 20 at 10:36
3
$begingroup$
My program was brute force, simply a breadth first search. There are fewer than a million possible positions (twice that if you include whose turn it is to move) so it can be done in memory. I have added the $3times3$ results to my answer. $5times5$ is theoretically feasible by the same method but my program would require a rewrite to be much more memory efficient. Larger boards need a very different method because the number of positions is too great.
$endgroup$
– Jaap Scherphuis
Jun 20 at 11:25
3
$begingroup$
@Kebabman I have added the C# source code to my answer.
$endgroup$
– Jaap Scherphuis
Jun 20 at 13:11
2
$begingroup$
@MikeTheLiar I know, and I think that is only possible if you allow consecutive moves to use the same colour pieces, and not possible if you strictly alternate the colours of the moved pieces.
$endgroup$
– Jaap Scherphuis
Jun 21 at 14:23
$begingroup$
Clever! How did you write this program? Was there some logic or just brute force?
$endgroup$
– shoopi
Jun 20 at 10:10
$begingroup$
Clever! How did you write this program? Was there some logic or just brute force?
$endgroup$
– shoopi
Jun 20 at 10:10
$begingroup$
I'd be curious to the results for 3x3, 5x5, 6x6, etc. Is your program flexible enough to find the answers with little effort? I wonder if the answer appears in oeis.org
$endgroup$
– David Dubois
Jun 20 at 10:36
$begingroup$
I'd be curious to the results for 3x3, 5x5, 6x6, etc. Is your program flexible enough to find the answers with little effort? I wonder if the answer appears in oeis.org
$endgroup$
– David Dubois
Jun 20 at 10:36
3
3
$begingroup$
My program was brute force, simply a breadth first search. There are fewer than a million possible positions (twice that if you include whose turn it is to move) so it can be done in memory. I have added the $3times3$ results to my answer. $5times5$ is theoretically feasible by the same method but my program would require a rewrite to be much more memory efficient. Larger boards need a very different method because the number of positions is too great.
$endgroup$
– Jaap Scherphuis
Jun 20 at 11:25
$begingroup$
My program was brute force, simply a breadth first search. There are fewer than a million possible positions (twice that if you include whose turn it is to move) so it can be done in memory. I have added the $3times3$ results to my answer. $5times5$ is theoretically feasible by the same method but my program would require a rewrite to be much more memory efficient. Larger boards need a very different method because the number of positions is too great.
$endgroup$
– Jaap Scherphuis
Jun 20 at 11:25
3
3
$begingroup$
@Kebabman I have added the C# source code to my answer.
$endgroup$
– Jaap Scherphuis
Jun 20 at 13:11
$begingroup$
@Kebabman I have added the C# source code to my answer.
$endgroup$
– Jaap Scherphuis
Jun 20 at 13:11
2
2
$begingroup$
@MikeTheLiar I know, and I think that is only possible if you allow consecutive moves to use the same colour pieces, and not possible if you strictly alternate the colours of the moved pieces.
$endgroup$
– Jaap Scherphuis
Jun 21 at 14:23
$begingroup$
@MikeTheLiar I know, and I think that is only possible if you allow consecutive moves to use the same colour pieces, and not possible if you strictly alternate the colours of the moved pieces.
$endgroup$
– Jaap Scherphuis
Jun 21 at 14:23
|
show 4 more comments
$begingroup$
Got 19 by moving around... might be possible to do better:
1) a1-a3
2) d4-d2
3) b1-b3
4) d2-a2
5) d1-d4
6) a2-a1
7) c1-d1
8) c4-c1
9) b3-c3
10) b4-b1
11) a3-b3
12) a4-a2
13) d4-a4
14) a2-c2
15) d1-d4
16) c2-d2
17) b3-b4
18) d2-d1
19) c3-c4
answered Jun 20 at 0:12
shoopishoopi
9665 silver badges15 bronze badges
$endgroup$
1
$begingroup$
Step 14 seems to be a pointless move. Just do step 15 first and then a2-d2.
$endgroup$
– James Coyle
Jun 20 at 11:19
1
$begingroup$
@JamesCoyle Step 14 is indeed a pointless move just to pass the turn. But I can't play move 15 (d1-d4) before I play move 13 (d4-a4) because the square is occupied. This is why I suspected a more optimal solution exists, as proven in Jaap's solution.
$endgroup$
– shoopi
Jun 20 at 11:55
2
$begingroup$
Ah I totally forgot about alternating moves...
$endgroup$
– James Coyle
Jun 20 at 12:02
add a comment |
$begingroup$
Got 19 by moving around... might be possible to do better:
1) a1-a3
2) d4-d2
3) b1-b3
4) d2-a2
5) d1-d4
6) a2-a1
7) c1-d1
8) c4-c1
9) b3-c3
10) b4-b1
11) a3-b3
12) a4-a2
13) d4-a4
14) a2-c2
15) d1-d4
16) c2-d2
17) b3-b4
18) d2-d1
19) c3-c4
answered Jun 20 at 0:12
shoopishoopi
9665 silver badges15 bronze badges
$endgroup$
1
$begingroup$
Step 14 seems to be a pointless move. Just do step 15 first and then a2-d2.
$endgroup$
– James Coyle
Jun 20 at 11:19
1
$begingroup$
@JamesCoyle Step 14 is indeed a pointless move just to pass the turn. But I can't play move 15 (d1-d4) before I play move 13 (d4-a4) because the square is occupied. This is why I suspected a more optimal solution exists, as proven in Jaap's solution.
$endgroup$
– shoopi
Jun 20 at 11:55
2
$begingroup$
Ah I totally forgot about alternating moves...
$endgroup$
– James Coyle
Jun 20 at 12:02
add a comment |
$begingroup$
Got 19 by moving around... might be possible to do better:
1) a1-a3
2) d4-d2
3) b1-b3
4) d2-a2
5) d1-d4
6) a2-a1
7) c1-d1
8) c4-c1
9) b3-c3
10) b4-b1
11) a3-b3
12) a4-a2
13) d4-a4
14) a2-c2
15) d1-d4
16) c2-d2
17) b3-b4
18) d2-d1
19) c3-c4
answered Jun 20 at 0:12
shoopishoopi
9665 silver badges15 bronze badges
$endgroup$
Got 19 by moving around... might be possible to do better:
1) a1-a3
2) d4-d2
3) b1-b3
4) d2-a2
5) d1-d4
6) a2-a1
7) c1-d1
8) c4-c1
9) b3-c3
10) b4-b1
11) a3-b3
12) a4-a2
13) d4-a4
14) a2-c2
15) d1-d4
16) c2-d2
17) b3-b4
18) d2-d1
19) c3-c4
answered Jun 20 at 0:12
shoopishoopi
9665 silver badges15 bronze badges
edited Jun 20 at 0:24
answered Jun 20 at 0:12
shoopishoopi
9665 silver badges15 bronze badges
answered Jun 20 at 0:12
shoopishoopi
9665 silver badges15 bronze badges
answered Jun 20 at 0:12
shoopishoopi
9665 silver badges15 bronze badges
9665 silver badges15 bronze badges
1
$begingroup$
Step 14 seems to be a pointless move. Just do step 15 first and then a2-d2.
$endgroup$
– James Coyle
Jun 20 at 11:19
1
$begingroup$
@JamesCoyle Step 14 is indeed a pointless move just to pass the turn. But I can't play move 15 (d1-d4) before I play move 13 (d4-a4) because the square is occupied. This is why I suspected a more optimal solution exists, as proven in Jaap's solution.
$endgroup$
– shoopi
Jun 20 at 11:55
2
$begingroup$
Ah I totally forgot about alternating moves...
$endgroup$
– James Coyle
Jun 20 at 12:02
add a comment |
1
$begingroup$
Step 14 seems to be a pointless move. Just do step 15 first and then a2-d2.
$endgroup$
– James Coyle
Jun 20 at 11:19
1
$begingroup$
@JamesCoyle Step 14 is indeed a pointless move just to pass the turn. But I can't play move 15 (d1-d4) before I play move 13 (d4-a4) because the square is occupied. This is why I suspected a more optimal solution exists, as proven in Jaap's solution.
$endgroup$
– shoopi
Jun 20 at 11:55
2
$begingroup$
Ah I totally forgot about alternating moves...
$endgroup$
– James Coyle
Jun 20 at 12:02
1
1
$begingroup$
Step 14 seems to be a pointless move. Just do step 15 first and then a2-d2.
$endgroup$
– James Coyle
Jun 20 at 11:19
$begingroup$
Step 14 seems to be a pointless move. Just do step 15 first and then a2-d2.
$endgroup$
– James Coyle
Jun 20 at 11:19
1
1
$begingroup$
@JamesCoyle Step 14 is indeed a pointless move just to pass the turn. But I can't play move 15 (d1-d4) before I play move 13 (d4-a4) because the square is occupied. This is why I suspected a more optimal solution exists, as proven in Jaap's solution.
$endgroup$
– shoopi
Jun 20 at 11:55
$begingroup$
@JamesCoyle Step 14 is indeed a pointless move just to pass the turn. But I can't play move 15 (d1-d4) before I play move 13 (d4-a4) because the square is occupied. This is why I suspected a more optimal solution exists, as proven in Jaap's solution.
$endgroup$
– shoopi
Jun 20 at 11:55
2
2
$begingroup$
Ah I totally forgot about alternating moves...
$endgroup$
– James Coyle
Jun 20 at 12:02
$begingroup$
Ah I totally forgot about alternating moves...
$endgroup$
– James Coyle
Jun 20 at 12:02
add a comment |
$begingroup$
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.
answered Jun 19 at 22:05
TedTed
936 bronze badges
$endgroup$
$begingroup$
I have 2 that are different and 20 and I am not sure either.
$endgroup$
– Duck
Jun 19 at 22:06
$begingroup$
Thanks, I've added the clarification.
$endgroup$
– Chaotic
Jun 19 at 22:15
add a comment |
$begingroup$
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.
answered Jun 19 at 22:05
TedTed
936 bronze badges
$endgroup$
$begingroup$
I have 2 that are different and 20 and I am not sure either.
$endgroup$
– Duck
Jun 19 at 22:06
$begingroup$
Thanks, I've added the clarification.
$endgroup$
– Chaotic
Jun 19 at 22:15
add a comment |
$begingroup$
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.
answered Jun 19 at 22:05
TedTed
936 bronze badges
$endgroup$
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.
answered Jun 19 at 22:05
TedTed
936 bronze badges
answered Jun 19 at 22:05
TedTed
936 bronze badges
answered Jun 19 at 22:05
TedTed
936 bronze badges
answered Jun 19 at 22:05
TedTed
936 bronze badges
936 bronze badges
$begingroup$
I have 2 that are different and 20 and I am not sure either.
$endgroup$
– Duck
Jun 19 at 22:06
$begingroup$
Thanks, I've added the clarification.
$endgroup$
– Chaotic
Jun 19 at 22:15
add a comment |
$begingroup$
I have 2 that are different and 20 and I am not sure either.
$endgroup$
– Duck
Jun 19 at 22:06
$begingroup$
Thanks, I've added the clarification.
$endgroup$
– Chaotic
Jun 19 at 22:15
$begingroup$
I have 2 that are different and 20 and I am not sure either.
$endgroup$
– Duck
Jun 19 at 22:06
$begingroup$
I have 2 that are different and 20 and I am not sure either.
$endgroup$
– Duck
Jun 19 at 22:06
$begingroup$
Thanks, I've added the clarification.
$endgroup$
– Chaotic
Jun 19 at 22:15
$begingroup$
Thanks, I've added the clarification.
$endgroup$
– Chaotic
Jun 19 at 22:15
add a comment |
$begingroup$
Found a 19 move solution, but no idea about optimum.
a1-a3
a3-d3
b1-b2
b2-d2
a4-a1
b4-b1
c1-c2
c2-a2
a2-a4
c4-c1
d4-c4
c4-c3
d3-d4
d4-b4
d2-d4
d4-c4
d1-d4
c3-d3
d3-d1
Where the columns are a, b, c, d and rows are 1, 2, 3, 4, starting from bottom left.
answered Jun 19 at 22:14
SteveVSteveV
7,2482 gold badges6 silver badges36 bronze badges
$endgroup$
1
$begingroup$
OP made an edit - moves must alternate between White and Black.
$endgroup$
– shoopi
Jun 19 at 23:11
add a comment |
$begingroup$
Found a 19 move solution, but no idea about optimum.
a1-a3
a3-d3
b1-b2
b2-d2
a4-a1
b4-b1
c1-c2
c2-a2
a2-a4
c4-c1
d4-c4
c4-c3
d3-d4
d4-b4
d2-d4
d4-c4
d1-d4
c3-d3
d3-d1
Where the columns are a, b, c, d and rows are 1, 2, 3, 4, starting from bottom left.
answered Jun 19 at 22:14
SteveVSteveV
7,2482 gold badges6 silver badges36 bronze badges
$endgroup$
1
$begingroup$
OP made an edit - moves must alternate between White and Black.
$endgroup$
– shoopi
Jun 19 at 23:11
add a comment |
$begingroup$
Found a 19 move solution, but no idea about optimum.
a1-a3
a3-d3
b1-b2
b2-d2
a4-a1
b4-b1
c1-c2
c2-a2
a2-a4
c4-c1
d4-c4
c4-c3
d3-d4
d4-b4
d2-d4
d4-c4
d1-d4
c3-d3
d3-d1
Where the columns are a, b, c, d and rows are 1, 2, 3, 4, starting from bottom left.
answered Jun 19 at 22:14
SteveVSteveV
7,2482 gold badges6 silver badges36 bronze badges
$endgroup$
Found a 19 move solution, but no idea about optimum.
a1-a3
a3-d3
b1-b2
b2-d2
a4-a1
b4-b1
c1-c2
c2-a2
a2-a4
c4-c1
d4-c4
c4-c3
d3-d4
d4-b4
d2-d4
d4-c4
d1-d4
c3-d3
d3-d1
Where the columns are a, b, c, d and rows are 1, 2, 3, 4, starting from bottom left.
answered Jun 19 at 22:14
SteveVSteveV
7,2482 gold badges6 silver badges36 bronze badges
answered Jun 19 at 22:14
SteveVSteveV
7,2482 gold badges6 silver badges36 bronze badges
answered Jun 19 at 22:14
SteveVSteveV
7,2482 gold badges6 silver badges36 bronze badges
answered Jun 19 at 22:14
SteveVSteveV
7,2482 gold badges6 silver badges36 bronze badges
7,2482 gold badges6 silver badges36 bronze badges
1
$begingroup$
OP made an edit - moves must alternate between White and Black.
$endgroup$
– shoopi
Jun 19 at 23:11
add a comment |
1
$begingroup$
OP made an edit - moves must alternate between White and Black.
$endgroup$
– shoopi
Jun 19 at 23:11
1
1
$begingroup$
OP made an edit - moves must alternate between White and Black.
$endgroup$
– shoopi
Jun 19 at 23:11
$begingroup$
OP made an edit - moves must alternate between White and Black.
$endgroup$
– shoopi
Jun 19 at 23:11
add a comment |
$begingroup$
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.
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
The last two columns give the minimal number of steps (ply) to the final position with either white (w) or black (b) to play.
The number of configurations is given by: $2 cdot n cdot m choose m cdot n cdot m - m choose m$, with $n$ the number of rows and $m$ the number of columns.
answered yesterday
vysarvysar
212 bronze badges
New contributor
vysar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
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.
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
The last two columns give the minimal number of steps (ply) to the final position with either white (w) or black (b) to play.
The number of configurations is given by: $2 cdot n cdot m choose m cdot n cdot m - m choose m$, with $n$ the number of rows and $m$ the number of columns.
answered yesterday
vysarvysar
212 bronze badges
New contributor
vysar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
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.
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
The last two columns give the minimal number of steps (ply) to the final position with either white (w) or black (b) to play.
The number of configurations is given by: $2 cdot n cdot m choose m cdot n cdot m - m choose m$, with $n$ the number of rows and $m$ the number of columns.
answered yesterday
vysarvysar
212 bronze badges
New contributor
vysar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
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.
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
The last two columns give the minimal number of steps (ply) to the final position with either white (w) or black (b) to play.
The number of configurations is given by: $2 cdot n cdot m choose m cdot n cdot m - m choose m$, with $n$ the number of rows and $m$ the number of columns.
answered yesterday
vysarvysar
212 bronze badges
New contributor
vysar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered yesterday
vysarvysar
212 bronze badges
New contributor
vysar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered yesterday
vysarvysar
212 bronze badges
answered yesterday
vysarvysar
212 bronze badges
212 bronze badges
New contributor
vysar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
vysar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
$begingroup$
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.
As such, just for fun, here is a symmetrical solution of 20 moves that uses the same notations as my below answer.
$1.$ Rh2 Rg3 $2.$ Rff2 Ree3 $3.$ Re2 Rh3 $4.$ Rg1 Rf4 $5.$ Rhf2 Reg3 $6.$ Rff1 Rgg4 $7.$ Ree1 Rhh4 $8.$ R4e2 R1h3 $9.$ Rh2 Re3 $10.$ Rhh1 Ree4
I found a solution in 12 moves. Here is a link to a GIF using Apronus. I'm using an 8 x 8 board for convenience in the gif, but I'm treating it as 4 x 4.
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.
My Solution:
$1.$ Rg3 Rh2 $2.$ Rh3 Rhg2 $3.$ Rh4 Rg1 $4.$ R1h3 R4g2 $5.$ Rg3 Rh2 $6.$ Rgg4 Rhh1 $7.$ Re3 Rf2 $8.$ Rf3 Rfe2 $9.$ Rff4 Re1 $10.$ R1f3 R4e2 $11.$ Re3 Rf2 $12.$ Ree4 Rff1
I'm fairly sure that this is optimal due to how each rook moves a minimum of three times.
edited Jun 20 at 4:59
Duck
1,6931 silver badge17 bronze badges
answered Jun 20 at 1:29
Rewan DemontayRewan Demontay
1,3402 silver badges21 bronze badges
$endgroup$
2
$begingroup$
Seems like the metric everyone else has adopted is total number of rook moves, in which case you'd have 24. I think people are reducing this to 20 by cleverly getting some rooks to the other side in one move.
$endgroup$
– greenturtle3141
Jun 20 at 2:06
1
$begingroup$
Oh. Well than the question should speifcy that the count is in ply, not in whole moves as I thought.
$endgroup$
– Rewan Demontay
Jun 20 at 2:40
add a comment |
$begingroup$
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.
As such, just for fun, here is a symmetrical solution of 20 moves that uses the same notations as my below answer.
$1.$ Rh2 Rg3 $2.$ Rff2 Ree3 $3.$ Re2 Rh3 $4.$ Rg1 Rf4 $5.$ Rhf2 Reg3 $6.$ Rff1 Rgg4 $7.$ Ree1 Rhh4 $8.$ R4e2 R1h3 $9.$ Rh2 Re3 $10.$ Rhh1 Ree4
I found a solution in 12 moves. Here is a link to a GIF using Apronus. I'm using an 8 x 8 board for convenience in the gif, but I'm treating it as 4 x 4.
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.
My Solution:
$1.$ Rg3 Rh2 $2.$ Rh3 Rhg2 $3.$ Rh4 Rg1 $4.$ R1h3 R4g2 $5.$ Rg3 Rh2 $6.$ Rgg4 Rhh1 $7.$ Re3 Rf2 $8.$ Rf3 Rfe2 $9.$ Rff4 Re1 $10.$ R1f3 R4e2 $11.$ Re3 Rf2 $12.$ Ree4 Rff1
I'm fairly sure that this is optimal due to how each rook moves a minimum of three times.
edited Jun 20 at 4:59
Duck
1,6931 silver badge17 bronze badges
answered Jun 20 at 1:29
Rewan DemontayRewan Demontay
1,3402 silver badges21 bronze badges
$endgroup$
2
$begingroup$
Seems like the metric everyone else has adopted is total number of rook moves, in which case you'd have 24. I think people are reducing this to 20 by cleverly getting some rooks to the other side in one move.
$endgroup$
– greenturtle3141
Jun 20 at 2:06
1
$begingroup$
Oh. Well than the question should speifcy that the count is in ply, not in whole moves as I thought.
$endgroup$
– Rewan Demontay
Jun 20 at 2:40
add a comment |
$begingroup$
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.
As such, just for fun, here is a symmetrical solution of 20 moves that uses the same notations as my below answer.
$1.$ Rh2 Rg3 $2.$ Rff2 Ree3 $3.$ Re2 Rh3 $4.$ Rg1 Rf4 $5.$ Rhf2 Reg3 $6.$ Rff1 Rgg4 $7.$ Ree1 Rhh4 $8.$ R4e2 R1h3 $9.$ Rh2 Re3 $10.$ Rhh1 Ree4
I found a solution in 12 moves. Here is a link to a GIF using Apronus. I'm using an 8 x 8 board for convenience in the gif, but I'm treating it as 4 x 4.
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.
My Solution:
$1.$ Rg3 Rh2 $2.$ Rh3 Rhg2 $3.$ Rh4 Rg1 $4.$ R1h3 R4g2 $5.$ Rg3 Rh2 $6.$ Rgg4 Rhh1 $7.$ Re3 Rf2 $8.$ Rf3 Rfe2 $9.$ Rff4 Re1 $10.$ R1f3 R4e2 $11.$ Re3 Rf2 $12.$ Ree4 Rff1
I'm fairly sure that this is optimal due to how each rook moves a minimum of three times.
edited Jun 20 at 4:59
Duck
1,6931 silver badge17 bronze badges
answered Jun 20 at 1:29
Rewan DemontayRewan Demontay
1,3402 silver badges21 bronze badges
$endgroup$
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.
As such, just for fun, here is a symmetrical solution of 20 moves that uses the same notations as my below answer.
$1.$ Rh2 Rg3 $2.$ Rff2 Ree3 $3.$ Re2 Rh3 $4.$ Rg1 Rf4 $5.$ Rhf2 Reg3 $6.$ Rff1 Rgg4 $7.$ Ree1 Rhh4 $8.$ R4e2 R1h3 $9.$ Rh2 Re3 $10.$ Rhh1 Ree4
I found a solution in 12 moves. Here is a link to a GIF using Apronus. I'm using an 8 x 8 board for convenience in the gif, but I'm treating it as 4 x 4.
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.
My Solution:
$1.$ Rg3 Rh2 $2.$ Rh3 Rhg2 $3.$ Rh4 Rg1 $4.$ R1h3 R4g2 $5.$ Rg3 Rh2 $6.$ Rgg4 Rhh1 $7.$ Re3 Rf2 $8.$ Rf3 Rfe2 $9.$ Rff4 Re1 $10.$ R1f3 R4e2 $11.$ Re3 Rf2 $12.$ Ree4 Rff1
I'm fairly sure that this is optimal due to how each rook moves a minimum of three times.
edited Jun 20 at 4:59
Duck
1,6931 silver badge17 bronze badges
answered Jun 20 at 1:29
Rewan DemontayRewan Demontay
1,3402 silver badges21 bronze badges
edited Jun 20 at 4:59
Duck
1,6931 silver badge17 bronze badges
edited Jun 20 at 4:59
Duck
1,6931 silver badge17 bronze badges
edited Jun 20 at 4:59
Duck
1,6931 silver badge17 bronze badges
1,6931 silver badge17 bronze badges
answered Jun 20 at 1:29
Rewan DemontayRewan Demontay
1,3402 silver badges21 bronze badges
answered Jun 20 at 1:29
Rewan DemontayRewan Demontay
1,3402 silver badges21 bronze badges
answered Jun 20 at 1:29
Rewan DemontayRewan Demontay
1,3402 silver badges21 bronze badges
1,3402 silver badges21 bronze badges
2
$begingroup$
Seems like the metric everyone else has adopted is total number of rook moves, in which case you'd have 24. I think people are reducing this to 20 by cleverly getting some rooks to the other side in one move.
$endgroup$
– greenturtle3141
Jun 20 at 2:06
1
$begingroup$
Oh. Well than the question should speifcy that the count is in ply, not in whole moves as I thought.
$endgroup$
– Rewan Demontay
Jun 20 at 2:40
add a comment |
2
$begingroup$
Seems like the metric everyone else has adopted is total number of rook moves, in which case you'd have 24. I think people are reducing this to 20 by cleverly getting some rooks to the other side in one move.
$endgroup$
– greenturtle3141
Jun 20 at 2:06
1
$begingroup$
Oh. Well than the question should speifcy that the count is in ply, not in whole moves as I thought.
$endgroup$
– Rewan Demontay
Jun 20 at 2:40
2
2
$begingroup$
Seems like the metric everyone else has adopted is total number of rook moves, in which case you'd have 24. I think people are reducing this to 20 by cleverly getting some rooks to the other side in one move.
$endgroup$
– greenturtle3141
Jun 20 at 2:06
$begingroup$
Seems like the metric everyone else has adopted is total number of rook moves, in which case you'd have 24. I think people are reducing this to 20 by cleverly getting some rooks to the other side in one move.
$endgroup$
– greenturtle3141
Jun 20 at 2:06
1
1
$begingroup$
Oh. Well than the question should speifcy that the count is in ply, not in whole moves as I thought.
$endgroup$
– Rewan Demontay
Jun 20 at 2:40
$begingroup$
Oh. Well than the question should speifcy that the count is in ply, not in whole moves as I thought.
$endgroup$
– Rewan Demontay
Jun 20 at 2:40
add a comment |
Thanks for contributing an answer to Puzzling Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f85281%2fswapping-rooks-in-a-4x4-board%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
4
$begingroup$
This is the type of question which might make a good secondary puzzle along the lines of "how many steps does it take to swap rooks on an nxn board"! (+1)
$endgroup$
– Adam
Jun 19 at 22:25
2
$begingroup$
Yes, I thought about that. In a 3x3 board I was able to do in 14 moves, but I'm not sure if it is the optimal solution. I also don't think it would be a good idea to open a new question for a 3x3, 5x5, 8x8, etc.
$endgroup$
– Chaotic
Jun 19 at 22:33
$begingroup$
Not necessarily, but the generalization is a worthy question to ask, though perhaps not by itself not that you've asked the instance for n = 4. Still, I do believe this should generalize quite nicely.
$endgroup$
– greenturtle3141
Jun 20 at 0:16
1
$begingroup$
I'm fairly sure that for a 3*3, 9 is optimal. Set up the rooks on the f-h files and ranks 1-3 and follow these moves: 1. Rh2 Rg2 2. Rgh3 Rg3 3. Rff2 Rhg1 4. Rh1 R1g2 5. Rg1 Rh2 6. Rfg2 Rff3 7. Rf2 Rhg2 8. Rhh1 Rh2 9. Rff1 Rhh3.
$endgroup$
– Rewan Demontay
Jun 20 at 1:52
4
$begingroup$
@Adam: the sequence R(n) of minimum rook moves R(n) for an n x n board swapping n rooks on top/bottom rows would make a great series in OEIS. I just checked and it doesn't exist.
$endgroup$
– smci
Jun 21 at 0:02