All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > General
Pax vobiscum (Posted on 2021-11-05) Difficulty: 3 of 5
a. For n=1 to 9 evaluate f(n) as the number of distinct ways n peaceful knights may be placed on a 4*4 chessboard.
b. Extend the above task for 8*8 chessboard.

Peaceful knights means no knight is threatening another.

No Solution Yet Submitted by Ady TZIDON    
Rating: 5.0000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution computer solution | Comment 1 of 4
For a 4 x 4 board:

     1    16
     2    96
     3   276
     4   412
     5   340
     6   170
     7    48
     8     6
     9     0

The 6 for n=8:

     1     1     1     1
     0     0     0     0
     0     0     0     0
     1     1     1     1
 
     1     1     0     1
     1     0     0     0
     0     0     0     1
     1     0     1     1
 
     1     0     1     1
     0     0     0     1
     1     0     0     0
     1     1     0     1
 
     1     0     1     0
     0     1     0     1
     1     0     1     0
     0     1     0     1
 
     1     0     0     1
     1     0     0     1
     1     0     0     1
     1     0     0     1
 
     0     1     0     1
     1     0     1     0
     0     1     0     1
     1     0     1     0
 
clearvars, clc

global boardSize board forbidden ct n

boardSize=4; 

for n=1:9
    board=zeros(boardSize);
    forbidden=zeros(boardSize);
    ct=0;
    place(1,1)
    disp([n ct])
end

function place(pce,st)
  global boardSize board forbidden ct n
  for psn=st:boardSize*boardSize
     boardSave=board; forbiddenSave=forbidden; 
     
     row=ceil(psn/boardSize); col=psn-boardSize*(row-1);
     if board(row,col)==0 && forbidden(row,col)==0
        board(row,col)=pce;
        for dr=-2:2
            tmp=3-abs(dr);
            for dc=-tmp:2*tmp:tmp
                if dc~=0 && dr~=0
                  if row+dr>0 && row+dr<=boardSize
                      if col+dc>0 && col+dc <=boardSize
                        forbidden(row+dr,col+dc)=1; 
                      end
                  end
                end
            end
        end
        if pce==n
            ct=ct+1;
            if n==8
             disp(sign(board))
             disp(' ')
            end
        else
            if boardSize*boardSize>psn+(n-pce)-1 && pce<n
                place(pce+1,psn+1)
            end
        end
     end
     board=boardSave; forbidden=forbiddenSave; 
  end
     
    
  end

For board size of 8:


           1          64
           2        1848
           3       32084
           4      376560
           5     3184708
           6    20202298
           7    98796304
           8   379978716
           9  1167053680
           
           
The computation for 9 on an 8x8 board took several hours (maybe 4 or 5).   

Compare with A244081 in OEIS, though that's hard to read given the 2-dimensional nature of the input variables (board size and number of knights).

  Posted by Charlie on 2021-11-05 14:55:38
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (14)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information