Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#26 2014-06-18 12:09:37

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: 64 pawns

I managed to find numbers 3, 30, 410 for the three smaller boards, but not for the 8x8.

Last edited by anonimnystefy (2014-06-18 12:34:29)


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#27 2014-06-20 11:29:33

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,810

Re: 64 pawns

I still haven't got a clue about how to solve this other than by hand...which ain't gonna happen.

I made up a worksheet (see image) in Excel to help speed up a systematic count that I'd planned to do, but then I realised that there seem to be far too many solutions to try that and so I gave it up as a bad idea.

Anyway, I'll describe how the worksheet works...

The worksheet has 2 grids, and pawns are entered into Entry grid via "w" for white & "b" for black. Upon each entry the Main grid populates all valid, linked squares by automatically displaying their pawn colour ("w" or "b").

There's a counter above and below the Entry grid to help keep track of the number of w & b pawns used.

To help avoid making an entry into an already populated square (which would generate an error), the colour of populated squares changes immediately in the Entry grid to white or black according to the pawn colour just entered.

Here's a little video that shows how it works. After all squares are filled, the Entry grid is then cleared by deleting the displayed letters one at a time. As each letter is deleted, the sister square in the Main grid, along with valid squares linked to the sister square, are also deleted, but in a different order from that of the entry...which affects the actual squares cleared per letter because of differing associations from those that applied when entering.

This spreadsheet is probably totally useless for solving the puzzle, though...

O7gdT7c.jpg

Last edited by phrontister (2017-02-25 22:38:37)


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

#28 2014-06-20 12:50:44

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: 64 pawns

Hi phro

I'm not sure I got how the spreadsheet works, but, I don't think we have to count all of them.

The way I've tried going about doing this is looking only at all possible arrangements of pawns on squares of one colour. Note: you can put any number of each colour as long as the squares are all occupied. What can be done is we can calculate what the number of ways is to put k white and n/2-k pawns on, say, white squares. It would be easy to get the answer afterwards, and the numbers are bound to be smaller than counting all the possibilities up.

Last edited by anonimnystefy (2014-06-21 00:26:06)


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#29 2014-06-21 01:03:20

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,810

Re: 64 pawns

Hi stefy,

I'm not sure I got how the spreadsheet works

Before I look at your method I'll try to explain my spreadsheet a bit better...without going right into it, because that would take too long.

The idea popped into my head following a decision I made during a moment of madness, which was to embark on a systematic hand-entry approach to test the following from post #3:

phanthanhtom wrote:

if a black pawn is present on H4, there are no less than 143 solutions

Once I had a close-ish look at the puzzle I knew I wasn't in the category referred to in post #1:

phanthanhtom wrote:

99% of people here will get to answer it in 5 minutes

That's why I opted to do the test by hand, hoping too that along the way a brilliant thought would leap out at me.

And so I began, but I soon found that the task of placing all the pawns was rather laborious, taking up far too much time...hence the spreadsheet method, by which I hoped to speed things up dramatically through automatically populating all valid linked cells along diagonals that commenced from cells into which pawns were entered by hand.

Btw, I swapped the grids and renamed them...and I've edited post #27 and updated the video.

To avoid wiping out cell formulas when placing pawns, I used two grids.

The Main grid contains all the formulas, that get the cells to:
(a) first check their 'sister' cells in the Entry grid for content: ie, a "w" (denoting a white pawn), a "b" (denoting a black pawn), or blank; and
(b) then look at their immediate diagonal neighbours to ascertain their contents.

Each time an entry is made in the Entry grid the cells in the Main grid go through these (a) and (b) steps, and are populated accordingly with "w", "b" or blank.

So that's the main idea. To help you understand that better, it's probably best that you look at the image in post #27.
1. My first pawn entry into the Entry grid was "b" into h5.
2. Consequently the following cells in the Main grid are automatically populated with "b": d1, e2, f1, f3, g2, g4, h1, h3, h5.
3. When a cell in the Main grid becomes populated that causes its sister cell in the Entry grid to change colour to black or white to help avoid making entries into already populated cells.

The next entries into the Entry grid were "b" into c3 and then "w" into c2...which populated the Main grid in the same manner as for h5 (you'll pick that up from the image).

So, from only 3 entries into the Enter grid, 36 of the 64 cells in the Main grid were populated...which is exactly the kind of result that I was hoping to achieve with the spreadsheet. The video shows that too but goes on to complete all 64 cells (with only 8 entries...but it can be done in less) and then clears both grids by deleting the Entry grid entries one by one.

There...clear as mud! smile

Last edited by phrontister (2014-06-21 01:52:25)


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

#30 2014-06-21 02:16:27

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: 64 pawns

Okay, I think I get how it works. So, how would you count all the possibilities if you were to try?


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#31 2014-06-22 01:25:58

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,810

Re: 64 pawns

I can only think of using a methodical count by hand, which, despite the spreadsheet's auto populating function, would still be far too laborious.

I had thought of using Excel's Solver on my spreadsheet to find all solutions for white if I had a white pawn in a1 as the only pawn on the board, and to then get Solver to do the same for all other possible placements of a single white pawn, but Solver didn't like my idea. sad


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

#32 2014-06-22 02:46:46

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: 64 pawns

Well, as I said, I don't think it is necessary to fill up the whole table. It is enough to see in how many ways the table below can be filled up with k white and 32-k black pawns.

EEJ3WQA.png


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#33 2015-06-23 12:26:22

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,810

Re: 64 pawns

Hi stefy,

I'd forgotten about this puzzle, until I saw the OP's reminder in another thread.

anonimnystefy wrote:

I managed to find numbers 3, 30, 410 for the three smaller boards, but not for the 8x8.

I overlooked checking those numbers of yours but have just finished verifying that there are only three 2x2-grid and thirty 4x4-grid solutions...the latter with help from my Excel program, which I'll explain:

(a) I worked systematically, always beginning with white, starting in the bottom right-hand corner and working my way up the grid from right to left until reaching white's quota of 8.

(b) Placing a pawn at the start of a diagonal automatically fills and counts all valid connecting squares, thus speeding up the process and also giving a good visual.

(c) There's a cumulative counter for white and for black, and these cells turn green when number quotas are reached and red for an exceeded quota.

(d) A red cell warning appears when a pawn is placed on a square occupied by the other colour.

bhxWF7S.jpg

Could you please explain your grid method to me? Thanks. I don't want to try my method on the 6x6 as that would be too laborious for 410 solutions...even more so with the 8x8, where it looks like there will be over 6000 solutions (as the OP said there might be).

Last edited by phrontister (2017-02-27 00:37:34)


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

#34 2015-06-23 12:50:18

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

Re: 64 pawns

This is a combinatorial search problem.

I think we should start writing a backtrack solver. I do not know how much time this method would take but at least we will discover a good many of the configurations


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#35 2015-06-23 12:59:29

ElainaVW
Member
Registered: 2013-04-29
Posts: 580

Re: 64 pawns

phrontister wrote:

I managed to find numbers 3, 30, 410 for the three smaller boards,

Which 3 and can you get a 4th one?

Offline

#36 2015-06-23 13:03:50

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,810

Re: 64 pawns

Hi Agnishom,

Oh, I see. I've never learnt that method and it may be beyond me.

Last edited by phrontister (2015-06-23 13:05:25)


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

#37 2015-06-23 13:15:11

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,810

Re: 64 pawns

Hi ElainaVW,

I was quoting anonimnystefy.

Which 3 and can you get a 4th one?

The '3' refers to the three 2x2 grid solutions shown in my post #33, which I believe are the only solutions for that size grid.

Last edited by phrontister (2015-06-23 13:16:08)


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

#38 2015-06-25 04:25:51

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

Re: 64 pawns

I have reasons to believe the answer is 6148.

@phanthanhtom, Could you please look into this?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#39 2015-06-25 22:59:20

phanthanhtom
Member
Registered: 2012-06-22
Posts: 290

Re: 64 pawns

I'll meet him up next Tuesday.

Can you please post the detailed solution, or at least the methodology?

Offline

#40 2015-06-26 00:44:04

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

Re: 64 pawns

You will need a computer for this: http://codegolf.stackexchange.com/quest … hess-board

One solution is a backtrack solution. Another guy (elsewhere) gave me a gf solution which I did not really understand that well.


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#41 2015-06-26 01:54:45

phanthanhtom
Member
Registered: 2012-06-22
Posts: 290

Re: 64 pawns

So that isn't a mathematical forum, its a programming/IT forum. Am I correct?

Offline

#42 2015-06-26 02:47:20

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

Re: 64 pawns

Yes, but if you think it is very far away from mathematics, you're wrong.

Many interesting Combinatorial problems requires computational power for solving. But does that mean computers can reduce the problems into pure bashing? Nope! As you can see there, the backtracking solution can only solve upto the 10 by 10 chessboard whereas the one supplemented by enough research can solve upto a 174 by 174 chessboard.

I found another solution (much like this one) on another forum: https://brilliant.org/problems/too-many … hessboard/


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#43 2015-06-26 07:15:43

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: 64 pawns

Well said!

Another guy (elsewhere) gave me a gf solution which I did not really understand that well.

Please point me to that place and was it Vaclav?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#44 2015-06-26 12:33:03

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

Re: 64 pawns

See the Brilliant link and click on Reveal Solutions


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#45 2015-06-26 15:11:02

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: 64 pawns

He does not show it anywhere. I guess his program computes it. Would have been nice to see it.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#46 2015-06-27 03:10:21

phanthanhtom
Member
Registered: 2012-06-22
Posts: 290

Re: 64 pawns

@Agishom: I'd like to see a more mathematical solution. In other words, the computer part should be reduced to computing formulae that we deduce purely through maths. Although his solution needed a mathematical start, I need more.

Offline

#47 2015-06-27 05:16:17

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

Re: 64 pawns

Why do you want a more "mathematical" solution?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#48 2015-06-27 16:01:09

phanthanhtom
Member
Registered: 2012-06-22
Posts: 290

Re: 64 pawns

Because I have almost no idea about programming. That being said, I work in IT, but now I'm working with servers and networks. I forgot all about programming.

Offline

#49 2015-06-27 17:33:12

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

Re: 64 pawns

I do not think I will be able to produce a very mathematical solution, sorry.

I liked this problem. Post more of these!


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

Board footer

Powered by FluxBB