10503 - The dominoes solitaire

[dwyak]

the rules of dominoes: the number of adjacent dots on two different dominoes must coincide. Pieces with repeated values are placed in the same way as the other pieces, and not at right angels.

what does "dots" & "values" mean? i didn't find anywhere contains description of "dots" & "value".

thanks!

[Observer]

Can this problem be solved by some quick approach?
Is backtracking the only way?

[Whinii F.]

What do you mean by a quick approach?
It seems backtracking works pretty fast.. I used a simple DP and got 1.8secs, and I'm the SLOWEST

[titid_gede]

i use backtracking, it quite fast, < 0.1 sec . so backtracking is more than enough.

[Observer]

Thx I've got ACC. I use backtracking too, and my program runs for 0.01s only. Not bad for a Pascal program, eh?

Btw, backtracking problems are fun! Please, if there are any other problems that can be solved by backtracking, tell me.

Some problems that can be solved by backtracking/exhaustion by recursion are listed below
(Of course, some of them could be solved with the help of DP) :
00140 Bandwidth
00165 Stamps
00167 Sultan's Successors, the
00193 Graph Colouring
00195 Anagrams
00216 Getting in Line
00259 Software Allocation
00291 House of Santa Claus, the
00296 Safebreaker
00301 Transportation
00399 Another Puzzling Problem (* the 500th problem that i've solved! *)
00441 Lotto
00524 Prime Ring Problem
00539 Settlers of Catan
00565 Pizza Anyone?
00574 Sum It Up
00598 Bundling Newspapers
00628 Passwords
00639 Don't Get Rooked
00656 Optimal Programs
00729 Hamming Distance Problem
00732 Anagrams by Stack
00750 8 Queens Chess Problem
10063 Knuth's Permutation
10068 Treasure Hunt, the
10098 Generating Fast, Sorted Permutations
10186 Euro Cup 2000
10344 23 out of 5
10364 Square
10400 Game Show Math
10419 Sum-up the Primes
10422 Knights in FEN
10447 Sum-up the Primes II
10496 Collecting Beepers
10501 Simplified Shisen-Sho
10503 Domino Solitaire, the
10513 Bangladesh Sequences
10582 ASCII Labyrinth
10605 Mines for Diamonds
10637 Coprimes

[Keywords] exhaustion backtracking Pascal easy recursion problems

(p.s. how i like this abandoned topic. my free area :p)

[wyvmak]

what does "dots" & "values" mean? i didn't find anywhere contains description of "dots" & "value".

one piece of domino has two "values", say (0,1). there are "dots" to represent the "value", so on the domino there is one dot for "1". just like a dice.

It took me some time to figure out the problem. And, finally, I treat the problem as: determining there exists a (directed) chain from (i1,i2) to (d1,d2).

[TISARKER]

the rules of dominoes: the number of adjacent dots on two different dominoes must coincide. Pieces with repeated values are placed in the same way as the other pieces, and not at right angels.

Plase Clarify Above Lines.

[helloneo]

Hello..~
What is the correct output for this input..?

Code: Select all

1
1
1 2
3 4
3 2
1
1
1 2
3 4
1 3
0

Thanks..

[Jan]

My accepted code returns 'NO' for both cases. [However, I forgot the problem completely]

[helloneo]

Thanks a lot..
Now, I understand the problem..

[helloneo]

I finally got AC on this problem..
But, my AC code returns..

Code: Select all

YES
NO

for my test case above..

Maybe, we're allow to rotate dominos except for the initial ones..

[frznlich]

Hi, can someone provide me with critical testcases?

I've tried all the above testcases, and still got WA. Thank you

[brianfry713]

Generate some input that you'd like the AC output for.

[tiendaotd]

For those who got WA : a domino (a,b) can provide (a,b) or (b,a) but only one of them is available. Therefore, when you already used (a,b) ( or (b,a) ) , it's impossible to use (b,a) ( or (a,b) ) in further spaces.

This simple logic may looks like that :

Code: Select all

// S : second
// idx : space index
if(a[i].F == line[idx-1].S)
			{
				use pair (a[i].F, a[i].S) ;
			}
			else if(a[i].S == line[idx-1].S)
			{
				use pair (a[i].S, a[i].F) ;
			}
...
                                       avail[i] = 0 ;
					line[idx] = pair used above;
					backtrack(idx+1) ;	
					avail[i] = 1 ;

[Munchor]

I'd just love some critical input for this one. I get correct output for the example, but WA on UVa:

Code: Select all

#include <stdio.h>
#include <string.h>

using namespace std;

unsigned int n, m, i, u, filled;
unsigned int first[2];
unsigned int last[2];
unsigned int dominoes[15][2];
unsigned int used[20];
bool problem_solved;

void place_from(int j, int to_match)
{
  //printf("%d %d %d\n", to_match, dominoes[j][0], dominoes[j][1]);

  if (filled == n - 1)
  {
    if (to_match == last[0])
    {
      problem_solved = true;
    }

    return;
  }

  filled++;
  
  for (u = 0; u < m; u++)
  {
    if (u == j || used[u]) continue;

    if (dominoes[u][0] == to_match)
    {
      used[u] = 1;
      place_from(u, dominoes[u][1]);
      used[u] = 0;
    }
    else if (dominoes[u][1] == to_match)
    {
      used[u] = 1;
      place_from(u, dominoes[u][0]);
      used[u] = 0;
    }
  }

  filled--;
}

int main()
{
  while (true)
  {
    scanf("%d", &n);
    if (n == 0) break;

    scanf("%d", &m);
    memset(dominoes, 0, sizeof dominoes);
    problem_solved = false;

    scanf("%d %d", &first[0], &first[1]);
    scanf("%d %d", &last[0], &last[1]);

    for (i = 0; i < m; i++)
    {
      scanf("%d %d", &dominoes[i][0], &dominoes[i][1]);
    }

    for (i = 0; i < m; i++)
    {
      memset(used, 0, sizeof used);
      filled = 0;

      if (dominoes[i][0] == first[1])
      {
        used[i] = 1;
        filled++;
        place_from(i, dominoes[i][1]);
      }
      else if (dominoes[i][1] == first[1])
      {
        used[i] = 1;
        filled++;
        place_from(i, dominoes[i][0]);
      }

      if (problem_solved) break;
    }

    if (problem_solved)
      printf("YES\n");
    else
      printf("NO\n");
  }

  return 0;
}

Any ideas? Thanks in advance.