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.)
dona nobis pacem | Comment 2 of 4 |
(In reply to computer solution by Charlie)

If rotations and reflections are discounted, each trial takes longer to compute, as the rotations and reflections of each are counted so that each occurrence is divided by the number of occurrences. 

For a 4x4 board:

     1     3
     2    18
     3    40
     4    66
     5    49
     6    30
     7     8
     8     3
     9     0


For an 8x8 board:

     1          10
     2         257
     3        4075
     4       47485
     5      398907
     6     2528655 
   
     
  ...

It's getting late and the results are so sloooww, so I'll stop there.    
     
     
clearvars, clc

global boardSize board forbidden ct n

boardSize=8; 


for n=1:8
    board=zeros(boardSize);
    forbidden=zeros(boardSize);
    ct=zeros(1,8);
    place(1,1)
    tot= ct(1)+ct(2)/2+ct(4)/4+ct(8)/8;
    disp([n tot])
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
            board=sign(board);
            boards={board};
            for rotk=1:3
               trialboard=rot90(board,rotk);
               good=true;
               for i=1:length(boards)
                   if isequal(boards{i},trialboard)
                       good=false;
                       break
                   end
               end
               if good 
                   boards={boards{1:end} trialboard};
               end
            end
            bp=board';
            for rotk=0:3
               trialboard=rot90(bp,rotk);
               good=true;
               for i=1:length(boards)
                   if isequal(boards{i},trialboard)
                       good=false;
                       break
                   end
               end
               if good 
                   boards={boards{1:end} trialboard};
               end
            end   
            rots=length(boards);
  
            ct(rots)=ct(rots)+1;

        else
            if boardSize*boardSize>psn+(n-pce)-1 && pce<n
                place(pce+1,psn+1)
            end
        end
     end
     board=boardSave; forbidden=forbiddenSave; 
  end
     
    
end     

  Posted by Charlie on 2021-11-07 21:17:09
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 (8)
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