Chess set combinations...

Printable View

Aug 25th, 2001, 11:25 AM
DavidHooper

Chess set combinations...

...how many ways of arranging the back row of a chess set are there?
Aug 25th, 2001, 01:19 PM
kedaman

what kind of chess set? can you give details?
Aug 25th, 2001, 10:07 PM
crptcblade

wouldn't it be 8^4?
Aug 26th, 2001, 08:33 AM
DavidHooper

More chess...

...ok so it's a normal chess set:
2 rooks, 2 bishops, 2 knights, 1 queen, 1 king.
Chess boards are 8x8.

How many ways can you arrange these pieces on the back row of a normal chess board?

It's obviously not 8! because some of the positions will be duplicated due to the 2 rooks/bishops/knights...

OK?
Aug 26th, 2001, 09:05 AM
kedaman

2nCr8 * 2nCr6 * 2nCr4 * 2 = 5040
Aug 26th, 2001, 10:32 AM
DavidHooper

Correct...

...correct well done.

Next question:
How many queens can you fit on the board without any attacking any other?
Aug 26th, 2001, 10:45 AM
kedaman

7

xxxxxxxx
xxxxxoxx
xxxoxxxx
xoxxxxxx
xxxxxxox
xxxxoxxx
xxoxxxxx
oxxxxxxx
Aug 26th, 2001, 03:45 PM
DavidHooper

nah i mean on the whole 8x8 board. (!)
Aug 26th, 2001, 03:48 PM
crptcblade

:D That's not really true, though, because every piece can be taken

:rolleyes:
Aug 26th, 2001, 04:37 PM
kedaman

:confused: do you have to put 64 queens or how do you mean? :rolleyes:
Aug 26th, 2001, 05:34 PM
beachbum

Quote:

Originally posted by kedaman
:confused: do you have to put 64 queens or how do you mean? :rolleyes:

Wouldnt 64 queens at once be a mardi gras instead of a chess game?
Aug 26th, 2001, 11:04 PM
Guv

5040 via diffierent route.

I also got 5040 for the arrangement of the back row, but it was via the following formula.

8! / 8, which is 7! or 5040.

If there were 8 distinct pieces, you could arrange them in 8! ways. For each pair of identical pieces (rooks, knights, bishops), you have over estimated by a factor of two. Hence divide by eight (divide by two three times).

I do not understand how Kedaman arrived at his formula, which gives the same numeric result.

W. W. Rouse Ball wrote a book (Mathematical Recreations & Essays) which claims that you can place 8 Queens on a chess board in such a way that no captures are possible.

I trust that book, and assume that the queens are arranged by scrambling an 8X8 Identity matrix. I think such a matrix is called a permutation matrix because when used as a multiplier, it merely exchanges (Id est permutes) rows/columns of the multiplicand matrix. No two Queens are in the same row, no two are in the same column, and you have to avoid diagonal captures.

I suspect that knight moves provide the clue to placing the queens. Perhaps put the first one in a corner, and place the others by making knight moves. This should be a good start at a solution.
Aug 27th, 2001, 01:44 AM
kedaman

After many tries i thought it was just impossible, well I have to look again.
2 rooks can be placed in 28 different ways on 8 columns, that you usually do with
8!
_____
2!(8-2)!
or
(8)
(2)
or
8 nCr 2 (easier to type)
I did use Pascal's triangle instead, since my calculator couldn't be found.
After placing the rooks, there's 6 columns for 2 bishops, hence 6 nCr 2 which is 15, and 4 columns for 2 knigts which is 6, 2 columns for the queen and one for the king. The product is 5040
Aug 27th, 2001, 05:46 AM
kedaman

1 Attachment(s)

ok, a bit cheating but it took a lot of work

PHP Code:

#include "stdafx.h" #include <iostream.h> int main() { char a[8];//available row char p[8];//queen position char du; //upper diagonal counter char dl; //lower diagonal counter for(char* ia=a;ia<&a[8];++ia)*ia=1;//all queens in first row for(char* ip=p;ip<&p[8];++ip)*ip=0; for(ia=a,ip=p;ia<&a[8]; ){//for each column for(;*ip<8;++*ip){//put queen in next row if (a[*ip]){//row availability du=*ip;dl=*ip;//reset diagonal counters for(char* ca=ip-1;ca>=p;--ca){ //diagonal availability ++du;--dl; if ((*ca==du)|(*ca==dl)) break; } if (ca<p)//no diagonal attackers break;//place next queen } } if (*ip==8){//queen attacked in all rows --ip;//backtrack a[*ip]=1;//make available ++*ip; //cout << "B"; } else{ a[*ip]=0;//make unavailable ++ip;//move to next column, reset queen *ip=0; //cout << "N"; } for(char* cp=p;cp<&p[8];++cp)cout << (int)*cp; cout << " :: "; for(char* ia=a;ia<&a[8];++ia)cout << (int)*ia; cout << endl; for(int c=0;c<10000000;c++); } for(ip=p;ip<&p[8];++ip)cout << (int)*ip; return 0; }

This program i made in c++ works in a way, but it fails to notice when it finds the correct combination, and instead starts to go terribly wrong with two queens at the same row and then locks on a single combination which i first thought was the correct one. Anyways 00000000 should mark the correct combination, with the queens at the correct rows.

http://www.vbforums.com/attachment.php?s=&postid=500513
Aug 27th, 2001, 06:49 AM
beachbum

Re: 5040 via diffierent route.

Quote:

Originally posted by Guv
W. W. Rouse Ball wrote a book (Mathematical Recreations & Essays) which claims that you can place 8 Queens on a chess board in such a way that no captures are possible.

Ok maybe i am too tired to get this :p I can see how 7 would easily work but not how 8 is possible. can u or someone else pls post a pic of chessboard with 8 on it. :)
Regards
Stuart
Aug 27th, 2001, 08:39 AM
kedaman

Code:

..X..... .....X.. ...X.... .X...... .......X ....X... ......X. X.......
Aug 27th, 2001, 10:10 AM
kedaman

I corrected my code and now it works with any size of board ;)

Code:

f..........X..... e........X....... d......X......... c....X........... b.......X........ a.............X.. 9...............X 8.....X.......... 7..............X. 6...........X.... 5.........X...... 4..X............. 3............X... 2.X.............. 1...X............ 0X...............
Aug 27th, 2001, 10:45 AM
kedaman

the effect of permutation starts to show at a board of size 29 which takes about 3 secs, 30 took 4 minutes (112,852,992 iterations in the outhermost loop). Of course that would take centillion milleniums if my algoritm hadn't strong recursion terminators ;)

Code:

1d................X............. 1c..................X........... 1b............X................. 1a.................X............ 19...........X.................. 18.............X................ 17...............X.............. 16..........X................... 15..............X............... 14............................X. 13.........................X.... 12.............................X 11........................X..... 10..........................X... f...................X.......... e........X..................... d...........................X.. c.......X...................... b....................X......... a......X....................... 9.....................X........ 8.....X........................ 7......................X....... 6.........X.................... 5.......................X...... 4..X........................... 3....X......................... 2.X............................ 1...X.......................... 0X............................. reference from my app if i plotted something wrong: 0 2 4 1 3 8 10 12 14 6 22 25 27 24 21*23 29 26 28 15 11 9 7 5 17 19 16 13 20 18 Press any key to continue

of course i could try 31 but it surely takes some hours
Aug 27th, 2001, 02:22 PM
DavidHooper

Well the answer I was looking for was that you can put 64 queens of the same colour on the board (!).

But it looks like you guys have some neat code. Cool, I like.

Guv and keda:
8! / 8 = 2nCr8 * 2nCr6 * 2nCr4 * 2 = 5040
this is because the Cr just hides the factorial. If you check what the formula for Cr is then all is clear.

Cool. Tomorrow I will ask for help with an algorithm that has been bugging me for aaages...
Sep 6th, 2001, 07:40 PM
Gaming_World

The 2nd question is a variation of the 8 queens problem (how can you place 8 queens on a sanderd chess board without any being able to attack another, assuming that all are enemies).
Sep 7th, 2001, 12:35 AM
DavidHooper

..X.....
.....X..
...X....
.X......
.......X
....X...
......X.
X.......

There are many solutions.

E.g.
1,5,8,6,3,7,2,4 =

x00000000 1
0000x0000 5
00000000x 8
00000x000 6
00x000000 3
0000000x0 7
000x00000 4

15863724
16837425
17468253
17582463
24683175
25713864
25741863
26831475
26174835
27368514
27581463
28613574
35714286
35841726
35281746
35286471
36814752
36815724
36824175
36258174
36271485
36275184
36418572
36428571
37285146
37286415
38471625
31758246
46827135
46831752
46152837
47185263
47382516
47526138
47531682
48136275
48157263
48531726
41582736
41586372
42586137
42736815
42736851
42751863
42857136
42861357
57138642
57142863
57248136
57263148
57263184
57413862
58413627
58417263
51468273
51842736
51863724
52468317
52473861
52617483
52814736
53847162
53168247
53172864
68241753
61528374
62713584
62714853
63571428
63581427
63724815
63728514
63741825
63175824
63184275
63185247
64713528
64718253
64158273
64285713
71386425
72418536
72631485
73825164
73168524
74258136
74286135
75316824
82417536
82531746
83162574
84136275

Here is the code in VB which runs approx 1.5 seconds on my pc.
VB Code:
Option Explicit
 
Private Sub Command1_Click()
Screen.MousePointer = vbHourglass
Call Permutations("12345678")
Screen.MousePointer = vbDefault
MsgBox "done"
End Sub
 
Sub Permutations(s As String, Optional sleading As String)
 'Nucleus
 Dim I       As Long
 
 For I = 1 To Len(s)
    If Len(s) > 2 Then
        Permutations Right$(s, Len(s) - 1), sleading & Left$(s, 1)
    Else
        If Works(sleading & s) Then Debug.Print sleading & s
    End If
    s = Right$(s, Len(s) - 1) & Left$(s, 1)
 Next
 
End Sub
 
Function Works(ByVal s$)
    Dim I&, j&, TrackRight&, NextQueen&, TrackLeft&
    
    For I = 1 To 8
        TrackRight = CLng(Mid(s, I, 1))
        TrackLeft = TrackRight
        For j = I + 1 To 8
            TrackRight = TrackRight + 1
            TrackLeft = TrackLeft - 1
            NextQueen = CLng(Mid(s, j, 1))
            If NextQueen = TrackRight Or NextQueen = TrackLeft Then Exit Function
        Next j
    Next I
 
    Works = True
End Function