64 pawns

anonimnystefy · 2014-06-18 12:09:37

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)

phrontister · 2014-06-20 11:29:33

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...

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

anonimnystefy · 2014-06-20 12:50:44

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)

phrontister · 2014-06-21 01:03:20

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!

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

anonimnystefy · 2014-06-21 02:16:27

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

phrontister · 2014-06-22 01:25:58

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.

anonimnystefy · 2014-06-22 02:46:46

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.

phrontister · 2015-06-23 12:26:22

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.

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)

Agnishom · 2015-06-23 12:50:18

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

ElainaVW · 2015-06-23 12:59:29

phrontister wrote:

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

Which 3 and can you get a 4th one?

phrontister · 2015-06-23 13:03:50

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)

phrontister · 2015-06-23 13:15:11

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)

Agnishom · 2015-06-25 04:25:51

I have reasons to believe the answer is 6148.

@phanthanhtom, Could you please look into this?

phanthanhtom · 2015-06-25 22:59:20

I'll meet him up next Tuesday.

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

Agnishom · 2015-06-26 00:44:04

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.

phanthanhtom · 2015-06-26 01:54:45

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

Agnishom · 2015-06-26 02:47:20

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/

bobbym · 2015-06-26 07:15:43

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?

Agnishom · 2015-06-26 12:33:03

See the Brilliant link and click on Reveal Solutions

bobbym · 2015-06-26 15:11:02

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

phanthanhtom · 2015-06-27 03:10:21

@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.

Agnishom · 2015-06-27 05:16:17

Why do you want a more "mathematical" solution?

phanthanhtom · 2015-06-27 16:01:09

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.

Agnishom · 2015-06-27 17:33:12

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

I liked this problem. Post more of these!

Math Is Fun Forum

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

Re: 64 pawns

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

Re: 64 pawns

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

Re: 64 pawns

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

Re: 64 pawns

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

Re: 64 pawns

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

Re: 64 pawns

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

Re: 64 pawns

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

Re: 64 pawns

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

Re: 64 pawns

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

Re: 64 pawns

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

Re: 64 pawns

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

Re: 64 pawns

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

Re: 64 pawns

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

Re: 64 pawns

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

Re: 64 pawns

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

Re: 64 pawns

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

Re: 64 pawns

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

Re: 64 pawns

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

Re: 64 pawns

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

Re: 64 pawns

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

Re: 64 pawns

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

Re: 64 pawns

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

Re: 64 pawns

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

Re: 64 pawns

Board footer