OJ Board

Posted: **Tue Jul 22, 2003 4:00 pm**

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!

Posted: **Sun Aug 31, 2003 1:11 pm**

Can this problem be solved by some quick approach?

Is backtracking the only way?

Posted: **Sun Aug 31, 2003 1:21 pm**

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

Posted: **Sun Aug 31, 2003 2:19 pm**

i use backtracking, it quite fast, < 0.1 sec

. so backtracking is more than enough.

Posted: **Sun Aug 31, 2003 3:04 pm**

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)

Posted: **Fri May 07, 2004 8:44 am**

dwyak wrote: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).

Posted: **Sat Nov 19, 2005 3:38 am**

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.

Posted: **Thu Aug 09, 2007 6:59 pm**

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

Code: Select all

Thanks..

Posted: **Thu Aug 09, 2007 7:29 pm**

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

Posted: **Fri Aug 10, 2007 5:00 am**

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

Posted: **Tue Aug 28, 2007 6:21 pm**

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..

Posted: **Mon Jun 11, 2012 1:00 am**

Hi, can someone provide me with critical testcases?

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

Posted: **Tue Jun 12, 2012 12:15 am**

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

Posted: **Tue Feb 19, 2013 8:37 am**

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 ;

Posted: **Tue Mar 19, 2013 1:51 am**

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.

OJ Board

10503 - The dominoes solitaire

10503 - The dominoes solitaire

Re: What does 10503 mean?

10503-The dominoes solitaire

Re: 10503 - The Dominoes Solitaire

Re: 10503 - The Dominoes Solitaire

Re: 10503 - The Dominoes Solitaire

Re: 10503 - The Dominoes Solitaire