Chess board problem(divide and conquer)

This PPT contains a divide and conquer chessboard problem solution and its algorithm.

1. DIVIDE AND CONQUER ALGORITHM

2. CHESS BOARD PROBLEM- DIVIDE AND CONQUER

3. The Defective Chessboard Problem GIVEN CONDITIONS:- We have a chessboard of size n x n , where n =2 k Exactly on square is defective in the chessboard. The tiles(trominoes) are in L-shape i.e. 3 squares. OBJECTIVE Cover all the chessboard with L-shape tiles(trominoes), except the defective square.

4. Is it possible to solve this? Absolutely, it is possible to cover all non-defective squares. Let’s see how As the size of the chessboard is n x n and n=2 k Therefore, Total no. of squares =2 k x2 k =2 2k No. of non-defective squares = 2 2k -1 Now, for the value of K,2 2k -1 is divisible by 3. For E.g. K=1 , 2 2(1) -1 =3 is divisible by 3. K=2, 2 2(2) -1 =15 is divisible by 3.

5. Defective chessboards. 1x1 2 x2 2 x2 2 x2 2 x2 As the Size of these chessboards displayed here, 1x1 and 2x2 we don’t have to place any L-shape tile in the first and rest can be filled by just using 1 L-shaped tile.

6. For 4x 4 chessboard.

7. 8X8 DEFECTIVE CHESS BOARD Step-1 One of the cell is defective Step- 2 We divide the chess board into equal sub half's.

8. Creation of defective box Step- 3 Trick to cover the chess board with tiles Step -4 Again creation of defective boxes as we divide the chess board DIVISION OF PROBLEM INTO SUB PROBLEM

9. Step-5 As we have finally divided the problem into 2x2 board we will put the tiles. Step-6 The procedure will continue until all the sub board are covered with the tiles.

10. Step-7 The final chess board covered with all the titles and only left with the defectives which we created. Step-7 Here we will cover the defectives which we have created as in the last, there should be only one defective left. COMBINIG OF ALL SUB PROBLEMS

11. 8x8 4x4 4x4 4x4 4x4

12. 2x2 2x2 2x2 4x4 2x2

13. 1x1 2x2 4x4 8x8

14. ALGORITHIM 1. For a 2x2 board with defective cell we just need to add the single tile to it. 2. We will place a L shape tile in the middle such that it does not cover the sub square in which there is already defective. All the cell have a defective cell. 3.Repeat this process recursively till we have a 2x2 board.

15. Time Complexity For Defective Chess Board Problem T(n) =4T(n/2) +C By Using Master Theorem, T(n) =a T(n/b) + Theta(n k log p n ),a>=1,b>1,k>=0 & p is real number. a=4,b=2,k=0,p=0 a>b k => 4 >2 Case1: If a>b k , then T(n) =Theta( n log b a ). After putting the values of a and b the Time complexity for this problem = n 2 .