I\'m working on Backtracking algorithm,The user will enter the sample input as s
ID: 3581138 • Letter: I
Question
I'm working on Backtracking algorithm,The user will enter the sample input as showing below, and the output must be the same as showing below as well.
**What I have done?**
I can print 80% of the output, but i can't finish the rest to print the numbers in the middle as showing in the image below.
I only need to print the middle number as showing in the image belwo
**Sample Input**
4
1 16 15 14 13 10 9 8 7 6 5 2
4
1 16 14 15 13 10 9 8 7 6 5 2
9
53 52 51 50 5 4 3 2 1 10 11 14 15 28 29 32 33 34 35 36 37 72 73 76 77 78 79
66 65 64 63 54
0
**Corresponding Sample Output**
1 16 15 14
2 3 12 13
5 4 11 10
6 7 8 9
No alibi
53 52 51 50 5 4 3 2 1
54 55 56 49 6 7 8 9 10
63 62 57 48 21 20 19 12 11
64 61 58 47 22 23 18 13 14
65 60 59 46 45 24 17 16 15
66 67 68 69 44 25 26 27 28
79 80 81 70 43 42 41 30 29
78 75 74 71 38 39 40 31 32
77 76 73 72 37 36 35 34 33
Here's My code
// Created by assam alzookery on 12/9/16.
// Copyright © 2016 assam alzookery. All rights reserved.
//
#include
#include
#include
using namespace std;
int arr[100][100] = {0};
int n;
// create the vector of positions
vector > possiblePos(int x,int y)
{
vector > v;
if(x+1 < n && arr[x+1][y] == 0)
v.push_back(make_pair(x+1,y));
if(x-1 >= 0 && arr[x-1][y] == 0)
v.push_back(make_pair(x-1,y));
if(y+1 < n && arr[x][y+1] == 0)
v.push_back(make_pair(x,y+1));
if(y-1 >= 0 && arr[x][y-1] == 0)
v.push_back(make_pair(x,y-1));
return v;
}
// checks weather there is zero left or not
bool checkState()
{
for(int i=0;i {
for(int j=0;j {
if(arr[i][j] == 0)
return false;
}
}
return true;
}
// validate if it is correct or not
bool validate(int x, int y)
{
if(arr[x][y] == n*n)
return true;
return false;
}
// recursion
bool backtrack(int startX , int startY)
{
// if the next element is present then recurse to that
if(startX +1 < n && arr[startX+1][startY] == arr[startX][startY] + 1 )
return backtrack(startX+1,startY);
if(startX -1 >= 0 && arr[startX-1][startY] == arr[startX][startY] + 1 )
return backtrack(startX-1,startY);
if(startY +1 < n && arr[startX][startY+1] == arr[startX][startY] + 1 )
return backtrack(startX,startY+1);
if(startY -1 >= 0 && arr[startX][startY-1] == arr[startX][startY] + 1 )
return backtrack(startX,startY-1);
// find all the next position available
vector > nextPos = possiblePos(startX,startY);
//recurse for every position available
for(int i=0;i {
pair p = nextPos[i];
arr[p.first][p.second] = arr[startX][startY] + 1;
if(backtrack(p.first,p.second))
return true;
else
arr[p.first][p.second] = 0;
}
return checkState() && validate(startX,startY);
}
int main()
{
while(1)
{
int Onex;
int Oney;
cin>>n;
if(n == 0)
break;
int hor = 0;
int ver = n;
int value;
//input from user
while(hor < ver)
{
cin>>value;
if(value == 1)
{
>> }
arr[0][hor] = value;
hor++;
}
hor = n;
ver = 1;
while(ver < hor)
{
cin>>value;
if(value == 1)
{
>> }
arr[ver][n-1] = value;
ver++;
}
ver = n-2;
while(ver >= 0)
{
cin >> value;
if(value == 1)
{
>> }
arr[n-1][ver] = value;
ver--;
}
hor = n-2;
while(hor > 0)
{
cin>>value;
if(value == 1)
{
>> }
arr[hor][0] = value;
hor--;
}
// checks for input
for(int i=0;i {
for(int j=0;j {
cout<
}
Auto C I O O Filter Project 4 1 16 15 14 13 10 9 8 7 6 5 2 1 16 14 15 13 10 9 8 7 6 5 2 53 52 51 50 5 4 3 2 1 10 11 14 15 28 29 32 33 34 35 36 37 72 73 76 77 78 79 66 65 64 63 54 01 16 15 14 2 0 0 13 5 0 0 10 6 7 8 9 1 16 15 14 2 3 12 13 5 11 10 6 7 8 9 1 16 14 15 2 3 12 13 5 11 10 6 7 8 9 No alibi 53 52 51 50 5 4 3 2 1 54 3 12 13 0 0 0 0 10 63 4 11 10 0 0 0 0 11 64 7 89 0 0 0 0 14 65 0 0 0 0 0 0 0 15 66 0 0 0 0 0 0 0 28 79 0 0 0 0 0 0 0 29 78 0 0 0 0 0 0 0 32 77 76 73 72 37 36 35 34 33 No alibi Filter All Output C OO OOExplanation / Answer
Kindly note the following initializations. Initialize hor value to 1 and proceed. This would produce the required results.
int hor = 0;
int ver = n;